Next: , Up: The Design of FSet   [Contents][Index]

4.1 Divergences from Common Lisp

There are two major ways in which FSet’s collections differ from the ones built into CL.

The first, of course, is the functional semantics. This isn’t a total departure, because lists are frequently used functionally. But, of course, cons cells sometimes are used as mutable objects; arrays are usually used as mutable objects; the CL sequence functions, that abstract over lists and vectors, expect mutability; and hash tables are mutable objects.

In What Is a Functional Datatype?, I explained what a functional datatype is, and pointed out that they can provide operations that can be conceptualized either as computing a new value for a collection and reassigning it to the variable holding it, or as a mutation to an unaliasable value.

This means that FSet’s update operations have to work differently from most CL builtins. The clearest example has to do with the behavior of setf. (I’ll say more about setf below; non-CL-programmers might want to read that first.) If you have a CL vector v, you can set one of its elements using setf of elt: 

(setf (elt v i) x)

If, instead, you have an FSet seq s, you can write an expression that looks superficially similar: 

(setf (lookup s i) x)

However, it means something quite different. In the elt case, if there are other variables directly or indirectly bound to v, they will also see the change: a mutable shared object has been modified. The lookup case, however, is equivalent to 

  (setq s (with s i x))

where the FSet with operation returns an updated seq that now has x at index i. The change will not be visible anywhere except through variable s.

I have occasionally heard people complain that this is against the spirit of the language, but it really isn’t. Consider this example: 

  (let* ((a nil)
         (b a))
    (push 'foo a)
    b)

Every CL programmer knows, without even thinking about it, that the above evaluates to nil: the modification performed by push is visible only through a, not through b. Lists are usually used functionally, and this, notwithstanding the setq implied by the push, is an example; there is no potentially shared list object being modified here.

"But," some might say, "that’s push, not setf." All right, here’s another example: 

  (let* ((a 1)
         (b a))
    (setf (ldb (byte 2 1) a) 3)   ; a becomes 7
    b)

Here there’s a setf of an expression wrapping a, but its effect is still just to assign a new value to a; b is still 1. Again, every CL programmer knows this without thinking about it; integers are not aliasing, mutable objects.

So no matter how long you’ve been writing Common Lisp, learning FSet is not going to break your brain.

The second major way in which FSet’s design diverges somewhat from CL’s has to do with semantic loading. Lisp lists are semantically unloaded. A list can be used as a sequence; as a set, where order is unimportant and duplicates are not allowed; as a bag, where order is unimportant and duplicates are allowed; as a map, in either alist or plist form; or in many other ways. So, as a programmer writing code to do something with a list, you have to remember the intended semantics of this particular list. Also, you have to remember what equivalence relation you intended to compare elements with. Sometimes, the default of eql suffices, but often, you want to compare elements by their contents rather than their identity; in such cases, you have to pass in the equivalence relation every time you call member, assoc, find, etc. But doing so violates the well-known “DRY principle” (Don’t Repeat Yourself).

In contrast, FSet collections are semantically loaded: they carry their semantics, including the applicable equivalence relation, along with them, so you don’t have to supply it at every call. (CL hash tables are like this too, so again, it’s not a complete departure.)

This semantic loading makes code that uses FSet more elegant, and practically eliminates bugs that can occur when a list is not used consistently across the program. But it did cause one design quandary. I wanted to provide shadowed versions of Lisp builtins like find, position, count, etc. that would work on FSet collections but would bounce to the CL builtins if passed a list. The catch was, FSet has its own default notion of equality; defaulting to eql didn’t make sense.

I finally settled on this approach: While generic versions of a number of operations will be provided, it is critical for the user to understand that the purpose of this genericity is not so that you can write code that will actually be called on both Lisp sequences and the FSet types. Rather, the goal is more modest: to make familiar functionality accessible by familiar names, so that you can write FSet code without having to learn new names for find etc.

One issue with this approach has to do with the Lisp names first, rest, last, and second through seventh. First, let’s note the inconsistencies already in CL:

For FSet seqs — as the sequence type is called, to distinguish it from CL sequences — I felt it was important to treat first and last symmetrically, since the implementation is symmetric. Also, there is a whole structure of related operations operating on the ends of seqs; I have called these with-first, with-last, less-first, less-last, push-first, push-last, pop-first, and pop-last, the first four being the functional update operations, and the last four being the modify macros that invoke the first four, respectively. Because of the importance of these operations, I felt it would be acceptable to force some compromises on existing code. So FSet exports a generic function first which includes a compatibility method for lists; here the impact on existing code is limited to the cost of the CLOS dispatch. For last, however, I decided to make an incompatible change: fset2:last, on a list, returns the last element rather than the last cons. FSet also exports the functionality of cl:last as lastcons — clearly a better name.

FSet does not, however, export any version of rest, or of second through seventh. For rest, I think less-first is better because it participates in the symmetric structure shown above.

(From the perspective of FSet, with its symmetric functional sequences, it strikes me as a little unfortunate that the names that caught on as modern replacements for car and cdr were first and rest instead of, say, head and tail. first and rest, it seems to me, are naturally applied to any sequence, where head and tail more specifically suggest the structure of a list. So FSet exports head and tail as synonyms for car and cdr.)

Another issue: I mentioned above that generic-function versions of find-if etc. are provided. They are, but they are not completely compatible when invoked on FSet types (they are completely compatible when invoked on Lisp sequences). The primary differences are:

Next: Comparison and Equality, Up: The Design of FSet   [Contents][Index]