Lisp argument pointer

Question

I'm learning lisp and I have to return modified input arguments from my function in Lisp.

Consider this easy example:

(defun swap (l1 l2)
  (let ((temp))
    (setf temp l1)
    (setf l1 l2)
    (setf l2 temp)))

(setf a (list 1 2 3))
(setf b (list 7 8 9))
(swap a b)
(print a)
(print b)

It doesn't work because I don't know how to pass reference to variable to function. Is that even possible in lisp? How can this function be solved?

---

UPDATE

;;; doesn't change original
(defun foo1 (x)
  (setf x (list 0 0 0)))

;;; but this does
(defun foo4 (x)
  (setf (car x) 0)
  (setf (cdr x) (list 0 0)))

The reason why I wanted to pass a variable by reference to be able to change it is that, when I have function with 3 input arguments and that function should change all of them, I think it is more elegant to change them by reference, then return list of three variables and then overwrite with them original variables:

;;; more elegant function
(defun foo (x y z)
  ;;... some work ...

  ;; Lets PRETEND this does work
  (setf x new-x)
  (setf y new-y)
  (setf z new-z))

; after this, a,b,c will have new values
(foo a b c)

;;; less elegant function
(defun foo (x y z)
  ;; ... some work ...
  (list new-x new-y new-z))

; after this, I still will have to manually set a,b,c
(setf temp (foo a b c))
(setf a (nth 0 tmp))
(setf b (nth 1 tmp))
(setf c (nth 2 tmp))

To explain why I'm trying to accomplish this is I got Hanoi towers homework. I was thinking about using three lists as stacks and use pop and push functions on them to insert and remove the "discs". I defined (move n source target temp) function, and it is recursively calling itself with n-1 change. The problem is, when I pop or push stack in recursive function, it doesn't influence stacks outside. If I want my move function to return stacks after n movements, should I really return list of new stacks (that less elegant function) instead of editing them by reference (that more elegant function)

What is the proper way in Functional languages?

Answer 1

First of all, if you are learning functional programming or Lisps in general, and not just Common Lisp, don't do it. Don't try to write functions that modify state - it's not the way functional programming works. If you ever need function that exchanges 2 values, just write functions that return them in reverse order.

If you are still interested in exchanging 2 values, see this similar question for several very good suggestions. Most important are macros and manual references (wrappers for actual values).

However these answers don't include one important concept, available only in Common Lisp and not most other Lisp dialects - places. But first let's recall 2 ways to pass variable to function. Consider following example in C++:

void f(int x) {
    ...
}
int a = 5;
f(a);

This is known as "pass-by-value" strategy: value of a is copied to parameter x. And since x is just a copy, if you modify it inside of f(), nothing will happen with original variable a.

However, in C++ you can also do the following:

void f(int& x) {    
    ...
}
int a = 5; 
f(a);

This strategy is called "pass-by-reference" - here you pass pointer to location in memory where a resides. Thus x and a point to the same piece of memory, and if you modify x, a will change too.

Functional languages, including Common Lisp, don't allow you to pass variables to functions by reference. So how setf works? It turns out that CL has concept of place (sometimes also referred as "location") that defines location in memory. setf (macro that is expanded to set special form) works directly with places and not values.

To summarize:

1. Common Lisp, like most Lisps, allows only to pass variables to function only by value.
2. Lisp has concept of places - locations in memory.
3. setf works directly with places and can be used to mutate variables. Macros may be used to overcome limitations of functions.

Note, that some built-in functions in CL can return places, e.g. car, cdr, aref and also all object accessors. See this pages for some examples.

UPDATE

Your new question is where to modify values - inside the function by reference or outside without references. However, none of these would be correct in functional programming. Right answer here is: don't modify anything. In FP you normally have some state variable(s), but instead of modifying it in place you create modified copy and pass it further, so that original variable is not changed. Consider example of recursive function for calculating factorial:

(defun factorial-ex (x accum)
   (if (<= x 1) 
      accum
      (factorial-ex (- x 1) (* x accum))))

(defun factorial (x)
   (factorial-ex x 1))

factorial-ex is auxiliary function that takes one more parameter - accumulator to hold current state of calculation. On each recursion call we decrease x by 1 and multiply accum by current value of x. However, we don't change values of x and accum - we pass new values into recursive call to the function. Physically there are many copies of x and accum - one for each function call - and none of them ever changes.

(Note, that some CL implementations with particular options could use so-called tail call optimization that breaks statement about different locations in memory above, but at the moment you shouldn't worry about it.)

In your task you can do the same thing. Instead of modifying your 3 variables - either inside or outside function - make their modified copies and pass them to recursive call. In imperative programming you use variables and loops, and in functional programming you should prefer immutable values and recursion.

Answer 2

The builtin macro rotateffulfills this functionality:

(setf x 1)
(setf y 3)
;x = 1, y = 3
(rotatef x y)
;x = 3, y = 1

In order to write your own function to do this, I would recommend creating a macro:

(defmacro my-swap (a b)
     `(let ((temp ,a))
          (setf ,a ,b)
          (setf ,b temp)))

However, as Clayton pointed out this macro will fail if it is applied to a variable named "temp". Hence, we can use gensym to create a new variable name (guaranteed to not be in use) and pass that to a secondary macro which actually switches the values:

(defmacro my-swap-impl (a b sym) ;;implementation of my-swap
          `(let ((,sym ,b)) ;evaluate the symbol and use it as a variable name
             (setf ,b ,a)
             (setf ,a ,sym)))

This is a version of the previous swap macro that accepts a third argument to serve as the temporary variable name. This is called from a simple macro:

(defmacro my-swap (a b) ;;simply passes a variable name for use in my-swap-impl
          `(my-swap-impl ,a ,b ,(gensym)))

This setup can be used exactly like the previous one except that it is safe from variable capture.

Answer 3

First of all, you have to make sure you properly understand you task. To return modified inputs doesn't equate to modify the inputs.

Returning modified inputs is trivial. Consider this simple example:

(defun foo (bar)
  (1+ bar))

This function will return the input bar modified by adding 1 to it. You can think of a more general function, that takes an input and a modification routine and applies it to the input (or inputs). Such function is called apply:

CL-USER> (apply '1+ '(1))
2

Now, if you want to modify the value of the variable passed to a function, it is indeed impossible to do straightforward, because Lisp uses pass-by-value and not pass-by-reference or pass-by-name for function application. So such task is usually accomplished with special or general-purpose modification macros like setf which use call-by-name.

Yet, there's another work-around here which may be useful in some limited number of cases - you can't modify the value of a variable, but you can modify a value stored in some data structure (because the data-structures are passed by value and not via copy). So if you pass the data-structure to a function, you can change the value inside it. For instance,

(defun swap (v1 v2)
  (psetf (elt v1 0) (elt v2 0)
         (elt v2 0) (elt v1 0)))
CL-USER> (defvar *v1* #(0))
CL-USER> (defvar *v2* #(1))
CL-USER> (swap *v1* *v2*)
CL-USER> (format t "~A ~A" *v1* *v2*)
#(1) #(0)

But I should repeat, this approach may be applicable only in a limited number of scenarios when you really know that it's what you need.

Answer 4

This is just a comment, not an answer.

"manually set a,b,c" part may be helped a bit with destructuring-bind.

To do Hanoi towers in a "modify states" way, I would invoke the move function like (move n stacks 0 2), which moves the n disks from the stack (elt stacks 0) to the other stack (elt stacks 2), thereby avoiding the "reference" issue.

If you want to call it like (move n source target) without writing it as a macro, source and target should be some kind of encapsulated stack-like objects you implement out of Lisp lists, maybe they have slots for data and their own push/pop methods which will make their slots point to new memory locations but won't change memory location of the stack objects themselves. Similar to implementing some encapsulated String class out of C null-terminated strings so that users of the String class don't need to resort to "double refer-to relation" tricks like double pointers (in C) or like the double refer-to relation: "The name stacks refers to a list, which in turn has a slot that refers to a list.." (in (move n stacks 0 2)).

One way of implementing a stack (Only tested on Emacs Lisp):

(defun make-hanoi-stack (&rest items)
  (cons items "unused slot"))
(defun hanoi-stack-push (item hanoi-stack)
  (push item (car hanoi-stack)))
(defun hanoi-stack-pop (hanoi-stack)
  (pop (car hanoi-stack)))
(defun hanoi-stack-contents (hanoi-stack)
  (car hanoi-stack))

Using stacks:

(defun move-one-item (from-hanoi-stack to-hanoi-stack)
  (hanoi-stack-push (hanoi-stack-pop from-hanoi-stack)
                    to-hanoi-stack))

(let ((stack1 (make-hanoi-stack 1 2 3))
      (stack2 (make-hanoi-stack 4)))
  (move-one-item stack1 stack2)
  (print (hanoi-stack-contents stack1))
  (print (hanoi-stack-contents stack2)))

Answer 5

^{(Make sure you understand what makes setf special).} Let's say you want to write a function that changes the content of a variable given as input. It is usually called destructive or in-place. For example you have a list (setq xs (list 1 2 3)), you call a function on your list (f xs), and suddenly your list equals (4 5 6) now.

(defun f (xs) (setf xs (list 4 5 6))) ; this won't work
(defun f (xs) (setf (car xs) 4) (setf (cdr xs) (list 5 6))) ; but this will
(defun f (xs) (setf (elt xs 0) 4)) ; this will change xs to (4 2 3)

In Common Lisp changing the value of a local (lexical) variable inside a function will just make this local variable bound to another value. (setf xs '(1 2 3)) just expands into (setq xs '(1 2 3)). But when you change the internal structure that the binding points to, then this change will be visible to every binding that points to it. So if you change a place of a list using setf, it will destructively modify the input variable.

General convention in Common Lisp is to use destructive updates as little as possible, usually on a newly created local variable, final value of which is yet to be seen by the rest of the code. Functional programming discourages destructive updates, so you can only have functions that don't touch its inputs, but only return new values. So if you come up with convoluted ways of modifying data in-place, then you are doing something wrong, try writing a function that returns new data.