Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Understanding how to implement once-only lisp macro

In Peter Seibel's book "Practical Common Lisp", we can find the definition of the very complicated macro once-only (see the bottom of page http://www.gigamonkeys.com/book/macros-defining-your-own.html).

I'm reading this macro definition for the 10th times in last 3 weeks and cannot understand how it works. :( Worse, I cannot develop this macro on my own, even though I understand its purpose and how to use it.

I'm especially interested in systematic "derivation" of this notoriously hard macro, step by step! Any help?

like image 680
Racket Noob Avatar asked Mar 21 '12 16:03

Racket Noob


2 Answers

Are you looking at this:

(defmacro once-only ((&rest names) &body body)
  (let ((gensyms (loop for n in names collect (gensym))))
    `(let (,@(loop for g in gensyms collect `(,g (gensym))))
      `(let (,,@(loop for g in gensyms for n in names collect ``(,,g ,,n)))
        ,(let (,@(loop for n in names for g in gensyms collect `(,n ,g)))
           ,@body)))))

It's not that complicated, but it does have a nested backquote, and multiple levels which are similar to each other, leading to easy confusion, even for experienced Lisp coders.

This is a macro which is used by macros for writing their expansions: a macro which writes parts of the bodies of macros.

There is a plain let in the body of the macro itself, then a once-backquoted generated let which will live inside the body of the macro which uses once-only. Finally, there is a doubly backquoted let which will appear in the macro expansion of that macro, in the code site where the macro is used by the user.

The two rounds of generating gensyms are necessary because once-only is a macro itself, and so it has to be hygienic for its own sake; so it generates a bunch of gensyms for itself in the outermost let. But also, the purpose of once-only is to simplify the writing of another hygienic macro. So it generates gensyms for that macro also.

In a nutshell, once-only needs to create a macro-expansion which requires some local variables whose values are gensyms. Those local variables will be used to insert the gensyms into another macro expansion to make it hygienic. And those local variables have to themselves be hygienic since they are a macro expansion, so they are also gensyms.

If you're writing a plain macro, you have local variables which hold gensyms, e.g.:

;; silly example
(defmacro repeat-times (count-form &body forms)
  (let ((counter-sym (gensym)))
    `(loop for ,counter-sym below ,count-form do ,@forms)))

In the process of writing the macro, you have invented a symbol, counter-sym. This variable is defined in plain view. You, the human, have chosen it in such a way that it does not clash with anything in the lexical scope. The lexical scope in question is that of your macro. We don't have to worry about counter-sym accidentally capturing references inside count-form or forms because forms are just data which is going into a piece of code which will end up inserted in some remote lexical scope (the site where the macro is used). We do have to worry about not confusing counter-sym with another variable inside our macro. For instance, we cannot give our local variable the name count-form. Why? Because that name is one of our function arguments; we would shadow it, creating a programming error.

Now if you want a macro to help you write that macro, then the machine has to do the same job as you. When it is writing code, it has to invent a variable name, and it has to be careful about what name it invents.

However, the code-writing machine, unlike you, does not see the surrounding scope. It cannot simply look at what variables are there and choose ones which do not clash. The machine is just a function which takes some arguments (pieces of unevaluated code) and produces a piece of code that is then blindly substituted into a scope after that machine has done its job.

Therefore, the machine has to choose the names extra wisely. In fact, to be completely bullet proof, it has to be paranoid and use symbols which are completely unique: gensyms.

So continuing with the example, suppose we have a robot which will write this macro body for us. That robot can be a macro, repeat-times-writing-robot:

(defmacro repeat-times (count-form &body forms)
  (repeat-times-writing-robot count-form forms))  ;; macro call

What might the robot macro look like?

(defmacro repeat-times-writing-robot (count-form forms)
  (let ((counter-sym-sym (gensym)))     ;; robot's gensym
    `(let ((,counter-sym-sym (gensym))) ;; the ultimate gensym for the loop
      `(loop for ,,counter-sym-sym below ,,count-form do ,@,forms))))

You can see how this has some of the features of once-only: the double nesting and the two levels of (gensym). If you can understand this, then the leap to once-only is small.

Of course, if we just wanted a robot to write repeat-times, we would make it a function, and then that function wouldn't have to worry about inventing variables: it is not a macro and so it doesn't need hygiene:

 ;; i.e. regular code refactoring: a piece of code is moved into a helper function
 (defun repeat-times-writing-robot (count-form forms)
   (let ((counter-sym (gensym)))
     `(loop for ,counter-sym below ,count-form do ,@forms)))

 ;; ... and then called:
(defmacro repeat-times (count-form &body forms)
  (repeat-times-writing-robot count-form forms))  ;; just a function now

But once-only cannot be a function because its job is to invent variables on behalf of its boss, the macro which uses it, and a function cannot introduce variables into its caller.

like image 119
Kaz Avatar answered Nov 02 '22 20:11

Kaz


An alternative to the once-only macro from Practical Common Lisp is derived in Let Over Lambda (see the 'Once Only' section in the third chapter).

like image 32
Miron Brezuleanu Avatar answered Nov 02 '22 20:11

Miron Brezuleanu