A while back I had the opportunity to work with Common Lisp professionally. As has happened to many before and after me, a lot of the powerful features of Common Lisp and its implementations made me a little drunk on power for a while, but I quickly recovered.
Some things stuck with me, however. Among them was setf,
which feels similar yet different to another concept that I quite adore:
Lenses.
As with lenses and many other concepts before them, I decided to try
to understand setf more deeply by implementing it in Carp.
The final pull
request to the Carp standard library got rejected—by myself, no
less!—, but the library
lives on!
In this blog post, we’re going to look at how to implement
setf together. It’s going to be an interesting riff on what
we did when we implemented derive.
Sit tight, and grab a drink! It’s follow-along time!
What is setf, anyway?
To know how to implement it, maybe we should get acquainted with
setf first.
To understand setf, we should first talk about “places”.
Places are the name for the getter functions that we use as descriptors
to tell setf what to update. For instance, we could do:
(def x [1 2 3])
(setf (nth &x 1) 4) ; => [1 4 3]The place here would be nth. The magic here is that, by
convention, the setter is named after an existing getter function, so it
feels as if setf magically knows how to transform a getter
into a setter.
You can also register your own places. For Carp, I chose to implement three such functions:
; register-place takes a name and a function that,
; given the arguments, knows how to transform them
; into a call to the setter
(register-place 'nth
(fn [args] `(Array.aset! %@args)))
; register-simple-place is a simple abstraction
; that takes a name and the function that it
; should be rewritten to
(register-simple-place 'nth 'Array.aset!)
; register-struct-places takes a type and creates
; places for all its members
(register-struct-places 'Vector2)
(let-do [x (Vector2.init 1 2)]
(setf (Vector2.x &x) 10)
x) ; => (Vector2 10 2)Given these parameters, implementing setf should be
easy! Let’s do this!
Implementing setf
First, we need a place—no pun intended—to store our places. Since
it’s going to be a mapping from names to functions, a hashmap seems like
a good data structure. Let’s call it places.
(defdynamic places {})Next up, let’s define the registration functions.
(defndynamic register-place [name builder]
(set! places (Map.put places name builder)))
(defndynamic register-simple-place [name setter]
(register-place name
(fn [args] (cons setter args))))register-place will simply update the
places map. register-simple-place will build
upon this by building a function that just puts the setter in front of
all the arguments received.
As might be expected, register-struct-places is a little
more involved.
(defndynamic register-struct-places [t]
(map
(fn [member]
(let [name (car member)
getter (Symbol.prefix t name)
setter (Symbol.prefix t
(Symbol.concat [
'set- name '!
]))]
(register-simple-place getter setter)))
(members t)))In the end, we just iterate over the members of the type and use
register-simple-place to tie together the getters and
setters that the compiler autogenerates for us. For a
Vector type with an x coordinate, for
instance, the appropriate pair will be Vector.x and
Vector.set-x.
For convenience, we define a function to get a place from the map:
(defndynamic get-place [n]
(Map.get places n))This is really just a simple wrapper around map retrieval.
Now that we have all the plumbing for registration in place, we can
finally implement the main event, i.e. the setf macro. It
is the most intricate part of the puzzle, but most of its complexity
comes from error handling. As such, let’s look at a naïve implementation
first:
(defmacro setf [place val]
(let [setter (get-place (car place))]
(setter (cons-last val (cdr place)))))We get the setter function, and then apply it to the rest of the
form, with the new value appended. This means that
(setf (nth &x 1) 10) will be given to the setter
registered under nth as (&x 1 10). This
happens to match the signature of Array.aset! perfectly, so
we can register it as a pass-through, i.e. a
simple-place.
Now, to enable setting variables, we use a trick: we transform it
into a list or (sym <variable>) and register
set! as a simple-place, meaning that
(setf x 10) will first be transformed to
(setf (sym x) 10), and then to (set! x 10). To
enable that behavior, we have to change setf a little:
(defmacro setf [place val]
(let [place (if (symbol? place) `(sym %place) place)
setter (get-place (car place))]
(setter (cons-last val (cdr place)))))Alright, all that’s left is handling errors gracefully. First, let’s make sure we give a good error message when a place isn’t known:
(defmacro setf [place val]
(let [place (if (symbol? place) `(sym %place) place)
key (car place)
setter? (get-place key)]
(if (= nil setter?)
(macro-error
(list
"I didn’t find a `setf` place for " key
". Is it defined?"))
(setter? (cons-last val (cdr place))))))Since Map.get will return nil when the key
doesn’t exist, we can just check for that and move on. Now there is only
one error case left that we have to deal with: garbage input.
(defdynamic malformed (gensym-with 'place-malformed))
(defmacro setf [place val]
(let [place (if (symbol? place) `(sym %place) place)
key (if (and (list? place)
(not (empty? place))
(symbol? (car place)))
(car place)
malformed)
setter? (get-place key)]
(cond
(= key malformed)
(macro-error
(list
"The `setf` place " place
" is malformed. Expected a list or symbol."))
(= nil setter?)
(macro-error
(list
"I didn’t find a `setf` place for " key
". Is it defined?"))
(setter? (cons-last val (cdr place))))))We introduce a special symbol to signal that the place that was put in was not a non-empty list that starts with a symbol. Any non-empty list that has a symbol as its first element could potentially be a valid place, anything else is invalid.
And that’s all we need to do to define setf!
Fin
If you followed my derive
journey, a lot of the ground we covered today should be familiar
territory. If you didn’t—and also if you did!—, I hope you enjoyed our
little journey, maybe learned a thing or two, and got inspired to play
around with the concepts a bit on your own time.
See you soon!