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