Places🔗

The base form of bindings in Lisp is assigning a value to a symbol¹:

> (setq x 2)

But what about assigning to things that aren’t symbols, like slots or arrays? If we want to access the first slot of a humble cons cell we can just use car:

> (defvar c (cons 1 2))

> (car c)
1

And to set it we use what seems to be one and the same:

> (setf (car c) 3)
> c
(3 . 2)

What just happened? Lisp doesn’t truly have something that lets you read and write some space. There is no variable.property like in C that would be a read-write reference to store your value.

Rather you have separate built-in functions to modify all the standard slots.

> c
(3 . 2)

> (rplaca c 0)
(0 . 2)

> (rplacd c 0)
(0 . 0)

And when you run setf, the form expands into these:

> (macroexpand '(setf (car x) 2))
(RPLACA X 2)

> (macroexpand '(setf (cdr x) 2))
(RPLACD X 2)

The magic of this is that (car x) looks like something that can be both read and written. Things with this kind of property are called a “place”.

As an example (there’s other ways to define setf expansions) defsetf² allows us to define a place changed by a function. The short form takes a name and the update function which will be called when setf is used on the given name. The function takes the container to be changed and the new value to place into it.

> (defsetf uppity update)
UPPITY

> (macroexpand '(setf (uppity p) v))
(UPDATE P V)

setf-s can also be nested, if we want to change the slot of a slot (variable.prop1.prop2 in C land):

> (macroexpand '(setf (car (car x)) 2))
(RPLACA (CAR X) 2)

> (macroexpand '(setf (car (aref x 1)) 2))
(RPLACA (AREF X 1) 2)

> (macroexpand '(setf (slot-value (aref x 1) 'v) 2))
(SB-PCL::SET-SLOT-VALUE (AREF X 1) 'V 2)

As you may notice, the entire trick is to only transform the outermost form and just run the rest, since they return the value you’re trying to edit.

A trick used by fset (functional collections)🔗

fset is an amazing library for functional data structures in Common Lisp. It also contains things that are so called “setf-able”³.

Now you may ask, how can a immutable collection use setf? Simply because modifying the collection sets your own reference to it to the new value, leaving the original unmodified.

Something like

foo->x = 2;

being rewritten to:

foo = &foo.with_changed_x(2);

In the case of fset, it defines fset:lookup which is setf-able:

> (defvar m (fset:empty-map))
M

> m
#{| |}

> (macroexpand '(setf (fset:lookup m "a") 2))
;; Desugared a bit
(LET* ((#:KEY "a")
       (#:VAL 2)
       (#:NEW
         (FSET:WITH M #:KEY #:VAL)))
  (SETQ M #:NEW)
  #:VAL)

> (setf (fset:lookup m "a") 2)
2 (2 bits, #x2, #o2, #b10)

> m
#{| ("a" 2) |}

And you can see that the expansion uses fset:with which returns a changed copy, and just sets your reference to the new value.

Sidenote on custom places🔗

I had a thought here that although one could define a setf expander and a reading function to create a place consisting of multiple accesses, a macro expanding to a place does this by itself.

> (defmacro headcar (a) `(car (aref ,a 0)))
HEADCAR

> (defvar a #((1)))
A

> a
#((1))

> (headcar a)
1 (1 bit, #x1, #o1, #b1)

> (setf (headcar a) 20)
20 (5 bits, #x14, #o24, #b10100)

> (headcar a)
20 (5 bits, #x14, #o24, #b10100)

> a
#((20))

Lenses (functional references)🔗

Haskell needs to solve a similar problem for a different reason. Getters are kind of simple, if I have functions like getAge :: Person -> Age and getPerson :: Employee -> Person I can just getAge . getPerson :: Employee -> Age. However modifying that value suddenly becomes much harder. By modify I of course mean, return a copy with the given change applied since we are pure here.

Although they can be used as just a getter and setter, I think one of the currently most talked about ways to do this is from Tan van Laarhoven’s blog. The idea is to have one value:

type RefF a b = forall f. Functor f => (b -> f b) -> (a -> f a)

Which based on the Functor will either return the property’s value, or apply the changed property back into the original structure and return that. I won’t go into too much detail since the original blogpost is a very short and interesting read by itself.

The important fact is that these are composable, _1 . _2 allows us to both read and write the x[1][2] field of some structure.

It’s also cool that these are values so can be saved and passed around⁴, and that they are polymorphic. Many of the lens operators use typeclasses so are general over anything that has a notion of “first”, “index into”, “prepend” or other similar characteristics.

Final words🔗

I find these two concepts to be remarkably similar in the association of projections and change, even though they employ vastly different methods to get there, which makes sense since they were created for completely different reasons.

I’m aware that the functional data structure modifications could easily be done via a wrapper struct which holds a pointer to an immutable structure which is a pattern I’ve actually not seen used anywhere yet.

Lenses are fascinating and I’m definitely adding them to my daily arsenal.

Footnotes🔗

¹ setq more or less just quotes the symbol, we could’ve used (set 'x 2)

² There is also define-setf-expander which is so general I don’t even understand how exactly to use it currently.

³ Which is a general term for anything that has a setf expansion. I guess something being a place implies it is setf-able, but if the setf call doesn’t emulate setting a reference then it’s not a place.

⁴ Equivalent to a lambda that returns a reference to a subfield in other languages.