git @ Cat's Eye Technologies Pail / develop-2019-2
Alternate formatting experiment. Chris Pressey 1 year, 3 months ago
1 changed file(s) with 80 addition(s) and 80 deletion(s). Raw diff Collapse all Expand all
8181 What follows is `Pail.lhs`, the reference implementation of the Pail
8282 programming language.
8383
84 > import Text.ParserCombinators.Parsec
85 > import qualified Data.Map as Map
84 > import Text.ParserCombinators.Parsec
85 > import qualified Data.Map as Map
8686
8787
8888 Definitions
9090
9191 An environment maps names (represented as strings) to expressions.
9292
93 > type Env = Map.Map String Expr
93 > type Env = Map.Map String Expr
9494
9595 A symbol is an expression.
9696
97 > data Expr = Symbol String
97 > data Expr = Symbol String
9898
9999 If a and b are expressions, then a pair of a and b is an expression.
100100
101 > | Pair Expr Expr
101 > | Pair Expr Expr
102102
103103 If a is an expression, then the evaluation of a is an expression.
104104
105 > | Eval Expr
105 > | Eval Expr
106106
107107 If f is a function that takes an environment and an expression
108108 to an expression, then f is an expression. f may optionally
110110 depiction of expressions more convenient, but there is no language-
111111 level association between the function and its name.
112112
113 > | Fn String (Env -> Expr -> Expr)
113 > | Fn String (Env -> Expr -> Expr)
114114
115115 Nothing else is an expression.
116116
119119 convenience, functions with known names can be represented by `<foo>`,
120120 where `foo` is the name of the function.
121121
122 > instance Show Expr where
123 > show (Symbol s) = s
124 > show (Pair a b) = "[" ++ (show a) ++ " " ++ (show b) ++ "]"
125 > show (Eval x) = "*" ++ (show x)
126 > show (Fn n _) = "<" ++ n ++ ">"
127
128 > instance Eq Expr where
122 > instance Show Expr where
123 > show (Symbol s) = s
124 > show (Pair a b) = "[" ++ (show a) ++ " " ++ (show b) ++ "]"
125 > show (Eval x) = "*" ++ (show x)
126 > show (Fn n _) = "<" ++ n ++ ">"
127
128 > instance Eq Expr where
129129
130130 Two symbols are equal if the strings by which they are represented
131131 are equal.
132132
133 > (Symbol s) == (Symbol t) = s == t
133 > (Symbol s) == (Symbol t) = s == t
134134
135135 Two pairs are equal if their contents are pairwise equal.
136136
137 > (Pair a1 b1) == (Pair a2 b2) = (a1 == a2) && (b1 == b2)
137 > (Pair a1 b1) == (Pair a2 b2) = (a1 == a2) && (b1 == b2)
138138
139139 Two evaluations are equal if their contents are equal.
140140
141 > (Eval x) == (Eval y) = x == y
141 > (Eval x) == (Eval y) = x == y
142142
143143 Two functions are never considered equal.
144144
145 > (Fn n _) == (Fn m _) = False
145 > (Fn n _) == (Fn m _) = False
146146
147147
148148 Parser
155155 A symbol is denoted by a string which may contain only alphanumeric
156156 characters, hyphens, underscores, and question marks.
157157
158 > symbol = do
159 > c <- letter
160 > cs <- many (alphaNum <|> char '-' <|> char '?' <|> char '_')
161 > return (Symbol (c:cs))
158 > symbol = do
159 > c <- letter
160 > cs <- many (alphaNum <|> char '-' <|> char '?' <|> char '_')
161 > return (Symbol (c:cs))
162162
163163 A pair of expressions a and b is denoted
164164
165165 [a b]
166166
167 > pair = do
168 > string "["
169 > a <- expr
170 > b <- expr
171 > spaces
172 > string "]"
173 > return (Pair a b)
167 > pair = do
168 > string "["
169 > a <- expr
170 > b <- expr
171 > spaces
172 > string "]"
173 > return (Pair a b)
174174
175175 An evaluation of an expression a is denoted
176176
177177 *a
178178
179 > eval = do
180 > string "*"
181 > a <- expr
182 > return (Eval a)
179 > eval = do
180 > string "*"
181 > a <- expr
182 > return (Eval a)
183183
184184 As a bit of syntactic sugar, the denotation
185185
189189
190190 **[*uneval a]
191191
192 > uneval = do
193 > string "#"
194 > a <- expr
195 > return (Eval (Eval (Pair (Eval (Symbol "uneval")) a)))
192 > uneval = do
193 > string "#"
194 > a <- expr
195 > return (Eval (Eval (Pair (Eval (Symbol "uneval")) a)))
196196
197197 The top-level parsing function implements the overall grammar given above.
198198 Note that we need to give the type of this parser here -- otherwise the
199199 type inferencer freaks out for some reason.
200200
201 > expr :: Parser Expr
202 > expr = do
203 > spaces
204 > r <- (eval <|> uneval <|> pair <|> symbol)
205 > return r
201 > expr :: Parser Expr
202 > expr = do
203 > spaces
204 > r <- (eval <|> uneval <|> pair <|> symbol)
205 > return r
206206
207207 A convenience function for parsing Pail programs.
208208
209 > parsePail program = parse expr "" program
209 > parsePail program = parse expr "" program
210210
211211
212212 Evaluator
226226
227227 An evaluation of an expression o-reduces to the i-reduction of its contents.
228228
229 > oReduce env (Eval x) = iReduce env x
229 > oReduce env (Eval x) = iReduce env x
230230
231231 Everything else o-reduces to itself.
232232
233 > oReduce env x = x
233 > oReduce env x = x
234234
235235 Inner Reduction
236236 ---------------
238238 A symbol i-reduces to the expression to which is it bound in the current
239239 environment. If it is not bound to anything, it i-reduces to itself.
240240
241 > iReduce env (Symbol s) = Map.findWithDefault (Symbol s) s env
241 > iReduce env (Symbol s) = Map.findWithDefault (Symbol s) s env
242242
243243 A pair where the LHS is a function i-reduces to the application of that
244244 function to the RHS of the pair, in the current function.
245245
246 > iReduce env (Pair (Fn _ f) b) = f env b
246 > iReduce env (Pair (Fn _ f) b) = f env b
247247
248248 Any other pair i-reduces to a pair with pairwise o-reduced contents.
249249
250 > iReduce env (Pair a b) = Pair (oReduce env a) (oReduce env b)
250 > iReduce env (Pair a b) = Pair (oReduce env a) (oReduce env b)
251251
252252 The inner reduction of an evaluation of some expression x is the i-reduction
253253 of x, i-reduced one more time.
254254
255 > iReduce env (Eval x) = iReduce env (iReduce env x)
255 > iReduce env (Eval x) = iReduce env (iReduce env x)
256256
257257
258258 Standard Environment
269269 Applying `fst` (resp. `snd`) to a pair returns the o-reduction of the
270270 first (resp. second) element of that pair.
271271
272 > pFst env (Pair a _) = oReduce env a
273 > pSnd env (Pair _ b) = oReduce env b
272 > pFst env (Pair a _) = oReduce env a
273 > pSnd env (Pair _ b) = oReduce env b
274274
275275 Applying `ifequal` to a pair of pairs proceeds as follows. The contents
276276 of the first pair are compared for (deep) equality. If they are equal,
277277 the o-reduction of the first element of the second pair is returned; if not,
278278 the o-reduction of the second element of the second pair is returned.
279279
280 > pIfEqual env (Pair (Pair a b) (Pair yes no))
281 > | a == b = oReduce env yes
282 > | otherwise = oReduce env no
280 > pIfEqual env (Pair (Pair a b) (Pair yes no))
281 > | a == b = oReduce env yes
282 > | otherwise = oReduce env no
283283
284284 Applying `typeof` to a value of any kind returns a symbol describing
285285 the type of that value. For symbol, `symbol` is returned; for pairs,
286286 `pair`; for evaluations, `eval`; and for functions, `function`.
287287
288 > pTypeOf env (Symbol _) = Symbol "symbol"
289 > pTypeOf env (Pair _ _) = Symbol "pair"
290 > pTypeOf env (Eval _) = Symbol "eval"
291 > pTypeOf env (Fn _ _) = Symbol "function"
288 > pTypeOf env (Symbol _) = Symbol "symbol"
289 > pTypeOf env (Pair _ _) = Symbol "pair"
290 > pTypeOf env (Eval _) = Symbol "eval"
291 > pTypeOf env (Fn _ _) = Symbol "function"
292292
293293 Applying `uneval` to an expression returns the evaluation of that
294294 expression. (Note that nothing is reduced in this process.)
295295
296 > pUnEval env x = Eval x
296 > pUnEval env x = Eval x
297297
298298 Applying `let` to a pair of a pair (called the "binder") and an expression
299299 returns the o-reduction of that expression in a new environment, constructed
302302 A new environment is created; it is just like the current evironment except
303303 with the obtained symbol bound to the obtained value.
304304
305 > pLet env (Pair (Pair name binding) expr) =
306 > let
307 > (Symbol sym) = oReduce env name
308 > val = oReduce env binding
309 > env' = Map.insert sym val env
310 > in
311 > oReduce env' expr
305 > pLet env (Pair (Pair name binding) expr) =
306 > let
307 > (Symbol sym) = oReduce env name
308 > val = oReduce env binding
309 > env' = Map.insert sym val env
310 > in
311 > oReduce env' expr
312312
313313 And finally, we define the standard environment by associating each of the
314314 above defined functions with a symbol.
315315
316 > stdEnv :: Env
317 > stdEnv = Map.fromList $ map (\(name, fun) -> (name, (Fn name fun)))
318 > [
319 > ("fst", pFst),
320 > ("snd", pSnd),
321 > ("if-equal?", pIfEqual),
322 > ("type-of", pTypeOf),
323 > ("uneval", pUnEval),
324 > ("let", pLet)
325 > ]
316 > stdEnv :: Env
317 > stdEnv = Map.fromList $ map (\(name, fun) -> (name, (Fn name fun)))
318 > [
319 > ("fst", pFst),
320 > ("snd", pSnd),
321 > ("if-equal?", pIfEqual),
322 > ("type-of", pTypeOf),
323 > ("uneval", pUnEval),
324 > ("let", pLet)
325 > ]
326326
327327
328328 Top-Level Driver
333333 begins with '%'. No Pail expression can begin with this character, so
334334 parse errors can be detected unambiguously.
335335
336 > runPail line =
337 > case (parse expr "" line) of
338 > Left err -> "%" ++ (show err)
339 > Right x -> show (oReduce stdEnv x)
336 > runPail line =
337 > case (parse expr "" line) of
338 > Left err -> "%" ++ (show err)
339 > Right x -> show (oReduce stdEnv x)
340340
341341 Happy bailing!
342342 Chris Pressey