Sketchy LISP

An Introduction to Functional Programming in Scheme

3.2 Quasiquotation

Quasiquote is like quote, but only quasi. At a first glance they look equal:

     (quote (1 2 (+ 1 2))) => (1 2 (+ 1 2))
(quasiquote (1 2 (+ 1 2))) => (1 2 (+ 1 2))

But quasiquote has a companion keyword named unquote which, as its name suggests, allows to unquote individual parts of a quasiquoted expression:

(quasiquote (1 2 (unquote (+ 1 2)))) => (1 2 3)

Quasiquote and unquote have single-character abbreviations (just like quote) which are much more handy than their pseudo function forms. The ` (backquote) character equals an application of quasiquote and the , (comma) character equals an application of unquote:

`(1 2 ,(+ 1 2))  =  (quasiquote (1 2 (unquote (+ 1 2))))

It is technically possible to quasiquote and unquote single atoms:

 `foo  =  'foo
`,foo  =  foo

However, quasiquoting an atom is equal to quoting it, and quasiquoting and then unquoting it is equal to not quoting it at all. The major purpose of quasiquotation is the construction of fixed list structures that contain only few variable parts:

(let ((var 'x))
  `(lambda (,var)
     (* ,var ,var)))
=> (lambda (x) (* x x))

Without using quasiquotation, this expression would have to be written this way:

(let ((var 'x))
  (list 'lambda
        (list var)
        (list '* var var)))

Not quite as readable, is it? And things get even worse when you start splicing lists using unquote-splicing (or ,@ in short):

                 `(1 2 3 ,@(list 4 5 6)) => (1 2 3 4 5 6)
`(1 2 3 (unquote-splicing (list 4 5 6))) => (1 2 3 4 5 6)

Like unquote, unquote-splicing unquotes its argument, but instead of including it in a surrounding list, it splices it into that list:

`(1 2 ,@(list 3 4))  =  (append '(1) '(2) (list 3 4))

Because unquote-splicing splices its argument into a list, it is not valid outside of quasiquoted lists:

`,@(list 3 4) => bottom

Here is an expression that constructs a form using unquote-splicing:

(let* ((var 'x)
       (body `((display ,var)
               (newline)
               ,var)))
  `(lambda (,var) ,@body))
=> (lambda (x) (display x) (newline) x)

and the same expression without quasiquotation:

(let* ((var 'x)
       (body (list (list 'display var)
                   '(newline)
                   var)))
  (append '(lambda)
          (list (list var))
          body))

If you see a pattern emerging here, you are not mistaken:

         `x = 'x
        `,x = x
       `(x) = (list 'x)
      `(,x) = (list x)
    `(x ,x) = (list 'x x)
     `(,@x) = (append x)
`(x ,x ,@x) = (append (list 'x) (list x) x)

We already know that a quasiquoted atom is a quoted atom and a quasiquoted and unquoted atom is an (unquoted) atom. Here are some new observations: 1) A quasiquoted list is an application of list to a series of quoted forms. 2) An unquoted form in a quasiquoted list is not quoted. 3) When ,@ occurs in a quasiquoted list, the application of list is replaced by an application of append, and list is applied to each subform except for those that will be spliced.

3.2.1 Metaprogramming

A metaprogram is a program that writes to re-writes a program. Metaprogramming is the art of writing metaprograms.

The previous section introduced some simple metaprograms, such as

(let ((var 'x))
  `(lambda (,var)
     (* ,var ,var)))

which generates the code of a procedure that squares its argument. Here is a more interesting metaprogram that makes heavy use of quotation and quasiquotation:

((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))

Can you find out what it does without reading ahead?

Programs like the above are widely known as quines in computer science, named after the logician W.V.O. Quine. What they do is to print a copy of their own code. Above quine makes use of the fact that Scheme environments print normal forms of expressions. It reduces to its own code which is then printed by the Scheme system. Some systems may print something like

((lambda (x) (quasiquote ((unquote x) '(unquote x))))
'(lambda (x) (quasiquote ((unquote x) '(unquote x)))))

instead of the original expression, but this is merely its expanded form. When you evaluate it again, you will finally reach a fixed point in the evaluation. Fixed points are an interesting concept in computer science, and we will get back to them in a later section.

In the previous subsection some rules regarding the equivalence of quasiquotation and list/append were introduced. Using metaprogramming, it should be possible to transform applications of quasiquote mechanically into applications of append and list by applying these rules. Indeed this is possible. The following metaprogram performs this transformation: [Footnote: Expand-qq is not a full quasiquote expander as required by standard Scheme. It does not handle improper lists correctly, ignores vectors, and does not support nested quasiquotation.]

(define (expand-qq form)
  (letrec
    ((does-splicing?
       (lambda (form)
         (and (pair? form)
              (or (and (pair? (car form))
                       (eq? 'unquote-splicing (caar form)))
                  (does-splicing? (cdr form))))))
     (expand-list
       (lambda (form)
         (if (does-splicing? form)
             (cons 'append
                   (map (lambda (x)
                          (if (and (pair? x)
                                   (eq? 'unquote-splicing
                                        (car x)))
                              (cadr x)
                              (list 'list (expand x))))
                        form))
             (cons 'list (map expand form)))))
     (expand
       (lambda (form)
         (cond ((not (pair? form))
                 (list 'quote form))
               ((eq? 'quasiquote (car form))
                 (expand (cadr form)))
               ((eq? 'unquote (car form))
                 (cadr form))
               (else (expand-list form))))))
    (expand (cadr form))))

The expand-qq procedure expands quasiquote to list and append as described in the previous section:

       (expand-qq '`(x)) => (list 'x)
      (expand-qq '`(,x)) => (list 'x)
(expand-qq '`(x ,x ,@x)) => (append (list 'x) (list x) x)

It also translates the quasiqoted part of the above quine properly:

(expand-qq '`(,x ',x)) => (list x (list 'quote x))

Verifying that the above result is actually equal to the original quasiquoted form is left as an exercise to the reader.