CODEWITHSUNDEEP
scheme
Kubelecer
Kubelecer

Reputation: 23

set! and aliasing in Scheme

I have a problem understanding destructive operations within scheme that don't seem consistent. Namely why bar doesn't change in the following example

(define foo '(a b))
(define bar foo)
(set! foo '(c d))
foo
>(c d)
bar
>(a b)

However this makes the bar change by changing foo

(define foo '(a b))
(define bar foo)
(set-car! foo 'c)
foo
>(c b)
bar
>(c b)

If I understand correctly, bar is pointing at foo in its' car in both examples, but somehow the old foo does not change while using set! in the first one. I can't find an answer anywhere about how and why this happens.

Upvotes: 2

Views: 311

Answers (2)

DBridgham
DBridgham

Reputation: 136

Aliasing doesn't mean that bar points to foo, but rather that bar points to the same thing that foo points to at the moment. If pictures help, here are box and arrow diagrams for what's going on. After your setup code, you have this:

(define foo (list 'a 'b))
(define bar foo)

initial

Now if you run your first try, you create a new list and set foo to point to it without changing anything about bar or what it references.

(set! foo (list 'c 'd))

first

But if you run this code instead, you modify the (shared) list that both foo and bar happen to point to, at the moment.

(set-car! foo 'c)

second

Upvotes: 5

Sylwester
Sylwester

Reputation: 48745

define makes a variable. A name that evaluates to a location of an object. 

(define foo (list 'a 'b))

Here foo might point to address 240. When evaluateing foo you get 240 back so (define bar foo) will make a second variable that point to the same object in memory. Addresses are not shown in the REPL so you'll se (a b) since the REPL prints whats in address 240.

This object in memory is a cons so each of those are just two pointer to other values in memory. Thus when you do:

(set-car foo 'c)

you are changing the cons located at address 240 by changing the car pointer from the address representation of a to the address representation of c. Since both foo and bar points to the same cons cell at address 240 they both will get the change since they point to the same data.

If you use set! you only change what value a name is pointing to:

(set! foo (cons 'd (cdr foo)))

Now this will update the variables pointer from pointing to 240 to some other address. Thus you can evaluate foo and bar and see they are different values: 

foo ; ==> (d b)
bar ; ==> (c b)

Here foo might be located in address 256. Since we used the old values cdr in foo we know that the tail of those are the same:

(cdr foo)                 ; ==> (b)
(eq? (cdr foo) (cdr bar)) ; ==> #t

If you set! bar to a different value:

(set! bar foo)

Now both foo and bar point to 256 and if there are no longer uses of 240 the pair at that location might be garbage collected but since cdr of the original foo is the cdr, lets say address 248, that address will not be garbage collected since it is pointed to by the cons in address 256.

NB: I've changed the definition of foo since you are not allowed to set-car literals like '(a b) since they are immutable. (list 'a 'b) creates a fresh list every time that line of code is executed and you can be assured the address is not being reused in eg. '(d a b).

NB2: The Scheme report tries its best to keep away from dictating how to store values. Thus they don't use the concept address in the report. Most implementations of both Scheme and CL models their data quite similar.

Upvotes: 1

Related Questions