Clementson's Blog

Nested Backquotes considered harmful

Sunday, December 5, 2004

Well, I guess nested backquotes aren't really "harmful" as they do allow you to do things that would otherwise be very difficult to do; however, they do result in code that is very hard to understand (which might be good for obfuscation contests, but is very difficult to maintain). In reality, the title of this article should have been "Nested Backquotes give me headaches" but I've always wanted to write an article titled "x considered harmful", so this is it! ;-).

Note: If you don't have a clue what nested backquotes are or why they are useful or are interested in learning more about writing (or understanding) the type of code-generating code typically generated with nested backquotes, it is worthwhile to read Alan Bawden's excellent paper "Quasiquotation in Lisp" (recommended by Jens Axel Søgaard). Alan's paper gives a history and overview of the development of this technology and is a very interesting read. Paul Graham also talks about nested backquotes in Chapter 16 of his book On Lisp:

"To define a macro-defining macro we will often need nested backquotes. Nested backquotes are notoriously hard to understand. Eventually common cases will become familiar, but one should not expect to be able to look at an arbitrary backquoted expression and say what it will yield. It is not a fault in Lisp that this is so, any more than it is a fault of the notation that one can't just look at a complicated integral and know what its value will be. The difficulty is in the problem, not the notation."

1. Use LIST, APPEND, etc. in the inner level, instead of backquote.
   
   OR
   
   
2. Use an auxiliary function which uses backquote.

(defmacro once-only (variables &rest body)
  (assert (every #'symbolp variables))
  (let ((temps nil))
    (dotimes (i (length variables)) (push (gensym) temps))
    `(if (every #'side-effect-free? (list .,variables))
       (progn .,body)
       `(let
          (,,@(mapcar #'(lambda (tmp var)
                          ``(,',tmp ,,var))
                      temps variables))
          ,(let ,(mapcar #'(lambda (var tmp) `(,var ',tmp))
                         variables temps)
             .,body)))))

(defmacro once-only (variables &rest body)
  (assert (every #'symbolp variables))
  (let ((temps nil))
    (dotimes (i (length variables)) (push (gensym) temps))
    `(if (every #'side-effect-free? (list .,variables))
       (progn .,body)
       (list 'let
         (list ,@(mapcar #'(lambda (tmp var)
                             `(list ',tmp ,var))
                         temps variables))
         (let ,(mapcar #'(lambda (var tmp) `(,var ',tmp))
                       variables temps)
           .,body)))))

(defun construct-binding (variable form)
  `(,variable ,form))

(defun construct-let-wrapper (bindings body-form)
  `(let ,bindings ,body-form))

(defmacro once-only (variables &rest body)
  (assert (every #'symbolp variables))
  (let ((temps nil))
    (dotimes (i (length variables)) (push (gensym) temps))
    `(if (every #'side-effect-free? (list .,variables))
       (progn .,body)
       (construct-let-wrapper
         (list ,@(mapcar #'(lambda (tmp var)
                             `(construct-binding ',tmp ,var))
                         temps variables))
         (let ,(mapcar #'(lambda (var tmp) `(,var ',tmp))
                       variables temps)
           .,body)))))

"Backquote is an indispensable feature of Lisp. Yet the standard spec for it leaves something to be desired. I have two main complaints:

1. There are three things to implement when implementing a facility like backquote: a reader, a macroexpander, and a writer. The reader converts a character sequence such as `(foo ,x) into an internal form such as (backquote (foo (bq-comma x))). (This is what Allegro reads it as.) The macroexpander then turns calls to backquote into constructor forms such as (list 'foo x). The writer prints (backquote (foo (bq-comma x))) as `(foo ,x).
   
   Unfortunately, the Common Lisp spec does not specify what the macros are. They are, therefore, implementation-dependent. Compare the situation with ordinary "quote," where there is a well-defined internal form (quote x), and therefore a well-defined transformation from the external form 'x. The problem with leaving it unspecified is that it is impossible to write your own tools that fit together with the reader, macro-expander, or writer. For instance, there is no way to write a portable code walker that does something special with backquoted expressions. In fact, an implementation is not required even to have an internal representation for backquotes. The reader and the macro-expander can be merged, so that `(f ,x) is read as (list 'f x). Then the backquote writer's behavior is not well defined, because it is impossible to tell wheter a list-constructing form came from a backquote or not.
   
   That's an example of why interacting with the macro-expander. You might also want to interact with the reader. Suppose you wanted to create a generalized backquote readmacro (call it !@) that built something other than list structures. You might write !@(make-a-foo (baz ,a) ,@l) as short for (apply #'make-a-foo (list 'baz a) l). Many Lisp implementations will signal an error of type "Comma not inside a backquote" when the expression !@(...) is read, and there is no portable way to intervene in the read process to make this legal.
   
   
2. The rule for interpreting nested backquotes is that a comma is paired with the innermost backquote surrounding (and "raises" its argument out of that context, so that the next comma matches up with the next backquote, and so forth).
   
   I think this is wrong, or at least wrong in some cases. I read backquotes left-to-right, and hence see the outermost backquote first. One would like it to be the case that from that backquote's point of view, everything inside it is "inert" (quoted), except stuff marked with a comma. This is true for all expressions that might occur inside it, except another backquote. So if you are editing a complex backquote expression:
   
   '(foo (bazaroo '(fcn a ,x)))
   
   the inner quote doesn't "shield" x from evaluation. But if you convert the inner quote to a backquote, that's exactly what happens. You have to convert it to this:
   
   '(foo (bazaroo `(,fcn a ,',x)))
   
   The ,', construct is just plain ugly. Its sole purpose is to raise its argument out of the innermost backquote; you can't say ,,x, because that would mean "Evaluate x when the outer backquote is expanded, getting e, and then evaluate e when the innermost backquote is expanded." Notice how the order of evaluation is outside-in, while the nested-backquote rule is inside-out. Very, very confusing.

These are not huge defects; 99.9% of all backquotes are not nested, and almost no one cares what the internal representation of a backquote is. But if you're interested, the file bq.lisp provides an alternative implementation."

1. Use nested backquotes.
2. Use LIST, APPEND, etc. in the inner level, instead of backquote.
3. Use an auxiliary function which uses backquote.
4. Use an alternative backquote implementation.