+> -- Pail.lhs -- reference implementation of the Pail programming language
+> -- Copyright (c)2011 Cat's Eye Technologies. All rights reserved.
+> -- Redistribution and use in source and binary forms, with or without
+> -- modification, are permitted provided that the following conditions
+> -- 1. Redistributions of source code must retain the above copyright
+> -- notices, this list of conditions and the following disclaimer.
+> -- 2. Redistributions in binary form must reproduce the above copyright
+> -- notices, this list of conditions, and the following disclaimer in
+> -- the documentation and/or other materials provided with the
+> -- 3. Neither the names of the copyright holders nor the names of their
+> -- contributors may be used to endorse or promote products derived
+> -- from this software without specific prior written permission.
+> -- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+> -- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+> -- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+> -- FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+> -- COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+> -- INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+> -- BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+> -- LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+> -- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+> -- LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+> -- ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+> -- POSSIBILITY OF SUCH DAMAGE.
+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
+(If you don't know anything about Pixley, just know that it's a tiny subset
+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
+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:
+...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:
+On the other hand, when Pail sees:
+It evaluates to exactly that,
+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:
+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
+(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.
+> import Text.ParserCombinators.Parsec
+> import qualified Data.Map as Map
+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.
+If a is an expression, then the evaluation of a is an expression.
+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 (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
+> (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
+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.
+> cs <- many (alphaNum <|> char '-' <|> char '?' <|> char '_')
+> return (Symbol (c:cs))
+A pair of expressions a and b is denoted
+An evaluation of an expression a is denoted
+As a bit of syntactic sugar, the denotation
+for some expression a is equivalent to the denotation
+> 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.
+> r <- (eval <|> uneval <|> pair <|> symbol)
+A convenience function for parsing Pail programs.
+> parsePail program = parse expr "" program
+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.
+An evaluation of some expression x o-reduces to the i-reduction of its
+> oReduce env (Eval x) = iReduce env x
+Everything else o-reduces to itself.
+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)
+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` to a pair (resp. `snd`) 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) =
+> (Symbol sym) = oReduce env name
+> val = oReduce env binding
+> env' = Map.insert sym val env
+And finally, we define the standard environment by associating each of the
+above defined functions with a symbol.
+> stdEnv = Map.fromList (map (\(name, fun) -> (name, (Fn name fun)))
+> ("if-equal?", pIfEqual),
+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.
+> case (parse expr "" line) of
+> Left err -> "%" ++ (show err)
+> Right x -> show (oReduce stdEnv x)