如何将字符串解析为GADT [英] How to parse string into GADT

问题描述

我试图在Haskell中实现组合逻辑，并且我想写入语言的解析器。我无法通过Parsec解析器工作。基本的问题是我需要一种方法来确保解析器返回的对象输入正确。有没有人有关于如何做到这一点的创意？

  { - ＃Language GeneralizedNewtypeDeriving＃ - } 
 
将合格的Data.Map导入为Map 
将合格的Text.ParserCombinators.Parsec导入为P 
 import Text.Parsec.Token（parens）
 import Text.ParserCombinators.Parsec（（< |>））
 import Control.Applicative （（< $>），（*），（*>），（< *））
 
 
 data CTree = CApp CTree CTree | CNode字符串派生（Eq，Read）
实例显示CTree其中
显示c @（CApp xy）= showL c 
其中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 
 
  -  |解析器
 parseC :: String  - >也许CTree 
 parseC s =提取$ P.parse exprcombinator_strings 
其中extract（Right r）=只是r 
提取（Left e）= Nothing 
 
 
 expr :: P.CharParser（）CTree 
 expr = P.try（CApp< $>（CApp<> term> term>< expr）
< |> P.try（CApp $ term * term）
< |>期限
 
 
 term = P.spaces *> （node< |> P.string（*> expr< * P.string））
 
 
 node :: P.CharParser（）CTree 
 node = CNode< $> （CApp（CApp（CApp（CNodeS））（） ）CA）（CApp（CApp（CNodeB）f）g）x）= $ b $（CApp（CApp fx）（CApp gx））
 eval （CApp（CApp fx）g）
 eval（CApp x = x 
  

解决方案

到单纯型表示，然后应用类型检查/精化阶段将其转换为类型化（GADT）表示。关于总体思想的最佳教程可能来自 Lennart Augustsson基于llvm的编译器

SKI演算的表示形式可能如下所示：

<$ p $ （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 - > （xz）（yz）
evalTyComb TyK = const
evalTyComb TyI = id
evalTyComb（TyApp ab）=（evalTyComb a）（evalTyComb b）

I am trying trying to implement Combinatory Logic in Haskell, and I would like to write to parser for the language. I am having trouble getting a parser to work via Parsec. The basic problem is that I need a way to ensure that the objects returned by the parser are well typed. Does anyone have any creative ideas on how to do this?

{-# 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 c@(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

解决方案

I'm a strong advocate of parsing to an monotyped representation, and then applying a typechecking/elaboration phase to convert that into the typed (GADT) representation. The best tutorial on the general idea is probably from Lennart Augustsson's llvm based compiler

A representation for the SKI calculus might look like

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)

这篇关于如何将字符串解析为GADT的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！