Two simple push functions; one permanently mutates global var, other doesn't, why?

Question

Here are two simple functions that use push on a variable passed in:

(defun push-rest (var) (push 99 (rest var)))

and

(defun just-push (something) (push 5 something))

The first one will permanently mutate the var passed. The second does not. This is quite confusing for someone who is learning the scoping behavior of this language:

CL-USER> (defparameter something (list 1 2))    
SOMETHING
CL-USER> something
(1 2)
CL-USER> (just-push something)
(5 1 2)
CL-USER> something
(1 2)
CL-USER> (push-rest something)
(99 2)
CL-USER> something
(1 99 2)

In push-rest why isn't the var's scope local to the function like in just-push, when they are both using the same function, push?

Answer 1

According to Peter Siebel's Practical Common Lisp, Chapter 6. Variables: This might help you a lot:

As with all Common Lisp variables, function parameters hold object references. Thus, you can assign a new value to a function parameter within the body of the function, and it will not affect the bindings created for another call to the same function. But if the object passed to a function is mutable and you change it in the function, the changes will be visible to the caller since both the caller and the callee will be referencing the same object.

And a footnote:

In compiler-writer terms Common Lisp functions are "pass-by-value." However, the values that are passed are references to objects.

(Pass by value also essentially means copy; but we aren't copying the object; we are copying the reference/pointer to the object.)

As I noted in another comment:

Lisp doesn't pass objects. Lisp passes copies of object references to functions. Or you could think of them as pointers. setf assigns a new pointer created by the function to something else. The previous pointer/binding is not touched. But if the function instead operates on this pointer, rather than setting it, then it operates on the original object the pointer points too. if you are a C++ guy, this might make much more sense for you.

Answer 2

Basedon your profile, it looks like you have familiarity with C-like languages. push is a macro, and is the following equivalence is roughly true (except for the fact that this would cause x to be evaluated twice, whereas push won't):

(push x y) === (setf x (list* x y))

That's almost a C macro. Consider a similar incf macro (CL actually defines an incf, but that's not important now):

(incf x) === (setf x (+ 1 x))

In C, if you do something like

void bar( int *xs ) {
  xs[0] = xs[0] + 1;   /* INCF( xs[0] ) */
}

void foo( int x ) {
  x = x + 1;           /* INCF( x ) */
}

and have calls like

bar(zs);               /* where zs[0] is 10 */
printf( "%d", zs[0] ); /* 11, not 10 */

foo(z);                /* where z is 10 */
printf( "%d", z );     /* 10, not 11 */

The same thing is happening in the Lisp code. In your first code example, you're modifying contents of some structure. In your second code example, you're modifying the value of lexical variable. The first you'll see across function calls, because the structure is preserved across function calls. The second you won't see, because the lexical variable only has lexical scope.

Sometimes I wonder if Lisp aficionados (myself included) promote the idea that Lisp is different so much that we confuse people into thinking that nothing's the same.

Answer 3

push works differently when it's passed a symbol or list as it's second argument. Pehaps you might understand it better if you do macroexpand on the two different.

(macroexpand '(push 99 (rest var))) 
;;==>
(let* ((#:g5374 99)) 
  (let* ((#:temp-5373 var)) 
    (let* ((#:g5375 (rest #:temp-5373))) 
      (system::%rplacd #:temp-5373 (cons #:g5374 #:g5375)))))

Now most of this is to not evaluate the arguments more than once so we can in this case rewrite it to:

(rplacd var (cons 99 (rest var)))

Now this mutates the cdr of var such that every binding to the same value or lists that has the same object in it's structure gets altered. Now lets try the other one:

(macroexpand '(push 5 something))
; ==>
(setq something (cons 5 something))

Here is creates a new list starting with 5 and alters the local functions binding something to that value, that in the beginning pointed to the original structure. If you have the original structure in a variable lst it won't get changed since it's a completely different binding than something. You can fix your problem with a macro:

(defmacro just-push (lst)
  (if (symbolp lst)
      `(push 5 ,lst)
      (error "macro-argument-not-symbol")))

This only accepts variables as argument and mutates it to a new list having 5 as it's first element and the original list as it's tail. (just-push x) is just an abbreviation for (push 5 x).

Just to be clear. In an Algol dialect the equivalent code would be something like:

public class Node
{
  private int value;
  private Node next;

  public Node(int value, Node next)
  {
    this.value = value;
    this.next  = next;
  }

  public static void pushRest(Node var)
  {
    Node n   = new Node(99, var.next); // a new node with 99 and chained with the rest of var
    var.next = n; // argument gets mutated to have new node as next
  }

  public static void justPush(Node var)
  {
    var = new Node(5, var); // overwrite var
    System.out.print("var in justPush is: ");
    var.print();
  }

  public void print()
  {
    System.out.print(String.valueOf(value) + " ");
    if ( next == null )
      System.out.println();
    else
      next.print();
  }

  public static void main (String[] args)
  {
    Node n = new Node( 10, new Node(20, null)); 
    n.print();    // displays "10 20"
    pushRest(n);  // mutates list
    n.print();    // displays "10 99 20"
    justPush(n);  // displays "var in justPush is :5 10 99 20" 
    n.print();    // displays "10 99 20"
  }
}

Answer 4

You can't push on a variable passed. Lisp does not pass variables.

Lisp passes objects.

You need to understand evaluation.

(just-push something)

Lisp sees that just-push is a function.

Now it evaluates something. The value of something is a list (1 2).

Then it calls just-push with the single argument (1 2).

just-push will never see the variable, it does not care. All it gets are objects.

(defun push-rest (some-list) (push 99 (rest some-list)))

Above pushes 99 onto the rest, a cons, of the list passed. Since that cons is visible outside, the change is visible outside.

(defun just-push (something) (push 5 something))

Above pushes 5 to the list pointed to by something. Since something is not visible outside and no other change has made, that change is not visible outside.

Answer 5

(push item place)

It work as follows　when the form is used to instruct the place where this is referred to in the setf:

(setf place (cons item place))