How to implement a macro system in my LISP

Question

I am writing my own LISP based on Write Yourself Scheme in 48 hours. (The code is here .) As a final exercise, I want to implement macros. How can this be done, given that I present expressions as a list of immutable data types. Is it possible to do this simply in LISP, or do I need 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
• Computes expressions and replaces them with a single expression
• Return this expression and print it

Expressions are presented in Haskell as follows:

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 do not evaluate their arguments, but are instead converted to an expression by "placing" the arguments inside the form. Returns a valid expression that can be evaluated or returned as a quoted list. I thought about this, having a special rating function that only evaluates characters in the form of macros. How this can be achieved, although there is something that I understand the problems. The correct solution seems to be that I should “just” change the form by replacing the characters inside it with arguments, but this is not possible due to the immutability of Haskell.

So, Clojure seems to have implemented macros in LISP. I cannot interpret the Clojure solution, but if it can be done, it seems a little easier than doing it in Haskell. I have no idea what macroexpand1 (which calls the macro call) does, does it call any function from the Clojure implementation? If so, then I still need 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 want to implement a macro system, then I could probably remove the evaluation part of the arguments, then bind the macro parameters to my arguments and have a special eval that evaluates only each character in the form, returning a new form in which the arguments are placed inside it . This is something that I cannot implement, but I'm not even sure that the logic is correct.

I understand that this question is quite broad and it may be easier to ask "How to implement a macro system in my LISP implementation written in Haskell

Answer 1

No, macros cannot be implemented in Lisp itself, which all points to them. You have a macro exposure of each macro in accordance with its definition as part of the loading / compilation / processing of this expression.

You will need to change the implementation of eval to call macros on unvalued arguments and return the results back to eval (not apply , for example, to process an application with a normal function). As suggested by sepp2k in the comments, you present your macros as Func... expressions, but keep them in a separate environment where only macros are stored.

see also: Lazy Evaluation vs Macros

Answer 2

You can try to read the interpreter implementations in the "Structure and Implementation of Computer Programs" section. The eval function that you explicitly show only works for the default evaluation rule, and not for the book invoking special forms.

The normal Lisp eval function looks something 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 do not need a special version of apply . Just call regular apply without evaluating the arguments, and then the eval expression returned by apply .