How to implement a Lisp macro system?

Question

I've implemented my own Lisp on top of node.js, I can run s-expressions like this:

(assert (= 3 (+ 1 2)))

(def even? (fn [n] (= 0 (bit-and n 1))))

(assert (even? 4))
(assert (= false (even? 5)))

Now I would like to add macros - the defmacro function - but this is where I'm stuck. I'm wondering how macro systems are implemented in other Lisps but I couldn't find many pointers (apart from this and this).

I've looked at the Clojure macro system - the Lisp I'm most familiar with - but that seemed too complicated and I couldn't find additional clues that I can readily apply (Clojure macros ultimately compile to byte code which doesn't apply to javascript, also I couldn't make sense of the macroexpand1 function.)

So my question is: given a Lisp implementation without macros but with an AST, how does one add a macro system like Clojure's macro system? Can this macro system be implemented in Lisp, or does it require extra features in the implementation in the host language?

One additional remark: I haven't implemented quote (') yet because I couldn't figure out what kind of values should be in the returned list. Should it contain AST elements or objects like Symbol and Keyword (the latter being the case for Clojure)?

Answer 1

All a macro does is take unevaluated forms as parameters and perform replacement on its body. The trick to implementation a macro system is to tell your compiler to be lazy.

Put in another way, when the compiler encounters a function, it first evaluates its formal parameter list, yields the results and passes them to the function. When the compiler finds a macro, it passes the arguments unevaluated to the body, then performs any computation the body requests, and finally replaces itself with the result of those.

For instance, lets say you have a function:

(defun print-3-f (x) (progn (princ x) (princ x) (princ x)))

and a macro:

(defmacro print-3-m (x) `(progn (princ ,x) (princ ,x) (princ ,x)))

Then you can see the difference straight away:

CL-USER> (print-3-f (rand))
* 234
* 234
* 234

CL-USER> (print-3-m (rand))
* 24
* 642
* 85

To understand why this is, you need to, in a manner of speaking, run the compiler in your head.

When Lisp comes across the function, it builds a tree in which (rand) is first evaluated and the result passed to the function, which prints said result three times.

On the other hand, when Lisp comes across the macro, it passes the form (rand) untouched to the body, which returns a quoted list where x is replaced by (rand), yielding:

(progn (princ (rand)) (princ (rand)) (princ (rand)))

and replacing the macro call for this new form.

Here you will find vast amounts of documentation regarding macros in a variety of languages, including Lisp.

Answer 2

This is from Peter Norvig's Paradigms of Artificial Intelligence Programming - an essential tome for any LISP programmers bookshelf.

He assumes you're implementing an Interpreted language, and provides the example of a Scheme Interpreter running in LISP.

The following two examples here show how he adds macros to the primary eval function (interp)

Here is the function for interpreting an S-expression prior to dealing with macros:

(defun interp (x &optional env)
  "Interpret (evaluate) the expression x in the environment env."
  (cond
    ((symbolp x) (get-var x env))
    ((atom x) x)
    ((case (first x)
       (QUOTE  (second x))
       (BEGIN  (last1 (mapcar #'(lambda (y) (interp y env))
                              (rest x))))
       (SET!   (set-var! (second x) (interp (third x) env) env))
       (IF     (if (interp (second x) env)
                   (interp (third x) env)
                   (interp (fourth x) env)))
       (LAMBDA (let ((parms (second x))
                     (code (maybe-add 'begin (rest2 x))))
                 #'(lambda (&rest args)
                     (interp code (extend-env parms args env)))))
       (t      ;; a procedure application
               (apply (interp (first x) env)
                      (mapcar #'(lambda (v) (interp v env))
                              (rest x))))))))

And here it is after a macro evaluation has been added (child methods have been in the reference link for clarity

(defun interp (x &optional env)
  "Interpret (evaluate) the expression x in the environment env.
  This version handles macros."
  (cond
    ((symbolp x) (get-var x env))
    ((atom x) x)

    ((scheme-macro (first x))              
     (interp (scheme-macro-expand x) env)) 

    ((case (first x)
       (QUOTE  (second x))
       (BEGIN  (last1 (mapcar #'(lambda (y) (interp y env))
                              (rest x))))
       (SET!   (set-var! (second x) (interp (third x) env) env))
       (IF     (if (interp (second x) env)
                   (interp (third x) env)
                   (interp (fourth x) env)))
       (LAMBDA (let ((parms (second x))
                     (code (maybe-add 'begin (rest2 x))))
                 #'(lambda (&rest args)
                     (interp code (extend-env parms args env)))))
       (t      ;; a procedure application
               (apply (interp (first x) env)
                      (mapcar #'(lambda (v) (interp v env))
                              (rest x))))))))

It is interesting to note that the opening Chapter of Christian Queinnec's Lisp In Small Pieces has a very similar function, he calls it eval.