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

backquoting: are lispworks, sbcl, clisp conformant?

20 views
Skip to first unread message

budden

unread,
Jan 18, 2009, 6:28:53 AM1/18/09
to
Hi!

> (defun ff () `(,0))
ff
> (eq (ff) (ff))
this returns:
t (in lispworks, sbcl, clisp)
nil (in allegro, clozure cl)

On my opinion, returning t is non-conformant. Standard (section
2.4.6,
http://www.lispworks.com/documentation/HyperSpec/Body/02_df.htm)
states:
"
`(x1 x2 x3 ... xn . atom) may be interpreted to mean
(append [ x1] [ x2] [ x3] ... [ xn] (quote atom))
where the brackets are used to indicate a transformation of an xj
as follows:
-- [form] is interpreted as (list `form), which contains a
backquoted form that must then be further interpreted.
-- [,form] is interpreted as (list form).
..."

so, `(,0) should mean (append (list 0)), but not '(0), as it is
interpreted in first three implementations I listed
Later it is stated that

"The constructed copy of the template might or might not share list
structure with the template itself. As an example, the above
definition implies that
`((,a b) ,c ,@d)
will be interpreted as if it were
(append (list (append (list a) (list 'b) 'nil)) (list c) d 'nil)
but it could also be legitimately interpreted to mean any of the
following:
(append (list (append (list a) (list 'b))) (list c) d)
(append (list (append (list a) '(b))) (list c) d)
(list* (cons a '(b)) c d)
(list* (cons a (list 'b)) c d)
(append (list (cons a '(b))) (list c) d)
(list* (cons a '(b)) c (copy-list d))
"
First of all, we see that it is always a copy. In an example, we see
that only literal parts (not under comma) are shared. Parts that under
comma are never inlined.

So, lispworks, clisp, sbcl treat `(,0) as '(0) and this leads to side
effect like this:
> (progn (setf (car (ff)) 1) (ff))
(1)

Rob Warnock

unread,
Jan 18, 2009, 6:56:14 AM1/18/09
to
budden <budde...@mail.ru> wrote:
+---------------

| > (defun ff () `(,0))
| ff
| > (eq (ff) (ff))
| this returns:
| t (in lispworks, sbcl, clisp)
| nil (in allegro, clozure cl)
|
| On my opinion, returning t is non-conformant.
+---------------

On the contrary, what EQ returns in this case is not specified.
T is a perfectly acceptable, and so is NIL.

+---------------


| Standard (section 2.4.6,
| http://www.lispworks.com/documentation/HyperSpec/Body/02_df.htm)
| states:
| "
| `(x1 x2 x3 ... xn . atom) may be interpreted to mean
| (append [ x1] [ x2] [ x3] ... [ xn] (quote atom))
| where the brackets are used to indicate a transformation of an xj
| as follows:
| -- [form] is interpreted as (list `form), which contains a
| backquoted form that must then be further interpreted.
| -- [,form] is interpreted as (list form).
| ..."
|
| so, `(,0) should mean (append (list 0)), but not '(0), as it is
| interpreted in first three implementations I listed

+---------------

Uh... What do you think (APPEND (LIST 0)) evaluates *to*?!?

> (append (list 0))

(0)
>

And what do you think `(,0) evaluates to?

> `(,0)

(0)
>

So the *only* thing you're quibbling about is whether the evaluation
of the (APPEND (LIST 0)) is done at READ time, in which case the
(EQ (FF) (FF)) will likely return T [since it's returning the identical
cons cell embedded in the function definition], or whether the evaluation
of the (APPEND (LIST 0)) is done at EVAL time, in which case the
(EQ (FF) (FF)) will likely return NIL [since freshly allocated cons
cells are always different under EQ].

What you're missing is that the CLHS specifically *doesn't* specify
whether backquote evaluation is done at READ time or at EVAL time,
only that it follow the rules. From the same CLHS 2.4.6 page that
you referenced above:

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.

Read closely: It says "the same under EQUAL", *not* "the same under EQ"!!

And, indeed:

> (equal `(,0) (append (list 0)))

T
>

*All* implementations should return T for (EQUAL (FF) (FF)).


-Rob

-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

Pascal J. Bourguignon

unread,
Jan 18, 2009, 7:09:11 AM1/18/09
to
budden <budde...@mail.ru> writes:

> Hi!
>
>> (defun ff () `(,0))
> ff
>> (eq (ff) (ff))
> this returns:
> t (in lispworks, sbcl, clisp)
> nil (in allegro, clozure cl)
>
> On my opinion, returning t is non-conformant. Standard (section
> 2.4.6,
> http://www.lispworks.com/documentation/HyperSpec/Body/02_df.htm)
> states:
> "
> `(x1 x2 x3 ... xn . atom) may be interpreted to mean
> (append [ x1] [ x2] [ x3] ... [ xn] (quote atom))
> where the brackets are used to indicate a transformation of an xj
> as follows:
> -- [form] is interpreted as (list `form), which contains a
> backquoted form that must then be further interpreted.
> -- [,form] is interpreted as (list form).
> ..."
>
> so, `(,0) should mean (append (list 0)), but not '(0), as it is
> interpreted in first three implementations I listed

Not at all, because ` may substitute any form for an equivalent (as
long as they evaluate to EQUAL results).

http://www.lispworks.com/documentation/HyperSpec/Body/02_df.htm

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.

> Later it is stated that


>
> "The constructed copy of the template might or might not share list
> structure with the template itself. As an example, the above
> definition implies that
> `((,a b) ,c ,@d)
> will be interpreted as if it were
> (append (list (append (list a) (list 'b) 'nil)) (list c) d 'nil)
> but it could also be legitimately interpreted to mean any of the
> following:
> (append (list (append (list a) (list 'b))) (list c) d)
> (append (list (append (list a) '(b))) (list c) d)
> (list* (cons a '(b)) c d)
> (list* (cons a (list 'b)) c d)
> (append (list (cons a '(b))) (list c) d)
> (list* (cons a '(b)) c (copy-list d))
> "
> First of all, we see that it is always a copy. In an example, we see
> that only literal parts (not under comma) are shared. Parts that under
> comma are never inlined.

Examples are not part of the standard. They are formally meaningless.

> So, lispworks, clisp, sbcl treat `(,0) as '(0) and this leads to side
> effect like this:
>> (progn (setf (car (ff)) 1) (ff))
> (1)

Yes. If the language designers had not wanted backQUOTE to behave
like QUOTE, that is to return immutable data, they would not have
named backQUOTE backQUOTE, but backLIST or something like that.

--
__Pascal Bourguignon__

Kaz Kylheku

unread,
Jan 18, 2009, 12:16:45 PM1/18/09
to
On 2009-01-18, budden <budde...@mail.ru> wrote:
> Hi!
>
>> (defun ff () `(,0))
> ff
>> (eq (ff) (ff))
> this returns:
> t (in lispworks, sbcl, clisp)
> nil (in allegro, clozure cl)
>
> On my opinion, returning t is non-conformant.

It would certainly be wrong if (list 0) didn't return a unique
object. But backquote allows optimizations.

> `(x1 x2 x3 ... xn . atom) may be interpreted to mean

[ snip ]

> so, `(,0) should mean (append (list 0)), but not '(0), as it is

The (albeit non-normative) example cited later constradicts this. For instance,
it's clear that `(,0) could be things like (list* 0 nil), (cons 0 nil) or (list
0).

It is not the intent that backquote must be constrained into generating
inefficient code, literally based on the APPEND structures.

> "The constructed copy of the template might or might not share list
> structure with the template itself. As an example, the above

This statement allows optimization of all constant material in the
backquote.

For instance, if the same statement was said about the LIST function, then
(list 0) would be allowed to return the same list every time (behaving like
(quote (0)), since 0 is a self-evaluating literal object.

If a specification for a list constructing function says that it ``may share
list structure across invocations'', that license is next to meaningless if the
function is not allowed to recognize self-evaluating objects in the form!

> definition implies that
> `((,a b) ,c ,@d)
> will be interpreted as if it were
> (append (list (append (list a) (list 'b) 'nil)) (list c) d 'nil)
> but it could also be legitimately interpreted to mean any of the
> following:
> (append (list (append (list a) (list 'b))) (list c) d)
> (append (list (append (list a) '(b))) (list c) d)
> (list* (cons a '(b)) c d)

Note that '(b) here is very much like 0. Both are self-evaluating literal
objects.

Note that the expression could be written:

`(,@(list a 'b) ,c ,@d)

and it wouldn't make a difference. The abstract translation is now:

(append (list a 'b) (list c) d)

which is indistinguishable from the kind of thing produced by

`((,a b) ,c ,@d)

You can no longer trace the origin of the (list a 'b). It could
have come from ,@(list a 'b) or from (,a b).

Unquoted material does not enjoy some special status
over template material!

> (list* (cons a (list 'b)) c d)
> (append (list (cons a '(b))) (list c) d)
> (list* (cons a '(b)) c (copy-list d))
> "
> First of all, we see that it is always a copy.

Nonsense. The above examples directly contradict you. Look at '(B).
It came from the backquote template and isn't freshly copied.

The overall obejct is a copy, but this is necessary because the backquote
unquotes the values of variables. It's logically impossible to return the same
object, since the variables might change between evaluations, so that the
objects coming out might not even be EQUAL, never mind EQ. Only the suffix
portions of the list structure at various levels can be shared.

This is just a single example from which you cannot generalize.

And you should also know that examples are usually not ``normative'' in
ANSI or ISO standards for programming languages; the Lisp one is no
exception.

> So, lispworks, clisp, sbcl treat `(,0) as '(0) and this leads to side
> effect like this:

So if you assume otherwise, your code isn't portable to CLISP, LispWorks
or SBCL. And that's not an exhaustive list, just the ones you tried so far.
You still have ECL, Allegro, and plenty others.

Suppose that you are right right and that the interpretation of what the
standard says is in fact that '(,0) -> '(0) should really be forbidden. But
suppose that nearly every Common Lisp implementation actually does that
reduction. That means there is a defect in the standard.

What determines the portability of your code is ultimately the concensus of
implementations, not some document. It's implementations that run your
code, not the document.

If most implementations do something differently, chances are that they
will never be fixed. The situation will persist unil the next revision
of the standard, which will clarify that their behavior is correct.

Kaz Kylheku

unread,
Jan 18, 2009, 12:21:01 PM1/18/09
to
On 2009-01-18, Rob Warnock <rp...@rpw3.org> wrote:
>|
>| so, `(,0) should mean (append (list 0)), but not '(0), as it is
>| interpreted in first three implementations I listed
> +---------------
>
> Uh... What do you think (APPEND (LIST 0)) evaluates *to*?!?
>
> > (append (list 0))
>
> (0)
> >
>
> And what do you think `(,0) evaluates to?
>
> > `(,0)
>

This is not the right way to argue this. Multiple invocations of (LIST 0)
are not in fact allowed to return objects that share list structure.

It's the statement about shared list structure being allowed which allows
backquote to do the reduction of `(,0) to effectively '(0).

> What you're missing is that the CLHS specifically *doesn't* specify
> whether backquote evaluation is done at READ time or at EVAL time,

This is quite wrong, Rob. What is not specified is whether the /expansion/ of
backquote (translating the syntax into code) is done at read time or later,
or some combination from different times (like translating the notation to
a macro at read time, and expanding the macro at macro-expansion time).

Of course evaluation is done at eval time. What part of "eval" being
a prefix of "evaluation" isn't clear? :) :) :)

Kaz Kylheku

unread,
Jan 18, 2009, 12:26:35 PM1/18/09
to

Bingo. So we can take F1 to be `(,0) and F2 to be '(0) since
the forms produce EQUAL results.

Q.E.D.

I still think that this possibility, in this case, does also independently
emerge from the permission to share substructure.

budden

unread,
Jan 18, 2009, 5:02:30 PM1/18/09
to
Thanks for comments. I don't say that I'm totally convinced. But
regardless of this, I see now that generating data with backquote is a
dangerous practice. I thought before that bacquote output is always
fresh and is never shared with a template. It turned out to be wrong.
So I can't rely on it being fresh even if substituted data is non-
constant. If I want data to be fresh, I need to enclose backquote in a
some copying function. And this particular case of `(,0)='(0) doesn't
matter much in this context.

After all, I think it'd be better to have two versions of a backquote:
the fully fresh-consing one the shared one.

If there is only one choice, having independent version would be more
expressive than having one with undefined sharing.

this way `(1 2 3) would mean (list 1 2 3) while '(1 2 3) would mean
just '(1 2 3) (literal and constant).
Partial sharing would be achieved by `(,x ,'(a b c) 3)

But this is another story...

Tamas K Papp

unread,
Jan 18, 2009, 6:38:37 PM1/18/09
to
On Sun, 18 Jan 2009 14:02:30 -0800, budden wrote:

> regardless of this, I see now that generating data with backquote is a
> dangerous practice. I thought before that bacquote output is always

I would say that relying on incorrect assumptions is a dangerous practice.

> fresh and is never shared with a template. It turned out to be wrong. So
> I can't rely on it being fresh even if substituted data is non-
> constant. If I want data to be fresh, I need to enclose backquote in a
> some copying function. And this particular case of `(,0)='(0) doesn't
> matter much in this context.

Backquote is used mostly for writing templates in macros, where the
issue does not arise. If you want to do something fancier and
manipulate the created list, you just have to use sg else.

> After all, I think it'd be better to have two versions of a backquote:
> the fully fresh-consing one the shared one.
>
> If there is only one choice, having independent version would be more
> expressive than having one with undefined sharing.

Nothing prevents you from writing that other version and using it in
your code (eg with a reader macro).

Tamas

Rob Warnock

unread,
Jan 18, 2009, 9:04:57 PM1/18/09
to
Kaz Kylheku <kkyl...@gmail.com> wrote:
+---------------

| Rob Warnock <rp...@rpw3.org> wrote:
| > Uh... What do you think (APPEND (LIST 0)) evaluates *to*?!?
| > > (append (list 0))
| > (0)
| > >
| > And what do you think `(,0) evaluates to?
| >
| > > `(,0)
| > (0)

| > >
|
| This is not the right way to argue this. Multiple invocations of (LIST 0)
| are not in fact allowed to return objects that share list structure.
+---------------

Good point. The correct argument for the OP's test case is the READ+EVAL
indeterminacy of form under EQUAL... which I *did* make later.

+---------------


| > What you're missing is that the CLHS specifically *doesn't* specify
| > whether backquote evaluation is done at READ time or at EVAL time,
|
| This is quite wrong, Rob. What is not specified is whether the
| /expansion/ of backquote (translating the syntax into code) is done
| at read time or later, or some combination from different times
| (like translating the notation to a macro at read time, and expanding
| the macro at macro-expansion time).

+---------------

You deleted the critical CLHS quote, which I will repeat:

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...

This implies that form F2 is free to be a *constant* [where the original
backquoted form can be fully expanded to such a constant at READ time],
as long as that constant is EQUAL to the canonical expansion given in
2.4.6, which, for the OP's test case, '(0) is.

+---------------


| Of course evaluation is done at eval time. What part of "eval"
| being a prefix of "evaluation" isn't clear? :) :) :)

+---------------

I'll try again, with more precision: The implementation of backquote
is free to produce at READ time, if it is able to, any alternate form
[perhaps simpler, perhaps more complex] than the canonical expansion
given in 2.4.6, provided that that other form, when evaluated (at EVAL
time), is EQUAL to the evaluation of the canonical expansion given in
2.4.6. That alternate form may indeed even be a constant.

*If* the backquote expansion produced at READ time *is* a constant,
then of course a function returning the evaluation of that expansion
will return the "same" (under EQL) result each time it is called.
And in fact, if the result is not a number or a character, the
multiple results will all be EQ.

If, on the other hand, the specific implementation of backquote chooses
*not* to return a constant, but a form which actively computes a new
result each time it is evaluated, that's fine, too, as long as all such
results are EQUAL (and EQUAL to the evaluation of the canonical form).
They might well *not* be EQL or EQ, however...

So the "equality" status of the OP's original (DEFUN FF () `(,0))
example function, is indeterminant. The values of multiple calls
of FF *must* be EQUAL; they might or might not be EQL or EQ.

Is that better?

Madhu

unread,
Jan 18, 2009, 10:40:04 PM1/18/09
to

* Kaz Kylheku <200901240...@gmail.com> :
Wrote on Sun, 18 Jan 2009 17:16:45 +0000 (UTC):

| Suppose that you are right right and that the interpretation of what
| the standard says is in fact that '(,0) -> '(0) should really be
| forbidden. But suppose that nearly every Common Lisp implementation
| actually does that reduction. That means there is a defect in the
| standard.

Generally speaking (without reference to this particular example), I
don't think your conclusion follows from the premise.

| What determines the portability of your code is ultimately the
| concensus of implementations, not some document. It's implementations
| that run your code, not the document.

No, this is but a practical defintion of `portability'. There is a well
defined notion of portability without reference to specific in the
ANS. Glossary entry

,----
| portable: adj. (of code) required to produce equivalent results and
| observable side effects in all conforming implementations.
`----

But `portability' is also a loaded word and has important meanings for
marketing, social engineering contexts etc. This sort of "portability"
is typically increased by dropping support for platforms [I believe I've
seen that in release notes somewhere!] --- which reduces it to being a
newspeak word.

| If most implementations do something differently, chances are that
| they will never be fixed. The situation will persist unil the next
| revision of the standard, which will clarify that their behavior is
| correct.

Not necessarily. For example I've heard on CLL some scheme implementors
refused to implement features in their new spec

--
Madhu

Barry Margolin

unread,
Jan 19, 2009, 1:54:37 AM1/19/09
to
In article
<6a43f500-407e-42ca...@d36g2000prf.googlegroups.com>,
budden <budde...@mail.ru> wrote:

> After all, I think it'd be better to have two versions of a backquote:
> the fully fresh-consing one the shared one.

In the rare case where you really care that the data be fresh, you can
call LIST, APPEND, etc. explicitly. It hardly seems necessary to have
another version of backquote just for this.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***

Kaz Kylheku

unread,
Jan 19, 2009, 8:11:38 AM1/19/09
to
On 2009-01-18, budden <budde...@mail.ru> wrote:
> Thanks for comments. I don't say that I'm totally convinced. But
> regardless of this, I see now that generating data with backquote is a
> dangerous practice.

Do you also think that generating data with QUOTE is dangerous practice?

You know, maybe manipulating data destructively is the dangerous practice,
not how that data was generated.

> I thought before that bacquote output is always
> fresh and is never shared with a template. It turned out to be wrong.
> So I can't rely on it being fresh even if substituted data is non-
> constant.

Actually you can. The cases in which multiple evaluations of a backquote cannot
possibly share structure tend to be obvious.

Backquote itself even has a destructive version of the ,@ splicing operator,
by the way. It would be a sort of logical contradiction if you could use
destructive splicing in backquotes but never use the result of the backquote
destructively.

As a rule of thumb, the output of the backquote can share only the tail parts
(suffixes) of any lists of the template which can be reduced to literal data.

So for instance

`(,this ,is ,not ,shared this probably is)

This can be clarified with dot notation:

`(,this ,is ,not ,shared . (this probably is))

I'd be careful about cases like this:

(let ((constant 42))
`(... ,constant ...))

Here it is conceivable that the backquote will do a deep folding based on
knowing that constant is always 42, and so the cons cell that ends up with 42
could conceivably be part of the shared structure. Backquote implementations
tend not to be integrated into the compiler into this extent. They typically do
their code-generation work in a context where that kind information is not
available. I.e. constant material in the template is recognized purely from its
form alone, not semantics. Some backquotes expand at read-time, even.

If you want to be sure that a tail section is copied, splice in a COPY-LIST
over a literal:

`(,not ,shared ,.(copy-list '(not shared either)))

We use the non-consing splice ,. to avoid the waste of copying
the list twice.

This will probably do the trick too:

`(,not ,shared ,@(identity '(not shared either)))

It's unlikely that any backquote will recognize the form (IDENTITY X)
where X is a constant as being a constant.

This won't do the trick:

`(,not ,shared ,@'(probably shared too))

Backquote will most likely recognize the constant here.

> After all, I think it'd be better to have two versions of a backquote:
> the fully fresh-consing one the shared one.

That would be poor because you might only care some subforms of the template to
be freshly consed.

For instance you might want only the ``backbone'' of the list to be freshly
consed, but not necessarily the sublists.

> Partial sharing would be achieved by `(,x ,'(a b c) 3)

This doesn't seem a whole lot better than, inversely, using explicit
non-sharing notation within a sharing backquote, like the earlier:

`(,not ,shared ,@(copy-list '(not shared either)))

It's more verbose, but then you only need it for tail material.

budden

unread,
Jan 19, 2009, 10:55:07 AM1/19/09
to
> As a rule of thumb, the output of the backquote can share only the tail parts
> (suffixes) of any lists of the template which can be reduced to literal data.
> So  for instance
>
>   `(,this ,is ,not ,shared this probably is)
>
Topic started from the example of violation of this rule. Is the
result of
the following calculation defined, according to CL standard?

(defun foo ()
(let ((is-this-shared? 0))
`(,is-this-shared?)))

(eq (foo) (foo))

> Backquote is used mostly for writing templates in macros, where the
> issue does not arise. If you want to do something fancier and
> manipulate the created list, you just have to use sg else.

Backquote notation is very elegant and general, I see no reason why I
should limit
myself using it for macros only. It is useful for generating any kind
of data.
`(,a (,b)) is more readable and shorter than
(list a (list b))

budden

unread,
Jan 19, 2009, 11:08:10 AM1/19/09
to
Oh, I see you, Kaz, have paid some attention to case of bound
constants.
One more question. What this would give?
(defmacro foo (x) ``(,',x))

(hope I have spelled it right, I'm not at lisp prompt now).

0 new messages