1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
{-# LANGUAGE LambdaCase #-}
module Minilang.Lambda.Parser where
import Control.Applicative (Alternative (many), (<|>))
import Data.Bifunctor (first)
import Data.Functor (void)
import qualified Data.List as List
import Data.Text (Text, pack)
import qualified Data.Text as Text
import Data.Void (Void)
import Minilang.Lambda.Eval (Term)
import qualified Minilang.Lambda.Eval as Eval
import Text.Megaparsec (Parsec, between, empty, errorBundlePretty, parse, try)
import Text.Megaparsec.Char (alphaNumChar, char, letterChar, space1, symbolChar)
import qualified Text.Megaparsec.Char.Lexer as L
type Parser = Parsec Void Text
data ParseError = ParseError Text
deriving (Eq, Show)
data AST = Sym Text | Abs [Text] AST | App AST AST [AST]
deriving (Eq, Show)
desugar :: AST -> Term
desugar = \case
Sym symb -> Eval.Var symb
Abs bound body ->
foldr
Eval.Lam
(desugar body)
bound
App x y rest ->
foldl
(\acc a -> Eval.App acc (desugar a))
(Eval.App (desugar x) (desugar y))
rest
pretty :: AST -> Text
pretty = \case
Sym symb -> symb
Abs bound body -> "(lam (" <> Text.unwords bound <> ") " <> pretty body <> ")"
App x y rest -> "(" <> mconcat (List.intersperse " " (pretty <$> (x : y : rest))) <> ")"
parse :: Text -> Either ParseError AST
parse =
first (ParseError . pack . errorBundlePretty) . Text.Megaparsec.parse ast ""
ast :: Parser AST
ast = try letExpr <|> try lambda <|> try sym <|> try app
app :: Parser AST
app =
between
lpar
rpar
(App <$> ast <*> ast <*> many ast)
lambda :: Parser AST
lambda =
between
lpar
rpar
( lexeme "lam"
*> ( (Abs . fmap pack <$> between lpar rpar (many identifier))
<*> ast
)
)
letExpr :: Parser AST
letExpr =
between
lpar
rpar
( do
void $ lexeme "let"
(bound, binding) <-
between
lpar
rpar
( (,) <$> identifier <*> ast
)
body <- ast
let fun = Abs [pack bound] body
return $ App fun binding []
)
lpar :: Parser Text
lpar = symbol "("
rpar :: Parser Text
rpar = symbol ")"
symbol :: Text -> Parser Text
symbol = L.symbol spaceConsumer
sym :: Parser AST
sym = Sym . pack <$> identifier
identifier :: Parser String
identifier =
lexeme $
(:)
<$> (letterChar <|> extraChars)
<*> many (alphaNumChar <|> extraChars)
lexeme :: Parser a -> Parser a
lexeme = L.lexeme spaceConsumer
extraChars :: Parser Char
extraChars =
foldl (\b a -> char a <|> b) symbolChar extraIdentifierChars
initialChars :: [Char]
initialChars =
['a' .. 'z'] <> ['A' .. 'Z'] <> extraIdentifierChars
restChars :: [Char]
restChars =
initialChars <> ['0' .. '9']
extraIdentifierChars :: String
extraIdentifierChars = ['-', '_', '*', '#', '%', '&', ':', '@', '/']
spaceConsumer :: Parser ()
spaceConsumer =
L.space space1 (L.skipLineComment ";") empty
|
