> module Language.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 ``, 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