Defining the defmacro function using only LISP primitives?

Question

McCarthy's Elementary S-functions and predicates were atom, eq, car, cdr, cons

He then went on to add to his basic notation, to enable writing what he called S-functions: quote, cond, lambda, label

On that basis, we'll call these "the LISP primitives" (although I'm open to an argument about type predicates like numberp)

How would you define the defmacro function using only these primitives in the LISP of your choice? (including Scheme and Clojure)

Answer 1

The problem with trying to do this on a machine like McCarthy's LISP machine is that there isn't a way to prevent argument evaluation at runtime, and there's no way to change things around at compile time (which is what macros do: they rearrange code before it's compiled, basically).

But that doesn't stop us from rewriting our code at runtime on McCarthy's machine. The trick is to quote the arguments we pass to our "macros", so they don't get evaluated.

As an example, let's look at a function we might want to have; unless. Our theoretical function takes two arguments, p and q, and returns q unless p is true. If p is true, then return nil.

Some examples (in Clojure's syntax, but that doesn't change anything):

(unless (= "apples" "oranges") "bacon")
=> "bacon"

(unless (= "pears" "pears") "bacon")
=> nil

So at first we might want to write unless as a function:

(defn unless [p q]
    (cond p nil
          true q))

And this seems to work just fine:

(unless true 6)
=> nil

(unless false 6)
=> 6

And with McCarthy's LISP, it would work just fine. The problem is that we don't just have side-effectless code in our modern day Lisps, so the fact that all arguments passed to unless are evaluated, whether or not we want them to, is problematic. In fact, even in McCarthy's LISP, this could be a problem if, say, evaluating one of the arguments took ages to do, and we'd only want to do it rarely. But it's especially a problem with side-effects.

So we want our unless to evaluate and return q only if p is false. This we can't do if we pass q and p as arguments to a function.

But we can quote them before we pass them to our function, preventing their evaluation. And we can use the power of eval (also defined, using only the primitives and other functions defined with the primitives later in the referenced paper) to evaluate what we need to, when we need to.

So we have a new unless:

(defn unless [p q] 
    (cond (eval p) nil 
          true (eval q)))

And we use it a little differently:

(unless (quote false) (quote (println "squid!")))
=> "squid" nil
(unless (quote true) (quote (println "squid!")))
=> nil

And there you have what could generously be called a macro.

---

But this isn't defmacro or the equivalent in other languages. That's because on McCarthy's machine, there wasn't a way to execute code during compile-time. And if you were evaluating your code with the eval function, it couldn't know not to evaluate arguments to a "macro" function. There wasn't the same differentiation between the reading and the evaluating as there is now, though the idea was there. The ability to "re-write" code was there, in the coolness of quote and the list operations in conjunction with eval, but it wasn't interned in the language as it is now (I'd call it syntactic sugar, almost: just quote your arguments, and you've got the power of a macro-system right there.)

I hope I've answered your question without trying to define a decent defmacro with those primitives myself. If you really want to see that, I'd point you to the hard-to-grok source for defmacro in the Clojure source, or Google around some more.

Answer 2

Explaining it fully in all its details would require an awful lot of space and time for an answer here, but the outline is really pretty simple. Every LISP eventually has in its core something like the READ-EVAL-PRINT loop, which is to say something that takes a list, element by element, interprets it, and changes state -- either in memory or by printing a result.

The read part looks at each element read and does something with it:

(cond ((atom elem)(lambda ...))
      ((function-p elem) (lambda ...)))

To interpret macros, you simply (?) need to implement a function that puts the template text of the macro somewhere in storage, a predicate for that repl loop -- which means simply defining a function -- that says "Oh, this is a macro!", and then copy that template text back into the reader so it's interpreted.

If you really want to see the hairy details, read Structure and Interpretation of Computer Programs or read Queinnec's Lisp in Small PIeces.