How do setf works under the hood?

Currently learning common lisp, following Peter Seibel's Practical Common Lisp (i'm at chapter 11, about collections), i have difficulties to understand how setf works behind the hood.

Considering this expression :

(setf a 10)

I completely understood how the interpreter can (1) retrieve the variable named a, and (2) change the value it points to to 10.

Now, i case of particular collections, for instance lists, vectors or hash tables, setf can also be used to change values contained by the collection. For instance, with a vector :

(defparameter *x* '(a b c d))
(setf (elt *x* 1) bb)

This makes me suspicious about setf, because it is eventually finding non-trivially accessible information, or making black magic. I see multiple possibilities.

1. setf is a function

The (elt *x* 1) expression is returning 'b, so setf is virtually working with (setf b bb). I then do not understand how setf can infer which object (here, the list *x*) it must modify, without having the return value of elt holding both an indication that it comes from a collection, and a pointer to the said collection. Seems complicated.

2. setf is a macro

The idea is, as setf is a macro, it works directly with the (setf (elt *x* 1) bb) and therefore can extract the elt *x* 1 part to infer which object/collection is used, and therefore must be modified.

It do not seems very efficient, nor reliable, nor resistant to complex operations. However, since i'm unable to run this code :

(funcall (find-symbol (concatenate 'string "E" "LT")) *x* 1)  ; -> B
(setf (funcall (find-symbol (concatenate 'string "E" "LT")) *x* 1) 'bb) ; -> ERROR : (SETF FUNCALL) is only defined for functions of the form #'symbol

This make me think that setf is a macro implementing a very simple heuristic to retrieve the function to call, and all other needed information. Seems complicated.

3. setf is a special case of interpretation

Another way to go could be to have setf be handled differently by the interpreter itself, dealing with some black magic to implement properly the expected behavior. Seems complicated.

4. there is something i do not know about lisp

Probably the real answer. What did i miss ?

Bonus question : is the implementation method dependent of the lisp interpreter implementation ? (or, more simply, what exactly the common lisp standard define about setf implementation) I'm currently using clisp but insights on others implementations are welcome.

Solution

SETF is a macro that sets a value to a place. A place means a form that has a setf expansion. There are various kinds of places built-in, and you can define more (see for example DEFSETF and DEFINE-SETF-EXPANDER, function call forms as places and macro forms as places).

You can get the setf expansion for a form using GET-SETF-EXPANSION. It returns five values. For example,

(get-setf-expansion '(elt *x* 1))
;=> (#:*X*660)
;   (*X*)
;   (#:NEW1)
;   (SB-KERNEL:%SETELT #:*X*660 1 #:NEW1)
;   (ELT #:*X*660 1)

The fifth value is a getter form that, when evaluated, returns the current value of the place. The fourth one is a setter form that, when evaluated, sets a new value to the place. Here you can see that SBCL uses SB-KERNEL:%SETELT to set the value.

The first value is a list of variable names that should be bound to the values returned by the forms in the second value when evaluating the setter/getter forms. The third value is a list of store variables, which should be bound to the new values to be stored by the setter.

With these we can define a simple MY-SETF-macro.

(defmacro my-setf (place values-form &environment env)
  (multiple-value-bind (vars vals stores setter)
      (get-setf-expansion place env)
    `(let* ,(mapcar #'list vars vals)
       (multiple-value-bind ,stores ,values-form
         ,setter))))

All we need to do is to bind the variables, and evaluate the setter. Notice that the environment should be passed to GET-SETF-EXPANSION. We ignore the fifth value (the getter), since we don't need it. MULTIPLE-VALUE-BIND is used to bind the store variables, because there may be more than one of them.

(let ((list (list 1 2 3 4)))
  (my-setf (elt list 2) 100)
  list)
;=> (1 2 100 4)

(let ((a 10) (b 20) (c 30))
  (my-setf (values a b c) (values 100 200 300))
  (list a b c))
;=> (100 200 300)

There are various ways to define your own places. The easiest ways are to use DEFSETF or just define a setf-function with DEFUN. For example:

(defun eleventh (list)
  (nth 10 list))

(defun set-eleventh (list new-val)
  (setf (nth 10 list) new-val))

(defsetf eleventh set-eleventh)

(let ((l (list 1 2 3 4 5 6 7 8 9 10 11 12 13)))
  (setf (eleventh l) :foo)
  l)
;=> (1 2 3 4 5 6 7 8 9 10 :FOO 12 13)

(get-setf-expansion '(eleventh l))
;=> (#:L662)
;   (L)
;   (#:NEW1)
;   (SET-ELEVENTH #:L662 #:NEW1)
;   (ELEVENTH #:L662)


(defun twelfth (list)
  (nth 11 list))

(defun (setf twelfth) (new-val list)
  (setf (nth 11 list) new-val))

(let ((l (list 1 2 3 4 5 6 7 8 9 10 11 12 13)))
  (setf (twelfth l) :foo)
  l)
;=> (1 2 3 4 5 6 7 8 9 10 11 :FOO 13)

(get-setf-expansion '(twelfth l))
;=> (#:L661)
;   (L)
;   (#:NEW1)
;   (FUNCALL #'(SETF TWELFTH) #:NEW1 #:L661)
;   (TWELFTH #:L661)