Sep | OCT | APR
| 6 |
2007 | 2008 | 2009

2 captures 6 Oct 08 - 30 Apr 09 |

Close Help

# sjs

## geeky ramblings

## ElSchemo: Boolean logic and branching

Posted by sjs
on Thursday, August 02

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

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

    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 `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.

    1
    2

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

### lispCond

Again, `lispCond` has the same type as `eval`.

    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 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`.

    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.

## 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.

Continue reading...

- Tags: elschemo haskell scheme
- Meta: permalink

##### Comments

Leave a response