Changes from second draft:

Specification
-------------

* The `equal?' procedure has been added.

* A `length<=?' procedure has been added for use in bounds checking on
  chains of pairs.

* Time and space bounds have been placed on `make-list'.  It must
  operate in both O(log(k)) time and space.

* Time bounds have been tightened on `list-ref', `list-set', etc.
  They are now required to operated in O(min(k,log(n))).

Implementation
--------------

* The reference implementation is completely portable.

* The implementation of `equal?' is based on code written by Michael
  D. Adams and R. Kent Dybvig in Efficient Nondestructive Equality
  Checking for Trees and Graphs, ICFP'08.

* Assertions added.

* The implementation of `car' no longer allocates.


Changes from initial draft:

Specification
-------------

* A `quote' form that produces random-access pairs when quoting
  syntactic pairs has been added.

* Examples have been rewritten to use `quote' where convenient and now
  more closely resembles the examples of R6RS.

* An issue inquiring about the scope of this SRFI has been added.
  Should the SRFI include bindings for all of (rnrs base) that deals
  with lists?

* A paragraph specifying that random-access pairs and lists are fully
  persistent has been added.  This paragraph was suggested and kindly
  provided by Alexey Radul.

* Procedure for converting between representation of lists have been
  added, following the suggestions of Taylor Campbell and Alexey
  Radul.

* A vector-like constructor, `make-list', which constructs a list
  using O(log n) space thanks to sharing, has been added.

Implementation
--------------

* The reference implementation is no longer completely portable.  It
  has been factored into a procedural and a syntactic portion.  The
  procedural portion is written in fully portable R6RS Scheme; the
  syntactic portion is written in implementation-specific libraries
  for Ikarus, Larceny, and PLT Scheme.

* Sub-libraries for the procedural and syntactic subset of the SRFI
  are now required (and provided).

* Improved test suite instructions are given for PLT Scheme to avoid
  installing the reference implementation as a collection, thus
  shadowing the srfi collection that ships with PLT.

* The reference implementation has been re-arranged into files
  according to common library name to file name mappings.

* A bug in the implementation of `list?' which had caused it to be
  O(n) has been fixed.  It is now O(log n) as required.

* The import clause of the test suite has been changed to include all
  of (rnrs base) except identifiers defined in SRFI 101, rather than
  only a small subset of (rnrs base), following the suggestion of
  Aubrey Jaffer.

Cosmetics
---------

* Procedure prototypes have been formatted so as to stand out more,
  following the suggestion of Taylor Campbell.  Prototypes now include
  return type and arity information.

* The term "sequential" has been replaced with "linear-access".

* Various typos have been fixed.