How to implement a macro system into my LISP

Question

I'm writing my own LISP based on Write Yourself a Scheme in 48 hours. (The code is here.) As a last exercise I want to implement macros. How can this be done considering that I represent expressions as a list of immutable datatypes. Can this be done simply in LISP itself or do I have to implement some function in Haskell?

My current implementation is written in Haskell and pretty much works like this:

• Parse input and turn it into a list of expressions
• Evaluates the expressions and substitute it tills it's a single expression
• Return that expression and print it

The expressions is represented in Haskell like this:

data Expr
  = Sym String
  | List [Expr]
  | Num Int
  | Str String
  | Bool Bool
  | Func Env [String] Expr
  | Prim ([Expr] -> ErrorOr Expr)
  | Action ([Expr] -> IOErrorOr Expr)

Okey, now to the real problem. Macros doesn't evaluates its arguments but instead transforms into an expression by "placing" the arguments inside the form. Returning valid expression that may be evaluated or returned as a quoted list. I was thinking of implementing this by having a special evaluation function which only evaluates the symbols in the macros' form. How this could be achieved though is something I have problem understanding. The proper solution feels like I should "simply" modify the form by replacing the symbols inside it with the arguments, but that's not possible due to Haskell's immutability.

So, Clojure seems to have implemented macros in Lisp itself though. I can't interpret Clojure's solution but if this can be done it feels like being a bit easier than doing it in Haskell. I have no idea what macroexpand1(which macroexpand call) do, does it call some function from within Clojure's implementation? If so, then I still have to implement it inside Haskell.

If we look at how functions are evaluated:

eval env (List (op:args)) = do
  func <- eval env op
  args <- mapM (eval env) args
  apply func args

apply :: Expr -> [Expr] -> IOErrorOr Expr
apply (Prim func) args = liftToIO $ func args
apply (Action func) args = func args
apply (Func env params form) args =
  case length params == length args of
    True -> (liftIO $ bind env $ zip params args)
        >>= flip eval form
    False -> throwError . NumArgs . toInteger $ length params
apply _ _ = error "apply"

So, if I wanna implement a macro system, then I could probably remove the evaluation part of the arguments, then bind the macros parameters to its arguments, and have a special eval which only evaluates every symbol in the form, returning a new form that has the arguments put inside it instead. This is what I can't implement though, and I'm not even sure the logic is correct.

I understand this question is quite wide and could probably be more simply asked with "How do I implement a macro system in my LISP implementation written in Haskell

Answer 1

No, macros can not be implemented in Lisp itself, that's the whole point to them. You have to macroexpand each macro call according to its definition, as part of loading/compiling/processing a given expression.

You would have to alter your eval implementation to call macros on unevaluated arguments, and feed the results back into eval (not apply, like processing the normal function application would). As suggested by sepp2k in the comments, you'd represent your macros as Func... expressions, but hold them in a separate environment, where only macros are stored.

see also: Lazy Evaluation vs Macros

Answer 2

You might try reading the interpreter implementations in Structure and Implementation of Computer Programs. The eval function that you show clearly only works for the default evaluation rule, and not for what the book calls special forms.

A normal Lisp eval function looks more like this:

eval env expr@(List _)
    | isSpecialForm env expr = evalSpecial env expr
    | otherwise = evalApplication env expr

evalApplication env (op:args) = do
  func <- eval env op
  args <- mapM (eval env) args
  apply func args

evalSpecial env expr@(List (op:args))
    | isMacro env op = eval env (macroExpand env expr)
    | otherwise = case op of
                    "lambda" -> ...
                    "if" -> ...
                    -- etc.

Answer 3

You don't need a special version of apply. Just call the regular apply without evaluating the arguments and then eval the expression returned by apply.