Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Language definition

24 views
Skip to first unread message

Dan Weinreb

unread,
Jan 19, 2009, 10:59:58 AM1/19/09
to pit...@nhplace.com
The key issue here is whether two uses of backquote can return the
same result.

The HyperSpec, as I read it, is less than 100% clear on this.

In the "summarize formally" section, item 3, it says that the
top level list structure must be new. It says that

`(a ,b ,@c)

must have the semantics of

(append (list (quote a)) (list b) c)

It is 100% clear that append and list generate new list structure.

But later, the HyperSpec says:

An implementation is free to interpret a backquoted form F1 as any
form F2 that, when evaluated, will produce a result that is the same
under equal as the result implied by the above definition, provided
that the side-effect behavior of the substitute form F2 is also
consistent with the description given above. The constructed copy of
the template might or might not share list structure with the template
itself.

There are examples, although none of them fails to
generate new list structure at the top level.

In any case, it seems to me that the example must
return nil, and indeed there is a bug in any CL
implementation that doesn't do that.

For better or for worse, there is no Supreme Court of Common
Lisp to rule on such questions of scriptural interpretation.
It's certainly a bad thing that the implementations do not
all do the same thing, and there's nothing in the spec
that indicates that the answer to the original question is
implementation-dependent.

Pascal J. Bourguignon

unread,
Jan 19, 2009, 12:12:16 PM1/19/09
to
Dan Weinreb <d...@alum.mit.edu> writes:

> The key issue here is whether two uses of backquote can return the
> same result.
>
> The HyperSpec, as I read it, is less than 100% clear on this.
>
> In the "summarize formally" section, item 3, it says that the
> top level list structure must be new. It says that
>
> `(a ,b ,@c)
>
> must have the semantics of
>
> (append (list (quote a)) (list b) c)
>
> It is 100% clear that append and list generate new list structure.


Here, "the semantics" means EQUAL, as:

> But later, the HyperSpec says:
>
> An implementation is free to interpret a backquoted form F1 as any
> form F2 that, when evaluated, will produce a result that is the same

> under EQUAL as the result implied by the above definition, provided


> that the side-effect behavior of the substitute form F2 is also
> consistent with the description given above. The constructed copy of
> the template might or might not share list structure with the template
> itself.
>
> There are examples, although none of them fails to
> generate new list structure at the top level.
>
> In any case, it seems to me that the example must
> return nil, and indeed there is a bug in any CL
> implementation that doesn't do that.
>
> For better or for worse, there is no Supreme Court of Common
> Lisp to rule on such questions of scriptural interpretation.
> It's certainly a bad thing that the implementations do not
> all do the same thing, and there's nothing in the spec
> that indicates that the answer to the original question is
> implementation-dependent.

(EQUAL '(0) (append (list (quote 0)) (list) nil)) --> T
;^^^^^

therefore any implementation is free to return always the same cons in
that case.

--
__Pascal Bourguignon__

Kaz Kylheku

unread,
Jan 19, 2009, 5:24:19 PM1/19/09
to
On 2009-01-19, Dan Weinreb <d...@alum.mit.edu> wrote:
> The key issue here is whether two uses of backquote can return the
> same result.
>
> The HyperSpec, as I read it, is less than 100% clear on this.
>
> In the "summarize formally" section, item 3, it says that the
> top level list structure must be new. It says that
>
> `(a ,b ,@c)
>
> must have the semantics of

Put your reading glasses back on, Dan!. The actual text uses the words ``may
be interpreted'', repeatedly! No ``must have''.

I can't find exact phrase ``must have'' anywhere in section 2.4.6.

There is but one occurence of the term ``must'', which gives the requirement
that FORM inside `(... FORM ...) must be treated as `FORM and further
interpreted. The word ``shall'' does not occur in the section.

The obvious intent is to provide a reference guide for determining what shape
of object is computed by a backquote, without actually /requiring/ that exact
interpretation. The word ``may'' does not introduce an obligatory requirement.

The description with APPEND and whatnot gives the abstract semantics, so
that there is a clear reference model for determining the shape of what object
is produced by a backquote, not to constrain the actual semantics.

> For better or for worse, there is no Supreme Court of Common
> Lisp to rule on such questions of scriptural interpretation.

Of course there is. This is it!

Objections overruled. Case dismissed.

Daniel Weinreb

unread,
Jan 19, 2009, 6:18:32 PM1/19/09
to
Kaz Kylheku wrote:
> On 2009-01-19, Dan Weinreb <d...@alum.mit.edu> wrote:
>> The key issue here is whether two uses of backquote can return the
>> same result.
>>
>> The HyperSpec, as I read it, is less than 100% clear on this.
>>
>> In the "summarize formally" section, item 3, it says that the
>> top level list structure must be new. It says that
>>
>> `(a ,b ,@c)
>>
>> must have the semantics of
>
> Put your reading glasses back on, Dan!. The actual text uses the words ``may
> be interpreted'', repeatedly! No ``must have''.

But what does "may be interpreted" mean? In American law,
there's something called "rules of construction", which is
essentially the definition of this kind of language. But
we don't have that here, unfortunately.

>
> I can't find exact phrase ``must have'' anywhere in section 2.4.6.
>
> There is but one occurence of the term ``must'', which gives the requirement
> that FORM inside `(... FORM ...) must be treated as `FORM and further
> interpreted. The word ``shall'' does not occur in the section.
>
> The obvious intent is to provide a reference guide for determining what shape
> of object is computed by a backquote, without actually /requiring/ that exact
> interpretation. The word ``may'' does not introduce an obligatory requirement.

I don't think it's that obvious. It might mean that. It
doesn't actually say that it means that. I think the
spec is ambiguous/unclear, and there isn't much more we
can say. We have to treat EQ-ness here the same way we
treat EQ-ness of integers, i.e., "don't ask that!".

I hope next time the spec can be written more carefully.

Kaz Kylheku

unread,
Jan 19, 2009, 11:00:11 PM1/19/09
to
On 2009-01-19, Daniel Weinreb <d...@alum.mit.edu> wrote:
> Kaz Kylheku wrote:
>> On 2009-01-19, Dan Weinreb <d...@alum.mit.edu> wrote:
>>> The key issue here is whether two uses of backquote can return the
>>> same result.
>>>
>>> The HyperSpec, as I read it, is less than 100% clear on this.
>>>
>>> In the "summarize formally" section, item 3, it says that the
>>> top level list structure must be new. It says that
>>>
>>> `(a ,b ,@c)
>>>
>>> must have the semantics of
>>
>> Put your reading glasses back on, Dan!. The actual text uses the words ``may
>> be interpreted'', repeatedly! No ``must have''.
>
> But what does "may be interpreted" mean? In American law,
> there's something called "rules of construction", which is
> essentially the definition of this kind of language.

This is from an ANSI standard which has conventions too.

I don't have a copy of the document that defines exactly what ``may'' and
``shall'' mean in an ANSI standard which doesn't explicitly define them, sorry.

I'm reasonably certain though that ``may'' introduces something optional,
and ``shall'' an actual requirement. I seem to have a hazy recollection
from somewhere that ``should'' gives a recommended practice.

Maybe someone who had been involved in standardization, like Kent Pitman, can
help here.

pit...@nhplace.com

unread,
Jan 21, 2009, 9:36:05 AM1/21/09
to
On Jan 19, 11:00 pm, Kaz Kylheku <kkylh...@gmail.com> wrote:
> On 2009-01-19, Daniel Weinreb <d...@alum.mit.edu> wrote:
>
>
>
>
>
> > Kaz Kylheku wrote:
> >> On 2009-01-19, Dan Weinreb <d...@alum.mit.edu> wrote:
> >>> The key issue here is whether two uses of backquote can return the
> >>> same result.
>
> >>> The HyperSpec, as I read it, is less than 100% clear on this.
>
> >>> In the "summarize formally" section, item 3, it says that the
> >>> top level list structure must be new.  It says that
>
> >>> `(a ,b ,@c)
>
> >>> must have the semantics of
>
> >> Put your reading glasses back on, Dan!.  The actual text uses the words ``may
> >> be interpreted'', repeatedly! No ``must have''.

Why focus on only these words? There may not be a huge lot of
flexibility of "must have" but there's quite a bit more flexibility of
what "semantics" here. :) Human language adds additional/
complementary/redundant text in order to make sure things get
overlooked, not in order to create logical contradictions that cause
robots to melt down (as in several star trek episodes) as if logic has
failed them and the universe is now uninterpretable. The fact that
there is additional text elsewhere is (in my view) "obviously" for the
point of clarifying, not for the point of contradicting.

> > But what does "may be interpreted" mean?  In American law,
> > there's something called "rules of construction", which is
> > essentially the definition of this kind of language.
>
> This is from an ANSI standard which has conventions too.  
>
> I don't have a copy of the document that defines exactly what ``may'' and
> ``shall'' mean in an ANSI standard which doesn't explicitly define them, sorry.
>
> I'm reasonably certain though that ``may'' introduces something optional,
> and ``shall'' an actual requirement. I seem to have a hazy recollection
> from somewhere that ``should'' gives a recommended practice.

There's a meaning for "should signal" but not for just "should" by
itself. For (non-binding, obviously) commentary in the word "should"
used in isolation, see a recent blog post of mine at Open Salon...
http://open.salon.com/content.php?cid=64455

Dan Weinreb asked me about this question of backquote in email
recently. I replied to him not realizing it was a comp.lang.lisp
question. If he wants to put up any or all of my reply to him here,
that's fine with me. I haven't the time to go dig it out myself just
now but if no one gets to it, perhaps at some point I'll go find what
I wrote him and put it here. It goes through the whole explanation of
how I would interpret this and why. There are a couple of reasoning
processes that lead to the same conclusion. (The bottom line is that
I believe strongly that you should not assume backquote always conses
freshly ... but that's just one person's [strong] personal opinion.
Heh.)

pit...@nhplace.com

unread,
Jan 21, 2009, 7:46:31 PM1/21/09
to
On Jan 19, 10:59 am, Dan Weinreb <d...@alum.mit.edu> wrote:
...

> But later, the HyperSpec says:
>
> An implementation is free to interpret a backquoted form F1 as any
>
...

> It's certainly a bad thing that the implementations do not
> all do the same thing, and there's nothing in the spec
> that indicates that the answer to the original question is
> implementation-dependent.

Isn't "An implementation is free to interpret..." just another
spelling for "is implementation-dependent"?

pit...@nhplace.com

unread,
Jan 25, 2009, 8:40:23 PM1/25/09
to
On Jan 21, 9:36 am, pit...@nhplace.com wrote:
> On Jan 19, 11:00 pm, Kaz Kylheku <kkylh...@gmail.com> wrote:
>
> > On 2009-01-19, Daniel Weinreb <d...@alum.mit.edu> wrote:
>
> > > Kaz Kylheku wrote:
> > >> On 2009-01-19, Dan Weinreb <d...@alum.mit.edu> wrote:
> > >>> The key issue here is whether two uses of backquote can return the
> > >>> same result.
>
> > >>> The HyperSpec, as I read it, is less than 100% clear on this.
>
> > >>> In the "summarize formally" section, item 3, it says that the
> > >>> top level list structure must be new.  It says that
>
> > >>> `(a ,b ,@c)
>
> > >>> must have the semantics of
[...]

>
> Dan Weinreb asked me about this question of backquote in email
> recently.  I replied to him not realizing it was a comp.lang.lisp
> question.

What follows is the copy&pasted text I had replied in email earlier to
Dan Weinreb:

I think in all cases where you see an ambiguity, you need to reason in
the most conservative way if possible. I think in this case, it means
you cannot rely on there being fresh consing. (I also think that's
the intent, but the intent counts for nothing.)

As a matter of history, when backquote was first introduced, at least
in Maclisp, it did guarantee it would really and truly use LIST and
CONS and whatnot, creating real fresh conses. I foolishly rewrote a
lot of code to expect this. Then a couple weeks later JonL or someone
changed Maclisp to use a different version of backquote that didn't do
this, presumably because of the 256k address limitation--the notion
that extra consing could be tolerated was probably too great. A lot
of people just needed to use backquote for templating and didn't care
about the consing thing. It was suggested that you could use the
(subst nil nil `(...)) trick if you needed all fresh conses; that
became copy-tree in CL, of course. Although it was infuriating to me
to have had this incompatible change thrust on me at the time, I think
the notion that Maclisp backquote did not reliably cons fresh
structure was a decent one. I think the notion that this would make
fresh structure is too subtle.

So both my theory about what should happen and my theory of how to
reason conservatively about ambiguity both align to give you a uniform
theory.

The fact that there is an ambiguity is unfortunate. I don't think it
meant to have the "freshness" implications when it showed the (append
(list ...) ...) example. It was only trying to show you the
connectivity requirements.

I've heard it claimed (and this might be a slight overgeneralization,
not really a theorem but just a good thing to watch for) that every
concrete representation of an idea into code is necessarily over-
specific and has implied semantics that will be unwanted, in addition
to the specific actions you're trying to achieve. So when people
write code as a reference implementation, you'll see lots of artifacts
that they don't really mean, and you need to always be on guard,
asking such questions.

If you believe that theory, it helps you to understand why the code
example might not be in conflict with the (append ...) example but
rather the restriction is a clarification intended to help undo the
necessarily over-concrete aspects of the example, there being no way
of saying (append-but-not-necessarily-freshly (list-but-maybe-shared
'a) (list-but-maybe-shared b) c)

One of the reasons this gets so complicated is what happens in nested
backquote situations, by the way, since those cases need special
optimization. There are cases where the semantics of a two-layer
backquote might totally resolve the backquote after pass1, leaving
something like (list 'a 'b 'c) which really wants to be '(a b c) for
efficiency. If backquote is not permitted to do this, it adds a LOT
of extra consing.

budden

unread,
Jan 26, 2009, 4:29:01 AM1/26/09
to
Hi!
Thanks for history tour. This was a missing chain: I could see a
reason why
backquote should share anything and why there is an ambiguity.
In fact, the problem can be solved this way:
I. Take reference implementation from CLTL2
II. Do not convert bacquote expression read just at readtime, keep it
in a form such as
(bq:bq-list ...). Implementations do so when asked to evaluate '`
(foo ,bar)
III. Add different optimization flags. E.g.

1 = resolve constants, replacing ,const with const
2 = share literal parts of template so that it is always (flet ((f (x)
(cdr `(,x a)))) (eq (f) (f)))
4 = simplify expression structure
8 = Unbox comma-prefixed values. E.g. allow conversion of (bq:bq-list
(bq:comma a)) to (bq:bq-list a)
16 = convert to implementation-specific representation

IV. Add `#s(s field ,val) syntax for greatter expressiveness.
V. Add just one new readmacro. I'd use #w (which I plan to use for
additional multipurpose dispatch sequence). Now
#<sum-of-flags>w`()
would act unambigously, expressively, portably and non-intrusively
(default
behavior of `-reader won't change).

Why is this important?

This is important not only to allow for fresh consing. More
interesting is backquote-based pattern matching.
In this way, pattern might have a literal fixed parts and comma-
prefixed variable parts to match.

pit...@nhplace.com

unread,
Jan 26, 2009, 2:48:01 PM1/26/09
to
On Jan 26, 4:29 am, budden <budden-l...@mail.ru> wrote:

> [...]


> This is important not only to allow for fresh consing. More
> interesting is backquote-based pattern matching.
> In this way, pattern might have a literal fixed parts and comma-
> prefixed variable parts to match.

I'll have to think harder on this sometime if I get time, but please
recall that the line between "literal" and "comma-prefixed" is
blurrier than this last sentence suggests. In the case of nested
backquotes, it's possible that the result of one level of processing
results in things that have commas but where the comma'd value is
quoted because of ,', situations. Really those are just the same as
non-comma literals, and backquote will want to optimize them.
Requiring them to be treated as non-literal in later macroexpansions
(the other pass of a double backquote) will make that pass
inefficient.

What I'm saying may or may not be consistent with your suggestion. I
don't have time to think about it. I just wanted to note the issue.

0 new messages