Initial import of Pail version 1.0 revision 2011.1214 sources.
catseye
9 years ago

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