Pass by Object Reference in Common Lisp

Question

Peter Seibel wrote in Practical Common Lisp that "All values in Common Lisp are, conceptually at least, references to objects."

I tried that concept with the following code:

(setf x 5)
(setf y x)
(print x) % output: x is 5
(print y) % output: y is 5
(setf x 6)
(print x) % output: x is 6
(print y) % output: y is 5

If Lisp was pass-by-object-reference, y should point to x and so changing x to 6 should also change y to 6. But that's not what happened. It looks instead like Lisp is pass-by-object-value. Can someone help explain what happened?

Answer 1

Small integers are not usually references in Lisp implementations. It is not correct to say that all values are references in Common Lisp. Programming under the suspicion that values are references is often the safer assumption that is more aligned with writing correct code.

However, your example is consistent with small integers being implemented as references. It doesn't prove that they are not.

If a variable x holds an integer like 5, and then we assign to x with (setf x 4), we are not mutating the object 5 into 4. We are mutating the variable binding x: we have overwritten the 5 value that was previously in x with the new value 4.

This will work even if we use objects that are positively references into the heap, like cons cells:

(setf x '(1 . 2))
(setf y x)
y -> (1 . 2)
(setf x '(4 . 5))
y -> (1 . 2)

x and y are independent variables, and independently hold references to cons cells. x initially holds a reference to the (1 . 2) object. We assign x to y, and so now y also holds a reference to (1 . 2). It has its own copy of the reference. So then when we assign (4 . 5), x's reference is overwritten with a reference to (4 . 5), but y is unaffected. Why should it be?

How we can demonstrate that conses use reference semantics is by mutating the cells themselves:

(setf x (cons 1 2)) ;; we better not use a literal any more!
x -> (1 . 2)
(setf y x)
y -> (1 . 2)

;; now mutate

(rplaca x 10)
(rplacd x 20)

x -> (10 . 20)
y -> (10 . 20)

Since mutating the cell stored in x makes the mutation appear on the cell stored in y, we know that x and y must hold a reference to the same object.

Now here is the kicker: we cannot perform this test with integers, because integers are not mutable! There is no function similar to rplaca that will clobber the actual bits representing 1, and turn them into 10.

The eq function doesn't help, because all it can do is to confirm that the two values are the same object:

(setf x 5)
(setf y x)

(eq x y) -> ?

If this eq call returns T, then x and y are the same object. I say if because ANSI Common Lisp leaves this implementation-specific. It is permitted for an implementation to yield NIL!

However, it yields T in implementations in which small integers (fixnums) are packed directly into a value, and are not pointer into boxed heap object (the prevalent implementation approach). So that is to say, a value like 4 is considered to be a one object everywhere it appears, even though it is propagated by the copying of a value that holds the the bit pattern representing 4 directly.

So it more or less boils down to that you just have to know how your implementation works to be sure about which kinds of objects are references.

Answer 2

[This answer mostly repeats others: I started it before they existed and don't want to throw it away.]

Lisp (specifically Common Lisp, but others too) is strictly call by value. In particular, if f is a function, then

(let ((x ...))
  (let ((y x))
    (f x)
    (eql y x)))

is true.

However many values are references, or in other words many kinds of objects have identity.

Implementationally what this usually means is that most values are the addresses of objects in memory. So, almost certainly given

(let ((x (cons nil nil)))
  (let ((y x))
    ...))

Then the value of x is, implementationally, the address of the object constructed by cons, and so is the value of y. That means that, for instance given

(defun mutate-cdr (c to)
  (setf (cdr c) to))

then

(let ((x (cons nil nil)))
  (let ((y x))
    (mutate-cdr x 3)
    (cdr y)))

is 3.

There are special cases however where some kinds of objects are represented immediately: typically small numbers, characters & some other things perhaps. All the kinds of objects represented immediately are immutable so it doesn't make a lot of difference, although there are complicated rules around equality related to this.

However Lisp is powerful enough to support call-by-reference if you want it, with a little syntax:

(declaim (inline locf (setf locf)))

(defun locf (loc)
  (funcall loc 'get))

(defun (setf locf) (new loc)
  (funcall loc 'set new))

(defmacro locative (place)
  `(lambda (op &optional val)
     (ecase op
       ((get) ,place)
       ((set) (setf ,place val)))))

And now given

(defun mutate-loc (loc new)
  (setf (locf loc) new))

then

(let ((x 1))
  (let ((y (locative x)))
    (mutate-loc y 4)
    x))

is 4. And of course this works for any place:

(let ((x (vector 1 2 3)))
  (let ((y (locative (aref x 2))))
    (mutate-loc y 4)
    x))

is a vector whose 2nd element is 4.

There were implementations where things like this were built into the language: I don't remember the details of how they worked however.

Answer 3

First of all, you're quoting Seibel's "all values are references", and asking why pass-by-reference is not working. The simple answer is, yes, values are references, but CL is pass-by-value, not pass-by-reference.

But to answer your next question in the comments: how can one achieve pass-by-reference, here is an approach:

After wondering something similar (pass by reference style in C) today, and checking Rainer's answer to Variable references in lisp, I realised there's another approach.

For the pass by reference question, using special variables is one of the answers. And we can define a local variable as special and pass that to a reference-taking function.

We want to have a function to change the reference value of a parameter.

If you write the function below, that would be incorrect because this function updates the local variable text, not the reference:

(defun display-and-update (text)
  (print text)
  (setf text (concatenate 'string text ", updated.")))

test:

(let ((my-text "test"))
  (display-and-update my-text)
  (print my-text))

outputs:

> "test"
> "test"

Instead we should use a different, explicit mechanism to show our purpose (as you do with pointer operator * and address-of / reference operator & in C for example). The way to do this is to use a symbol (in C the closest equivalent would be a variable, instead of a literal, since we can't use pointer and address-of operators on C literals either).

Now, let's redefine the function to use references:

(defun display-and-update (sym-text)
  (print (symbol-value sym-text))
  (set sym-text (concatenate 'string
                             (symbol-value sym-text)
                             ", updated.")))

Here, symbol-value function is our "dereferencing" operator, as * is in C. And set is the *_ = operator in C, which sets the symbol's value.

Now, the question of how we can pass a local symbol (I should actually say lexical variable) to this function is solved by special variables, because a lexical variable cannot be used by another lexical scope - here for example the function display-and-udpate's scope. The same call from above is slightly modified to achieve this:

(let ((my-text "test"))
  (declare (special my-text))
  (display-and-update 'my-text)
  (print my-text))

outputs:

> "test"
> "test, updated."

And as you may have noticed, we're calling display-and-update with 'my-text instead of my-text, because my-text would evaluate the value and pass "test", which would fail. ' here is like & operator in C.

Now, apologies for derailing from the original question, but they were related, at least for better understanding.

To have a variable referencing another, again in C, we can write:

int a = 3;
int *b = &a;
*b = 5; // a is 5

To achieve the same in common-lisp:

(defparameter a 3)
(defparameter b 'a)
(set b 5) ;; a is 5

Now, one can again see that set function is actually not the = operator in C, but rather *var = operator, as it first gets the value of the symbol and sets it. If, for example you create b to equal something else, maybe nil:

(defparameter a 3)
(defparameter b nil)
;; (set b 'a) ;; this won't work, as it's trying to set the symbol nil's value to 'a
;; instead:
(setf b 'a) ;; this is a better match for C's = operator

will achieve the same.

Answer 4

As @Kaz mentioned, literals like strings, numbers, symbols they are implemented in a special way and thus mostly copied/recreated when assigned to.

But as soon as you generate some more complex structures - composed structures - setf will refer to the location.

(defparameter *x* (list 3))
(setf *y* *x*)
*x* ;; (3)
*y* ;; (3)

;; mutate *x*
(setf (car *x*) 5)
*x* ;; (5)
*y* ;; (5)

;; if you mutate *x* by letting things be there and adding sth e.g.
(setf (cdr *x*) 7)
*x* ;; (5 . 7)
*y* ;; (5 . 7)

(setf (cdr *x*) (list 1 2))
*x* ;; (5 1 2)
*y* ;; (5 1 2)

;; however, completely refedine *x*
;; then *y* will still refer to the old *x*
;; maybe because the creation of a new object (list 5 6) 
;; makes the symbol *x* be bound to a completely new place 
;; - where (list 5 6) was generated.
(setf *x* (list 5 6))
*x* ;; (5 6)
*y* ;; (5 1 2)

;; at least we can say, as long as we are mutation on the structures
;; of the cons cells - *y* will follow *x*'s mutations

What you want to do, one could reach by refering to your variable using a function (using a closure!)

(defparameter *q* 3)
(defun y () *q*)

From now on, whatever value you assign to *q* using (setf *q* <whatever>), you will be able to get by (y).

However, to change *q* by using (setf (y) ...) you must first define the corresponding setf function (and define it in a way that it modifies then *q* directly.

To have more a feeling to invoke a variable and not a function, one could perhaps create a readermacro e.g. for @y which then expands to (y). And macros to define (and in background defining the corresponding setf functions ...). So that one would have at least the illusion to deal with a variable ...

Are just my thoughts.