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?

Corpuscle

Note that the consequences of modifying literal constants is undefined. Don't do that. Never. '(a b c) is a literal constant in your code. You should not modify it. You can modify lists that are created with the function LIST like (list 'a 'b 'c) . – Cholecystectomy

also note that (SETF original '(a b c)) makes no sense. SETF does not introduce variables. the variable 'original' is nowhere defined. You can set variables that have been introduced via LET, DEFUN, DEFVAR, DEFPARAMETER, ... – Cholecystectomy

Answer 1

SETF modifies a place. n can be a place. The first element of the list n points to can also be a place.

In both cases, the list held by original is passed to modify as its parameter n. This means that both original in the function test and n in the function modify now hold the same list, which means that both original and n now point to its first element.

After SETF modifies n in the first case, it no longer points to that list but to a new list. The list pointed to by original is unaffected. The new list is then returned by modify, but since this value is not assigned to anything, it fades out of existence and will soon be garbage collected.

In the second case, SETF modifies not n, but the first element of the list n points to. This is the same list original points to, so, afterwards, you can see the modified list also through this variable.

In order to copy a list, use COPY-LIST.

Lathery

Answer 2

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.

Cholecystectomy

Answer 3

it's nearly the same as this example in C:

void modify1(char *p) {
    p = "hi";
}

void modify2(char *p) {
    p[0] = 'h';
}

in both cases a pointer is passed, if you change the pointer, you're changing the parameter copy of the pointer value (that it's on the stack), if you change the contents, you're changing the value of whatever object was pointed.

Bodega

I wish there was a book which explains the equivalent operations, whenever possible, in terms of C. A C programmer will grasp certain aspects of Common Lisp much quicker. – Flavio

Answer 4

You probably have problems because even though Lisp is pass-by-value references to objects are passed, like in Java or Python. Your cons cells contain references which you modify, so you modify both original and local one.

IMO, you should try to write functions in a more functional style to avoid such problems. Even though Common Lisp is multi-paradigm a functional style is a more appropriate way.

(defun modify (n) (cons 'x (cdr n))

Derrek

This is my first project in lisp, and I don't really understand functional programming yet. I guess I just need to rethink the way I've structured my program? I'm trying to examine potential modifications to a game state without modifying the state. So instead of making functions for makechange and undochange, I was hoping I could just modify a "copy" of the state instead. – Corpuscle

Generally it is wise to avoid unnecessary state changes. Often you don't need them and they make you program harder to debug and lead to mistakes such as this. – Derrek