In common-lisp, how do I modify part of a list parameter from within a function without changing the original list?

Question

I'm trying to pass a list to a function in Lisp, and change the contents of that list within the function without affecting the original list. I've read that Lisp is pass-by-value, and it's true, but there is something else going on that I don't quite understand. For example, this code works as expected:

(defun test ()
    (setf original '(a b c))
    (modify original)
    (print original))
(defun modify (n)
    (setf n '(x y z))
    n)

If you call (test), it prints (a b c) even though (modify) returns (x y z).

However, it doesn't work that way if you try to change just part of the list. I assume this has something to do with lists that have the same content being the same in memory everywhere or something like that? Here is an example:

(defun test ()
    (setf original '(a b c))
    (modify original)
    (print original))
(defun modify (n)
    (setf (first n) 'x)
    n)

Then (test) prints (x b c). So how do I change some elements of a list parameter in a function, as if that list was local to that function?

Answer 1

Lisp lists are based on cons cells. Variables are like pointers to cons cells (or other Lisp objects). Changing a variable will not change other variables. Changing cons cells will be visible in all places where there are references to those cons cells.

A good book is Touretzky, Common Lisp: A Gentle Introduction to Symbolic Computation.

There is also software that draws trees of lists and cons cells.

If you pass a list to a function like this:

(modify (list 1 2 3))

Then you have three different ways to use the list:

destructive modification of cons cells

(defun modify (list)
   (setf (first list) 'foo)) ; This sets the CAR of the first cons cell to 'foo .

structure sharing

(defun modify (list)
   (cons 'bar (rest list)))

Above returns a list that shares structure with the passed in list: the rest elements are the same in both lists.

copying

(defun modify (list)
   (cons 'baz (copy-list (rest list))))

Above function BAZ is similar to BAR, but no list cells are shared, since the list is copied.

Needless to say that destructive modification often should be avoided, unless there is a real reason to do it (like saving memory when it is worth it).

Notes:

never destructively modify literal constant lists

Dont' do: (let ((l '(a b c))) (setf (first l) 'bar))

Reason: the list may be write protected, or may be shared with other lists (arranged by the compiler), etc.

Also:

Introduce variables

like this

(let ((original (list 'a 'b 'c)))
   (setf (first original) 'bar))

or like this

(defun foo (original-list)
   (setf (first original-list) 'bar))

never SETF an undefined variable.