Literal Lists

Discussion of Common Lisp
Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Literal Lists

Post by Paul » Sat Jun 25, 2011 6:37 pm

Kompottkin wrote:“The consequences are undefined if literal objects are destructively modified.” As far as I can see, that's all there is to it. (Of course, it wouldn't be the first time I misread the spec. :))
But you're reading the spec as if it has some mystical powers. The spec says that because it's true, but it's not true in every instance; the fact that the spec says it doesn't make otherwise well-defined (by that same spec) operations magically behave differently.
No, it's not the only thing that matters. In fact, QUOTE seems to me to be irrelevant. It's true that modifying the return value of (eval `(quote ,(list 1 2 3))) is (I believe) perfectly well-defined, but that's because in this case, the argument to quote is not a literal (while in (quote (1 2 3)), it is).
You're right, quote isn't relevant because most data types don't need it: "123" is the same as (quote "123"), etc. The identity of the object inside the (putative) quote form is what matters. There is no way for Lisp to distinguish (list 1 2 3) from (quote (1 2 3)) after the object exists (the only difference is when it comes into existence: read time vs. eval time). The reason it's "undefined" is that the file-compiler can (=necessarily must) change object identities: if it puts that list in the file, it's not going to be the same, identical, list when you load the file. But that can't happen "inside" Lisp (to stuff you type at the REPL). In other words, even if a Lisp implementer actively wanted to make destructive modification of a literal do something unexpected, just for laughs or whatever, there's no way he could do it (in general; you can catch special cases, like where it's lexically apparent...so SBCL can issue warnings, etc.)

I.e., the consequences of what is defined in the spec takes precedence over what isn't. (If I define ⊕ such that a⊕b=a+b when 6<=a<=b<=14, my spec would be correct to say "the consequences are undefined if ⊕ is applied to two integers", nevertheless 8⊕11 is 19!)

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Literal Lists

Post by nuntius » Sat Jun 25, 2011 8:39 pm

It is common for compilers to put constants in read-only memory... It is also common to identify multiple instances of a constant value and coalesce them. A compiler may precompute the length of a literal list. etc. etc.

Modifying literals is not recommended in most any language.

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Literal Lists

Post by Paul » Sat Jun 25, 2011 10:09 pm

nuntius wrote:It is common for compilers to put constants in read-only memory... It is also common to identify multiple instances of a constant value and coalesce them.
But the in-core compile (COMPILE, as opposed to COMPILE-FILE) can't do those things; it would require changing the identity of the objects.

Kompottkin
Posts: 94
Joined: Mon Jul 21, 2008 7:26 am
Location: München, Germany
Contact:

Re: Literal Lists

Post by Kompottkin » Sun Jun 26, 2011 2:52 am

Paul wrote:But you're reading the spec as if it has some mystical powers. The spec says that because it's true, but it's not true in every instance; the fact that the spec says it doesn't make otherwise well-defined (by that same spec) operations magically behave differently.
Good point. :)

even if a Lisp implementer actively wanted to make destructive modification of a literal do something unexpected, just for laughs or whatever, there's no way he could do it
That's the thing I'm not so sure about. eval could be evil and magically tag the code objects given to it by putting them into a hash table or something so as to be able to detect modification of literals. In this case, the following would be ill-defined even though *stuff* is perfectly mutable from the point of view of the outside code:

Code: Select all

(declaim (special *stuff*))
(let ((*stuff* (copy-list '(setf (car *stuff*) 'cons))))
  (eval *stuff*))
Moreover, it's not clear to me that the following is a non-conforming REPL implementation (given that the spec doesn't really say much about the behavior of a REPL):

Code: Select all

(loop
  (let ((input (move-into-read-only-memory (read))))
    (print (eval input))))
Of course, all of the above is pretty pathological. After all, I don't know of any implementation that disagrees with your interpretation here, so it's mostly a moot point. If some behavior is quasi-standard, it may as well be considered standard behavior.

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Literal Lists

Post by Paul » Sun Jun 26, 2011 3:13 pm

Kompottkin wrote:Moreover, it's not clear to me that the following is a non-conforming REPL implementation (given that the spec doesn't really say much about the behavior of a REPL):

Code: Select all

(loop
  (let ((input (move-into-read-only-memory (read))))
    (print (eval input))))

Code: Select all

(defvar *x* (list 1 2 3 4))
So *x* is safely mutable...

Code: Select all

(quote #.*x*)  ; anything involving #.*x* here 
Oops...REPL just put *x* in read-only memory... :)

Kompottkin
Posts: 94
Joined: Mon Jul 21, 2008 7:26 am
Location: München, Germany
Contact:

Re: Literal Lists

Post by Kompottkin » Mon Jun 27, 2011 2:59 pm

Paul wrote:

Code: Select all

(quote #.*x*)  ; anything involving #.*x* here 
Oops...REPL just put *x* in read-only memory... :)
Ah, sharp-dot! I completely forgot about that one. It may well prevent REPLs from doing anything disruptive here.

You win. I guess. ;)

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Literal Lists

Post by nuntius » Mon Jun 27, 2011 10:41 pm

To me, the sharp-dot appears to be a red herring. How does evaluating a variable make its value into a literal list? It counters Kompottkin's example, but not the general statement that modifying literals invokes explicitly undefined behavior.

Relevant passages (from a quick search):
http://www.lispworks.com/documentation/ ... /03_bd.htm
"eval and compile do not copy or coalesce constants"

http://www.lispworks.com/documentation/ ... s083_w.htm

http://www.lispworks.com/documentation/ ... y/03_g.htm

http://www.lispworks.com/documentation/ ... ql.htm#eql
"(eql '(a . b) '(a . b))
=> true
OR=> false
...
(eql "Foo" "Foo")
=> true
OR=> false"

You don't need coalescing to cause a violation. Constant data can be put into read-only memory or induce optimizations all by itself. Here's a simple example that IMO rightly gives rather contradictory information in SBCL's REPL (ecl and clisp both give a "consistent" final answer).

Code: Select all

(let ((a '(1 2)))
  (setf (cddr a) (cons 3 nil))
  (list a (length a)))

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Literal Lists

Post by Paul » Tue Jun 28, 2011 12:58 am

nuntius wrote:To me, the sharp-dot appears to be a red herring. How does evaluating a variable make its value into a literal list?
It doesn't. The point is that there's no place in the implementation where it could possibly tell the difference between a literal and a non-literal value, therefore it can't do anything that would make modifying literals behave badly (as long as you don't go through the file compiler; note that the #.*x* "literal" in would be split off from the in-core *x* variable if you put that through the file-compiler, too ... so that value would indeed have the same restriction on mutation as any (other) literal; it's only because the in-core identity can't be changed that it works there)
http://www.lispworks.com/documentation/ ... ql.htm#eql
"(eql '(a . b) '(a . b))
=> true
OR=> false
...
(eql "Foo" "Foo")
=> true
OR=> false"
But these, again, are making allowance for the file-compiler, etc.; the reader can't know, when it reads the first '(', that what follows is similar to something the implementation already knows about, which it would have to know in order to return the same object. I.e., there's no way for (eql '(a . b) '(a . b)) or (eql "Foo" "Foo"), typed directly at the REPL, to return anything but NIL; that would either require READing (a . b) or "Foo" to return the identical object as a previous invocation of READ, which this one has no way to know about, or, lower down the call chain, for one object to be switched for another similar one—which could again be defeated by the #. trick! It can't change object identity after it's constructed (except for fixnums and characters, theoretically...but I think not in practice)
Here's a simple example that IMO rightly gives rather contradictory information in SBCL's REPL (ecl and clisp both give a "consistent" final answer).

Code: Select all

(let ((a '(1 2)))
  (setf (cddr a) (cons 3 nil))
  (list a (length a)))
[/quote]

Yes, you can do optimizations when the "literalness" is visible to the compiler. Hence my comment above, "(you can catch special cases, like where it's lexically apparent...so SBCL can issue warnings, etc.)". But that's an optimization on LENGTH, nothing to do with the list itself. You can't write

Code: Select all

(defun flub (x)
  (setf (cddr x) (cons 3 nil)
  (list x (length x)))

(flub '(1 2))
and get the same result.

Konfusius
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: Literal Lists

Post by Konfusius » Tue Jun 28, 2011 7:17 am

Paul wrote:
http://www.lispworks.com/documentation/ ... ql.htm#eql
"(eql '(a . b) '(a . b))
=> true
OR=> false
...
(eql "Foo" "Foo")
=> true
OR=> false"
But these, again, are making allowance for the file-compiler, etc.; the reader can't know, when it reads the first '(', that what follows is similar to something the implementation already knows about,
The compiler might decide to fold common literal sub-expressions. In that case (eq '(a . b) '(a . b)) might return true.

Your mistake is that you exclude ways the compiler might work just because you cannot imagine it. That doesn't mean that a smart compiler builder couldn't imagine either. In fact, the only thing you really know is that an ANSI compiant lisp compiler obeyes the rules of the ANSI standard. If you cannot derive a compiler behaviour form those rules then you cannot assume it. You cannot make assumptions just because they are sound.

Paul
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Literal Lists

Post by Paul » Tue Jun 28, 2011 8:09 am

Konfusius wrote:
Paul wrote:
http://www.lispworks.com/documentation/ ... ql.htm#eql
"(eql '(a . b) '(a . b))
=> true
OR=> false
...
(eql "Foo" "Foo")
=> true
OR=> false"
But these, again, are making allowance for the file-compiler, etc.; the reader can't know, when it reads the first '(', that what follows is similar to something the implementation already knows about,
The compiler might decide to fold common literal sub-expressions. In that case (eq '(a . b) '(a . b)) might return true.
The compiler only sees the tree of objects that comes out of READ, not the text that goes in (in real Lisp; not necessarily true in Scheme), so it can't distinguish between (eq '(a . b) '(a . b)) and something like (eq '#.*x* '#.*y*) where *x* and *y* are guaranteed to be distinct conses which require it to return NIL. The file-compiler would break the connection to *x* and *y*, so it can make them EQ. Since it can see them both, and has reason to think they're similar constants, the compiler could replace the whole form with T (never even looking at *x* and *y*), but then you'll have different behaviour between the compiler and interpreter (which is only a problem if you have an interpreter, I suppose, but still...)

Post Reply