CODEWITHSUNDEEP
data-structurescommon-lisp
ben_za
ben_za

Reputation: 131

Partially Shared data structures common lisp

Say I wanted to have two lists(setq x '(1 2 3)) and (setq y (list 1 (cadr x) 3) but I wanted (cadr y) to actually point to (cadr x) so that after (setf (cadr x) 'a) saying (cadr y) would give me A not 2. Is there a way to do that?

Upvotes: 0

Views: 156

Answers (2)

Sylwester
Sylwester

Reputation: 48745

Lets imagine x is (list 1 2 3) instead since mutating literals have undefined consequences in the standard.

In your example you are not having shared list structure at all. What you have is different list structure pointing at the same value. (setf (cadr x) 'a) alters the list structure of x so it points to a different value. It does not alter the value 2 to something else. The result of course is that you only changed one place.

With shared list structure will have the effect that several lists that has the same cons in its list will get a new value when that cons is mutated:

(let ((tmp (list 2 3)))
  (defparameter *x* (cons 1 tmp))
  (defparameter *y* (cons 'a tmp)))

*x* ; ==> (1 2 3)
*y* ; ==> (a 2 3)

;; the cdr of both are the same
(eq (cdr *x*) (cdr *y*)) ; ==> t

;; mutating the cadr changes both since both list use the same cons
(setf (cadr *x*) 'q)
*x* ; ==> (1 q 3)
*y* ; ==> (a q 3)

Shared mutable object

If you have a value which is an object you can mutate, like a mutable string, you can mutate that directly instead of altering the cons. 

(let ((ele (copy-seq "ni"))) ; make ele mutable
  (defparameter *x* (list ele 1 2 4))
  (defparameter *y* (list 5 6 ele 7)))

*x* ; ==> ("ni" 1 2 4)
*y* ; ==> (5 6 "ni" 7)

;; mutating the string value, not the reference to the value
(setf (aref (car *x*) 1) #\o)

*x* ; ==> ("no" 1 2 4)
*y* ; ==> (5 6 "no" 7)

You can make a box to generalize it for all types:

(defstruct box (data))

(let ((ele (make-box :data "ni"))) ; make ele mutable
  (defparameter *x* (list ele 1 2 4))
  (defparameter *y* (list 5 6 ele 7)))

*x* ; ==> (#s(box :data "ni") 1 2 4)
*y* ; ==> (5 6 #s(box :data "ni") 7)

;; mutating the string value, not the reference to the value
(setf (box-data (car *x*)) 10)

*x* ; ==> (#s(box :data 10) 1 2 4)
*y* ; ==> (5 6 #s(box :data 10) 7)

As you notice what really happens is that a box is a structure with a value that we change but the lists point to the same box.

Upvotes: 4

Rainer Joswig
Rainer Joswig

Reputation: 139261

Generally this is not possible.

Imagine you have two lists:

CL-USER 11 > (sdraw (list 1 2 3))

[*|*]--->[*|*]--->[*|*]--->NIL
 |        |        |
 v        v        v
 1        2        3

CL-USER 12 > (sdraw (list 'a 'b 'c))

[*|*]--->[*|*]--->[*|*]--->NIL
 |        |        |
 v        v        v
 A        B        C

How would you represent the link between the cons cells? How would you make it that when you change the CAR of the second cons cell in the first list, that it then would also change a cons cell in the second list?

One way is to have a mechanism below the machine, which would detect a change and then would do something. On a Lisp Machine you could watch memory locations, but in plain Common Lisp this is not possible.

Alternatively you could change CADR to do something to detect changes to certain marked cons cells. Again, this is not in plain Common Lisp.

Excursion

Clozure CL has a mechanism to watch cons cells:

? (setf l1 (list 1 2 3))
(1 2 3)


? (watch (cdr l1))
(2 3)

? (setf (cadr l1) 'a)
> Error: Write to the CAR of watched cons cell (2 3)
>        Faulting instruction: #<X86-DISASSEMBLED-INSTRUCTION (movq (% rsi) (@ 5 (% rdi))) #x302000E1EA0D>
> While executing: CCL::SET-CADR, in process Listener(4).

Thus one could detect that a cons cell is changed and call a condition handler which would do something on that change...

Upvotes: 4

Related Questions