As mentioned, even though FSet’s collections are functional, it nonetheless provides several operations that appear at first glance to be mutating. As I explained in that section, you can, if you like, employ the mental model that FSet’s collections are mutable, but that binding and assignment do not cause aliasing. This isn’t actually how the FSet implementation works, but the semantics would be equivalent if it did.
Common Lisp provides a general, extensible macro, setf, which takes an expression called a
“place” (in C/C++, the term would be “lvalue expression”) and a second expression which is
evaluated normally, and updates the place so it holds the value. Exactly what this means depends on
the place expression.
There are, for our purposes, two kinds of place expressions: those that are directly assignable, and
those that use what I’ll call a “functional accessor”. Directly assignable places include
variables (the most common example), as well as invocations of built-in accessors such as car
or aref, slot accessors on user-defined classes, and function calls for which a setf
function is also defined. For such cases, CL has, or has been given, a procedure that writes a
value into the location, however it is represented.
Functional accessors, in contrast, take another place as an argument; a setf of a functional
accessor expression then updates the inner place so that its value contains the value being stored.
That is, the functional accessor specifies a computation, on the existing value of the inner place
and the value being stored, to produce a new value of the inner place.
CL has three predefined
functional accessors: ldb, mask-field, and getf. For example, ldb as a
function extracts a byte from an integer; when used as a setf place, it arranges for a value
to be stored back into such a byte. So, (setf (ldb (byte 6 4) w) 42) is equivalent to
(setq w (dpb 42 (byte 6 4) w)); that is, it updates w so that its byte of width 6 at
position 4 contains 42. (Nowadays most people would say “bitfield”, but Lisp harks back to a time
when “byte” did not necessarily imply 8 bits.)
FSet defines two functional accessors, lookup and @.
They take the first argument as the inner place expression, and effectively expand to a setf
of that place:
(setf (lookup place key) value) ; or (setf (@ place key) value)
is equivalent to
(setf place (with place key value))
(Three-argument with performs a functional update on a map or seq, adding a map pair or
replacing the previous value, or changing the value of a seq at an index. I’m skipping over some
details here having to do with avoiding repeated evaluation of subexpressions.)
Functional accessor expressions can be nested. Sometimes people use “chained maps”, where the range values of an outer map are inner maps. An FSet expression like
(setf (@ (@ m k1) k2) value)
will have the effect of storing value under key k2 of the inner map that’s under key
k1 of the outer map. Again, it will do this by constructing a new inner map and then a new
outer map, and assigning the latter back to m.
Thus, setf expansion descends recursively through functional accessors in the place
expression until it reaches a directly assignable inner place. Usually, that’s a variable
reference, but it could also reference an array element or a slot of an object.
CL also has a concept called a “modify macro”, that abstracts expressions of the form:
(setf place (operation place args...))
Examples of predefined modify macros in CL are incf and push. FSet defines several of
these. An example is includef:
(includef s x)
is equivalent to
(setf s (with s x))
(Two-argument with adds an element to a set or bag.)