Nondestructive setf?

Question

Common Lisp seems to go to great lengths to provide both nondestructive functions (like subst & remove) and destructive functions and modify macros (like delete & rotatef) for general use. Presumably this is to effectively support both functional and nonfunctional styles of programming. But there also seems to be a particular bias toward the nonfunctional style in the design of the ubiquitous setf. The setf macro, incorporating generalized reference, is apparently flexible enough to modify any specifiable place (except perhaps for immutable integers and characters). This power probably accounts for its widespread useage in spite of its nonfunctional/destructive behavior.

The question is why there is not a corresponding "functional style" nondestructive operator, patterned after setf (call it put, since set is already taken), analogous to other nondestructive/destructive lisp operator pairs. Such an operator would probably take the same arguments, a place and a value, but would return a copy of the object in which the place was embedded, instead of the new value at that place. It also would probably involve a universal copier of some sort, with the standard setf simply modifying the copy before returning it. The nondestructive operator then could be used in lieu of setf for most assignments, with setf being reserved for really large objects. Is such an operator feasible (or even possible) given the (presumed) requirement for a universal copier and the need to recover an object from an arbitrary place embedded in it?

Answer 1

Common Lisp has no universal copier for the same reason it does not have a built-in printable representation of CLOS objects (see, e.g., Saving CLOS objects): the power of MOP.

Specifically, object creation can have arbitrary side effects whose replication is hard to guarantee. E.g., define initialize-instance for your class to modify slots based something fluid (e.g., tides or just random). Then the result of make-instance called with the same arguments twice may be different. You might argue that this is an argument in favor of a memcpy-style generic copier. However, imagine now a class which does instance accounting (an :allocation :class slot which contains a hash table mapping unique ID to instance). Now, the round trip from the copied object via the table will get a different object (the original, not the copy) - a major contract violation. And these examples are just the tip of the iceberg.

However, I would not agree that Common Lisp encourages imperative style more than functional style. It merely discourages the style you describe (copy+setf). Think about it this way: from the functional POV, a copy is indistinguishable from the original (because everything is immutable).

There are also "small hints" showing a clear preference for functional style. Observe that the "natural" names (e.g., append) are reserved for non-destructive functions; the destructive versions (e.g., nconc) are given obscure names.

Additionally, pathnames, characters and numbers (including composites like ratio and complex) are immutable, i.e., all pathname and number functions create new objects (functional style).

Thus, IMO, Common Lisp encourages programmers to use functional style while still making imperative style feasible, in conformance to the slogan "simple things should be easy, hard things should be possible".

See also Kent Pitman's writeup.

Answer 2

There is no universal setter either, but with SETF you are supposed to provide one when you use DEFINE-SETF-EXPANDER. I suppose you could define the equivalent of lenses/functional references. For another approach, Clojure defines an update function (borrowed from other languages, I know it exists in Prolog), which is not universal either. The FSET library provides some functional structures, notably associative maps which work like the ones in Clojure.

Suppose for a moment you limit yourself to structures:

(defstruct foo a b c)
(defstruct bar x y z)

(defparameter *test*
  (make-foo :a (make-bar :x 0 :y 0 :z 0)
            :b 100
            :c "string"))

;; *test* is now
;; #S(FOO :A #S(BAR :X 0 :Y 0 :Z 0) :B 100 :C "string")

The following approach makes a copy, it relies on copy-structure and slot-value, which, while not standard, is well supported:

(defun update (structure keys value)
  (if (endp keys)
      value
      (destructuring-bind (key &rest keys) keys
        (let ((copy (copy-structure structure)))
          (setf (slot-value copy key)
                (update (slot-value copy key)
                         keys
                         value))
          copy))))

You can update *test* as follows:

(update *test* '(a z) 10)

Here is a trace:

0: (UPDATE #S(FOO :A #S(BAR :X 0 :Y 0 :Z 0) :B 100 :C "string") (A Z) 10)
  1: (UPDATE #S(BAR :X 0 :Y 0 :Z 0) (Z) 10)
    2: (UPDATE 0 NIL 10)
    2: UPDATE returned 10
  1: UPDATE returned #S(BAR :X 0 :Y 0 :Z 10)
0: UPDATE returned #S(FOO :A #S(BAR :X 0 :Y 0 :Z 10) :B 100 :C "string")

In order to generalize, you could accept a function instead of a value, so that you could implement the equivalent of incf by partially applying the update function with #'1+ (the resulting closure would accept a list of keys).

Also, you need to generalize the copy operation, which is possible with generic functions. Likewise, you could use other kinds of accessors, and replace slot-value with a generic access function (for which there is a (setf access) operation). This generic copy/setf approach could be wasteful, however, if you want to share some data. For example, you only need to copy the part of a list which leads to your data, not the cons cells that are following it.

You could define some facility for defining custom updaters:

(defmethod perform-update (new (list list) position)
  (nconc (subseq list 0 position)
         (list new)
         (nthcdr (1+ position) list)))