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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE LambdaCase #-}
module Minilang.Lambda.Parser where
import Control.Applicative (Alternative (many), (<|>))
import Data.Aeson (FromJSON, ToJSON)
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 GHC.Generics (Generic)
import Minilang.Lambda.Eval (Term)
import qualified Minilang.Lambda.Eval as Eval
import Text.Megaparsec (Parsec, between, empty, errorBundlePretty, optional, parse, some, try)
import Text.Megaparsec.Char (alphaNumChar, char, digitChar, 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
| Lit Int
| Abs [Text] AST
| App AST AST [AST]
| Def Text AST
deriving (Eq, Show, Generic, ToJSON, FromJSON)
desugar :: AST -> Term
desugar = \case
Sym symb -> Eval.Var symb
Lit n -> Eval.Num n
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
Def _name _body ->
undefined
resugar :: Term -> AST
resugar = \case
Eval.Var s -> Sym s
Eval.Num n -> Lit n
Eval.Lam x body -> case resugar body of
Abs vars ast -> Abs (x : vars) ast
other -> Abs [x] other
Eval.App l r -> case resugar l of
App f a rest -> App f a (rest ++ [r'])
where
r' = resugar r
other -> App other r' []
where
r' = resugar r
pretty :: AST -> Text
pretty = \case
Sym symb -> symb
Lit n -> prettyInt n
Abs bound body -> "(lam (" <> Text.unwords bound <> ") " <> pretty body <> ")"
App x y rest -> "(" <> mconcat (List.intersperse " " (pretty <$> (x : y : rest))) <> ")"
Def name body -> "(def " <> name <> " " <> pretty body <> ")"
-- | Render an integer with no space between '-' and digits for negative numbers.
prettyInt :: Int -> Text
prettyInt n
| n < 0 = "-" <> Text.pack (show (abs n))
| otherwise = Text.pack (show n)
parseProgram :: Text -> Either ParseError [AST]
parseProgram input =
first (ParseError . pack . errorBundlePretty) $
Text.Megaparsec.parse (many ast) "" input
parse :: Text -> Either ParseError AST
parse =
first (ParseError . pack . errorBundlePretty) . Text.Megaparsec.parse ast ""
ast :: Parser AST
ast = try defExpr <|> try letExpr <|> try lambda <|> try lit <|> 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
)
)
defExpr :: Parser AST
defExpr =
between
lpar
rpar
( lexeme "def"
*> ((Def . pack <$> identifier) <*> ast)
)
letExpr :: Parser AST
letExpr =
between
lpar
rpar
( do
void $ lexeme "let"
bindings <-
between
lpar
rpar
(some binding)
body <- ast
return $ foldr mkLet body bindings
)
mkLet :: (Text, AST) -> AST -> AST
mkLet (var, bound) body = App (Abs [var] body) bound []
binding :: Parser (Text, AST)
binding =
between
lpar
rpar
(((,) . pack <$> identifier) <*> ast)
lpar :: Parser Text
lpar = symbol "("
rpar :: Parser Text
rpar = symbol ")"
symbol :: Text -> Parser Text
symbol = L.symbol spaceConsumer
-- | Parse an integer literal. The minus sign, if present, must immediately
-- precede the digits with no intervening whitespace; this distinguishes @-7@
-- (a negative number) from @- 7@ (the identifier @-@ applied to @7@).
lit :: Parser AST
lit = lexeme $ do
sign <- optional (char '-')
digits <- some digitChar
let n = read digits
pure $ Lit $ case sign of
Just _ -> negate n
Nothing -> n
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
|
