samhuri.net

I’ve been developing a Scheme interpreter in Haskell called ElSchemo. It started from Jonathan’s excellent Haskell tutorial which I followed in order to learn both Haskell and Scheme. Basically that means the code here is for me to get some feedback as much as to show others how to do this kind of stuff. This may not be too interesting if you haven’t at least browsed the tutorial.

I’m going to cover 3 new special forms: and, or, and cond. I promised to cover the let family of special forms this time around but methinks this is long enough as it is. My sincere apologies if you’ve been waiting for those.

Short-circuiting Boolean logic

Two functions from the tutorial which may irk you immediately are and and or, defined in Scheme in the given standard library. If your code is free of side-effects then it may not bother you so much. It bothered me. The problem with the implementation in stdlib.scm is that all the arguments are evaluated before control enters the function. Besides being inefficient by doing unnecessary work, if any of the arguments have side-effects you can make use of short-circuiting by using and to sequence actions, bailing out if any fail (by returning nil), and using or to define a set of alternative actions which will bail out when the first in the list succeeds (by returning anything but nil). Had we macros then we could implement them as macros. We don’t, so we’ll write them as special forms in Haskell.

Unlike the special forms defined in the tutorial I’m going to implement these as separate functions for clarity, rather than lump them all in eval. However, they will be invoked directly from eval so their type is easy; it’s the same as eval’s.

Code first, ask questions later. Haskell is a pretty clear and concise language. My explanations may be redundant because of this.

lispAnd

lispAnd :: Env -> [LispVal] -> IOThrowsError LispVal
lispAnd env [] = return $ Bool True
lispAnd env [pred] = eval env pred
lispAnd env (pred:rest) = do
    result <- eval env pred
    case result of
      Bool False -> return result
      _ -> lispAnd env rest

Starting with the trivial case, and returns #t with zero arguments.

With one argument, a single predicate, simply evaluate and return that argument.

Given a list of predicates, evaluate the first and inspect its value. If the argument evaluated to #f then our work is done and we return #f, otherwise we keep plugging along by making a recursive call with the first argument stripped off. Eventually we will reach our base case with only one predicate.

It’s possible to eliminate the case of one predicate. I think that just complicates things but it’s a viable solution.

lispOr

Predictably this is quite similar to lispAnd.

lispOr :: Env -> [LispVal] -> IOThrowsError LispVal
lispOr env [] = return $ Bool False
lispOr env [pred] = eval env pred
lispOr env (pred:rest) = do
    result <- eval env pred
    case result of
        Bool False -> lispOr env rest
        _ -> return result

With no arguments lispOr returns #f, and with one argument it evaluates and returns the result.

With 2 or more arguments the first is evaluated, but this time if the result is #f then we continue looking for a truthy value. If the result is anything else at all then it’s returned and we are done.

A new branching construct

First let me define a convenience function that I have added to ElSchemo. It maps a list of expressions to their values by evaluating each one in the given environment.

evalExprs :: Env -> [LispVal] -> IOThrowsError [LispVal]
evalExprs env exprs = mapM (eval env) exprs

lispCond

Again, lispCond has the same type as eval.

lispCond :: Env -> [LispVal] -> IOThrowsError LispVal
lispCond env (List (pred:conseq) : rest) = do
    result <- eval env pred
    case result of
        Bool False -> if null rest then return result else lispCond env rest
        _ -> liftM last $ evalExprs env conseq

Unlike Lisp – which uses a predicate of T (true) – Scheme uses a predicate of else to trigger the default branch. When the pattern matching on Atom "else" succeeds, we evaluate the default expressions and return the value of the last one. This is one possible base case. Atom "else" could be defined to evaluate to #t, but we don’t want else to be evaluated as #t anywhere except in a cond so I have chosen this solution.

If the first predicate is not else then we evaluate it and check the resulting value. If we get #f then we look at the rest of the statement, if it’s empty then we return #f, otherwise we recurse on the rest of the parameters. If the predicate evaluates to a truthy value – that is, anything but #f – then we evaluate the consequent expressions and return the value of the last one.

Plumbing

Now all that’s left is to hook up the new functions in eval.

eval env (List (Atom "and" : params)) = lispAnd env params
eval env (List (Atom "or" : params)) = lispOr env params
eval env (List (Atom "cond" : params)) = lispCond env params

You could, of course, throw the entire definitions in eval itself but eval is big enough for me as it is. YMMV.

Done!

So, that’s a wrap. It only took 20 lines of code for the 3 new special forms, and it could easily be done with less code. Next time I will show you how to implement the various let functions. Really!

Do you like me describing ElSchemo piece by piece as I have been? I plan on posting the Haskell code and my stdlib.scm in their entirety sometime, and I could do that before or after I finish writing about the features I’ve developed beyond the tutorial. Just let me know in the comments.