Difference Between Lists Constructed by Quote and Cons in Scheme

lispscheme

(define ls1 '((1 . 2) 1 . 2))
(set-car! (car ls1) 6)
ls1
(define ls2 (cons '(1 . 2) '(1 . 2)))
(set-car! (car ls2) 6)
ls2

After set-car!ing, ls1 will be ((6 . 2) 1 . 2) and ls2 ((6 . 2) 6 . 2). It seems that ls1 and ls2 have different storage model, and what does it mean when someone says x is bound to a list? is x stand for a starting address or location like that a is the starting address of a[10] in C?

Best Answer

Quote

Quote returns data which you should not modify, and which may share structure between themselves. E.g. if you have a file which contains

(define l1 '(1 2 3))
(define l2 '(4 2 3))

then the compiler is permitted to allocate l1 and l2 in a way that they share their common tail (cdr l1) and (cdr l2) and/or in the read-only memory.

Modification of such lists is undefined behavior. Do not do it.

list

list and cons create fresh objects (different from everything which already exist), they allocate and populate memory. You own them - you can modify them as much as you want.

Your case

Both your set-car! calls are wrong - you are modifying read-only data and thus triggering undefined behavior (i.e., you are lucky your computer did not blow up in your face :-).

Specifically, in the first case, ls1, you get what you would get if you did the right thing, i.e., 

(define ls1
  (cons (cons 1 2)
        (cons 1 2)))

while in the second case the implementation allocated only one cons cell (1 . 2) and re-used it in creating ls2, i.e., you see what you would see if you evaluate the following (legal) code:

(define ls2
  (let ((l (cons 1 2)))
    (cons l l)))

If there were print-circle in scheme, you could see the data re-use:

[1]> (let ((l (cons 1 2)))
        (cons l l)) 
((1 . 2) 1 . 2)
[2]> (setq *print-circle* t)
T
[3]> (let ((l (cons 1 2)))
        (cons l l)) 
(#1=(1 . 2) . #1#)

Binding

x is bound to a value means that the name x refers to the object, the same way in all languages.

The difference in Lisp/Scheme is what the object is.

Here it is the first cons cell of the list - as you have probably seen many times, a (linked) list is a chain of cons cell, where car contains the value and cdr contains the next cons cell in the list.

Related Topic