Sunday, April 28, 2013

A quasiquote I can understand

I've written two Lisps (1, 2) with quasiquotation, and in both, quasiquotation was the most difficult thing to implement, and gave me the most headaches. That shouldn't be, right? After all, it only creates new forms.

I think now I've found a formulation for quasiquote that has a really simple implementation, and yields more or less the same results as existing quasiquote implementations.

Some definitions:
  • `foo stands for (quasiquote foo), `(foo) stands for (quasiquote (foo)).
  • ,foo stands for (unquote foo) and is only allowed within a quasiquote.
  • ,@foo stands for (unquote-splicing foo) and is only allowed within a quasiquote.
  • Quasiquote, unquote, and unquote-splicing only ever take a single operand.
  • `foo = 'foo, i.e. a quasiquoted symbol yields simply the symbol.
  • `"foo" = "foo", `12 = 12, and likewise for other literals.
The main difficulty I previously had with quasiquote came from unquote-splicing, which inserts a list of multiple elements into the constructed list (whereas nested quoted or unquoted forms only insert a single element). The main idea in this new formulation is to make inserting multiple elements the default, and define nested quoted or unquoted elements as simply inserting a list containing a single element.

Every `(...) expression therefore stands for an APPEND of the list's further processed elements.

For example, given

(define foo 1)
(define bar 2)
(define quux '(3 4))

the quasiquote expression

`(foo ,bar ,@quux)

stands for

(append (list 'foo) (list bar) quux)

which produces the following when evaluated:

'(foo 2 3 4)

So, processing a quasiquoted list works by wrapping each element, except for unquote-splicing forms, in a call to LIST, and APPENDing the results. Quoted elements (foo) get processed recursively. Unquoted elements (bar) are passed to the call to LIST unprocessed. Unquote-splicing forms (quux) are inserted directly into the APPEND form.

I haven't implemented this yet, but I think defining a quasiquoted list `(...) as an APPEND really simplifies things.