quasiquote as syntax-rules macro

In section 4 of R5RS, it says "With the exception of QUASIQUOTE, whose
macro definition is complex, the derived expressions are classified as
library features. Suitable definitons are given in section 7.3"

Now, I agree that QUASIQUOTE is a bit complex, at least with respect to
how it "should" behave on nested quasiquoted expressions.

But that shouldn't stop us from attempting to define it as a SYNTAX-RULES
derived expression, for the purposes of specification.

What, if anything, is wrong with the following attempt at a definition
(see end of post)? It seems to pass all of the examples that I feed to it
from R5RS.

I have already attempted to break it by using the identifier SUCC (which
has a special purpose in the macro), but it seems like "Macros That Work"
really do "Work", at least in this case.

[[ I'm not arguing that this would be a suitable implementation in a
production system. In particular, check out the (append X (car Y)) bit in
the middle for a good laugh. But it seems like it specifies how
QUASIQUOTE should behave reasonably well. ]]

-Felix


(letrec-syntax
((quasiquote (syntax-rules ()
[(_ X) (car (qq* 0 X))]))
;; qq* expands into a expression that evaluates to some sort of
;; list (protocol established to handle unquote-splicing).
;;
;; Depth is handled by [de]constructing a primitive
;; representation for the naturals: N ::= 0 | (succ N)
(qq* (syntax-rules (unquote quasiquote succ unquote-splicing)
[(qq* 0 ,X) (list X)]
[(qq* 0 ,@X) X]
[(qq* n `X)
(list (cons 'quasiquote (qq* (succ n) X)))]
[(qq* (succ n) ,X)
(list (cons 'unquote (qq* n X)))]
[(qq* (succ n) ,@X)
(list (cons 'unquote-splicing (qq* n X)))]
[(qq* n (X . Y))
(list (append (qq* n X) (car (qq* n Y))))]
[(qq* n #(X ...))
(list (apply vector (append (qq* n X) ...)))]
[(qq* n X) (list (quote X))])))

;; Examples from R5RS
(list `(list ,(+ 1 2) 4)
(let ((name 'a)) `(list ,name ',name))
`(a ,(+ 1 2) ,@(map abs '(4 -5 6)) b)
`(( foo ,(- 10 3)) ,@(cdr '(c)) . ,(car '(cons)))
`#(10 5 ,(sqrt 4) ,@(map sqrt '(16 9)) 8)
`(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f)
(let ((name1 'x)
(name2 'y))
`(a `(b ,,name1 ,',name2 d) e))
(quasiquote (list (unquote (+ 1 2)) 4))
'(quasiquote (list (unquote (+ 1 2)) 4))
))

"Felix S. Klock II" <pnkfelix@ccs.neu.edu> wrote:
> Now, I agree that QUASIQUOTE is a bit complex, at least with respect to
> how it "should" behave on nested quasiquoted expressions.
>
> But that shouldn't stop us from attempting to define it as a SYNTAX-RULES
> derived expression, for the purposes of specification....
>
> [[ I'm not arguing that this would be a suitable implementation in a
> production system. In particular, check out the (append X (car Y)) bit in
> the middle for a good laugh. But it seems like it specifies how
> QUASIQUOTE should behave reasonably well. ]]

Larceny implements QUASIQUOTE as a SYNTAX-RULES macro. Larceny's
definition is based on a definition that Jonathan Rees posted to
this newsgroup on 22 December 1986. See Compiler/usual.sch

Will

Well, strictly speaking, the Larceny implementation of QUASIQUOTE is using
some sort of funky extra argument to DEFINE-SYNTAX that changes the
"scope" of the macro. [[ No, I don't know what that means, that's just
what I'm inferring from reading the comments and the macro definitions
themselves. ]] I'm not sure what that means for trying to port the
Larceny definition over to pure R5RS Scheme.

Also, the Larceny definition is over 100 lines long! Okay, okay, 25 of
those lines are comments, but that's still over 75 lines of hair! The one
I posted was a little over 20 lines (at least for the macro definition
part), and could probably be brought down to 15 or so without trouble. I
was trying to suggest something that would be appropriate for inclusion in
the spec (e.g. R6RS), not a production level version.

I suppose the biggest reason for my posting is that I had been under the
mistaken impression that the nesting depth rules in QUASIQUOTE kept it
from being definable as a SYNTAX-RULES macro. The text of R5RS doesn't
really do much to correct that impression. So I was pretty surprised to
find that it can be defined using SYNTAX-RULES, and what's more, it seems
like it has a really *simple* definition.

The only problem that I anticipate with my proposed definition is that it
might accept inputs that aren't strictly legal according to R5RS; the
other macro definitions in R5RS seem to have been written to ensure that
only legal input forms will pass through; it would be nice to have a
similar assurance for QUASIQUOTE...

-Felix

On Thu, 26 Aug 2004, William D Clinger wrote:

> "Felix S. Klock II" <pnkfelix@ccs.neu.edu> wrote:
> > Now, I agree that QUASIQUOTE is a bit complex, at least with respect to
> > how it "should" behave on nested quasiquoted expressions.
> >
> > But that shouldn't stop us from attempting to define it as a SYNTAX-RULES
> > derived expression, for the purposes of specification....
> >
> > [[ I'm not arguing that this would be a suitable implementation in a
> > production system. In particular, check out the (append X (car Y)) bit in
> > the middle for a good laugh. But it seems like it specifies how
> > QUASIQUOTE should behave reasonably well. ]]
>
> Larceny implements QUASIQUOTE as a SYNTAX-RULES macro. Larceny's
> definition is based on a definition that Jonathan Rees posted to
> this newsgroup on 22 December 1986. See Compiler/usual.sch
>
> Will
>

Hello,

I have found a definition of quasiquote that is simpler. But I have
not
tested it intensively. At least it could help understood how it work:

(define-syntax quasiquote
(syntax-rules
(quasiquote unquote unquote-splicing quote)
((quasiquote a) (quasiquote "zero" a))
((quasiquote l (quote a)) (list 'quote (quasiquote l a)))
((quasiquote "zero" (unquote a)) a)
((quasiquote "zero" b . (unquote a))
(cons b a))
((quasiquote ("succ" . l) (unquote a))
(list 'unquote (quasiquote l a)))
((quasiquote l (unquote-splicing a))
(syntax-error "unquote-splicing"))
((quasiquote "zero" ((unquote-splicing a) . r))
(append a (quasiquote "zero" r)))
((quasiquote ("succ" . l) ((unquote-splicing a) . r))
(cons (list 'unquote-splicing (quasiquote l a)) (quasiquote (1 .
l) r)))
((quasiquote l (quasiquote a)) (list 'quasiquote (quasiquote (1 .
l) a)))
((quasiquote l (r . r1)) (cons (quasiquote l r) (quasiquote l r1)))
((quasiquote l #(r ...)) (list->vector (quasiquote l (r ...))))
((quasiquote l a) (quote a))
))
)

To be usable it need a definition of syntax-error that is
implementation dependant.

jftrevien-

Ah, you're may be a bit simpler than mine; yours is more clever than mine
in how it descends into #(X ...), so that you didn't need to return a list
to handle UNQUOTE-SPLICING

However, your definition has a bug somewhere. Try out this example (which
is from R5RS and is one of the expressions that I gave in my first post) :

(let ((name1 'x)
(name2 'y))
`(a `(b ,,name1 ,',name2 d) e))

When I use your macro, this yields:
(a `(b ,,name1 ,',name2 d) e)

But in MzScheme proper, it yields:
(a `(b ,x ,'y d) e)

I will see about applying your ideas to my own macro definition.

-Felix

On Fri, 27 Aug 2004, jftrevien wrote:

> Hello,
>
> I have found a definition of quasiquote that is simpler. But I have
> not
> tested it intensively. At least it could help understood how it work:
>
> (define-syntax quasiquote
> (syntax-rules
> (quasiquote unquote unquote-splicing quote)
> ((quasiquote a) (quasiquote "zero" a))
> ((quasiquote l (quote a)) (list 'quote (quasiquote l a)))
> ((quasiquote "zero" (unquote a)) a)
> ((quasiquote "zero" b . (unquote a))
> (cons b a))
> ((quasiquote ("succ" . l) (unquote a))
> (list 'unquote (quasiquote l a)))
> ((quasiquote l (unquote-splicing a))
> (syntax-error "unquote-splicing"))
> ((quasiquote "zero" ((unquote-splicing a) . r))
> (append a (quasiquote "zero" r)))
> ((quasiquote ("succ" . l) ((unquote-splicing a) . r))
> (cons (list 'unquote-splicing (quasiquote l a)) (quasiquote (1 .
> l) r)))
> ((quasiquote l (quasiquote a)) (list 'quasiquote (quasiquote (1 .
> l) a)))
> ((quasiquote l (r . r1)) (cons (quasiquote l r) (quasiquote l r1)))
> ((quasiquote l #(r ...)) (list->vector (quasiquote l (r ...))))
> ((quasiquote l a) (quote a))
> ))
> )
>
> To be usable it need a definition of syntax-error that is
> implementation dependant.
>
>

On Fri, 27 Aug 2004, Felix S. Klock II wrote:

> However, your definition has a bug somewhere. Try out this example (which
> is from R5RS and is one of the expressions that I gave in my first post) :
> ...

Ah, I found your bug. You are using the literal 1 in some places and the
literal "succ" in others for the same purpose. If you replace 1 with
"succ" everywhere in the macro definition, your code no longer breaks on
the example I posted.

Nice job overall.

-Felix

Felix S. Klock II wrote:
>
> On Fri, 27 Aug 2004, Felix S. Klock II wrote:
>
>
>>However, your definition has a bug somewhere. Try out this example (which
>>is from R5RS and is one of the expressions that I gave in my first post) :
>>...
>
>
> Ah, I found your bug. You are using the literal 1 in some places and the
> literal "succ" in others for the same purpose. If you replace 1 with
> "succ" everywhere in the macro definition, your code no longer breaks on
> the example I posted.
>
> Nice job overall.
>
> -Felix

I apologize, in fact the original definition contain only 1 and no
"succ" but when i send it i think that "succ" would be more coherent,
unfortunately i missed two of them.
So the right definiton was:

(define-syntax quasiquote
(syntax-rules
(quasiquote unquote unquote-splicing quote)
((quasiquote a)
(quasiquote "zero" a))
((quasiquote l (quote a))
(list 'quote (quasiquote l a)))
((quasiquote "zero" (unquote a))
a)
((quasiquote "zero" b . (unquote a))
(cons b a))
((quasiquote ("succ" . l) (unquote a))
(list 'unquote (quasiquote l a)))
((quasiquote l (unquote-splicing a))
(syntax-error "unquote-splicing"))
((quasiquote "zero" ((unquote-splicing a) . r))
(append a (quasiquote "zero" r)))
((quasiquote ("succ" . l) ((unquote-splicing a) . r))
(cons (list 'unquote-splicing (quasiquote l a))
(quasiquote ("succ" . l) r)))
((quasiquote l (quasiquote a))
(list 'quasiquote (quasiquote ("succ" . l) a)))
((quasiquote l (r . r1))
(cons (quasiquote l r) (quasiquote l r1)))
((quasiquote l #(r ...))
(list->vector (quasiquote l (r ...))))
((quasiquote l a)
(quote a))
))

Felix S. Klock II wrote:
> In section 4 of R5RS, it says "With the exception of QUASIQUOTE, whose
> macro definition is complex, the derived expressions are classified as
> library features. Suitable definitons are given in section 7.3"
>
> Now, I agree that QUASIQUOTE is a bit complex, at least with respect to
> how it "should" behave on nested quasiquoted expressions.
>
> But that shouldn't stop us from attempting to define it as a SYNTAX-RULES
> derived expression, for the purposes of specification.

I like the syntax-rules implementations of quasi-quote given in
this thread. For comparison there is a traditional implementation
in the appendix of Bawdens "Quasiquotation in Lisp":

<http://www.linearity.org/bawden/ftp/pepm99.ps.gz>

--
Jens Axel Søgaard

On Thu, 2 Sep 2004, Jens Axel Søgaard wrote:

> I like the syntax-rules implementations of quasi-quote given in
> this thread. For comparison there is a traditional implementation
> in the appendix of Bawdens "Quasiquotation in Lisp":
>
> <http://www.linearity.org/bawden/ftp/pepm99.ps.gz>

Hmm. I hadn't seen this paper before.

I've been playing with the code in the appendix for a little while now,
and I'm not confident that it has the same semantics the macro that I
wrote. This is disturbing. The code in the appendix is very oriented
towards a reader-macro based expansion for QUASIQUOTE...

One very disturbing note by Bawden: "I am not aware of the existence of a
correct optimizing quasiquotation expander for Scheme. (None of the
Scheme implementations that I tested implement nested splicing
correctly.)"

It is the parenthetical remark that I find disturbing; he may have meant
to only refer to the Scheme implementations that try to optimize their
handling of quasiquote. Or he may have indeed been referring to a larger
set of Scheme implementations. Its not clear which ones he tested.

-Felix

On Thu, 2 Sep 2004, Felix S. Klock II wrote:

>
>
> On Thu, 2 Sep 2004, Jens Axel Søgaard wrote:
>
> > I like the syntax-rules implementations of quasi-quote given in
> > this thread. For comparison there is a traditional implementation
> > in the appendix of Bawdens "Quasiquotation in Lisp":
> >
> > <http://www.linearity.org/bawden/ftp/pepm99.ps.gz>
>
> Hmm. I hadn't seen this paper before.
>
> I've been playing with the code in the appendix for a little while now,
> and I'm not confident that it has the same semantics the macro that I
> wrote. This is disturbing. The code in the appendix is very oriented
> towards a reader-macro based expansion for QUASIQUOTE...

Okay. I managed to resolve this issue for myself. I didn't read page 3
of the paper carefully enough.

Footnote 3 of Bawden's paper gives an explanation for why my code is
producing different results than his; he is deliberately ignoring the way
R5RS specifies quotation of QUASIQUOTEs themselves, because he wants to be
able to optimize `,X into X *no matter where it occurs* (that includes
expressions like '`,X which Bawden's expander turns into 'X)

This sort of makes sense, if you assume that all you ever do with code is
generate more and more of it and only for eventual runtime evaluation.
That is, if you assume that your human readers are never going to want to
see the actual results of expressions like '`,X in a truly quoted form
[[ (quasiquote (unquote X)) ]], then Bawden's system is fine.

However, I'm pretty sure its not R5RS compliant. Bawden says that he is
skeptical of the utility of specifying the exact expansion in the way that
R5RS does. However, I believe that he is overlooking the fact that this
way, the result of evaluating any quoted expression is fully specified,
which means that it is (easily) testable! If we allowed the
implementation to choose any expansion it wanted for these reader-based
macros, we would be forced to test R5RS compliance by actually EVAL'ing
the generated forms, rather than just comparing them with a call to EQUAL?

> One very disturbing note by Bawden: "I am not aware of the existence of a
> correct optimizing quasiquotation expander for Scheme. (None of the
> Scheme implementations that I tested implement nested splicing
> correctly.)"
>
> It is the parenthetical remark that I find disturbing; he may have meant
> to only refer to the Scheme implementations that try to optimize their
> handling of quasiquote. Or he may have indeed been referring to a larger
> set of Scheme implementations. Its not clear which ones he tested.

I still haven't figured this one out. If Alan's reading this, I'd love to
know which Scheme implementations he tested and what sort of problems he
encountered.

-Felix

"Felix S. Klock II" <pnkfelix@ccs.neu.edu> writes:

> > One very disturbing note by Bawden: "I am not aware of the
> > existence of a correct optimizing quasiquotation expander for
> > Scheme. (None of the Scheme implementations that I tested
> > implement nested splicing correctly.)"

> I still haven't figured this one out. If Alan's reading this, I'd
> love to know which Scheme implementations he tested and what sort of
> problems he encountered.

(assuming any Alan will do ...) The problem is that scheme's
quasiquote specification is broken with respect to nested splicing.
See below.

-al


From: Alf Petrofsky <alf@petrofsky.org>
Newsgroups: comp.lang.scheme
Subject: Re: getting a list into a macro
Date: 27 Nov 2001 16:39:42 -0800
Message-ID: <87k7wbbuep.fsf@radish.petrofsky.org>

ds26@goldshoe.gte.com (Dorai Sitaram) writes:

>(define-macro create-class
> (lambda (superclass slots . methods)
> `(create-class-proc
> ,superclass
> (list ,@(map (lambda (slot) `',slot) slots))
> (list ,@(map (lambda (method) `',(car method)) methods))
> (vector ,@(map (lambda (method) `,(cadr method)) methods)))))

This quasiquotation seems overly complicated to me. Is there any
reason you don't write it more simply, like this:

(define-macro create-class
(lambda (superclass slots . methods)
`(create-class-proc
,superclass
',slots
',(map car methods)
(vector ,@(map cadr methods)))))

-al

P.S. The vector should be further abbreviable to `#(,,@(map cadr
methods)), but unfortunately the r5rs specification of quasiquote is
broken with respect to nested unquote-splicing. Chez scheme supports
such quasiquotations as a compatible extension to the r5rs semantics.

P.P.S. Common Lisp specifies nested quasiquotation in a way that
makes ,,@expr useful. When nested quasiquote was added to scheme in
r3rs, it was intended to be compatible with lisp. Because the method
of specification was turned inside out from the lisp method, it was
not noticed that nested quasiquotation had been broken. One way to
make scheme compatible with common lisp would be to add the following
to r5rs:

When a comma at-sign and the expression that follows it are being
replaced by the elements of the list that resulted from the
expression's evaluation, any sequence of commas and comma at-signs
that immediately preceeded the comma at-sign is also removed and is
added to the front of each of the replacements.

(let ((x '(a b c))) ``(,,x ,@,x ,,@x ,@,@x))
=> `(,(a b c) ,@(a b c) ,a ,b ,c ,@a ,@b ,@c)

``(,,@'() ,@,@(list))
=> `()

`````(a ,(b c ,@,,@,@(list a b c)))
=> ````(a ,(b c ,@,,@a ,@,,@b ,@,,@c))

When I discovered this problem, I couldn't find anything that had been
written about it, so I started to prepare a long-winded missive and a
srfi. The work withered after I discovered the chez scheme fix and
couldn't decide whether I preferred their approach (uglier, but more
backwards-compatible) or mine. This postscript, and the excuse for an
article that preceeded it, are an attempt to at least get something
about the subject into google.

Here's a simple implementation of the above specification:

;; As an undocumented "feature" this takes optional extra arguments,
;; which must all be #f. One level of unquotation is ignored per
;; extra argument supplied.
(define-syntax quasiquote
(syntax-rules (unquote unquote-splicing quasiquote)
((_ ,x ) x)
((_ (,@x . y) ) (append x `y))
((_ `x . d) (list 'quasiquote (quasiquote x #f . d)))
((_ ,x #f . d) (list 'unquote (quasiquote x . d)))
((_ (,x . y) #f . d) (append (map (lambda (z) (list 'unquote z))
(quasiquote (x) . d))
(quasiquote y #f . d)))
((_ (,@x . y) #f . d) (append (map (lambda (z) (list 'unquote-splicing z))
(quasiquote (x) . d))
(quasiquote y #f . d)))
((_ (x . y) . d) (cons (quasiquote x . d) (quasiquote y . d)))
((_ #(x ...) . d) (list->vector (quasiquote (x ...) . d)))
((_ x . d) 'x)))