In my previous post, I discussed a very minor thing that I thought should be simple to do with a Lisp macro, but that I’d been working on for the better part of a week without success.

As I’ve said before, once I run into a problem, I can’t leave it alone — I pound my head against it until either the problem breaks or my head does. This one finally broke, and I discovered the true power of Lisp at the same time.

I knew that the parameters to Lisp’s macros were the instructions from the code, but the only examples I’d seen of macros were fairly simple things, using back-quoted expressions to build additional expressions for the ones that were passed to the macro. The key realization that let me solve this problem was that the macro can itself be a program of arbitrary complexity, and that the data it’s passed — the instructions that are being compiled — are in the form of a list themselves, and can be arbitrarily manipulated.

Once I hit on those facts, it was easy to see a solution: replace all instances of each of the variables in the original body with new gensym-created variables, with a let to assign the new variables their initial values. 🙂 It sounds a little complicated, but it’s not really.

When I first realized that this is the power that Paul Graham means when he talks about Lisp, I was incredulous. That’s all? But after thinking about it for a little while, I started to see its usefulness: at a minimum, I can alter code at compile time, changing the names and syntax of calls to functions that aren’t intuitively obvious to me into ones that are. And when necessary, I can invent whatever syntax best describes the problem that I’m solving, and have macros that change that into standard Lisp code when it’s compiled! I’d written some C++ code that wrote other C++ code before, but it’s a multi-step pain-in-the-neck process that takes a lot of effort. By comparison, this is simplicity itself, and it’s built right into the language!

Anyway, here’s the first version of the code for it:

(defmacro gensym-let (vars-and-values &body body)
  (labels ((first-or-only (x) (if (listp x) (first x) x))
           (second-or-nil (x) (if (listp x) (second x) nil)))
    (let ((newlets nil))
      (dolist (i vars-and-values `(let ,newlets ,@body))
        (let ((g (gensym)))
          (setf newlets (append newlets `((,g ,(second-or-nil i)))))
          (setf body (subst g (first-or-only i) body)))))))

(Again, sorry for the lack of proper spacing — it’s there, but WordPress doesn’t display it. Any Lisp-compatible editor should be able to reformat it without difficulty.)

The first two lines define two sub-functions. first-or-only takes an atom or a list and returns the atom itself or the first item in the list — in other words, if you pass it b or (b), it will return b, and if you pass it the list (a 12) it will return a. second-or-nil works similarly, but returns either the second item in the list it’s passed, or nil if the passed item is an atom. They’re basically there so that the rest of the code is easier to read.

The rest of the macro runs through the vars-and-values list, generating a new symbol for each variable in the list and assigning the value from vars-and-values (if one is supplied) to it, then going through the body of code that it’s passed and replacing all mention of that variable with the newly-generated symbol.

The end result: if I pass it this…

(gensym-let ((n2 5) (n3 88))
    `(format t "~a equals ~a, ~a equals ~a" n2 ,n2 n3 ,n3))

…the compiler sees something like this instead…

(LET ((#:G1887 5) (#:G1888 88))
  `(FORMAT T ,"~a equals ~a, ~a equals ~a" #:G1887 ,#:G1887 #:G1888 ,#:G1888))

…and the result is:

G1887 equals 5, G1888 equals 88

No errors, no warnings, and no mention of the original symbols in the output so it avoids the problem of variable capture (which is what it was intended for). Perfect!

Well, almost perfect. It works, but to make this production-quality code, I should really add error-checking too, to intelligently report problems such as if the vars-and-values list is fed lists with more than two items in them, or with a first item that’s not a symbol. And I should probably tell the gensym function to use more descriptive names, ones that incorporate the name of the original variable too, to make it easier for the programmer to interpret the output of the macro and relate it to his original code. And with that first version, you’ll get a warning if you declare a variable that you want to use in a function that also declares it. (All of these problems are taken care of in the final version.)

There are probably a couple other minor improvements that will suggest themselves as I use it too. But the original problem seems to be solved now, so I can go pound my head against a different one. 🙂

(For the curious: an associate tried to solve the challenge too, and ran into the same difficulties that I did. When I mentioned the key insights to him, it took him less than a minute to see the same idea, and a couple hours to make it work — he has a little less experience with Lisp than I do.)