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:
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
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
and to sequence actions, bailing out if any fail (by returning
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
Code first, ask questions later. Haskell is a pretty clear and concise language. My explanations may be redundant because of this.
1 2 3 4 5 6 7 8
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,
#t with zero
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.
Predictably this is quite similar to
1 2 3 4 5 6 7 8
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
#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
#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 has the same type as
1 2 3 4 5 6
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
else to trigger the default branch. When the pattern
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
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.
Now all that’s left is to hook up the new functions in
1 2 3
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.
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.