git @ Cat's Eye Technologies Pail / rel_1_0_2011_1214
Initial import of Pail version 1.0 revision 2011.1214 sources. catseye 9 years ago
3 changed file(s) with 564 addition(s) and 0 deletion(s). Raw diff Collapse all Expand all
0 > module Pail where
1
2 > --
3 > -- Pail.lhs -- reference implementation of the Pail programming language
4 > -- Copyright (c)2011 Cat's Eye Technologies. All rights reserved.
5 > --
6 > -- Redistribution and use in source and binary forms, with or without
7 > -- modification, are permitted provided that the following conditions
8 > -- are met:
9 > --
10 > -- 1. Redistributions of source code must retain the above copyright
11 > -- notices, this list of conditions and the following disclaimer.
12 > -- 2. Redistributions in binary form must reproduce the above copyright
13 > -- notices, this list of conditions, and the following disclaimer in
14 > -- the documentation and/or other materials provided with the
15 > -- distribution.
16 > -- 3. Neither the names of the copyright holders nor the names of their
17 > -- contributors may be used to endorse or promote products derived
18 > -- from this software without specific prior written permission.
19 > --
20 > -- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 > -- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 > -- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 > -- FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 > -- COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 > -- INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 > -- BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 > -- LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 > -- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 > -- LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30 > -- ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 > -- POSSIBILITY OF SUCH DAMAGE.
32 > --
33
34 Pail
35 ====
36
37 Pail is a programming language based on pairs; just as Lisp stands for
38 *LIS*t *P*rocessing, Pail stands for *PAI*r *L*anguage.
39
40 Pail's original working title was "Bizaaro[sic]-Pixley", as it resembles
41 Pixley in many ways, but everything's all changed around and made wicked
42 funny, man.
43
44 (If you don't know anything about Pixley, just know that it's a tiny subset
45 of Scheme.)
46
47 The first way in which Pail is "Bizaaro" is that while Pixley structures are
48 expressed solely with lists (proper ones, too,) Pail structures are expressed
49 solely with pairs. So where Pixley has `car` and `cdr`, Pail has `fst` and
50 `snd`.
51
52 The second and more significant way is that while Pixley, like Scheme
53 and Lisp, is "evaluate-first-quote-only-when-asked", Pail is "quote-first-
54 evaluate-only-when-asked". What this means is, when Pixley sees:
55
56 (+ 1 2)
57
58 ...it evaluates `+` to get a function (addition), `1` to get the number one,
59 `2` to get the number two, then applies the function to the arguments to
60 arrive at the result (the number three.) If you wanted to arrive at the
61 result `(+ 1 2)`, you would have to say:
62
63 (quote (+ 1 2))
64
65 On the other hand, when Pail sees:
66
67 [add [1 2]]
68
69 It evaluates to exactly that,
70
71 [add [1 2]]
72
73 In order to get Pail to look at that structure as an expression and evaluate
74 it, you need to wrap it in an evaluation. Each kind of term is evaluated
75 slightly differently (symbols evaluate to what they're bound to, pairs
76 recursively evaluate their contents, etc.), so to get Pail to evaluate that
77 term like Pixley would do straight off, you would have to say:
78
79 *[*add [1 2]]
80
81 If the 1 and 2 weren't literal integers, but rather bound variables, you
82 would need even more asterisks in there.
83
84 A third and fairly minor way is related to how bindings are created.
85 Noting that Haskell lets you say awesome things like
86
87 let 2 + 2 = 5 in 2 + 2
88
89 and
90
91 let in 5
92
93 (the latter apparently being in emulation of Scheme's allowing an empty
94 list of bindings, i.e. `(let () 5)`), it struck the author that, in order
95 for this senselessness to be total, you ought also to be able to say
96
97 let let a = b in a = 5 in b
98
99 Alas, Haskell does not allow this. Pail, however, does.
100
101 I don't actually know how to do recursion in Pail yet; I think you can,
102 somehow, by using `let`s and evaluations and `uneval`, but I haven't actually
103 constructed the equivalent of a recursive function with that. So it might
104 be the case that in some future version, a lambda form (or, hopefully,
105 something even more interesting) will be added.
106
107 In this respect, and in the "`let let a = b`" circumstance, Pail echoes an
108 earlier attempt of mine to create a reflective rewriting language called Rho.
109 I didn't ever really figure out how to program in Rho, and I really haven't
110 figured out how to program in Pail. But maybe someone else will, and maybe
111 that will shed some more light on Rho.
112
113 > import Text.ParserCombinators.Parsec
114 > import qualified Data.Map as Map
115
116
117 Definitions
118 ===========
119
120 An environment maps names (represented as strings) to expressions.
121
122 > type Env = Map.Map String Expr
123
124 A symbol is an expression.
125
126 > data Expr = Symbol String
127
128 If a and b are expressions, then a pair of a and b is an expression.
129
130 > | Pair Expr Expr
131
132 If a is an expression, then the evaluation of a is an expression.
133
134 > | Eval Expr
135
136 If f is a function that takes an environment and an expression
137 to an expression, then f is an expression. f may optionally
138 be associated with a name (represented as a string) for to make
139 depiction of expressions more convenient, but there is no language-
140 level association between the function and its name.
141
142 > | Fn String (Env -> Expr -> Expr)
143
144 Nothing else is an expression.
145
146 See below for how expressions are denoted. We will mention only here
147 that functions cannot strictly speaking be denoted directly, but for
148 convenience, functions with known names can be represented by `<foo>`,
149 where `foo` is the name of the function.
150
151 > instance Show Expr where
152 > show (Symbol s) = s
153 > show (Pair a b) = "[" ++ (show a) ++ " " ++ (show b) ++ "]"
154 > show (Eval x) = "*" ++ (show x)
155 > show (Fn n _) = "<" ++ n ++ ">"
156
157 > instance Eq Expr where
158
159 Two symbols are equal if the strings by which they are represented
160 are equal.
161
162 > (Symbol s) == (Symbol t) = s == t
163
164 Two pairs are equal if their contents are pairwise equal.
165
166 > (Pair a1 b1) == (Pair a2 b2) = (a1 == a2) && (b1 == b2)
167
168 Two evaluations are equal if their contents are equal.
169
170 > (Eval x) == (Eval y) = x == y
171
172 Two functions are never considered equal.
173
174 > (Fn n _) == (Fn m _) = False
175
176
177 Parser
178 ======
179
180 The overall grammar of the language is:
181
182 Expr ::= symbol | "[" Expr Expr "]" | "*" Expr | "#" Expr
183
184 A symbol is denoted by a string which may contain only alphanumeric
185 characters, hyphens, underscores, and question marks.
186
187 > symbol = do
188 > c <- letter
189 > cs <- many (alphaNum <|> char '-' <|> char '?' <|> char '_')
190 > return (Symbol (c:cs))
191
192 A pair of expressions a and b is denoted
193
194 [a b]
195
196 > pair = do
197 > string "["
198 > a <- expr
199 > b <- expr
200 > spaces
201 > string "]"
202 > return (Pair a b)
203
204 An evaluation of an expression a is denoted
205
206 *a
207
208 > eval = do
209 > string "*"
210 > a <- expr
211 > return (Eval a)
212
213 As a bit of syntactic sugar, the denotation
214
215 #a
216
217 for some expression a is equivalent to the denotation
218
219 **[*uneval a]
220
221 > uneval = do
222 > string "#"
223 > a <- expr
224 > return (Eval (Eval (Pair (Eval (Symbol "uneval")) a)))
225
226 The top-level parsing function implements the overall grammar given above.
227 Note that we need to give the type of this parser here -- otherwise the
228 type inferencer freaks out for some reason.
229
230 > expr :: Parser Expr
231 > expr = do
232 > spaces
233 > r <- (eval <|> uneval <|> pair <|> symbol)
234 > return r
235
236 A convenience function for parsing Pail programs.
237
238 > parsePail program = parse expr "" program
239
240
241 Evaluator
242 =========
243
244 We evaluate a Pail expression by reducing it. (We use this terminology
245 to try to limit confusion, since "an evaluation of" is already part of our
246 definition of Pail expressions.)
247
248 There are two kinds of reductions in Pail: outer ("o-") reductions and inner
249 ("i-") reductions. So, to be more specific, we evaluate a Pail expression
250 by o-reducing it. Outer reductions may involve inner reductions, which may
251 themselves involve further outer reductions.
252
253 Outer Reduction
254 ---------------
255
256 An evaluation of some expression x o-reduces to the i-reduction of its
257 contents.
258
259 > oReduce env (Eval x) = iReduce env x
260
261 Everything else o-reduces to itself.
262
263 > oReduce env x = x
264
265 Inner Reduction
266 ---------------
267
268 A symbol i-reduces to the expression to which is it bound in the current
269 environment. If it is not bound to anything, it i-reduces to itself.
270
271 > iReduce env (Symbol s) = Map.findWithDefault (Symbol s) s env
272
273 A pair where the LHS is a function i-reduces to the application of that
274 function to the RHS of the pair, in the current function.
275
276 > iReduce env (Pair (Fn _ f) b) = f env b
277
278 Any other pair i-reduces to a pair with pairwise o-reduced contents.
279
280 > iReduce env (Pair a b) = Pair (oReduce env a) (oReduce env b)
281
282 The inner reduction of an evaluation of some expression x is the i-reduction
283 of x, i-reduced one more time.
284
285 > iReduce env (Eval x) = iReduce env (iReduce env x)
286
287
288 Standard Environment
289 ====================
290
291 Applying any of these functions to any type of argument which is not
292 defined here (for example, applying `fst` to a non-pair) is an error;
293 evaluation terminates immediately with an error term or message.
294
295 Again, to try to limit confusion (I must not say "reduce confusion" or
296 things will get even worse), we use the terminology that a function
297 "returns" a value here, rather than "reducing" or "evaluating" to one.
298
299 Applying `fst` to a pair (resp. `snd`) returns the o-reduction of the
300 first (resp. second) element of that pair.
301
302 > pFst env (Pair a _) = oReduce env a
303 > pSnd env (Pair _ b) = oReduce env b
304
305 Applying `ifequal` to a pair of pairs proceeds as follows. The contents
306 of the first pair are compared for (deep) equality. If they are equal,
307 the o-reduction of the first element of the second pair is returned; if not,
308 the o-reduction of the second element of the second pair is returned.
309
310 > pIfEqual env (Pair (Pair a b) (Pair yes no))
311 > | a == b = oReduce env yes
312 > | otherwise = oReduce env no
313
314 Applying `typeof` to a value of any kind returns a symbol describing
315 the type of that value. For symbol, `symbol` is returned; for pairs,
316 `pair`; for evaluations, `eval`; and for functions, `function`.
317
318 > pTypeOf env (Symbol _) = Symbol "symbol"
319 > pTypeOf env (Pair _ _) = Symbol "pair"
320 > pTypeOf env (Eval _) = Symbol "eval"
321 > pTypeOf env (Fn _ _) = Symbol "function"
322
323 Applying `uneval` to an expression returns the evaluation of that
324 expression. (Note that nothing is reduced in this process.)
325
326 > pUnEval env x = Eval x
327
328 Applying `let` to a pair of a pair (called the "binder") and an expression
329 returns the o-reduction of that expression in a new environment, constructed
330 as follows. The first element of the binder is o-reduced to obtain a symbol;
331 the second element of the binder is o-reduced to obtain a value of any type.
332 A new environment is created; it is just like the current evironment except
333 with the obtained symbol bound to the obtained value.
334
335 > pLet env (Pair (Pair name binding) expr) =
336 > let
337 > (Symbol sym) = oReduce env name
338 > val = oReduce env binding
339 > env' = Map.insert sym val env
340 > in
341 > oReduce env' expr
342
343 And finally, we define the standard environment by associating each of the
344 above defined functions with a symbol.
345
346 > stdEnv :: Env
347 > stdEnv = Map.fromList (map (\(name, fun) -> (name, (Fn name fun)))
348 > [
349 > ("fst", pFst),
350 > ("snd", pSnd),
351 > ("if-equal?", pIfEqual),
352 > ("type-of", pTypeOf),
353 > ("uneval", pUnEval),
354 > ("let", pLet)
355 > ])
356
357
358 Top-Level Driver
359 ================
360
361 Note that if this driver is given text which it cannot parse, it will
362 evaluate to a string which contains the parse error message and always
363 begins with '%'. No Pail expression can begin with this character, so
364 parse errors can be detected unambiguously.
365
366 > runPail line =
367 > case (parse expr "" line) of
368 > Left err -> "%" ++ (show err)
369 > Right x -> show (oReduce stdEnv x)
370
371 Happy bailing!
372 Chris Pressey
373 Evanston, Illinois
374 May 27, 2011
0 #!/bin/sh
1 cd src && falderal test ../tests/Pail.falderal
0 -> encoding: UTF-8
1
2 Test Suite for Pail
3 ===================
4
5 This test suite is written in the format of Falderal 0.5. It is far from
6 exhaustive, but provides a basic sanity check that the language I've designed
7 here comes close to what I had in mind.
8
9 Pail Tests
10 ----------
11
12 -> Tests for Haskell function Pail:runPail
13
14 A symbol reduces to that symbol.
15
16 | fst
17 = fst
18
19 | plains-of-leng?
20 = plains-of-leng?
21
22 A symbol must begin with a letter and contain only letters, digits,
23 hyphens, and question marks.
24
25 | ^hey
26 = %(line 1, column 1):
27 = unexpected "^"
28 = expecting white space, "*", "#", "[" or letter
29
30 A pair reduces to that pair.
31
32 | [a b]
33 = [a b]
34
35 | [fst [a b]]
36 = [fst [a b]]
37
38 | [*fst [a b]]
39 = [*fst [a b]]
40
41 Square brackets must be properly matched.
42
43 | [a b
44 = %(line 1, column 5):
45 = unexpected end of input
46 = expecting letter or digit, "-", "?", "_", white space or "]"
47
48 Evaluation of a symbol reduces to that to which it is bound.
49
50 | *fst
51 = <fst>
52
53 Evaluation of a pair recursively reduces its contents.
54
55 | *[*fst [a b]]
56 = [<fst> [a b]]
57
58 | *[*fst *snd]
59 = [<fst> <snd>]
60
61 | *[*fst *[*snd *fst]]
62 = [<fst> [<snd> <fst>]]
63
64 Evaluation of a pair w/a fun on the lhs applies the fun.
65
66 | **[*fst [a b]]
67 = a
68
69 | **[*snd [a b]]
70 = b
71
72 Reducing an evaluation of a pair can accomplish a cons.
73
74 | *[**[*fst [a b]] **[*snd [c d]]]
75 = [a d]
76
77 Reducing on the lhs of a pair can obtain a fun to apply.
78
79 | **[**[*fst [*snd *fst]] [a b]]
80 = b
81
82 Applying uneval reduces to an evaluation.
83
84 | **[*uneval hello]
85 = *hello
86
87 The form `#x` is syntactic sugar for `**[*uneval x]`.
88
89 | #hello
90 = *hello
91
92 Syntactic sugar is expanded at parse time.
93
94 | [#fst [a b]]
95 = [**[*uneval fst] [a b]]
96
97 It is possible to uneval a fun.
98
99 | #*fst
100 = *<fst>
101
102 Reduction of an uneval'ed symbol can be used to obtain an eval'ed symbol.
103
104 | *[#fst [a b]]
105 = [*fst [a b]]
106
107 Reduction of uneval'ed symbol can be used to obtain a fun.
108
109 | **[#fst [a b]]
110 = [<fst> [a b]]
111
112 Reduction of uneval'ed symbol can be used to apply the obtained fun.
113
114 | ***[#fst [a b]]
115 = a
116
117 Positive test of `if-equal?` on symbols.
118
119 | **[*if-equal? [[a a] [one two]]]
120 = one
121
122 Negative test of `if-equal?` on symbols.
123
124 | **[*if-equal? [[a b] [one two]]]
125 = two
126
127 Negative test of `if-equal?` on evals.
128
129 | ***[*if-equal? [[*a *b] [fst snd]]]
130 = <snd>
131
132 Let can bind a symbol to a symbol.
133
134 | **[*let [[a b] *a]]
135 = b
136
137 Let can bind a symbol to a pair.
138
139 | **[*let [[g [x y]] **[*snd *g]]]
140 = y
141
142 Let can bind a symbol to an expression containing an uneval,
143 which can at a later point be eval'ed and reduced.
144
145 | **[*let [
146 | [sndg *[**[*uneval snd] **[*uneval g]]]
147 | **[*let [
148 | [g [x y]]
149 | ***sndg
150 | ]]
151 | ]]
152 = y
153
154 | **[*let [
155 | [cadrg *[#fst ##*[#snd #g]]]
156 | **[*let [
157 | [g [x [y z]]]
158 | ***cadrg
159 | ]]
160 | ]]
161 = y
162
163 Let can bind uneval'ed expression; prior bindings are honoured.
164
165 | **[*let [
166 | [g moo]
167 | **[*let [
168 | [consnull *[#g null]]
169 | ***consnull
170 | ]]
171 | ]]
172 = [moo null]
173
174 Let can bind uneval'ed expression; prior bindings are shadowed.
175
176 | **[*let [
177 | [g moo]
178 | **[*let [
179 | [consnull *[#g null]]
180 | **[*let [
181 | [g k]
182 | ***consnull
183 | ]]
184 | ]]
185 | ]]
186 = [k null]