Date: Monday, 8 March 1982 11:31-EST
From: Jonathan Rees <Rees at YALE>
To: Mcdermott at YALE
Cc: Riesbeck at YALE, Alan at MIT-MC, Kmp at MIT-MC
Subject: Quasi-Quote
I forwarded your little report to Alan Bawden and Kent Pitman at MC... if anyone has opinions, they do, and perhaps they can defend Maclisp's world view (which seems poorly represented) better than I...
I don't think the use of the character ` is due to Sussman; in fact I
had the impression he thought ` was an unfortunate choice. In Scheme
they used " , and @ (for ` , and ,@); this choice was made just a little
before the Lisp Machine people decided to go with ` , ,@. I think it
was only after the Lisp Machine had been using ` that it was adopted for
Maclisp; Alan Bawden probably knows the history here.
From: Jonathan Rees <Rees at YALE>
To: Kmp at MIT-MC, Alan at MIT-MC
Subject: [Mcdermott: Quasi-Quote]
Date: Monday, 8 March 1982 10:42-EST
From: Drew McDermott <Mcdermott>
To: Riesbeck, Rees
Re: Quasi-Quote
I am thinking of sending the following thing to Sigart Newsletter. (It is also found in [RES]<MCDERMOTT>QUASIQ.TXT) I would appreciate your thoughts before I do. (Feel free to show it to anyone else you think might have an opinion.)
Drew McDermott Yale University
One of the major annoyances of pure Lisp is the awkwardness of building lists that are "mostly constant." For instance, if you want to build
(COND ((EQ y 'A) (SETQ L (CONS x L))) )
where x and y are expressions whose values are to be plugged in, you must evaluate
(LIST 'COND
(LIST (CONS 'EQ (LIST y ''A))
(LIST 'SETQ 'L (CONS 'CONS (LIST x 'L))))))
This is hard to get right and impossible to read.
Ten years ago, the solution everyone adopted to this plan was to
use SUBLIS or some such, and write
(SUBLIS (LIST (CONS '*X* x) (CONS '*Y* y))
'(COND ((EQ *Y* 'A) (SETQ L (CONS *X* L)))))
but this is less efficient, and not all that readable itself.
A new solution appeared at about that time. Hewitt's Planner language was supposed to have the opposite convention, that unmarked things were quoted. So the original expression could simply be written
(COND ((EQ <y> 'A) (SETQ L (CONS <x> L))) )
where <y> and <x> depended on the form of y and x. For
example, if y was the variable V1, and x was the expression <+ I 1>
(angle brackets denoted function calls), the whole thing would be
written
(COND ((EQ .V1 'A) (SETQ L (CONS <+ I 1> L))) )
To summarize the idea, we change function calls so we can differentiate them from lists, and we change the usual Lisp convention so that symbols evaluate to themselves unless preceded by a dot, a la Bliss. (The 'A could therefore be written as A alone.) The new convention was adopted by the MDL language, still in use at MIT.
This revised convention did not catch on. (Perhaps the angle brackets
were more unsettling than the peaceful curves of parentheses.) However,
Gerry Sussman and I adopted a revised form of it for the Conniver
programming language. Within the context of a !", everything was
quoted except things marked with an "@". (The intention was to remind
you of indirection on a PDP-10.)
So the expression could be written as
!"(COND ((EQ @y 'A) (SETQ L (CONS @x L))) )
This proved to be the right idea. It made quasi-quoting@Foot{A term
due to Quine}
optional,
and in a consistent way. We also had a prefix !@, which caused the value
of its argument to be spliced in. So if X = (A B C),
!"(1 @X 2 !@X 3 . @X)
would evaluate to (1 (A B C) 2 A B C 3 A B C).
Unfortunately, in Lisp's inimitable way, it soon developed two different versions of quasi-quote. I will sketch both, and argue that one is better.
I took quasi-quote to Yale in 1976. In 1980, it appeared in @i[Artificial
Intelligence Programming], by Charniak, Riesbeck, and McDermott, under
the name |", but otherwise the same. Meanwhile, Sussman changed it to
` ("backquote"), and sold it to the rest of the MacLisp community.
He also substituted , for @—so that the COND would now be written
`(COND ((EQ ,y 'A) (SETQ L (CONS ,x L))) )
I think this is prettier, and would adopt it without reservation, except
for my gripes below. He (or some later hacker) made the splicing version
,@—an unfortunate choice, since no one can now keep the two versions
straight, but never mind. In what follows I will assume Sussman's
syntax for both versions.
Sussman also made the code produced a little nicer, but that's a different issue.
Once everyone started using quasi-quote (in one of the two main versions),
an interesting issue popped up. What if you want a quasi-quote to
expand into something to be evaluated, where that thing itself contains
a quasi-quote? This is actually quite common, since one of the prime
uses of quasi-quote is in macros, which often expand to things that
build expressions. For instance, consider PUSH:
(DEFUN PUSH MACRO (EXP)
`(SETQ ,(CADDR EXP) (CONS ,(CADR EXP) ,(CADDR EXP))) )
Why not replace the inner CONS with a quasi-quote? (It's not necessary
here, but for larger expression it definitely would be.) If we do this
replacement, then we suddenly have a miniature combinatorial explosion
on our hands. Every piece of a double-quasi-quoted expression can
suffer one of four fates: not to be evaluted at all; to be evaluated
by the outer quasi-quote, and not again; to be evaluated by the inner
one only; or to be evaluated twice.
For instance, consider (EVAL (EVAL e1)), where
e1 = `(LET ((X 5)) `(FOO #X))
with X = (+ X 2). Here the # stands for some prefix. The empty prefix
should clearly mean "Don't evaluate either time." Here is a table of
all four possibilities:
Prefix Meaning Result
1 Neither (FOO X)
2 Outer only (FOO (+ X 2))
3 Inner only (FOO 5)
4 Outer and inner (FOO 7)
Alas, the two quasi-quotes differ on what prefixes mean what. The MacLisp
quasi-quote takes the following position: Comma takes you out of one
quasi-quote, i.e., suppresses one level of quasi-quoting, i.e., exposes you
to evaluation for the innermost level. Therefore, one comma means
"evaluate on inner only" (case 3). Two commas take you out of
two quasi-quotes, and expose you to evaluation for the last two levels.
Therefore, ",," means "evaluate twice" (case 4).
The Yale quasi-quote takes the following position: Comma suppresses the current quasi-quote, regardless of where it occurs in that quasi-quote. The existence of other quasi-quotes between you and the outermost is irrelevant. Therefore, one comma means "evaluate on outer only" (case 2).
So the table looks like this:
Prefix Meaning Result MIT Yale
1 Neither (FOO X) X X
2 Outer only (FOO (+ X 2)) ? ,X
3 Inner only (FOO 5) ,X ?
4 Outer and inner (FOO 7) ,,X ?
We see immediately that the two conventions are incompatible, and that they
leave gaps to be filled. The MacLisp convention can fill its gap without
any more machinery, by using the following trick: we expose X to
evaluation in such a way that it gets protected on the next iteration. The
proper prefix is ",'," . The explanation is this: The first comma exposes
you to the inner EVAL. The second exposes X to the outer EVAL. So X is
evaluated once, giving, in the example, (+ X 2). But then a quote is
wrapped around it, giving '(+ X 2), which is evalated, giving (+ X 2).
The Yale solution is, I think, nicer. The problem for my version is
"send a comma into a quasi-quote." That is, I want a convention
whereby I can produce an expression of the form ",e" inside a targeted
inner quasi-quote. The convention is this: If a comma is to be
left untouched by the outer quasi-quote, put a backquote right after it.
So the table gets filled out thus:
Prefix Meaning Result MIT Yale
1 Neither (FOO X) X X
2 Outer only (FOO (+ X 2)) ,',X ,X
3 Inner only (FOO 5) ,X ,`X
4 Outer and inner (FOO 7) ,,X ,`,X
There is no other reason one would ever write ",`"—it would be a no-op.
We can think of ",`" as meaning "send this comma on through to the next
quasi-quote." E.g., ,`,X expands to ,(+ X 2) on the first EVAL, because
the ,X expand to (+ X 2), and the ,` expands to ,. Whereas ,`X expands
to ,X on the first EVAL, because the X expands to X, and ,` expands to ,.
It's all consistent and logical.
It occasionally occurs that you want to embed quasi-quotes to three levels.
The Yale convention generalizes quite cleanly. A comma followed by n
backquotes means "evaluate on the n+1 st level." ,X still means outer
only. To evaluate on the first and third, but not the second, you write
,``,X. ,`` tells you to evalute on the third round, and , tells you to
evaluate on the first. Note that the Yale convention is additive: to
evaluate on a set of levels, you string together the prefixes for each
level. What could be cleaner?
By contrast, the MacLisp convention relies on a trick that is hard
to explain or generalize. It is easy to evaluate on every level --
just pile up the commas. But finer control requires carefully
synchronizing commas and quotes. I conjecture that evaluating on
the first and third levels would require ,,',X.
I am curious to hear people's opinions about this issue. Perhaps it is not too late to change the way quasi-quote works.
Date: 10 March 1982 00:13-EST
From: Alan Bawden <ALAN at MIT-MC>
Subject: Quasi-Quote
To: Rees at YALE, Mcdermott at YALE
cc: ALAN at MIT-MC, KMP at MIT-MC, Riesbeck at YALE
Here is everthing I know about backquote. (Hold on, there is quite a bit of it...)
History:
I first saw backquote when I joined the LispMachine project in the summer of 1977. At that time the characters in use were:
"`" start quasi-quote
"," evaluate element
",," evaluate and splice in list (",@" today)
",," was used because no one in the LispMachine group believed that nested
backquotes "worked right", so there was no need to ever write two commas in a
row. There was even a comment in the source of the defstruct macro in the
place where nested backquotes should have been used that said that nested
backquotes were "broken".
I was intrigued by this piece of hair and set out to fix whatever bug it was that caused nested backquotes to be broken. After figuring out just what it was that nested backquotes might do when they were working, I determined that this was in fact exactly the behavior they exhibited. (At the time backquote was only about a half-page or so of code.) The problem was simply that no one had been able to make nested backquotes do what they wanted, not that there was any fixable "bug". Since there was nothing for me to fix about backquote I set out to convert the LispMachine source (and programmers) to the use of nested backquotes.
This presented a problem because of the choice of ",," to indicate splicing.
It was agreed that since nested backquotes did in fact work, we would choose
some other character to indicate splicing. (In those days it was still
reasonably easy to make a global change to the entire LispMachine source.)
At about this time, perhaps even prompted by our need to choose a new ",,", Guy
Steele made an elaborate proposal for a backquote facility that allowed the
programmer to control many aspects of backquote's operation. This proposal
included things like "`?" and "`!" which were backquote variants that did
things like consing a completely new structure each for evaluation (instead of
the usual sharing), etc. I don't remember too much about this proposal, it may
be the source of ",@". Perhaps if we are going to grovel around in the history
and theory of backquote, this would be a good thing to retrieve.
Also at about this time, SCHEME was influencing the LispMachine project
somewhat (we borrowed IF from them for example), and my memory is that they
were using just "@" to indicate splicing. Perhaps this is where the at-sign
came from. (We wouldn't have ever gobbled a third character for this purpose,
it had to be ",<something>".)
I personally thought ",." would be a clever idea since then there wouldn't be
any difference between `(a .,b) and `(a ,.b). Dave Moon persuaded me that this
would be a bad idea on the grounds of too much meaning in too little ink, and
we eventually agreed on ",@".
Much later when many of the LispMachine macros and features were migrating back
into MacLisp an additional backquote feature was added. It was felt that we
needed a way to cause "`" to generate code that called nconc rather than append
in the splicing case. At this time, unaware that the LispMachine group had
rejected ",." as unreasonable to mean anything, the MacLisp maintainers chose
it for this purpose. (Presumably they also though it was clever.)
(I like to explain ",." as being exactly like ",@", the "." is just a
declaration to the backquote expander telling it that the list returned by the
following form is expendable, and that it is therefore free to use nconc or
nreverse or rplaca or anything else destructive to build the requested list
structure.)
Somewhere between the summer of 1977 and the present, I completely rewrote
backquote to produce more readable, and more compilable, code. (The function
list* was introduced for this purpose.)
Sussman had nothing to do with any of this. As far as I know, I am responsible for the idea of improving the code that backquote expands into (and its implementation). I have never seen Sussman use backquote for anything, and I would guess that this is one example of the kind of hair that he now completely aviods.
A Controversy:
I was only aware of one controversy about backquote until I saw your suggestion
for ",`". That is the one between those of us who believe that backquote
should be as stingy and clever as it can about sharing structure between
individual calls, and those people who believe that backquote should always
make complete copies. I'll summarize my argument (stingy) and leave it to KMP
to present the other side if he desires.
Given a backquoted expression like `(a ((x) ,b y) c) both sides agree that it
is hard in general to tell just by inspection where the sharing is going to
occur (given a stingy backquote). It becomes even harder to tell when you have
to deal with nested backquotes.
Well, just why would you care about sharing? In 95% of the cases you are using backquote to cons up a piece of code and you are perfectly happy to share as much as possible. The only issue is what happens if you want to side-effect some list-structure created by backquote. Well, simply don't do that! Even if you are 100% certain that the cons you are rplacing must have been created fresh by backquote, all the poor people that are going to have to read your code are going to have to convince themselves of this as well, and it is a hard problem (as we all agree).
Better you should insert an explicit call to the function cons to assure yourself that a fresh cons is always made, and to document your code to that effect. (I would thus argue that using nested backquotes in the push macro is probably a bad idea, because you really want to emphasize that you are making a fresh cons at that point. You should not leave it implicit.)
The other side argues that since it is hard to tell if you are sharing, you simply shouldn't. I don't believe that it is worth the extra consing in every macro in the world in order just to allow some people to write obscure code.
Expansion Time and Nesting:
The MIT backquote is defined something like this (not worring about ",@" and
",."):
(setsyntax #/, 'macro '(lambda () (list '*%comma%* (read))))
(setsyntax #/` 'macro '(lambda () (backquotify (read))))
where backquotify is a function that performs a tree walk looking for lists of
the form (*%comma%* <form>) and returns a piece of code that conses up such a
tree with the values of the various <form>'s substituted in.
This is the way that it works at MIT. Notice that since the function
backquotify is called at READTIME, inner backquoted expressions are expanded
first. Thus they encounter outermost (*%comma%* ...) lists when they tree
walk.
Now the Yale backquote could be defined as follows (I don't know how you really
do it of course) (ignoring ",`" for the moment):
(setsyntax #/, 'macro '(lambda () (list '*%comma%* (read))))
(setsyntax #/` 'macro '(lambda () (list 'backquote (read))))
(defmacro backquote (x)
(backquotify x))
Now, backquote is a macro that calls the function backquotify at EVALUATION time (well macroexpand time actually). This means that the outermost backquoted expression will be backquotified first rather than the innermost. Thus, outermost backquotes will find outermost commas when they tree walk.
I suspect that this is approximately how the Yale version actually works
(modulo the ",`" hack), I'd be curious to know how close I am. The MIT MacLisp
version actually operates at macroexpand time, but the backquotify function is
careful to simulate the effect of doing it at readtime. The LispMachine
version works at readtime.
Triple Nesting:
Examples of true triply nested backquotes are hard to come by. All of the examples I have seen use the third level of backquote to actually construct a piece of data rather than a piece of code. This makes them all subject to the same criticism I have of using doubly nested backquotes in the push macro. I have included a piece of mail at the end of this message that contains an example of this kind of triple nesting due to Steele.
Nested ",@"s:
That same piece of mail is mostly about the following wierd construct that
Steele used in his example: ",,@". I'll not comment more on this subject here
since the included message is as far as I have gotten in my thinking on this
issue. You might consider what stand the Yale backquote wants to take on this
problem.
The Yale ",`" Kludge:
I feel justified in calling this a kludge since the MIT backquote has just been explicitly labeled the "Wrong Way" and implicitly accused of being inconsistent, illogical and unclean. My rebuttal:
-
The fact that the MIT backquote needs no extra mechanism to deal with double nesting speaks for itself I think.
-
The MIT backquote is referentially transparent in the following way:
What does `(list ',x) mean? Well, at MIT it means the same thing as
(list 'list (list 'quote x)). At Yale we are told, the meaning depends on
whether or not it appears within a higher level of backquote or not. If there
is no surrounding backquote, then it means the same as before, but if it is
surrounded by another backquote then it means quite something else.
Thus, if I write a function:
(defun make-singleton-lister (x)
`(list ',x))
and start using it in my code, and if later I decide that I really only need to do this once, I cannot simply move the body of that definition into where it is needed. I have to make sure I am not accidentally moving it into the scope of another backquote. At MIT I needn't worry.
- The MIT backquote is not any more difficult to explain. The real difficulty stems from the fact that quasi-quoting is hard to think about no matter where you are (MIT or Yale). The MIT backquote may even be easier to explain given the property noted in 2 above. Since I know that
`(a ,b ,<whatever> ,<moreever>)
ALWAYS means
(list 'a b <whatever> <moreever>)
I can immediately tell you that
``(a ,b ,,c ,',d)
means
`(list 'a b ,c ',d)
That is logical, consistent, and clean!
Backquote Mania:
Here is the message about triple nesting and ",,@" I mentioned above:
— Begin included message —
Date: 16 January 1982 01:47-EST
From: Alan Bawden <ALAN at MIT-MC>
Subject: Backquote mania!
To: DLW at MIT-MC, MOON at MIT-MC, GSB at MIT-MC, Guy.Steele at CMU-10A
Date: 15 January 1982 2140-EST (Friday) From: Guy.Steele at CMU-10AHere is a perhaps plausible example:
(defmacro define-record-type (name . selectors) `(progn 'compile ,@<loop to make selector DEFMACROs> (defmacro ,(symbolconc 'make- name) (&rest x) ;constructor macro ``(,',',name ,,@x))))The "
,','," is fairly obvious, but it took me a few tries to get the ",,@" right. (I tested this.)
Sure enough!
But I don't understand ",,@". It has no right to work at all!
Consider:
`(a ,n c) = (list 'a n 'c)
This always makes a list of three things right? Well, maybe not, because inside a backquote this:
`(a ,,@x c) = (list 'a ,@x 'c)
makes a list whose length depends on what x turns out to be! If you
don't think that this is strange, consider what backquote would be
like if we didn't have lexprs. In that alternate universe we might
have:
`(a ,n c) = (cons 'a (cons n '(c)))
which works fine until some hacker tries ",,@":
`(a ,,@x c) = (cons 'a (cons ,@x '(c)))
See? When we evaluate the outer backquote the value of x had better
be a list of exactly ONE form or we will get an error! (Not
immediately, but later when the inner backquote is evaluated.)
",,@" only "works" because backquote USUALLY uses lexprs in the code
it conses up (LIST, APPEND, NCONC)! Currently the LispMachine
backquote occasionally calls CONS instead of LIST*, so for example:
`(,,@x a) = (cons ,@x '(a))
on the LispMachine.
Does this mean that simply assuring that backquote always calls the
lexprs will make ",,@" meaningful? Maybe, but if ",,@" is going to
work, why not ",@,@"? Currently, in all backquote implementations I
know of:
(setq x '(n m) n '(b c) m '(d e))
(eval ``(a ,@,@x f)) => (A B C D E F) ;Right (I think)
(eval ``(a ,@,@x)) => (A (B C) D E) ;Wrong (I hope)
Which is a consequence of the fact that the last argument to LIST*
isn't like the rest of them, so (list* 'a ,@x) does something
novel. The correct expansion would thus seem to be:
`(a ,@x) = (list* 'a (append x))
(which we hope some compiler optimizes I guess) so that:
`(a ,@,@x) = (list* 'a (append ,@x))
Hard to think about!
— End included message —
I hope I haven't flamed on to far about all this stuff. I seem to have acquired a fair amout of knowledge on the subject over the last 5 years or so.
— Alan
Date: 10-Mar-82 1752-EST
From: Drew McDermott <Mcdermott at YALE>
Subject: Quasi-quote
To: Alan at MIT-MC
Cc: Riesbeck at YALE, Rees at YALE, Kmp at MIT-MC
-
Thanks for the history. I recall under prompting that Sussman did indeed use
"-,-@instead of`-,-,@. My other recollection, that he improved the code, is from a phone call where he mentioned that he had invented "maximal quoting," or what you call sharing. The original Conniver quasi-quote didn't do this. -
The sharing controversy: I entirely agree with you. Quasi-quote should feel free to do any optimization, on the assumption that the only destructive transformations on the result will leave the value the same (as in macros). The benefit from this is that these optimizations can be extensive. The only loss is that the code that builds rplac-able structures can be less concise. But (a) such code is usually small anyway; and (b) rplac-able structures and S-expressions are two entirely different kinds of objects, both of which just happen to be built out of cons-cells in Lisp; having them constructed by different-looking code is an advantage. (In fact, I follow the convention that list, cons, etc. are used solely for building "records," while quasi-quote is used solely for building "expressions." This is a useful sort of self-documentation.)
-
Your conjecture about MIT's backquote being expanded at read time, while Yale's is expanded at eval time, is correct. However, the version in Charniak et al. expands at read time, and, as far as I know, doesn't handle nested quasi-quotes.
There is another, rather quaint, reason to prefer eval-time expansion. Due to sins in a prevous life, I have recently been using Franz on Vax/VMS. In this system, Interlisp-style in-core editing is necessary, since you can't get to a real editor without killing the Lisp (as far as I know). The Franz backquote, which expands at read time, is completely useless in this context, since when you go to edit your code you see the impenetrable junk backquote was designed to avoid.
Of course, if you do character editing, as God intended, this is irrelevant.
- "Kludge" vs. "Wrong Way": I find revealing your comment about embedded
back-quotes being intrinsically difficult to understand. I used to find
them hard, because I was producing them with kludges like
(,'*comma* ,x)[where,xbecomes(*comma* x)]. After I introduced ",`,x", which expands into the above without your having to know what any of it expands into, my conceptual difficulties cleared up. For instance, Steele's example becomes
(defmacro define-record-type (name . selectors)
`(progn 'compile
,@<loop to make selector DEFMACROs>
(defmacro ,(symbolconc 'make- name) (&rest x) ;constructor macro
``(,name ,@``x) )))
The ,@ is told to survive until the innermost backquote, by putting two
backquotes after it.
Referential transparency cuts both ways. It all depends on whether you're
counting outside in or inside out. From the outside in, it is irritating
that ",x" might mean "the value of x," or "x," depending on whether it
occurs inside another quasi-quote.
In the example, the occurrence of ,name means the value of name -- the meaning is independent of the immediate context. We don't have to tell the system to quote the result from then on—the innermost quasi-quotes do that for us; quasi-quote always means quasi-quote!
Outside-in Transparency (me) is transparent "at the comma level." That is,
inside a quasi-quote, ,x always means the same thing. Inside-out
Transparency (you) is transparent "at the backquote level." A backquote
expression always means the same thing. The reason that I prefer my
approach is that >> I don't want want to have to think at all about what an
embedded backquote expression means. << In Steele's example, it's not
clear to me that `(,',',name ,,@x) means anything at the start. It's
only going to mean something when its pieces are plugged in. I don't want
it to get in the way of said plugging. Just because it's a backquote
itself doesn't give it the right to interfere in the process of backquote
instantiation.
Chris Riesbeck has pointed out that the MIT hack is not as bad as I made it
sound. There is a weird logic in ,,',x meaning: "eval-quote-eval." The
problem, I guess, is ,x. It should be written ,,'x ("quote-eval") to fit
the convention. It just seems counterintuitive to abbreviate this way.
- I'll let you know before releasing anything inflammatory to SIGART. Any suggestions on presentation?
Date: 10-Mar-82 1833-EST
From: Drew McDermott
Subject: Egg on face
To: Alan at MIT-MC
Cc: Riesbeck at YALE, Rees at YALE, Kmp at MIT-MC
As soon as I sent my latest missive on quasi-quote, I realized I had gotten Steele's example wrong, which is just great as evidence for my claim that quasi-quote is easy to understand. In fact, there is no way at all to get my quasi-quote to do the job, roughly because my quasi-quote already believes your argument that it's impossible.
The closest I can come is:
(defmacro define-record-type (name . selectors)
`(progn 'compile
,@<loop to make selector DEFMACROs>
(defmacro ,(symbolconc 'make- name) (&rest x) ;constructor macro
`(list ,name ,@`x) )))
And, of course, we can't go one step further, because we don't want
either to evaluate or quote the result of @`x. Instead, we want to
evaluate each of its elements.
Well, you're half right—this use of embedded quasi-quotes is certainly hard to understand.
;;;-*-Lisp-*-
(setsyntax #/, 'macro '(lambda ()
(cond ((= (tyipeek) #/`)
(tyi)
(list (list '/, ''/,) (read)))
(t (list '/, (read))))))
(setsyntax #/` 'macro '(lambda () (list '/` (read))))
(defmacro /` (x)
(backquotify x))
(defun constant? (x)
(if (atom x)
(or (null x)
(eq x t)
(not (symbolp x)))
(eq (car x) 'quote)))
(defun constant (x)
(if (atom x) x (cadr x)))
(defun backquotify (x)
(cond ((atom x) (list 'quote x))
((eq (car x) '/,) (cadr x))
(t (let ((a (backquotify (car x)))
(d (backquotify (cdr x))))
(if (and (constant? a) (constant? d))
(list 'quote (cons (constant a) (constant d)))
(list 'cons a d))))))
(defun f (x)
`(lambda (y)
`(lambda (z)
(list ',x ',`y z))))
(defun g (x y z)
(funcall (funcall (f x) y) z))
Date: 13 March 1982 01:54-EST
From: Alan Bawden <ALAN at MIT-MC>
Subject: Quasi-quote
To: Mcdermott at YALE
cc: ALAN at MIT-MC, MOON at MIT-MC, KMP at MIT-MC, Riesbeck at YALE,
Rees at YALE
Ah! Yes indeed, the version of backquote that I started with in '77 already had sharing or "maximal quoting", so it is entirely possible that GJS is responsable for that part of the hack. I must confess that it had never occured to me that that was an idea that had to be discovered.
The version in Charniak et al. looks to me to be exactly an MIT backquote (by
virtue of the fact that it does the tree-walk at read-time). I see no reason
why it shouldn't nest correctly (in the MIT way, that is. ",'," and all that).
I am aware of the argument for eval-time expansion that it can be correctly
printed by pretty-printers etc. This is the reason that the PDP10 MacLisp
version does its expansion at eval-time. There is however an alternative
read-time solution to that problem, which the LispMachine version employs.
LispMachine backquote expands into calls to functions like backquote/'s-list*
instead of the regular list*. Then grindef and other pretty-printers know how
to invert (backquote/'s-list* 'a b '(c d)) and print it as "`(a ,b c d)". This
is an idea with problems, and the current LispMachine implementation of this
has additional problems. I think I think that it is a kludge, and I mention it
only for completeness.
I did not intend to imply that the intrinsic difficulty in understanding nested
backquotes was insurmountable. I no longer have any trouble dealing with them
even three levels deep. (Especially now that I have figured out how nesting
interacts with ",@".) I only refered to the difficulty of the subject (and you
have to admit that the topic presents difficulties, otherwise you and I
wouldn't be able to generate this much text) as an explanation for why it might
SEEM that an unfamiliar version of backquote was hard to explain.
Your observation about referential transparency cutting both ways...
Well there is definitely SOMETHING here that cuts both ways. It is indeed the case that there is a "counting from the outside" vs. "counting from the inside" property here. I was going to point that out myself to demonstrate how MIT backquote nesting could be explained in a similar way to the way you were explaining your backquote nesting. You count evaluation times as the "first time", "second time", etc. where at MIT we count "last time", "second-to-last time", etc. But I decided that that wasn't really what either of us was really talking about.
Perhaps you indeed also have a kind of referential transparency here (maybe there is even a dual kind of relationship between the two of them), and perhaps we are both defending equally valid styles, but the temptation for me to try and convince you that my-way-is-better-than-your-way is too great...
I would claim that MIT backquote enjoys the same kind of referential
transparency as the lambda and predicate calculi. (Thus putting logic on my
side (!).) A lambda expression like (lambda (x) (f x)) has the property that
the second occurence of x always refers to the "binding" of the first occurence
of x, regardless of the placement of the expression within other expressions.
This is similar to `(foo ,x) where the comma refers to the backquote regardless
of the placement of the form withing other forms. Your kind of referential
tranparency, where `(foo ... ,x ...) pairs the backquote and the comma
regardless of what is placed BETWEEN them (like replacing the elipsies with
"`(bar" and ")" respectively), would be analogous to ruling that all occurences
of a variable x in the body of a lambda must refer to the binding of the
outermost x, regardless of any intervening lambdas using the same variable.
(I think I have an idea of a refutation for that last paragraph...)
Here is an experiment to try with your implementation of backquote. Consider the following functions (MIT backquote):
(defun f (x)
`(lambda (y)
`(lambda (z)
(list ',',x ',y z))))
(defun g (x y z)
(funcall (funcall (f x) y) z))
It's fairly clear what f and g do, I think. And I think you will agree that
one would expect that (g 'a 'b 'c) => (a b c), and that in general g should
behave sort of like a three-argument version of list.
Well translate f into Yale backquote:
(defun f (x)
`(lambda (y)
`(lambda (z)
(list ',x ',`y z))))
(This is correct, right? I think It loses some of its symmetry in the translation... perhaps I should use that as an argument for my side?)
Now try the following experiment with f and g:
(setq a (f 'foo)) ;make some function...
(LAMBDA (Y) ...)
(setq b (car (g a 1 2))) ;make a three list, and extract the function
(LAMBDA (Y) ...) ;back out.
(funcall (funcall a 'bar) 'baz) ;try out the original version.
(FOO BAR BAZ) ;right.
(funcall (funcall b 'bar) 'baz) ;try out the new one.
(FOO 1 BAZ) ;do you get this?
That last bogus answer is what my quick-and-dirty Yale-style backquote gets, and I don't see how you can easily avoid it in yours. (I am not trying to use this as an argument pro or con anybody's backquote. Just pointing out a potentially interesting phenomenon.)
— Alan
Date: 14 March 1982 01:24-EST
From: Kent M. Pitman
Subject: A few comments on Quasi-Quote and related issues
To: ALAN at MIT-MC
cc: MOON at MIT-MC, KMP at MIT-MC, Mcdermott at YALE, Riesbeck at YALE,
Rees at YALE
Alan,
I don't think counting outward (a la MIT) is as much the dual of counting inward (Yale) as for fairness you have tried to cede. It isn't that Yale is counting inward and we are counting out. Eg, if you insert into a piece of backquote structure
`(a ,(b c) `(d ,e ,',f))
a new piece of structure with more backquotes,
`(a ,(b c) `(d ,e ,',f `(g ,h)))
then the f and e are not now being evaluated differently even though
they are the second backquote context from the ‘middle’ instead of
the innermost. That would be the ‘dual’ of the Yale system.
The difference is the difference between absolute and relative
labeling. The MIT backquote structure preserves the property that
if there is some piece of code surrounding that which you see, it
will not affect the differential analysis about evaluation in the
relative rings of backquote context about any given point in the code.
eg,
(a `(e ,f))
means f and a are evaluated in the same context, regardless of what that context is (ie, whether there are surrounding contexts).
In defense of the current system, I should point out that the LMS/XLMS system that Bill Martin/Lowell Hawkinson were working on until recently used to use outside relative (ie, absolute) references for their colon anaphor syntax—
[a :]
referred to a structure which was the same as [a [a [a ...]]],
and [a [b :]] referred to [a [b [a [b ...]]]] and [a [b ::]]
meant [a [b [b [b ...]]]]—unless you put it inside a
[c ...], because then [c [a [b ::]]] meant not [c [a [b [b ...]]]]
but [c [a [b [a [b ...]]]]]. Sou you could never look at an isolated
piece of structure independent of knowing what its outermost point
was, and you could never trivially pick up a piece of text containing
anaphors and move it inside another because its meaning would change.
They finally found it to be too non-transparent, and adopted relative
anaphors, so they moved to a syntax (^'s or some such), which meant the
innermost [ ... ] ring was referred to be an ^. So you had to write ^^ to
talk about two levels out. (I actually don't know if it was ^'s, but the
concepts I know are right.) So, [a [b ^]] meant [a [b [b [b ...]]]] and
[a [b ^^]] meant [a [b [a [b [a [b ...]]]]]], and if you put it inside
another piece of text [c ...], then [c [a [b ^^]]] still meant
[c [a [b [a [b ...]]]]], which was nice. This argues that reading
from the inside out is not the only way MIT people have ever viewed the
world (hence making it not a Yale vs MIT thing, which I hate for these
discussions to wind up being), and saying that it may not be as symmetric
as it might appear. There is a lot to be said for being able to move
backquote expressions into other non-interfering backquote contexts without
having to re-write them; this is something the relative, but not the
absolute counting scheme provides.
That's all I have to say for now. I'll sit back and listen awhile again, as I think you're doing a good job in defense of most views I have on the subject. (Where you and I differ on backquote philosophies are relatively minor and not relevant to this discussion.)
— kmp
Date: 14-Mar-82 1749-EST
From: Drew McDermott
Subject: Stop me if this is boring you...
To: Alan at MIT-MC
Cc: Riesbeck at YALE, Rees at YALE, Kmp at MIT-MC
I think the backquote controversy is converging on enlightenment in my brain—unhappy fate for any controversy. I can't really see that this is worth sending to anybody's newsletter. For one thing, multiply-embedded backquotes are so rare that the whole thing is a tempest in a teapot. All but the most fanatic simply have to know where to look up what the prefixes mean when they run into them.
That aside, more of my thoughts:
- This point of yours --
A lambda expression like
(lambda (x) (f x))has the property that the second occurence ofxalways refers to the "binding" of the first occurence ofx, regardless of the placement of the expression within other expressions. This is similar to`(foo ,x)where the comma refers to the backquote regardless of the placement of the form withing other forms. Your kind of referential tranparency, where`(foo ... ,x ...)pairs the backquote and the comma regardless of what is placed BETWEEN them (like replacing the elipsies with "`(bar" and ")" respectively), would be analogous to ruling that all occurences of a variablexin the body of a lambda must refer to the binding of the outermostx, regardless of any intervening lambdas using the same variable.(I think I have an idea of a refutation for that last paragraph...)
is not bad. Is this the refutation you had in mind?—A quoted lambda exerts no such influence over the things inside it. It's just a symbol. It comes down to whether every uncomma'd thing inside a backquote is quoted—even backquotes.
- Your
f-gexample was ingenious. You could have gone one step further, to
(defun f (x) (defun f (x)
`(lambda (y) vs. `(lambda (y)
`(lambda (z) `(lambda (z)
`(,',',x ,',y ,z)))) `(,x ,``y ,``z))))
which shows the notational duality nicely. In this case,
(funcall (funcall (car (g a 1 2)) 'bar) 'baz)
is (foo 1 2).
Does this hurt my case? I don't think so. It just shows once more that building lambda expressions, instead of enclosing them, is a lousy model of building functions. Put another way, textual substitution is a lousy model of variable binding.
- Besides, and this is where the enlightenment comes in, the fact that yours "works" and mine doesn't in this case has nothing to do with the inside-out vs. outside-in distinction, and everything to do with whether expansion occurs at read time or eval time. I threw together a new version of quasi-quote that applied Yale conventions at read time, and it did exactly what yours did. The explanation is clear: if you expand at read time, then the result doesn't look any different from a random piece of lisp. If you expand later, you've got to mark pieces of the quasi-quote as being "unquoted," and then the potential for ambiguity creeps in. In this case, the ambiguity screws my quasi-quote. But there must be dual cases where it screws yours, where you send a marked thing into a context which wraps an unforeseen quasi-quote around it.
Which brings us to
- The only empirical evidence that could bear on the quasi-quote question is a tally of how often people a) wrap quasi-quotes around subpieces of existing quasi-quotes b) move entire quasi-quotes inside other quasi-quotes Since as far as I know I have never done either, I'm afraid that the question has no empirical significance. It all comes down to what you're used to. After this little dialogue, I'm now used to both of them.
Date: 16 March 1982 01:03-EST
From: Alan Bawden
Subject: Stop me if this is boring you...
To: Mcdermott at YALE
cc: ALAN at MIT-MC, KMP at MIT-MC, Riesbeck at YALE, Rees at YALE
I must agree that nested backquotes are not a very vital controversy. I believe, however, that backquote problems must reveal something about the nature of quotation that is not otherwise apparent.
I expected a refutation for my lambda-expression argument to be based on the following observation:
The parallel between variable binding in the lambda calculus and backquote
"level binding" is only completely parallel in the case where your
lambda-expressions are restricted to only mention the single variable "x".
In other words, when nesting lambda-expressions you always have the option to
use a NEW variable, while when entering a new level of backquote you are forced
to rebind a single (implicit) variable. We could give backquote variables by
allowing a "[" after a "`" or a "," to introduce a subscript that would tell us
how to match the backquotes to the commas:
(defun f (x)
`[1](lambda (y)
`[2](lambda (z)
`[3](,[1]x ,[2]y ,[3]z))))
The fact that you lack this freedom to name levels of backquote might be used to somehow argue against me. (I don't perceive a full argument.)
Two points about the f-g example:
You are right that introducing the third level of backquote makes both our
backquotes look symmetrical (not just mine). Unfortunately the fact that I
used the function "list" in the innermost lambda is a coincidence, I could have
used "+" instead and then there would be no way for your backquote to look as
symmetric as mine.
Indeed, the fact that I was able to find a bug in your implementation (I THINK that that is a bug at least), doesn't mean anything about whose backquote works better than whose. Mostly it demonstrates that I have debugged enough versions of backquote that I am now totally familiar with the various subtle screws. Any kind of backquote that works at macroexpand time runs the risk of having simething like this kind of bug. (I believe that the PDP10 MacLisp one has had them all flushed by now, all the other backquotes I know of expand at read-time and thus sidestep this screw.)
Oh, well. We seem to have wrung this issue out now.
— Alan