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.
8 comments:
This is the approach of the expansion algorithm in Alan Bawden's Quasiquotation in Lisp (http://repository.readscheme.org/ftp/papers/pepm99/bawden.pdf).
This is the usual way. Guy Steele's implementation from CLtL2, for instance, uses APPEND but then complexly simplifies it away (in the interest of efficiency, even though that's seldom an issue for backquote). It would be difficult to make nested splicing work correctly otherwise. (Actually, I was hoping this post was about alternative semantics for nested backquotes, but I guess I'll have to write that myself.)
You didn't cover how to match unquotes with quasiquotes, since nested quasiquotes can get confusing too.
Congratulations. You've again hit on the very thing that Clojure does. When will you be switching to Clojure again? ;-) Just kidding of course.
You really should look at Clojure, that is exactly what it does.
Same here. I did it multiple times and I still find it extremely mind-bending. Long ago I used to think it's a reader thing, but nope, the quasiquotation happens at run time (hence, it's pointless to try to implement it in JS or whatever is the host language, it has to be implemented in Lisp).
I found a small and elegant implementation: https://github.com/mishoo/SLip/blob/master/lisp/compiler.lisp#L25
(from http://norstrulde.org/ilge10/)
> (from http://norstrulde.org/ilge10/)
As the author of that page, I can say that that version, in turn, is a de-optimized variant of what is printed in Peter Norvig's Paradigms of Artificial Intelligence Programming. (I didn't try to save memory by sharing structure.)
And Norvig, in turn, credits Artificial Intelligence Programming by Charniak et al. :)
I've been re-implementing my quasiquote for R as a memoizing macro style for speed concerns.
Implementing quasiquote as an fexpr was easy peasy, just take your parse tree and march over it stuffing in new eval results. The macro style where you build an expression that evals to the actual thing you want is making me go crosseyed.
(R is one of those languages that is perfectly horrible with an awful library except it has one or two accidentally good ideas. it's the most widely used language built on first class environments + fexpr equivalents + almost lexical scope, for instance, but no one writing it knows how to do hygeine.)
Post a Comment