backquote

[Michael Greenwald <Greenwald@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: Fri, 11 Nov 88 10:18:20 PST
    From: Don Cohen <donc@vaxa.isi.edu>

    First, I was hoping for a clear statement of what nested backquotes
    meant.  Here's my current theory - the result of experimentation.
    I don't see how to interpret CLtL to mean this (innermost backquote
    expanded first??), but at least maybe someone in the know can
    either confirm my theory (and provide the mapping from CLtL) or
    correct it (and still provide the mapping):

First, you should distinguish between the two cases of nested backquotes
with an intervening comma, and nested backquotes without an intervening
comma.  The former case is unambigously specified by CLtL.  The latter
isn't (the outer backquote will capture the intermediate state of the
computation of the inner backquote.)

Yours is an example of the latter case.

    When you evaluate a backquote expression (oh, all right, the 
    result of reading one evaluates as if ...), you throw away the
    backquote (we're always evaluating the "outermost" backquote now!),
    find all the "matching" commas 
You can't do this without expanding the inner nested backquotes first.
					(which must all be innermost
    commas, although not all innermost commas match this backquote!)
    and replace them with the results of evaluating them.  Leave all
    other backquotes and commas (and everything else) alone!  Thus
    ``(a ,s ,',d ,,f `(,g)) 
	      --  --
    results in evaluation of the underlined expressions, yielding 
    something like
     `(a ,s ,'4 ,7 `(,g))
    ,@ is just like , except that you throw out an outer pair of parens.

    Is that right?

No (it's not outright "wrong").  It is sort of backwards.

CLtL states "If the backquote syntax is nested, the innermost backquoted
form should be expanded first."

This means that you can't start stripping commas until all inner
backquotes have been expanded.  At any given level of expansion you
use the outtermost comma first.

The result of expanding a backquote is only defined after evaluation, so
the exact details of the list structure returned by `` will vary from
implementation to implementation, however, the result of evaluating the
value of a ``<form> should be consistent.

In your example what's happening is something like this:

Using the transformation rules at the top of page 350 this means that
the interpretation of your example proceeds as follows: 

(forms like <...>, inside angle brackets are uninterpreted expressions
inside a backquote. Note that there's an implicit backquote before a <.
You cannot intrepet the body of a <...> unless there are no <>'s inside
it.)

``(a ,s ,',d ,,f `(,g))

<`(a ,s ,',d ,,f `(,g))>

;; now we have a problem.  The inner backquote is going to produce a
;; form that "when evaluated will ...", but the outer backquote is
;; telling us not to actually evaluate that form.  So we exposing the
;; innards of whichever reader we happen to be using.
;; For the sake of pedagogy we choose a very simple backquote
;; implementation.  We use bq-list instead of
;; list so that the pretty printer will be able to print out these lists
;; in backquote syntax.
;; So the next step is:
<(bq-list <a> <,s> <,',d> <,,f> <`(,g)>)>

<(bq-list 'a <,s> <,',d> <,,f> <`(,g)>)>
<(bq-list 'a s <,',d> <,,f> <`(,g)>)>
;; now, the rules tell us how to take off the outermost ","
<(bq-list 'a s ',d <,,f> <`(,g)>)>
;; ditto
<(bq-list 'a s ',d ,f <`(,g)>)>
<(bq-list 'a s ',d ,f (bq-list <,g>))>
<(bq-list 'a s ',d ,f (bq-list g))>
;; now we can interpret <(bq-list ...)> relative to the outer backquote
(bq-list <bq-list> <'a> <s> <',d> <,f> <(bq-list g)>)
;; the interpretation of <bq-list>, <'a>, and <s> are done in one step here
;; because I'm getting bored...
(bq-list 'bq-list ''a 's <',d> <,f> <(bq-list g)>)
;; this should help illustrate what >really< happened to <'a> in all of
;; its boring steps.
(bq-list 'bq-list ''a 's (list 'quote <,d>) <,f> <(bq-list g)>)
(bq-list 'bq-list ''a 's (list 'quote d) <,f> <(bq-list g)>)
(bq-list 'bq-list ''a 's (list 'quote d) f <(bq-list g)>)
(bq-list 'bq-list ''a 's (list 'quote d) f (list 'bq-list 'g))

Say that BQ-LIST acts exactly like LIST, except that the pretty printer
knows how to print a list whose car is BQ-LIST by printing a leading
backquote, and stripping one quote from each elt of the list, and if
there's no quote to strip, inserting a comma.

Then the result of the reading and evaluating your example (if D is 4
and F is 7)

read of ``(a ,s ,',d ,,f `(,g)) 
  => (bq-list 'bq-list ''a 's (list 'quote d) f (list 'bq-list 'g))
Eval of that 
  => (bq-list 'a s '4 7 (bq-list g))
Which would be printed
  `(a ,s 4 7 `(,g))

So the illusion is that it is matching inner-most comma's to the
outermost backquote, but in fact it is behaving roughly the way I
describe, and CLtL defines.  (I wasn't very careful about this, so I
might have made some mistakes - it's an awfully baroque transformation).

A more common case is where the nested backquote is inside a comma, so
that the backquote implementation isn't exposed in the final result.