How to implement the Lisp macrosystem?

Question

I implemented my own Lisp on top of node.js, I can run s-expressions as follows:

 (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 am stuck. I am wondering how the macro systems are implemented in other Lisps, but I could not find many pointers (except this and this ).

I looked at the Clojure macro system - Lisp, which I am most familiar with - but it seemed too complicated, and I could not find additional hints that I could easily apply (the Clojure macro will ultimately compile into byte code that does not apply to javascript , also I could not understand the function macroexpand1 .)

So, my question is: when implementing Lisp without macros, but with AST, how to add a macro system like Clojure macro system? Can this macro system be implemented in Lisp, or are additional features required in the implementation in the host language?

One more note: I have not implemented quote ( ' ) yet, because I could not understand what values ​​should be in the returned list. Should they contain AST elements or objects, such as Symbol and Keyword (the latter refers to Clojure)?

Answer 1

All macros take raw forms as parameters and perform a replacement on their body. The trick of implementing a macro system is to tell your lazy compiler.

To put in another way, when the compiler encounters a function, it first evaluates its list of formal parameters, gives the results and passes them to the function. When the compiler finds a macro, it passes arguments that have no analogues in the body, then performs any calculations that the body asks for, and finally replaces the result.

For example, let's say you have a function:

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

and macro:

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

Then you can immediately see the difference:

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

To understand why this is so, you need, as it were, to run the compiler in your head.

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

On the other hand, when Lisp gets into the macro, it passes the (rand) form intact to the body, which returns a list with quotes, where x is replaced by (rand) , giving:

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

and replace the macro call for this new form.

Here you will find a wealth of documentation on macros in various languages, including Lisp.

Answer 2

This is from Peter Norwig Artificial Intelligence Programming Paradigms - an important issue for any bookshelf of LISP programmers.

It assumes that you are implementing an interpreted language and provides an example of a schema interpreter running in LISP.

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

Here is a function to interpret an S-expression before working 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 now, after the macro evaluation was added (the child methods were in the 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 Lisp in Small Pieces has a very similar function, he calls it eval .

Answer 3

Your evaluation chain should have a macro expansion phase:

 text-input -> read -> macroexpand -> compile -> load 

Note that the macro extension must be recursive (macroexpand until there is nothing macro exchange left).

In your environment, you need to be able to "hold" the macro extension functions, which you can see by name at this stage. Note that defmacro is a macro in Common Lisp that sets the correct calls to associate a name with the macro extension function in this environment.

Answer 4

Take a look at this example. This is a toy implementation of an Arc-like compiler with decent macro support.