git @ Cat's Eye Technologies Pail / rel_1_0_2019_1008
Merge pull request #2 from catseye/develop-2019-2 Develop 2019 2 Chris Pressey authored 1 year, 9 months ago GitHub committed 1 year, 9 months ago
12 changed file(s) with 605 addition(s) and 589 deletion(s). Raw diff Collapse all Expand all
+0
-36
README.markdown less more
0 Pail
1 ====
2
3 Pail is an esoteric programming language based on pairs; just as Lisp
4 stands for *LIS*t *P*rocessing, Pail stands for *PAI*r *L*anguage.
5
6 This is the reference distribution for Pail.
7
8 The Pail programming language is documented in the literate Haskell
9 source code of its reference interpreter, `Pail.lhs`, which can be
10 found in the `src` subdirectory:
11
12 * [src/Pail.lhs](src/Pail.lhs)
13
14 Some tests, in [Falderal][] format, which might clarify the intended
15 behaviour, can be found in `Pail.markdown` in the `tests` subdirectory:
16
17 * [tests/Pail.markdown](tests/Pail.markdown)
18
19 These files are distributed under a 3-clause BSD license. See the file
20 `LICENSE` for the license text.
21
22 There is also a demonstration of running the Pail interpreter in
23 a web browser, by compiling the reference implementation to Javascript
24 with the [Haste][] compiler. You can try this locally by building
25 `demo/pail.js` and opening `demo/pail.html` in a web browser.
26
27 More information
28 ----------------
29
30 For more information on the language, see the [Pail][] entry at
31 Cat's Eye Technologies.
32
33 [Pail]: https://catseye.tc/node/Pail
34 [Falderal]: https://catseye.tc/node/Falderal
35 [Haste]: https://haste-lang.org/
0 Pail
1 ====
2
3 Pail is an esoteric programming language based on pairs; just as Lisp
4 stands for *LIS*t *P*rocessing, Pail stands for *PAI*r *L*anguage.
5
6 This is the reference distribution for Pail.
7
8 The Pail programming language is documented in the literate Haskell
9 source code of its reference interpreter, `Pail.lhs`, which can be
10 found in the `src/Language` subdirectory:
11
12 * [src/Language/Pail.lhs](src/Language/Pail.lhs)
13
14 The literate Haskell was written as if it were Markdown, so you might
15 (or might not) have luck looking at it as such in a browsing interface:
16
17 * [Language.Pail](src/Language/)
18
19 Some tests, in [Falderal][] format, which might clarify the intended
20 behaviour, can be found in `Pail.md` in the `tests` subdirectory:
21
22 * [tests/Pail.md](tests/Pail.md)
23
24 These files are distributed under a 3-clause BSD license. See the file
25 `LICENSE` for the license text.
26
27 There is also a demonstration of running the Pail interpreter in
28 a web browser, by compiling the reference implementation to Javascript
29 with the [Haste][] compiler. You can try this locally by building
30 `demo/pail.js` and opening `demo/pail.html` in a web browser.
31
32 More information
33 ----------------
34
35 For more information on the language, see the [Pail][] entry at
36 Cat's Eye Technologies.
37
38 [Pail]: https://catseye.tc/node/Pail
39 [Falderal]: https://catseye.tc/node/Falderal
40 [Haste]: https://haste-lang.org/
33 DIR=`dirname $THIS`
44 NAME=`basename $THIS`
55 SRC=$DIR/../src
6 if [ -x $DIR/$NAME.exe ] ; then
6 if [ "x$FORCE_HUGS" != "x" ] ; then
7 exec runhugs -i$SRC $SRC/Main.hs $*
8 elif [ -x $DIR/$NAME.exe ] ; then
79 exec $DIR/$NAME.exe $*
810 elif command -v runhaskell 2>&1 >/dev/null ; then
911 exec runhaskell -i$SRC $SRC/Main.hs $*
00 #!/bin/sh
11
2 rm -f src/*.hi src/*.o src/*.jsmod bin/*.exe
2 find . -name "*.o" -exec rm {} \;
3 find . -name "*.hi" -exec rm {} \;
4 find . -name "*.jsmod" -exec rm {} \;
5 find . -name "*.exe" -exec rm {} \;
00 module Main where
11
2 import Haste
3 import Haste.DOM
4 import Haste.Events
2 import Haste.DOM (withElems, getValue, setProp)
3 import Haste.Events (onEvent, MouseEvent(Click))
54
6 import Pail
5 import Language.Pail (runPail)
6
77
88 main = withElems ["prog", "result", "run-button"] driver
99
10 escapeHTML "" = ""
11 escapeHTML ('<' : rest) = "&lt;" ++ escapeHTML rest
12 escapeHTML ('>' : rest) = "&gt;" ++ escapeHTML rest
13 escapeHTML ('&' : rest) = "&amp;" ++ escapeHTML rest
14 escapeHTML (c : rest) = (c : escapeHTML rest)
15
16 driver [progElem, resultElem, runButtonElem] = do
17 onEvent runButtonElem Click $ \_ -> execute
18 where
19 execute = do
20 Just prog <- getValue progElem
21 setProp resultElem "innerHTML" (escapeHTML $ runPail prog)
10 driver [progElem, resultElem, runButtonElem] =
11 onEvent runButtonElem Click $ \_ -> do
12 Just prog <- getValue progElem
13 setProp resultElem "textContent" $ runPail prog
0 > module Language.Pail where
1
2 Pail
3 ====
4
5 Pail is a programming language based on pairs; just as Lisp stands for
6 *LIS*t *P*rocessing, Pail stands for *PAI*r *L*anguage.
7
8 Pail's original working title was "Bizaaro[sic]-Pixley", as it resembles
9 Pixley in many ways, but everything's all changed around and made wicked
10 funny, man.
11
12 (If you don't know anything about Pixley, just know that it's a tiny subset
13 of Scheme.)
14
15 The first way in which Pail is "Bizaaro" is that while Pixley structures are
16 expressed solely with lists (proper ones, too,) Pail structures are expressed
17 solely with pairs. So where Pixley has `car` and `cdr`, Pail has `fst` and
18 `snd`.
19
20 The second and more significant way is that while Pixley, like Scheme
21 and Lisp, is "evaluate-first-quote-only-when-asked", Pail is "quote-first-
22 evaluate-only-when-asked". What this means is, when Pixley sees:
23
24 (+ 1 2)
25
26 ...it evaluates `+` to get a function (addition), `1` to get the number one,
27 `2` to get the number two, then applies the function to the arguments to
28 arrive at the result (the number three.) If you wanted to arrive at the
29 result `(+ 1 2)`, you would have to say:
30
31 (quote (+ 1 2))
32
33 On the other hand, when Pail sees:
34
35 [add [1 2]]
36
37 It evaluates to exactly that,
38
39 [add [1 2]]
40
41 In order to get Pail to look at that structure as an expression and evaluate
42 it, you need to wrap it in an evaluation. Each kind of term is evaluated
43 slightly differently (symbols evaluate to what they're bound to, pairs
44 recursively evaluate their contents, etc.), so to get Pail to evaluate that
45 term like Pixley would do straight off, you would have to say:
46
47 *[*add [1 2]]
48
49 If the 1 and 2 weren't literal integers, but rather bound variables, you
50 would need even more asterisks in there.
51
52 A third and fairly minor way is related to how bindings are created.
53 Noting that Haskell lets you say awesome things like
54
55 let 2 + 2 = 5 in 2 + 2
56
57 and
58
59 let in 5
60
61 (the latter apparently being in emulation of Scheme's allowing an empty
62 list of bindings, i.e. `(let () 5)`), it struck the author that, in order
63 for this senselessness to be total, you ought also to be able to say
64
65 let let a = b in a = 5 in b
66
67 Alas, Haskell does not allow this. Pail, however, does.
68
69 I don't actually know how to do recursion in Pail yet; I think you can,
70 somehow, by using `let`s and evaluations and `uneval`, but I haven't actually
71 constructed the equivalent of a recursive function with that. So it might
72 be the case that in some future version, a lambda form (or, hopefully,
73 something even more interesting) will be added.
74
75 In this respect, and in the "`let let a = b`" circumstance, Pail echoes an
76 earlier attempt of mine to create a reflective rewriting language called Rho.
77 I didn't ever really figure out how to program in Rho, and I really haven't
78 figured out how to program in Pail. But maybe someone else will, and maybe
79 that will shed some more light on Rho.
80
81 What follows is `Pail.lhs`, the reference implementation of the Pail
82 programming language.
83
84 > import Text.ParserCombinators.Parsec
85 > import qualified Data.Map as Map
86
87
88 Definitions
89 ===========
90
91 An environment maps names (represented as strings) to expressions.
92
93 > type Env = Map.Map String Expr
94
95 A symbol is an expression.
96
97 > data Expr = Symbol String
98
99 If a and b are expressions, then a pair of a and b is an expression.
100
101 > | Pair Expr Expr
102
103 If a is an expression, then the evaluation of a is an expression.
104
105 > | Eval Expr
106
107 If f is a function that takes an environment and an expression
108 to an expression, then f is an expression. f may optionally
109 be associated with a name (represented as a string) for to make
110 depiction of expressions more convenient, but there is no language-
111 level association between the function and its name.
112
113 > | Fn String (Env -> Expr -> Expr)
114
115 Nothing else is an expression.
116
117 See below for how expressions are denoted. We will mention only here
118 that functions cannot strictly speaking be denoted directly, but for
119 convenience, functions with known names can be represented by `<foo>`,
120 where `foo` is the name of the function.
121
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
129
130 Two symbols are equal if the strings by which they are represented
131 are equal.
132
133 > (Symbol s) == (Symbol t) = s == t
134
135 Two pairs are equal if their contents are pairwise equal.
136
137 > (Pair a1 b1) == (Pair a2 b2) = (a1 == a2) && (b1 == b2)
138
139 Two evaluations are equal if their contents are equal.
140
141 > (Eval x) == (Eval y) = x == y
142
143 Two functions are never considered equal.
144
145 > (Fn n _) == (Fn m _) = False
146
147
148 Parser
149 ======
150
151 The overall grammar of the language is:
152
153 Expr ::= symbol | "[" Expr Expr "]" | "*" Expr | "#" Expr
154
155 A symbol is denoted by a string which may contain only alphanumeric
156 characters, hyphens, underscores, and question marks.
157
158 > symbol = do
159 > c <- letter
160 > cs <- many (alphaNum <|> char '-' <|> char '?' <|> char '_')
161 > return (Symbol (c:cs))
162
163 A pair of expressions a and b is denoted
164
165 [a b]
166
167 > pair = do
168 > string "["
169 > a <- expr
170 > b <- expr
171 > spaces
172 > string "]"
173 > return (Pair a b)
174
175 An evaluation of an expression a is denoted
176
177 *a
178
179 > eval = do
180 > string "*"
181 > a <- expr
182 > return (Eval a)
183
184 As a bit of syntactic sugar, the denotation
185
186 #a
187
188 for some expression a is equivalent to the denotation
189
190 **[*uneval a]
191
192 > uneval = do
193 > string "#"
194 > a <- expr
195 > return (Eval (Eval (Pair (Eval (Symbol "uneval")) a)))
196
197 The top-level parsing function implements the overall grammar given above.
198 Note that we need to give the type of this parser here -- otherwise the
199 type inferencer freaks out for some reason.
200
201 > expr :: Parser Expr
202 > expr = do
203 > spaces
204 > r <- (eval <|> uneval <|> pair <|> symbol)
205 > return r
206
207 A convenience function for parsing Pail programs.
208
209 > parsePail program = parse expr "" program
210
211
212 Evaluator
213 =========
214
215 We evaluate a Pail expression by reducing it. (We use this terminology
216 to try to limit confusion, since "an evaluation of" is already part of our
217 definition of Pail expressions.)
218
219 There are two kinds of reductions in Pail: outer ("o-") reductions and inner
220 ("i-") reductions. So, to be more specific, we evaluate a Pail expression
221 by o-reducing it. Outer reductions may involve inner reductions, which may
222 themselves involve further outer reductions.
223
224 Outer Reduction
225 ---------------
226
227 An evaluation of an expression o-reduces to the i-reduction of its contents.
228
229 > oReduce env (Eval x) = iReduce env x
230
231 Everything else o-reduces to itself.
232
233 > oReduce env x = x
234
235 Inner Reduction
236 ---------------
237
238 A symbol i-reduces to the expression to which is it bound in the current
239 environment. If it is not bound to anything, it i-reduces to itself.
240
241 > iReduce env (Symbol s) = Map.findWithDefault (Symbol s) s env
242
243 A pair where the LHS is a function i-reduces to the application of that
244 function to the RHS of the pair, in the current function.
245
246 > iReduce env (Pair (Fn _ f) b) = f env b
247
248 Any other pair i-reduces to a pair with pairwise o-reduced contents.
249
250 > iReduce env (Pair a b) = Pair (oReduce env a) (oReduce env b)
251
252 The inner reduction of an evaluation of some expression x is the i-reduction
253 of x, i-reduced one more time.
254
255 > iReduce env (Eval x) = iReduce env (iReduce env x)
256
257
258 Standard Environment
259 ====================
260
261 Applying any of these functions to any type of argument which is not
262 defined here (for example, applying `fst` to a non-pair) is an error;
263 evaluation terminates immediately with an error term or message.
264
265 Again, to try to limit confusion (I must not say "reduce confusion" or
266 things will get even worse), we use the terminology that a function
267 "returns" a value here, rather than "reducing" or "evaluating" to one.
268
269 Applying `fst` (resp. `snd`) to a pair returns the o-reduction of the
270 first (resp. second) element of that pair.
271
272 > pFst env (Pair a _) = oReduce env a
273 > pSnd env (Pair _ b) = oReduce env b
274
275 Applying `ifequal` to a pair of pairs proceeds as follows. The contents
276 of the first pair are compared for (deep) equality. If they are equal,
277 the o-reduction of the first element of the second pair is returned; if not,
278 the o-reduction of the second element of the second pair is returned.
279
280 > pIfEqual env (Pair (Pair a b) (Pair yes no))
281 > | a == b = oReduce env yes
282 > | otherwise = oReduce env no
283
284 Applying `typeof` to a value of any kind returns a symbol describing
285 the type of that value. For symbol, `symbol` is returned; for pairs,
286 `pair`; for evaluations, `eval`; and for functions, `function`.
287
288 > pTypeOf env (Symbol _) = Symbol "symbol"
289 > pTypeOf env (Pair _ _) = Symbol "pair"
290 > pTypeOf env (Eval _) = Symbol "eval"
291 > pTypeOf env (Fn _ _) = Symbol "function"
292
293 Applying `uneval` to an expression returns the evaluation of that
294 expression. (Note that nothing is reduced in this process.)
295
296 > pUnEval env x = Eval x
297
298 Applying `let` to a pair of a pair (called the "binder") and an expression
299 returns the o-reduction of that expression in a new environment, constructed
300 as follows. The first element of the binder is o-reduced to obtain a symbol;
301 the second element of the binder is o-reduced to obtain a value of any type.
302 A new environment is created; it is just like the current evironment except
303 with the obtained symbol bound to the obtained value.
304
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
312
313 And finally, we define the standard environment by associating each of the
314 above defined functions with a symbol.
315
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 > ]
326
327
328 Top-Level Driver
329 ================
330
331 Note that if this driver is given text which it cannot parse, it will
332 evaluate to a string which contains the parse error message and always
333 begins with '%'. No Pail expression can begin with this character, so
334 parse errors can be detected unambiguously.
335
336 > runPail line =
337 > case (parse expr "" line) of
338 > Left err -> "%" ++ (show err)
339 > Right x -> show (oReduce stdEnv x)
340
341 Happy bailing!
342 Chris Pressey
343 Evanston, Illinois
344 May 27, 2011
00 module Main where
11
22 import System.Environment
3 import Pail
3 import System.Exit
4 import System.IO
5
6 import Language.Pail (runPail)
7
48
59 main = do
6 [fileName] <- getArgs
7 c <- readFile fileName
8 putStrLn $ runPail c
10 args <- getArgs
11 case args of
12 [fileName] -> do
13 c <- readFile fileName
14 putStrLn $ runPail c
15 return ()
16 _ -> do
17 abortWith "Usage: pail <filename.pail>"
18
19 abortWith msg = do
20 hPutStrLn stderr msg
21 exitWith (ExitFailure 1)
+0
-345
src/Pail.lhs less more
0 > module Pail where
1
2 Pail
3 ====
4
5 Pail is a programming language based on pairs; just as Lisp stands for
6 *LIS*t *P*rocessing, Pail stands for *PAI*r *L*anguage.
7
8 Pail's original working title was "Bizaaro[sic]-Pixley", as it resembles
9 Pixley in many ways, but everything's all changed around and made wicked
10 funny, man.
11
12 (If you don't know anything about Pixley, just know that it's a tiny subset
13 of Scheme.)
14
15 The first way in which Pail is "Bizaaro" is that while Pixley structures are
16 expressed solely with lists (proper ones, too,) Pail structures are expressed
17 solely with pairs. So where Pixley has `car` and `cdr`, Pail has `fst` and
18 `snd`.
19
20 The second and more significant way is that while Pixley, like Scheme
21 and Lisp, is "evaluate-first-quote-only-when-asked", Pail is "quote-first-
22 evaluate-only-when-asked". What this means is, when Pixley sees:
23
24 (+ 1 2)
25
26 ...it evaluates `+` to get a function (addition), `1` to get the number one,
27 `2` to get the number two, then applies the function to the arguments to
28 arrive at the result (the number three.) If you wanted to arrive at the
29 result `(+ 1 2)`, you would have to say:
30
31 (quote (+ 1 2))
32
33 On the other hand, when Pail sees:
34
35 [add [1 2]]
36
37 It evaluates to exactly that,
38
39 [add [1 2]]
40
41 In order to get Pail to look at that structure as an expression and evaluate
42 it, you need to wrap it in an evaluation. Each kind of term is evaluated
43 slightly differently (symbols evaluate to what they're bound to, pairs
44 recursively evaluate their contents, etc.), so to get Pail to evaluate that
45 term like Pixley would do straight off, you would have to say:
46
47 *[*add [1 2]]
48
49 If the 1 and 2 weren't literal integers, but rather bound variables, you
50 would need even more asterisks in there.
51
52 A third and fairly minor way is related to how bindings are created.
53 Noting that Haskell lets you say awesome things like
54
55 let 2 + 2 = 5 in 2 + 2
56
57 and
58
59 let in 5
60
61 (the latter apparently being in emulation of Scheme's allowing an empty
62 list of bindings, i.e. `(let () 5)`), it struck the author that, in order
63 for this senselessness to be total, you ought also to be able to say
64
65 let let a = b in a = 5 in b
66
67 Alas, Haskell does not allow this. Pail, however, does.
68
69 I don't actually know how to do recursion in Pail yet; I think you can,
70 somehow, by using `let`s and evaluations and `uneval`, but I haven't actually
71 constructed the equivalent of a recursive function with that. So it might
72 be the case that in some future version, a lambda form (or, hopefully,
73 something even more interesting) will be added.
74
75 In this respect, and in the "`let let a = b`" circumstance, Pail echoes an
76 earlier attempt of mine to create a reflective rewriting language called Rho.
77 I didn't ever really figure out how to program in Rho, and I really haven't
78 figured out how to program in Pail. But maybe someone else will, and maybe
79 that will shed some more light on Rho.
80
81 What follows is `Pail.lhs`, the reference implementation of the Pail
82 programming language.
83
84 > import Text.ParserCombinators.Parsec
85 > import qualified Data.Map as Map
86
87
88 Definitions
89 ===========
90
91 An environment maps names (represented as strings) to expressions.
92
93 > type Env = Map.Map String Expr
94
95 A symbol is an expression.
96
97 > data Expr = Symbol String
98
99 If a and b are expressions, then a pair of a and b is an expression.
100
101 > | Pair Expr Expr
102
103 If a is an expression, then the evaluation of a is an expression.
104
105 > | Eval Expr
106
107 If f is a function that takes an environment and an expression
108 to an expression, then f is an expression. f may optionally
109 be associated with a name (represented as a string) for to make
110 depiction of expressions more convenient, but there is no language-
111 level association between the function and its name.
112
113 > | Fn String (Env -> Expr -> Expr)
114
115 Nothing else is an expression.
116
117 See below for how expressions are denoted. We will mention only here
118 that functions cannot strictly speaking be denoted directly, but for
119 convenience, functions with known names can be represented by `<foo>`,
120 where `foo` is the name of the function.
121
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
129
130 Two symbols are equal if the strings by which they are represented
131 are equal.
132
133 > (Symbol s) == (Symbol t) = s == t
134
135 Two pairs are equal if their contents are pairwise equal.
136
137 > (Pair a1 b1) == (Pair a2 b2) = (a1 == a2) && (b1 == b2)
138
139 Two evaluations are equal if their contents are equal.
140
141 > (Eval x) == (Eval y) = x == y
142
143 Two functions are never considered equal.
144
145 > (Fn n _) == (Fn m _) = False
146
147
148 Parser
149 ======
150
151 The overall grammar of the language is:
152
153 Expr ::= symbol | "[" Expr Expr "]" | "*" Expr | "#" Expr
154
155 A symbol is denoted by a string which may contain only alphanumeric
156 characters, hyphens, underscores, and question marks.
157
158 > symbol = do
159 > c <- letter
160 > cs <- many (alphaNum <|> char '-' <|> char '?' <|> char '_')
161 > return (Symbol (c:cs))
162
163 A pair of expressions a and b is denoted
164
165 [a b]
166
167 > pair = do
168 > string "["
169 > a <- expr
170 > b <- expr
171 > spaces
172 > string "]"
173 > return (Pair a b)
174
175 An evaluation of an expression a is denoted
176
177 *a
178
179 > eval = do
180 > string "*"
181 > a <- expr
182 > return (Eval a)
183
184 As a bit of syntactic sugar, the denotation
185
186 #a
187
188 for some expression a is equivalent to the denotation
189
190 **[*uneval a]
191
192 > uneval = do
193 > string "#"
194 > a <- expr
195 > return (Eval (Eval (Pair (Eval (Symbol "uneval")) a)))
196
197 The top-level parsing function implements the overall grammar given above.
198 Note that we need to give the type of this parser here -- otherwise the
199 type inferencer freaks out for some reason.
200
201 > expr :: Parser Expr
202 > expr = do
203 > spaces
204 > r <- (eval <|> uneval <|> pair <|> symbol)
205 > return r
206
207 A convenience function for parsing Pail programs.
208
209 > parsePail program = parse expr "" program
210
211
212 Evaluator
213 =========
214
215 We evaluate a Pail expression by reducing it. (We use this terminology
216 to try to limit confusion, since "an evaluation of" is already part of our
217 definition of Pail expressions.)
218
219 There are two kinds of reductions in Pail: outer ("o-") reductions and inner
220 ("i-") reductions. So, to be more specific, we evaluate a Pail expression
221 by o-reducing it. Outer reductions may involve inner reductions, which may
222 themselves involve further outer reductions.
223
224 Outer Reduction
225 ---------------
226
227 An evaluation of an expression o-reduces to the i-reduction of its contents.
228
229 > oReduce env (Eval x) = iReduce env x
230
231 Everything else o-reduces to itself.
232
233 > oReduce env x = x
234
235 Inner Reduction
236 ---------------
237
238 A symbol i-reduces to the expression to which is it bound in the current
239 environment. If it is not bound to anything, it i-reduces to itself.
240
241 > iReduce env (Symbol s) = Map.findWithDefault (Symbol s) s env
242
243 A pair where the LHS is a function i-reduces to the application of that
244 function to the RHS of the pair, in the current function.
245
246 > iReduce env (Pair (Fn _ f) b) = f env b
247
248 Any other pair i-reduces to a pair with pairwise o-reduced contents.
249
250 > iReduce env (Pair a b) = Pair (oReduce env a) (oReduce env b)
251
252 The inner reduction of an evaluation of some expression x is the i-reduction
253 of x, i-reduced one more time.
254
255 > iReduce env (Eval x) = iReduce env (iReduce env x)
256
257
258 Standard Environment
259 ====================
260
261 Applying any of these functions to any type of argument which is not
262 defined here (for example, applying `fst` to a non-pair) is an error;
263 evaluation terminates immediately with an error term or message.
264
265 Again, to try to limit confusion (I must not say "reduce confusion" or
266 things will get even worse), we use the terminology that a function
267 "returns" a value here, rather than "reducing" or "evaluating" to one.
268
269 Applying `fst` (resp. `snd`) to a pair returns the o-reduction of the
270 first (resp. second) element of that pair.
271
272 > pFst env (Pair a _) = oReduce env a
273 > pSnd env (Pair _ b) = oReduce env b
274
275 Applying `ifequal` to a pair of pairs proceeds as follows. The contents
276 of the first pair are compared for (deep) equality. If they are equal,
277 the o-reduction of the first element of the second pair is returned; if not,
278 the o-reduction of the second element of the second pair is returned.
279
280 > pIfEqual env (Pair (Pair a b) (Pair yes no))
281 > | a == b = oReduce env yes
282 > | otherwise = oReduce env no
283
284 Applying `typeof` to a value of any kind returns a symbol describing
285 the type of that value. For symbol, `symbol` is returned; for pairs,
286 `pair`; for evaluations, `eval`; and for functions, `function`.
287
288 > pTypeOf env (Symbol _) = Symbol "symbol"
289 > pTypeOf env (Pair _ _) = Symbol "pair"
290 > pTypeOf env (Eval _) = Symbol "eval"
291 > pTypeOf env (Fn _ _) = Symbol "function"
292
293 Applying `uneval` to an expression returns the evaluation of that
294 expression. (Note that nothing is reduced in this process.)
295
296 > pUnEval env x = Eval x
297
298 Applying `let` to a pair of a pair (called the "binder") and an expression
299 returns the o-reduction of that expression in a new environment, constructed
300 as follows. The first element of the binder is o-reduced to obtain a symbol;
301 the second element of the binder is o-reduced to obtain a value of any type.
302 A new environment is created; it is just like the current evironment except
303 with the obtained symbol bound to the obtained value.
304
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
312
313 And finally, we define the standard environment by associating each of the
314 above defined functions with a symbol.
315
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 > ]
326
327
328 Top-Level Driver
329 ================
330
331 Note that if this driver is given text which it cannot parse, it will
332 evaluate to a string which contains the parse error message and always
333 begins with '%'. No Pail expression can begin with this character, so
334 parse errors can be detected unambiguously.
335
336 > runPail line =
337 > case (parse expr "" line) of
338 > Left err -> "%" ++ (show err)
339 > Right x -> show (oReduce stdEnv x)
340
341 Happy bailing!
342 Chris Pressey
343 Evanston, Illinois
344 May 27, 2011
00 #!/bin/sh
11
22 APPLIANCES="tests/appliances/pail.md"
3 falderal $APPLIANCES tests/Pail.markdown
3 falderal $APPLIANCES tests/Pail.md
+0
-185
tests/Pail.markdown less more
0 Test Suite for Pail
1 ===================
2
3 This test suite is written in the format of Falderal 0.7. It is far from
4 exhaustive, but provides a basic sanity check that the language I've designed
5 here comes close to what I had in mind.
6
7 Pail Tests
8 ----------
9
10 -> Tests for functionality "Evaluate Pail Expression"
11
12 A symbol reduces to that symbol.
13
14 | fst
15 = fst
16
17 | plains-of-leng?
18 = plains-of-leng?
19
20 A symbol must begin with a letter and contain only letters, digits,
21 hyphens, and question marks.
22
23 | ^hey
24 = %(line 1, column 1):
25 = unexpected "^"
26 = expecting white space, "*", "#", "[" or letter
27
28 A pair reduces to that pair.
29
30 | [a b]
31 = [a b]
32
33 | [fst [a b]]
34 = [fst [a b]]
35
36 | [*fst [a b]]
37 = [*fst [a b]]
38
39 Square brackets must be properly matched.
40
41 | [a b
42 = %(line 1, column 5):
43 = unexpected end of input
44 = expecting letter or digit, "-", "?", "_", white space or "]"
45
46 Evaluation of a symbol reduces to that to which it is bound.
47
48 | *fst
49 = <fst>
50
51 Evaluation of a pair recursively reduces its contents.
52
53 | *[*fst [a b]]
54 = [<fst> [a b]]
55
56 | *[*fst *snd]
57 = [<fst> <snd>]
58
59 | *[*fst *[*snd *fst]]
60 = [<fst> [<snd> <fst>]]
61
62 Evaluation of a pair w/a fun on the lhs applies the fun.
63
64 | **[*fst [a b]]
65 = a
66
67 | **[*snd [a b]]
68 = b
69
70 Reducing an evaluation of a pair can accomplish a cons.
71
72 | *[**[*fst [a b]] **[*snd [c d]]]
73 = [a d]
74
75 Reducing on the lhs of a pair can obtain a fun to apply.
76
77 | **[**[*fst [*snd *fst]] [a b]]
78 = b
79
80 Applying uneval reduces to an evaluation.
81
82 | **[*uneval hello]
83 = *hello
84
85 The form `#x` is syntactic sugar for `**[*uneval x]`.
86
87 | #hello
88 = *hello
89
90 Syntactic sugar is expanded at parse time.
91
92 | [#fst [a b]]
93 = [**[*uneval fst] [a b]]
94
95 It is possible to uneval a fun.
96
97 | #*fst
98 = *<fst>
99
100 Reduction of an uneval'ed symbol can be used to obtain an eval'ed symbol.
101
102 | *[#fst [a b]]
103 = [*fst [a b]]
104
105 Reduction of uneval'ed symbol can be used to obtain a fun.
106
107 | **[#fst [a b]]
108 = [<fst> [a b]]
109
110 Reduction of uneval'ed symbol can be used to apply the obtained fun.
111
112 | ***[#fst [a b]]
113 = a
114
115 Positive test of `if-equal?` on symbols.
116
117 | **[*if-equal? [[a a] [one two]]]
118 = one
119
120 Negative test of `if-equal?` on symbols.
121
122 | **[*if-equal? [[a b] [one two]]]
123 = two
124
125 Negative test of `if-equal?` on evals.
126
127 | ***[*if-equal? [[*a *b] [fst snd]]]
128 = <snd>
129
130 Let can bind a symbol to a symbol.
131
132 | **[*let [[a b] *a]]
133 = b
134
135 Let can bind a symbol to a pair.
136
137 | **[*let [[g [x y]] **[*snd *g]]]
138 = y
139
140 Let can bind a symbol to an expression containing an uneval,
141 which can at a later point be eval'ed and reduced.
142
143 | **[*let [
144 | [sndg *[**[*uneval snd] **[*uneval g]]]
145 | **[*let [
146 | [g [x y]]
147 | ***sndg
148 | ]]
149 | ]]
150 = y
151
152 | **[*let [
153 | [cadrg *[#fst ##*[#snd #g]]]
154 | **[*let [
155 | [g [x [y z]]]
156 | ***cadrg
157 | ]]
158 | ]]
159 = y
160
161 Let can bind uneval'ed expression; prior bindings are honoured.
162
163 | **[*let [
164 | [g moo]
165 | **[*let [
166 | [consnull *[#g null]]
167 | ***consnull
168 | ]]
169 | ]]
170 = [moo null]
171
172 Let can bind uneval'ed expression; prior bindings are shadowed.
173
174 | **[*let [
175 | [g moo]
176 | **[*let [
177 | [consnull *[#g null]]
178 | **[*let [
179 | [g k]
180 | ***consnull
181 | ]]
182 | ]]
183 | ]]
184 = [k null]
0 Test Suite for Pail
1 ===================
2
3 This test suite is written in the format of Falderal 0.7. It is far from
4 exhaustive, but provides a basic sanity check that the language I've designed
5 here comes close to what I had in mind.
6
7 Pail Tests
8 ----------
9
10 -> Tests for functionality "Evaluate Pail Expression"
11
12 A symbol reduces to that symbol.
13
14 | fst
15 = fst
16
17 | plains-of-leng?
18 = plains-of-leng?
19
20 A symbol must begin with a letter and contain only letters, digits,
21 hyphens, and question marks.
22
23 | ^hey
24 = %(line 1, column 1):
25 = unexpected "^"
26 = expecting white space, "*", "#", "[" or letter
27
28 A pair reduces to that pair.
29
30 | [a b]
31 = [a b]
32
33 | [fst [a b]]
34 = [fst [a b]]
35
36 | [*fst [a b]]
37 = [*fst [a b]]
38
39 Square brackets must be properly matched.
40
41 | [a b
42 = %(line 1, column 5):
43 = unexpected end of input
44 = expecting letter or digit, "-", "?", "_", white space or "]"
45
46 Evaluation of a symbol reduces to that to which it is bound.
47
48 | *fst
49 = <fst>
50
51 Evaluation of a pair recursively reduces its contents.
52
53 | *[*fst [a b]]
54 = [<fst> [a b]]
55
56 | *[*fst *snd]
57 = [<fst> <snd>]
58
59 | *[*fst *[*snd *fst]]
60 = [<fst> [<snd> <fst>]]
61
62 Evaluation of a pair w/a fun on the lhs applies the fun.
63
64 | **[*fst [a b]]
65 = a
66
67 | **[*snd [a b]]
68 = b
69
70 Reducing an evaluation of a pair can accomplish a cons.
71
72 | *[**[*fst [a b]] **[*snd [c d]]]
73 = [a d]
74
75 Reducing on the lhs of a pair can obtain a fun to apply.
76
77 | **[**[*fst [*snd *fst]] [a b]]
78 = b
79
80 Applying uneval reduces to an evaluation.
81
82 | **[*uneval hello]
83 = *hello
84
85 The form `#x` is syntactic sugar for `**[*uneval x]`.
86
87 | #hello
88 = *hello
89
90 Syntactic sugar is expanded at parse time.
91
92 | [#fst [a b]]
93 = [**[*uneval fst] [a b]]
94
95 It is possible to uneval a fun.
96
97 | #*fst
98 = *<fst>
99
100 Reduction of an uneval'ed symbol can be used to obtain an eval'ed symbol.
101
102 | *[#fst [a b]]
103 = [*fst [a b]]
104
105 Reduction of uneval'ed symbol can be used to obtain a fun.
106
107 | **[#fst [a b]]
108 = [<fst> [a b]]
109
110 Reduction of uneval'ed symbol can be used to apply the obtained fun.
111
112 | ***[#fst [a b]]
113 = a
114
115 Positive test of `if-equal?` on symbols.
116
117 | **[*if-equal? [[a a] [one two]]]
118 = one
119
120 Negative test of `if-equal?` on symbols.
121
122 | **[*if-equal? [[a b] [one two]]]
123 = two
124
125 Negative test of `if-equal?` on evals.
126
127 | ***[*if-equal? [[*a *b] [fst snd]]]
128 = <snd>
129
130 Let can bind a symbol to a symbol.
131
132 | **[*let [[a b] *a]]
133 = b
134
135 Let can bind a symbol to a pair.
136
137 | **[*let [[g [x y]] **[*snd *g]]]
138 = y
139
140 Let can bind a symbol to an expression containing an uneval,
141 which can at a later point be eval'ed and reduced.
142
143 | **[*let [
144 | [sndg *[**[*uneval snd] **[*uneval g]]]
145 | **[*let [
146 | [g [x y]]
147 | ***sndg
148 | ]]
149 | ]]
150 = y
151
152 | **[*let [
153 | [cadrg *[#fst ##*[#snd #g]]]
154 | **[*let [
155 | [g [x [y z]]]
156 | ***cadrg
157 | ]]
158 | ]]
159 = y
160
161 Let can bind uneval'ed expression; prior bindings are honoured.
162
163 | **[*let [
164 | [g moo]
165 | **[*let [
166 | [consnull *[#g null]]
167 | ***consnull
168 | ]]
169 | ]]
170 = [moo null]
171
172 Let can bind uneval'ed expression; prior bindings are shadowed.
173
174 | **[*let [
175 | [g moo]
176 | **[*let [
177 | [consnull *[#g null]]
178 | **[*let [
179 | [g k]
180 | ***consnull
181 | ]]
182 | ]]
183 | ]]
184 = [k null]