Merge pull request #2 from catseye/develop-2019-2
Develop 2019 2
Chris Pressey authored 3 years ago
GitHub committed 3 years ago

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/ |

3 | 3 | DIR=`dirname $THIS` |

4 | 4 | NAME=`basename $THIS` |

5 | 5 | 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 | |

7 | 9 | exec $DIR/$NAME.exe $* |

8 | 10 | elif command -v runhaskell 2>&1 >/dev/null ; then |

9 | 11 | exec runhaskell -i$SRC $SRC/Main.hs $* |

0 | 0 | #!/bin/sh |

1 | 1 | |

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 {} \; |

0 | 0 | module Main where |

1 | 1 | |

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)) | |

5 | 4 | |

6 | import Pail | |

5 | import Language.Pail (runPail) | |

6 | ||

7 | 7 | |

8 | 8 | main = withElems ["prog", "result", "run-button"] driver |

9 | 9 | |

10 | escapeHTML "" = "" | |

11 | escapeHTML ('<' : rest) = "<" ++ escapeHTML rest | |

12 | escapeHTML ('>' : rest) = ">" ++ escapeHTML rest | |

13 | escapeHTML ('&' : rest) = "&" ++ 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 |

0 | Pail.lhs⏎ |

0 | 0 | module Main where |

1 | 1 | |

2 | 2 | import System.Environment |

3 | import Pail | |

3 | import System.Exit | |

4 | import System.IO | |

5 | ||

6 | import Language.Pail (runPail) | |

7 | ||

4 | 8 | |

5 | 9 | 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 | > 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 |

0 | 0 | #!/bin/sh |

1 | 1 | |

2 | 2 | APPLIANCES="tests/appliances/pail.md" |

3 | falderal $APPLIANCES tests/Pail.markdown | |

3 | falderal $APPLIANCES tests/Pail.md |

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] |