Last active
February 23, 2022 20:42
-
-
Save tchajed/72ee757cab4c0e4cfde5 to your computer and use it in GitHub Desktop.
Parsec parser for the untyped lambda calculus
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Text.ParserCombinators.Parsec | |
import System.Environment (getArgs) | |
import Safe | |
data Expr = | |
Var Name -- variable | |
| App Expr Expr -- application | |
| Lambda Name Expr -- lambda abstraction | |
deriving | |
(Eq,Show) | |
type Name = String | |
type LCParser = GenParser Char () Expr | |
varName :: GenParser Char () Name | |
varName = many1 $ letter <|> char '\'' | |
var :: LCParser | |
var = Var <$> varName | |
abstr :: LCParser -> LCParser | |
abstr expr = do | |
char '\\' | |
name <- varName | |
char '.' | |
body <- expr | |
return $ Lambda name body | |
parens = between (char '(') (char ')') | |
nonApp :: LCParser | |
nonApp = parens expr <|> abstr expr <|> var | |
expr :: LCParser | |
expr = chainl1 nonApp $ optional space >> return App | |
parseLC :: String -> Either ParseError Expr | |
parseLC = parse expr "" | |
{- Driver -} | |
getExpr :: IO String | |
getExpr = getArgs >>= return . headDef "(\\x.\\y.x) a b" | |
main = do | |
estring <- getExpr | |
case parseLC estring of | |
Left err -> error $ show err | |
Right e -> putStrLn $ show e |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
> ./lambda-calculus # True | |
App (App (Lambda "x" (Lambda "y" (Var "x"))) (Var "a")) (Var "b") | |
> ./lambda-calculus '\F.(\x.F (x x)) (\x.F (x x))' # Y-combinator | |
Lambda "F" (App (Lambda "x" (App (Var "F") (App (Var "x") (Var "x")))) (Lambda "x" (App (Var "F") (App (Var "x") (Var "x"))))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment