The Common Lisp setf function is deceptively humble looking. At the start I didn’t think much of it – except that it looked eccentric compared to the assignment syntax from other languages – but recently I’ve found out how powerful it is, though not quite as convenient as I would hope.
In most languages to perform a variable assignment one does something like
int a = 22;
which places the value “22” into a place in memory which can be accessed by writing “a” in the program.
In Common Lisp the corresponding syntax is
(setf a 22)
and the only thing weird about it is the everything-is-a-list pattern of Lisp.
I was blown away, though, when I saw code that looked like this
(setf x `(1 2 3 4 5)) ; x -> (1 2 3 4 5) (setf (rest x) `(6 7 8)) ; x -> (1 6 7 8)
You can’t do this as transparently in C++ or Python. You can implement a function to do the equivalent thing, but you can’t assign a value to the return value of a function. This Lisp syntax makes writing code very compact and logical.
However, I stumbled when I tried to use this in a function I wrote. My function started at the root of a complete binary tree and then snaked recursively through it to find and return a particular node.
;; Use the binary representation trick to thread through the ;; tree to a given node. No bounds checking is done here ; root - the root of the tree ; index - the index number of the node (1 = root) (defun find-node (root index) (multiple-value-bind (n-idx rem) (floor index 2) (if (= n-idx 1) (find-node-pick-child root rem) (find-node-pick-child (find-node root n-idx) rem)))) (defun find-node-pick-child (nd rem) (if (= rem 0) (node-lchild nd) (node-rchild nd)))
When I tried to execute the statement (which I expected to attach new-node to the place returned by find-node)
(setf (find-node root 8) new-node)
I ran into compiler errors.
This lead me on a very interesting chase all round the internet with the word “generalized variables” turning up a lot. It turns out that (setf …) is a lisp macro that can figure out how to get hold of the “place” its first argument refers to. If the first argument is just a variable, (setf …) acts just like the assignment statement in any other language. If the first argument is a function, Lisp will (effectively) call that function and setf on the place returned by the function. This function however has to have a special form for this to work and is called an accessor function
Following advice from answers on comp.lang.lisp, I came up with the following code:
;; Use the binary representation trick to thread through the ;; tree to return an tree node and some auxiliary information ;; No bounds checking is done here ; root - the root of the tree ; index - the index number of the node (1 = root) ; Return value is a pair ; node - a node of the tree ; info - :me - this is the node we're looking for ; :lchild - we want the left child ; :rchild - we want the right child (defun find-node-with-index (root index) (multiple-value-bind (new-idx rem) (floor index 2) (cond ((= new-idx 0) (values root :me)) ((= new-idx 1) (values root (if (= rem 0) :lchild :rchild))) (t (find-node-with-index (if (= rem 0) (node-lchild root) (node-rchild root)) new-idx))))) (defun node-with-index (bh index) (multiple-value-bind (nd info) (find-node-with-index (bheap-root bh) index) (case info (:me (bheap-root bh)) ; Special case - root of heap (:lchild (node-lchild nd)) (:rchild (node-rchild nd))))) (defun (setf node-with-index) (new-node bh index) (multiple-value-bind (nd info) (find-node-with-index (bheap-root bh) index) (case info (:me (setf (bheap-root bh) new-node)) ; Special case - root of heap (:lchild (setf (node-lchild nd) new-node)) (:rchild (setf (node-rchild nd) new-node)))))
I like the DRY principle primarily because it reduces bugs and the total amount of code. I tried to abstract as much of the core functionality into a single function as I could, but the getter and setter functions look so duplicate, but I don’t think I can reduce them further.
Thanks go to Kaz Kylheku and Barry Margolin on comp.lang.lisp for answering my questions on this topic.