On Implementing a Lisp

Question

Background:
This began with James Colgan's Lisp-Dojo for Ruby. My implementation can be found here. I then moved on to Write yourself a scheme in 48 hours. This question has to do with one of the implementation decisions.

Code:

My implementation of eval

--# The eval function takes a scope and paresed Lisp value and
--# returns the resulting Lisp Value.
--# String, Number and Bool return themselves.
--# An Atom trys to find its self in the scope and retrun that value
--# A List is evaluated using the normal Lisp rules.
eval :: LispScope-> LispVal -> IOThrowsError LispVal
eval s val@(String _) = return val
eval s (Atom val) = do
 (liftIO $ getValue s val) >>= maybe (throwError $ "Value not in scope: " ++ val) (return)
eval s val@(Number _) = return val
eval s val@(Bool _) = return val
eval scope (List (fn:lvs)) = do
 fun <- eval scope fn
 case fun of 
 Syntax f _-> f scope lvs
 Function f _-> evalMap scope lvs >>= f
 val -> throwError $ (show val) ++ " is not a function"
eval scope (List []) = return $ List []
eval _ badForm = throwError $ "Unrecognized form: " ++ show badForm

Note two things: 1) I do not refer to any special forms, 2) the use of Syntax for hygenic forms.

This is a piece of code from Write yourself a scheme in 48 hours:

--# evaluate the "if" form
eval (List [Atom "if", pred, conseq, alt]) = 
 do result <- eval pred
 case result of
 Bool False -> eval alt
 otherwise -> eval conseq

Note that in the tutorial the form is written directly into the eval function. This pattern is followed for other syntaxes like define and lambda.

Question: When I implemented my version I followed what I thought was a wise choice demonstrated in James Colgan's solution to the lisp-dojo to keep eval as simple as possible and instead to push the syntax implementations into the root scope. eg:

ifSyntax :: LispScope -> [LispVal] -> IOThrowsError LispVal
ifSyntax s [pred, consequent, alternate] = do
 pred' <- eval s pred
 case pred' of 
 Bool False -> eval s alternate
 otherwise -> eval s consequent
ifSyntax _ _ = throwError "if: Bad Syntax"
ifVal = (Syntax ifSyntax $ Left "syntax (if)")
--# this is then added to the initial scope

I would like to know why one choice might be better then the other, and what is typical in real-world implementations.

Reference:

My definition of the LispVal data type:

type LispScope = Scope LispVal
data Lambda = Lambda {params :: [String], body :: [LispVal]}
data LispVal = Atom String
 | List [LispVal]
 | Number Integer
 | Real Double
 | String String
 | Function ([LispVal] -> IOThrowsError LispVal) (Either String Lambda)
 | Syntax (LispScope -> [LispVal] -> IOThrowsError LispVal) (Either String Lambda)
 | Bool Bool
 | Port Handle

Answer 1

When I went through the WYAS48 I made the same decision of breaking the bits of eval off into smaller functions. I found this made testing easier since I could focus on just one function at a time.

I find that having a function be one massive bunch of logic is not helpful. In an imperative language the equivalent would be a single function with a ton of if/else or case/switch logic. Whenever I see that I tend to break things off into more manageable functions.

The issue that tends to happen is the little functions need some kind of state from the original big function. Finding this out and resolving it can be difficult at times and others just plain messy. The code is often better for it in the end.

• Mathieu Guindon: Congratulations! You are officially a zombie killer! Well done!