Как разобрать строку в GADT

Я пытаюсь реализовать Combinatory Logic в Haskell, и я хотел бы написать парсер для языка. У меня возникли проблемы с получением парсера для работы через Parsec. Основная проблема заключается в том, что мне нужен способ убедиться, что объекты, возвращаемые синтаксическим анализатором, хорошо набраны. У кого-нибудь есть какие-то творческие идеи о том, как это сделать?Как разобрать строку в GADT

{-# Language GeneralizedNewtypeDeriving #-} 

import qualified Data.Map as Map 
import qualified Text.ParserCombinators.Parsec as P 
import Text.Parsec.Token (parens) 
import Text.ParserCombinators.Parsec ((<|>)) 
import Control.Applicative ((<$>), (<*>), (*>), (<*)) 


data CTree = CApp CTree CTree | CNode String deriving (Eq, Read) 
instance Show CTree where 
    show [email protected](CApp x y) = showL c 
     where showL (CApp x' y')= "(" ++ showL x' ++ " " ++ showR y' ++ ")" 
       showL (CNode s) = s 
       showR (CApp x' y') = "(" ++ showL x' ++ " " ++ showR y' ++ ")" 
       showR (CNode s) = s 

    show (CNode s) = s 

-- | Parser 
parseC :: String -> Maybe CTree 
parseC s = extract$ P.parse expr "combinator_string" s 
      where extract (Right r) = Just r 
       extract (Left e) = Nothing 


expr :: P.CharParser() CTree 
expr = P.try (CApp <$> (CApp <$> term <*> term) <*> expr) 
     <|> P.try (CApp <$> term <*> term) 
     <|> term 


term = P.spaces *> (node <|> P.string "(" *> expr <* P.string ")") 


node :: P.CharParser() CTree 
node = CNode <$> (P.many1 $ P.noneOf "() ") 

eval (CApp (CNode "I") x) = x 
eval (CApp (CApp (CApp (CNode "S") f) g) x) = 
    (CApp (CApp f x) (CApp g x)) 
eval (CApp (CApp (CApp (CNode "B") f) g) x) = 
    (CApp f (CApp g x)) 
eval (CApp (CApp (CApp (CNode "C") f) g) x) = 
    (CApp (CApp f x) g) 
eval x = x

источник

2012-10-17 Eyal

Вы будете хотеть использовать экзистенциальный или более высокий ранг (продолжение маловероятно, так что могут потребовать здесь недискриминационные типы). Есть несколько примеров (не о разборе в частности, но идеи аналогичны) по адресу http://stackoverflow.com/questions/7978191/how-to-make-a-type-with-restrictions/7984155#7984155. – copumpkin

Я сильный сторонник разбора на monotyped представления, а затем применять фазу проверки типов/Разработка для преобразования, что в набранной (GADT) представления. Лучший учебник по общей идее, вероятно, из Lennart Augustsson's llvm based compiler

Представление для SKI исчисления может выглядеть

data TyComb t where 
    TyS :: TyComb ((a -> b -> c) -> (a -> b) -> a -> c) 
    TyK :: TyComb (a -> b -> a) 
    TyI :: TyComb (a -> a) 
    TyApp :: TyComb (a -> b) -> TyComb a -> TyComb b 

evalTyComb :: TyComb t -> t 
evalTyComb TyS   = \x y z -> (x z) (y z) 
evalTyComb TyK   = const 
evalTyComb TyI   = id 
evalTyComb (TyApp a b) = (evalTyComb a) (evalTyComb b)

источник

2012-10-18 03:15:46

ответ

Смежные вопросы