2.40.3 Rationale

The first question about this library is why it should exist at all. Why not simply eliminate mutability from Scheme’s ordinary pairs and use a version of SRFI-1 that treats the linear–update procedures (with ‘!’) as identical to their functional counterparts, as Racket does? The main answer is that this approach breaks R5RS and R6RS–small. All the data structures in these versions of Scheme are inherently mutable, and portable code is allowed to depend on that property.

R6RS segregates set-car! and set-cdr! into a separate library, thus allowing implementations to provide immutable Scheme pairs if this library is not (transitively) imported into a program, and mutable ones if it is. However, it is not possible to write portable R6RS programs that differentiate between mutable and immutable pairs, for example by using immutable pairs most of the time and mutable pairs where necessary.

Because of the Liskov Substitution Principle, it is not possible to treat mutable pairs as either a subtype or a supertype of mutable ones; they must be distinct, and if operations are to apply to both, they can do so only by ad hoc polymorphism of the kind that Scheme traditionally avoids for several reasons, including clarity, efficiency, and flexibility. This proposal, therefore, treats mutable and immutable pairs separately, while allowing easy conversion from one to the other.

Rather than attempting to design this library from scratch, I have chosen the conservative option of modifying SRFI-1. Consequently, most of the rationale given in that document applies to this one as well. I have made the following changes:

• Removed all linear–update procedures ending in ‘!’.
• Removed all references to circular lists (there will be a future SRFI for immutable bidirectional cycles).
• Removed the O(n^2) lists–as–sets procedures (there will be a future SRFI supporting O(log n) immutable sets).
• Inserted an ‘i’ at a judicious place in each identifier, usually at the beginning. However, because “icons” means something else in both ordinary English and computer jargon, the basic constructor and its immediate relatives are named ipair, xipair and ipair* instead.
• Added procedures for conversion between ordinary and immutable pairs, lists, and trees.
• Added an analogue of apply for applying a procedure to an immutable list of arguments.
• Added SRFI-114 comparators for immutable pairs, lists, and dotted lists.

NOTE In the prose, immutable pairs and lists are known as ipairs and ilists throughout.