Welcome to SRFI 116, Immutable Lists

[John Cowan <cowan@xxxxxxxxxxxxxxxx>]

Though SRFI 116 has been up for a while, the mailing list wasn't working
until today, when the efforts of our Able Editor made it available.
For those of you who haven't seen the SRFI yet, here are the abstract
and rationale:

Abstract

    Scheme currently does not provide immutable pairs corresponding
    to its existing mutable pairs, although most uses of pairs do not
    exploit their mutability. The Racket system takes the radical
    approach of making Scheme's pairs immutable, and providing a
    minimal library of mutable pairs with procedures named mpair?,
    mcons, mcar, mcdr, set-mcar!, set-mcdr!. This SRFI takes the
    opposite approach of leaving Scheme's pairs unchanged and
    providing a full set of routines for creating and dealing
    with immutable pairs. The sample implementation is portable
    (to systems with SRFI 9) and efficient.

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 R7RS-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(n2) 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.


-- 
John Cowan          http://www.ccil.org/~cowan    cowan@xxxxxxxx
They tried to pierce your heart with a Morgul-knife that remains in
the wound.  If they had succeeded, you would become a wraith under the
domination of the Dark Lord.         --Gandalf