2.2.4.2 “Linear update” procedures

Many procedures in this library have “pure” and “linear update” variants. A “pure” procedure has no side–effects, and in particular does not alter its arguments in any way. A “linear update” procedure is allowed, but not required, to side–effect its arguments in order to construct its result. “Linear update” procedures are typically given names ending with an exclamation point.

So, for example, (append! list1 list2) is allowed to construct its result by simply using set-cdr! to set the cdr of the last pair of list1 to point to list2, and then returning list1 (unless list1 is the empty list, in which case it would simply return list2). However, append! may also elect to perform a pure append operation, this is a legal definition of append!:

(define append! append)

This is why we do not call these procedures “destructive”, because they aren’t required to be destructive. They are potentially destructive.

What this means is that you may only apply linear–update procedures to values that you know are “dead”, values that will never be used again in your program. This must be so, since you can’t rely on the value passed to a linear–update procedure after that procedure has been called. It might be unchanged; it might be altered.

The “linear” in “linear update” doesn’t mean “linear time” or “linear space” or any sort of multiple–of–n kind of meaning. It’s a fancy term that type theorists and pure functional programmers use to describe systems where you are only allowed to have exactly one reference to each variable. This provides a guarantee that the value bound to a variable is bound to no other variable. So when you use a variable in a variable reference, you “use it up”. Knowing that no one else has a pointer to that value means the a system primitive is free to side–effect its arguments to produce what is, observationally, a pure–functional result.

In the context of this library, “linear update” means you, the programmer, know there are no other live references to the value passed to the procedure; after passing the value to one of these procedures, the value of the old pointer is indeterminate. Basically, you are licensing the Scheme implementation to alter the data structure if it feels like it; you have declared you don’t care either way.

You get no help from Scheme in checking that the values you claim are “linear” really are. So you better get it right. Or play it safe and use the non–! procedures; it doesn’t do any good to compute quickly if you get the wrong answer.

Why go to all this trouble to define the notion of “linear update” and use it in a procedure spec, instead of the more common notion of a “destructive” operation?

First, note that destructive list–processing procedures are almost always used in a linear–update fashion. This is in part required by the special case of operating upon the empty list, which can’t be side–effected. This means that destructive operators are not pure side–effects, they have to return a result.

Second, note that code written using linear–update operators can be trivially ported to a pure, functional subset of Scheme by simply providing pure implementations of the linear–update operators.

Finally, requiring destructive side–effects ruins opportunities to parallelise these operations, and the places where one has taken the trouble to spell out destructive operations are usually exactly the code one would want a parallelising compiler to parallelise: the efficiency–critical kernels of the algorithm.

Linear–update operations are easily parallelised. Going with a linear–update spec doesn’t close off these valuable alternative implementation techniques. This list library is intended as a set of low–level, basic operators, so we don’t want to exclude these possible implementations.

The linear–update procedures in this library are:

alist-delete!           append!
append-map!             append-reverse!
break!                  concatenate!
delete!                 delete-duplicates!
drop-right!             filter!
lset-adjoin!            lset-diff+intersection!
lset-difference!        lset-xor!
lset-intersection!      lset-union!
map!                    partition!
remove!                 reverse!
span!                   split-at!
take!                   take-while!