## Pail.lhs @develop-2019-1 — raw · history · blame

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 | ```
> module Pail where
Pail
====
Pail is a programming language based on pairs; just as Lisp stands for
*LIS*t *P*rocessing, Pail stands for *PAI*r *L*anguage.
Pail's original working title was "Bizaaro[sic]-Pixley", as it resembles
Pixley in many ways, but everything's all changed around and made wicked
funny, man.
(If you don't know anything about Pixley, just know that it's a tiny subset
of Scheme.)
The first way in which Pail is "Bizaaro" is that while Pixley structures are
expressed solely with lists (proper ones, too,) Pail structures are expressed
solely with pairs. So where Pixley has `car` and `cdr`, Pail has `fst` and
`snd`.
The second and more significant way is that while Pixley, like Scheme
and Lisp, is "evaluate-first-quote-only-when-asked", Pail is "quote-first-
evaluate-only-when-asked". What this means is, when Pixley sees:
(+ 1 2)
...it evaluates `+` to get a function (addition), `1` to get the number one,
`2` to get the number two, then applies the function to the arguments to
arrive at the result (the number three.) If you wanted to arrive at the
result `(+ 1 2)`, you would have to say:
(quote (+ 1 2))
On the other hand, when Pail sees:
[add [1 2]]
It evaluates to exactly that,
[add [1 2]]
In order to get Pail to look at that structure as an expression and evaluate
it, you need to wrap it in an evaluation. Each kind of term is evaluated
slightly differently (symbols evaluate to what they're bound to, pairs
recursively evaluate their contents, etc.), so to get Pail to evaluate that
term like Pixley would do straight off, you would have to say:
*[*add [1 2]]
If the 1 and 2 weren't literal integers, but rather bound variables, you
would need even more asterisks in there.
A third and fairly minor way is related to how bindings are created.
Noting that Haskell lets you say awesome things like
let 2 + 2 = 5 in 2 + 2
and
let in 5
(the latter apparently being in emulation of Scheme's allowing an empty
list of bindings, i.e. `(let () 5)`), it struck the author that, in order
for this senselessness to be total, you ought also to be able to say
let let a = b in a = 5 in b
Alas, Haskell does not allow this. Pail, however, does.
I don't actually know how to do recursion in Pail yet; I think you can,
somehow, by using `let`s and evaluations and `uneval`, but I haven't actually
constructed the equivalent of a recursive function with that. So it might
be the case that in some future version, a lambda form (or, hopefully,
something even more interesting) will be added.
In this respect, and in the "`let let a = b`" circumstance, Pail echoes an
earlier attempt of mine to create a reflective rewriting language called Rho.
I didn't ever really figure out how to program in Rho, and I really haven't
figured out how to program in Pail. But maybe someone else will, and maybe
that will shed some more light on Rho.
What follows is `Pail.lhs`, the reference implementation of the Pail
programming language.
> import Text.ParserCombinators.Parsec
> import qualified Data.Map as Map
Definitions
===========
An environment maps names (represented as strings) to expressions.
> type Env = Map.Map String Expr
A symbol is an expression.
> data Expr = Symbol String
If a and b are expressions, then a pair of a and b is an expression.
> | Pair Expr Expr
If a is an expression, then the evaluation of a is an expression.
> | Eval Expr
If f is a function that takes an environment and an expression
to an expression, then f is an expression. f may optionally
be associated with a name (represented as a string) for to make
depiction of expressions more convenient, but there is no language-
level association between the function and its name.
> | Fn String (Env -> Expr -> Expr)
Nothing else is an expression.
See below for how expressions are denoted. We will mention only here
that functions cannot strictly speaking be denoted directly, but for
convenience, functions with known names can be represented by `<foo>`,
where `foo` is the name of the function.
> instance Show Expr where
> show (Symbol s) = s
> show (Pair a b) = "[" ++ (show a) ++ " " ++ (show b) ++ "]"
> show (Eval x) = "*" ++ (show x)
> show (Fn n _) = "<" ++ n ++ ">"
> instance Eq Expr where
Two symbols are equal if the strings by which they are represented
are equal.
> (Symbol s) == (Symbol t) = s == t
Two pairs are equal if their contents are pairwise equal.
> (Pair a1 b1) == (Pair a2 b2) = (a1 == a2) && (b1 == b2)
Two evaluations are equal if their contents are equal.
> (Eval x) == (Eval y) = x == y
Two functions are never considered equal.
> (Fn n _) == (Fn m _) = False
Parser
======
The overall grammar of the language is:
Expr ::= symbol | "[" Expr Expr "]" | "*" Expr | "#" Expr
A symbol is denoted by a string which may contain only alphanumeric
characters, hyphens, underscores, and question marks.
> symbol = do
> c <- letter
> cs <- many (alphaNum <|> char '-' <|> char '?' <|> char '_')
> return (Symbol (c:cs))
A pair of expressions a and b is denoted
[a b]
> pair = do
> string "["
> a <- expr
> b <- expr
> spaces
> string "]"
> return (Pair a b)
An evaluation of an expression a is denoted
*a
> eval = do
> string "*"
> a <- expr
> return (Eval a)
As a bit of syntactic sugar, the denotation
#a
for some expression a is equivalent to the denotation
**[*uneval a]
> uneval = do
> string "#"
> a <- expr
> return (Eval (Eval (Pair (Eval (Symbol "uneval")) a)))
The top-level parsing function implements the overall grammar given above.
Note that we need to give the type of this parser here -- otherwise the
type inferencer freaks out for some reason.
> expr :: Parser Expr
> expr = do
> spaces
> r <- (eval <|> uneval <|> pair <|> symbol)
> return r
A convenience function for parsing Pail programs.
> parsePail program = parse expr "" program
Evaluator
=========
We evaluate a Pail expression by reducing it. (We use this terminology
to try to limit confusion, since "an evaluation of" is already part of our
definition of Pail expressions.)
There are two kinds of reductions in Pail: outer ("o-") reductions and inner
("i-") reductions. So, to be more specific, we evaluate a Pail expression
by o-reducing it. Outer reductions may involve inner reductions, which may
themselves involve further outer reductions.
Outer Reduction
---------------
An evaluation of an expression o-reduces to the i-reduction of its contents.
> oReduce env (Eval x) = iReduce env x
Everything else o-reduces to itself.
> oReduce env x = x
Inner Reduction
---------------
A symbol i-reduces to the expression to which is it bound in the current
environment. If it is not bound to anything, it i-reduces to itself.
> iReduce env (Symbol s) = Map.findWithDefault (Symbol s) s env
A pair where the LHS is a function i-reduces to the application of that
function to the RHS of the pair, in the current function.
> iReduce env (Pair (Fn _ f) b) = f env b
Any other pair i-reduces to a pair with pairwise o-reduced contents.
> iReduce env (Pair a b) = Pair (oReduce env a) (oReduce env b)
The inner reduction of an evaluation of some expression x is the i-reduction
of x, i-reduced one more time.
> iReduce env (Eval x) = iReduce env (iReduce env x)
Standard Environment
====================
Applying any of these functions to any type of argument which is not
defined here (for example, applying `fst` to a non-pair) is an error;
evaluation terminates immediately with an error term or message.
Again, to try to limit confusion (I must not say "reduce confusion" or
things will get even worse), we use the terminology that a function
"returns" a value here, rather than "reducing" or "evaluating" to one.
Applying `fst` (resp. `snd`) to a pair returns the o-reduction of the
first (resp. second) element of that pair.
> pFst env (Pair a _) = oReduce env a
> pSnd env (Pair _ b) = oReduce env b
Applying `ifequal` to a pair of pairs proceeds as follows. The contents
of the first pair are compared for (deep) equality. If they are equal,
the o-reduction of the first element of the second pair is returned; if not,
the o-reduction of the second element of the second pair is returned.
> pIfEqual env (Pair (Pair a b) (Pair yes no))
> | a == b = oReduce env yes
> | otherwise = oReduce env no
Applying `typeof` to a value of any kind returns a symbol describing
the type of that value. For symbol, `symbol` is returned; for pairs,
`pair`; for evaluations, `eval`; and for functions, `function`.
> pTypeOf env (Symbol _) = Symbol "symbol"
> pTypeOf env (Pair _ _) = Symbol "pair"
> pTypeOf env (Eval _) = Symbol "eval"
> pTypeOf env (Fn _ _) = Symbol "function"
Applying `uneval` to an expression returns the evaluation of that
expression. (Note that nothing is reduced in this process.)
> pUnEval env x = Eval x
Applying `let` to a pair of a pair (called the "binder") and an expression
returns the o-reduction of that expression in a new environment, constructed
as follows. The first element of the binder is o-reduced to obtain a symbol;
the second element of the binder is o-reduced to obtain a value of any type.
A new environment is created; it is just like the current evironment except
with the obtained symbol bound to the obtained value.
> pLet env (Pair (Pair name binding) expr) =
> let
> (Symbol sym) = oReduce env name
> val = oReduce env binding
> env' = Map.insert sym val env
> in
> oReduce env' expr
And finally, we define the standard environment by associating each of the
above defined functions with a symbol.
> stdEnv :: Env
> stdEnv = Map.fromList $ map (\(name, fun) -> (name, (Fn name fun)))
> [
> ("fst", pFst),
> ("snd", pSnd),
> ("if-equal?", pIfEqual),
> ("type-of", pTypeOf),
> ("uneval", pUnEval),
> ("let", pLet)
> ]
Top-Level Driver
================
Note that if this driver is given text which it cannot parse, it will
evaluate to a string which contains the parse error message and always
begins with '%'. No Pail expression can begin with this character, so
parse errors can be detected unambiguously.
> runPail line =
> case (parse expr "" line) of
> Left err -> "%" ++ (show err)
> Right x -> show (oReduce stdEnv x)
Happy bailing!
Chris Pressey
Evanston, Illinois
May 27, 2011
``` |