[Scheme-reports] Proposed new SRFI for immutable lists

[John Cowan]

Note: The SRFI number is not yet official and is therefore subject to change.

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 and efficient.

Rationale:

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 first, second , etc., which are mostly used for poor man's records.

* Removed the O(n2) lists-as-sets procedures (there will be a future SRFI
supporting O(n 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.

SRFI: http://www.ccil.org/~cowan/temp/srfi-116.html
Implementation: http://www.ccil.org/~cowan/temp/ilists.tar.gz

Please send comments to <srfi-***@srfi.schemers.org> when it is created,
or to this list in the meantime.

[Vassil Nikolov | Васил Николов]

I wonder if it would be useful to have a
specialized means to check for or guard
against anomalies like the value of

(cons 0 (cons 1 (ipair 2 (ipair 3 '()))))

and similar.

---Vassil.

[Kevin Wortman]

Some initial thoughts:

Should these procedures take SRFI 114 comparators instead of equality
predicates?

Are cycles actually possible in strict immutable structures? When you
create a head node, there's no way for it to have a circular link to a tail
node that doesn't exist yet.

Personally I am fond of first, second, etc.; I think they are more readable
than car, cadr, etc.

The immutable set data structures I have in mind do set-theoretic
operations in O(n) time, though constructing them from an unordered list is
O(n log n).

I would ditch xipair and factor out parameter rotation to a "flip"
procedure, probably in a separate library or SRFI, as defined in Chicken (
http://wiki.call-cc.org/man/4/Unit%20data-structures#combinators ).

Best regards,
Kevin Wortman

Post by John Cowan
Note: The SRFI number is not yet official and is therefore subject to change.
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 and efficient.
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
* Removed all linear-update procedures ending in !
* Removed all references to circular lists (there will be a future SRFI for
immutable bidirectional cycles).
* Removed first, second , etc., which are mostly used for poor man's records.
* Removed the O(n2) lists-as-sets procedures (there will be a future SRFI
supporting O(n 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.
SRFI: http://www.ccil.org/~cowan/temp/srfi-116.html
Implementation: http://www.ccil.org/~cowan/temp/ilists.tar.gz
or to this list in the meantime.
--
Schlingt dreifach einen Kreis vom dies!
Schliesst euer Aug vor heiliger Schau,
Denn er genoss vom Honig-Tau,
Und trank die Milch vom Paradies.
_______________________________________________
Scheme-reports mailing list
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports

[Alex Shinn]

Post by Kevin Wortman
Should these procedures take SRFI 114 comparators instead of equality
predicates?
Are cycles actually possible in strict immutable structures? When you
create a head node, there's no way for it to have a circular link to a tail
node that doesn't exist yet.

Yes, if you provide implementation support for it,
see http://docs.racket-lang.org/reference/shared.html

Also for lazy data structures see
http://www.haskell.org/haskellwiki/Tying_the_Knot,
for which I have a Scheme version lying around somewhere.

Personally I am fond of first, second, etc.; I think they are more readable

Post by Kevin Wortman
than car, cadr, etc.

At least remove the (scheme cxr) equivalents.

The immutable set data structures I have in mind do set-theoretic

Post by Kevin Wortman
operations in O(n) time, though constructing them from an unordered list is
O(n log n).

We should just remove the lset equivalents - that's what SRFI 113 is for.

What about iqq (quasiquote) in addition to iq?

iphone seems to be missing.

[John Cowan]

Post by Alex Shinn
Yes, if you provide implementation support for it,
see http://docs.racket-lang.org/reference/shared.html

I'll have a look.

Post by Alex Shinn
Also for lazy data structures see
http://www.haskell.org/haskellwiki/Tying_the_Knot,
for which I have a Scheme version lying around somewhere.

We're going to have SRFI 42 streams.

Post by Alex Shinn
Personally I am fond of first, second, etc.; I think they are more readable

Post by Kevin Wortman
than car, cadr, etc.

At least remove the (scheme cxr) equivalents.

Okay, both go in.

Post by Alex Shinn
We should just remove the lset equivalents - that's what SRFI 113 is for.

Already done.

Post by Alex Shinn
What about iqq (quasiquote) in addition to iq?

Good in principle, but painful.

Post by Alex Shinn
iphone seems to be missing.

*snort*

[Vassil Nikolov | Васил Николов]

Post by Alex Shinn

Post by Kevin Wortman
...
Are cycles actually possible in strict immutable structures? When you
create a head node, there's no way for it to have a circular link to a tail
node that doesn't exist yet.

Yes, if you provide implementation support for it,
see http://docs.racket-lang.org/reference/shared.html
Also for lazy data structures see
http://www.haskell.org/haskellwiki/Tying_the_Knot,
for which I have a Scheme version lying around somewhere.

By the way, some languages offer yet
another approach, in principle similar to
the latter, but more procedural. It is
to make the object construction protocol
a little more elaborate so the user (not
just the implementor) can see object
_allocation_ as a separate step from
object _initialization_. Probably
needless to add, in this way a reference
to the object becomes available (for
plugging into other objects) before the
construction of the object is finished
(with references to those other objects
plugged into it). This is just with
regards to the possibility of cycles in
strictly immutable structures; whether
this can be a candidate for adopting by
Scheme is another question.

There is also the more general approach
of "arbitrarily delayed once-only
component initialization", where any
component of an immutable object can be
initialized at any time after object
creation (no matter how much later), but
only once. If I recall correctly, Oz
allows (something like) that, but I
forget how exactly it is called there.

---Vassil.

[John Cowan]

By the way, some languages offer yet another approach, in principle
similar to the latter, but more procedural. It is to make the object
construction protocol a little more elaborate so the user (not just
the implementor) can see object _allocation_ as a separate step from
object _initialization_.

This is commonplace in OO languages such as Smalltalk and Java/C#. The
danger of it, of course, is that methods wind up being called on an object
before it is fully constructed, when its invariants do not yet hold. In a
multi-threaded program, of course, this is even more likely to happen.
Consequently, more modern APIs provide a mutable builder object that can
have various setup methods called on it, and then a "done" method which
returns an immutable working object. The builder can then be discarded.
This approach does not permit circularity, but runs far fewer risks.

[Eli Barzilay]

Post by Alex Shinn
Also for lazy data structures see
http://www.haskell.org/haskellwiki/Tying_the_Knot,
for which I have a Scheme version lying around somewhere.

Um, the usual way in which lazy code results in a proper pointer cyclic
is when it goes through some process that translates the lazy structures
into strict ones.

For example, with a (define ones (cons 1 ones)) you don't have a cycle
of pointers, in a similar way that in plain racket you don't get such a
cycle with (define ones (cons 1 (λ() ones))); the cycle is instead
implicit in the semantics of looking up `ones'. This is similar to the
pointer cycle you implicitly get with (define (onses) (cons 1 ones)).
But it does generate *real* cycle when you display the above value --
the process of translating the lazy structure to a strict one (ie,
removing all promises) results in a real #=0(1 . #0#).

It would be very interesting if you have code that achieves such a cycle
without using mutation. (Or similar features, like Racket's
`make-reader-graph' which is what Lazy Racket uses; in addition to the
usual mutation that is needed to implement call-by-need.)

[Alex Shinn]

Post by Eli Barzilay

Post by Alex Shinn
Also for lazy data structures see
http://www.haskell.org/haskellwiki/Tying_the_Knot,
for which I have a Scheme version lying around somewhere.

Um, the usual way in which lazy code results in a proper pointer cyclic
is when it goes through some process that translates the lazy structures
into strict ones.
For example, with a (define ones (cons 1 ones)) you don't have a cycle
of pointers, in a similar way that in plain racket you don't get such a
cycle with (define ones (cons 1 (λ() ones))); the cycle is instead
implicit in the semantics of looking up `ones'. This is similar to the
pointer cycle you implicitly get with (define (onses) (cons 1 ones)).
But it does generate *real* cycle when you display the above value --
the process of translating the lazy structure to a strict one (ie,
removing all promises) results in a real #=0(1 . #0#).
It would be very interesting if you have code that achieves such a cycle
without using mutation. (Or similar features, like Racket's
`make-reader-graph' which is what Lazy Racket uses; in addition to the
usual mutation that is needed to implement call-by-need.)

What are these "pointer" things you speak of? o_0

The original question was whether cycles were possible in
"strict immutable structures." I would allow promises as part of
that structure, and consider them immutable so long as they
aren't using mutable variables or data structures. There's no
reason immutable pairs couldn't be implemented in terms of
promises, in which case the tying the knot trick could be used
(under the hood) to provide utilities for generating cyclic
immutable lists.

Anyway, what I did was simply transliterate Oleg's circular
doubly-linked list example into Scheme, making Haskell's
implicit laziness explicit in the usual manner:

(define (force* x)
(if (promise? x) (force* (force x)) x))

(define (dlnode prev x next)
(vector prev x next))

(define (dlnode-prev node) (vector-ref (force* node) 0))
(define (dlnode-value node) (vector-ref (force* node) 1))
(define (dlnode-next node) (vector-ref (force* node) 2))

(define (list->dlist ls)
(define (go prev x next)
(if (null? x)
(list next prev)
(letrec ((this (delay (dlnode prev (car x) rest)))
(tmp (delay (go (force this) (cdr x) next)))
(rest (delay (car (force tmp))))
(last (delay (cadr (force tmp)))))
(list (force this) (force last)))))
(letrec ((tmp (delay (go last ls first)))
(first (delay (car (force tmp))))
(last (delay (cadr (force tmp)))))
(force first)))

(define (take-forward i node)
(if (zero? i)
'()
(cons (dlnode-value node)
(take-forward (- i 1) (dlnode-next node)))))

(define (take-reverse i node)
(if (zero? i)
'()
(cons (dlnode-value node)
(take-reverse (- i 1) (dlnode-prev node)))))

(define (test)
(take-reverse 5 (list->dlist '(1 2 3 4 5 6 7))))

[Eli Barzilay]

The original question was whether cycles were possible in "strict
immutable structures." I would allow promises as part of that
structure, and consider them immutable so long as they aren't using
mutable variables or data structures.

OK, so IOW nothing new.

There's no reason immutable pairs couldn't be implemented in terms of
promises, in which case the tying the knot trick could be used (under
the hood) to provide utilities for generating cyclic immutable lists.

IME, it comes out like regular code -- not much different from Racket's
reader graphs which are used to implement cyclic cons structures. (Only
that requires an explicit step that turns the "reader graph" into a
sexpr.)

[Alex Shinn]

Post by Eli Barzilay

The original question was whether cycles were possible in "strict
immutable structures." I would allow promises as part of that
structure, and consider them immutable so long as they aren't using
mutable variables or data structures.

OK, so IOW nothing new.

Indeed, the trick is quite old.

Post by Eli Barzilay
There's no reason immutable pairs couldn't be implemented in terms of

promises, in which case the tying the knot trick could be used (under
the hood) to provide utilities for generating cyclic immutable lists.

IME, it comes out like regular code -- not much different from Racket's
reader graphs which are used to implement cyclic cons structures. (Only
that requires an explicit step that turns the "reader graph" into a
sexpr.)

Yes, but doesn't the conversion from graph to immutable
cons cells require Racket-specific extensions?

I believe for purposes of this SRFI, the question of adding
support for shared structure in ipairs should depend on
whether it can be done portably.

The naive approach would be to define ipairs with setters
and simply not export those setters to the user. This runs
into problems with future extensions for record introspection.

However, using lazy evaluation one could have truly
immutable, portable records and still provide such
utilities as `circular-ilist' and the equivalent of Racket's
`shared'.

[John Cowan]

Post by Alex Shinn
The naive approach would be to define ipairs with setters
and simply not export those setters to the user. This runs
into problems with future extensions for record introspection.

Hopefully such extensions will make provision for opaque record types
on which `record-rtd?` does not work (and `record?` returns #f).

Post by Alex Shinn
However, using lazy evaluation one could have truly
immutable, portable records and still provide such
utilities as `circular-ilist' and the equivalent of Racket's
`shared'.

Sure. But the question is whether such polymorphism is useful, or whether
it's better to have a distinct type of immutable cycles, either one-way
or (per CyclesMedernach) two-way. The only SRFI 1 procedures that apply
equally to circular and normal lists are list-ref, length+ (aka R7RS
length), zip, count, fold(-right), pair-fold(-right), map, for-each,
append-map, map-in-order, pair-for-each, filter-map, find(-tail),
take-while, drop-while, span, break, any, every, list-index. Most of
these accept multiple lists, of which at least one must be finite, so
for example you cannot map a procedure over a circular list and get a
circular list. Having to be prepared to handle promises at any point
will make all these functions slower on normal ilists.

[John Cowan]

Post by Kevin Wortman
Should these procedures take SRFI 114 comparators instead of equality
predicates?

I thought about it, but only the equality predicate is actually useful,
and only for a few operations. To extract the equality predicate from
a comparator, use comparator-equality-predicate (binary) or make-=? (N-ary).

Post by Kevin Wortman
Are cycles actually possible in strict immutable structures? When you
create a head node, there's no way for it to have a circular link to a tail
node that doesn't exist yet.

They aren't, unless they are constructed under the table. See CyclesMedernach
for a preliminary proposal.

Post by Kevin Wortman
Personally I am fond of first, second, etc.; I think they are more readable
than car, cadr, etc.

Okay, easy to add.

Post by Kevin Wortman
The immutable set data structures I have in mind do set-theoretic
operations in O(n) time, though constructing them from an unordered list is
O(n log n).

Fair enough.

Post by Kevin Wortman
I would ditch xipair and factor out parameter rotation to a "flip"
procedure, probably in a separate library or SRFI, as defined in Chicken (
http://wiki.call-cc.org/man/4/Unit%20data-structures#combinators ).

I plan such a library anyway, but I want to make this SRFI as much as
possible a drop-in replacement.

[Michael Montague]

Why do two different implementations of pairs (mutable and immutable) have
two different interfaces?

I suggest that immutable pairs should use the same names (cons, car, cdr,
pair?, etc) as mutable pairs. A programmer can control which implementation
of pairs they use in a particular module using import.

The only downsides that I can see are (1) a programmer who uses both
implementations of pairs will have to do more work and (2) because (scheme
base) contains a bunch of stuff in addition to mutable pairs, using it with
immutable pairs would require something like (import (except (scheme base)
cons car cdr pair? ...)).

Issue (2) could be solved by factoring (scheme base) into pieces: (scheme
base pairs), (scheme base strings), etc.

Post by John Cowan
Note: The SRFI number is not yet official and is therefore subject to change.
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 and efficient.
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
* Removed all linear-update procedures ending in !
* Removed all references to circular lists (there will be a future SRFI for
immutable bidirectional cycles).
* Removed first, second , etc., which are mostly used for poor man's records.
* Removed the O(n2) lists-as-sets procedures (there will be a future SRFI
supporting O(n 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.
SRFI: http://www.ccil.org/~cowan/temp/srfi-116.html
Implementation: http://www.ccil.org/~cowan/temp/ilists.tar.gz
or to this list in the meantime.
--
Schlingt dreifach einen Kreis vom dies!
Schliesst euer Aug vor heiliger Schau,
Denn er genoss vom Honig-Tau,
Und trank die Milch vom Paradies.
_______________________________________________
Scheme-reports mailing list
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports

[John Cowan]

Post by Michael Montague
I suggest that immutable pairs should use the same names (cons, car,
cdr, pair?, etc) as mutable pairs. A programmer can control which
implementation of pairs they use in a particular module using import.

That's exactly what I thought when I started this effort, but after
all, some Schemes don't have modules, so I figured I'd just go with the
minimal name changes. So I wrote a script to refactor all the names in
the code (a few names of local variables got missed, I think), wrote a
bunch of tests, and started debugging. I figured it would be a doddle.

Only not.

What I wasn't thinking of was that the mechanism of procedures with
arbitrary numbers of arguments, of which SRFI-1 and SRFI-116 have many,
involves the use of lists, not ilists. In Racket, ordinary Scheme
lists were immutable and there was no problem. But to make the code
work in Chicken and Chibi, where I do most of my development, I had to
scrutinize all of the converted code for map and for-each and many other
routines in order to decide when I was dealing with immutable lists and
when with mutable argument lists.

Post by Michael Montague
(scheme base pairs), (scheme base strings), etc.

Actually, there is nothing magic about (scheme base) except that it's
loaded by default in the REPL. Chibi allows you to start a REPL with
an arbitrary base package, so it would be no problem to create (scheme
ilist base) and (scheme ilist list) to provide the base library and
SRFI-1 respectively, but with immutable pairs. But if you want to
deal with arbitrary numbers of arguments, you'd still have to have the
mutable-pair operations available with prefixes.

[Sam Tobin-Hochstadt]

Post by John Cowan
What I wasn't thinking of was that the mechanism of procedures with
arbitrary numbers of arguments, of which SRFI-1 and SRFI-116 have many,
involves the use of lists, not ilists. In Racket, ordinary Scheme
lists were immutable and there was no problem. But to make the code
work in Chicken and Chibi, where I do most of my development, I had to
scrutinize all of the converted code for map and for-each and many other
routines in order to decide when I was dealing with immutable lists and
when with mutable argument lists.

It's almost like there's a lesson here ...

Sam

[John Cowan]

Post by Sam Tobin-Hochstadt
It's almost like there's a lesson here ...

Absolutely, for members of the "post-Scheme community". But some of us
remain loyal to the language of 80 divergent implementations, in which
pairs are mutable, lists are built from them, and arbitrarily large
numbers of arguments are expressed using lists. Are those decisions
ideal? No. But they are part of what makes "naš jezik" what it is.

[John Cowan]

There's also a lesson for everyone in the Scheme community, if they
care to take it.

Some do and some don't: that's what makes horse races.

At one time, Scheme featured `LABELS`,

In the pre-standardization period only.

unhygenic macros,

Never standardized.

and `(eq? 'nil #f)`.

Deprecated from the beginning of standardization (R2RS).

Fortunately, those decisions were discarded.

Indeed, the only case of a Scheme standard which was fully backward
compatible was R5RS.

Given the general attitude of this process toward the prior Scheme
standard, I guess backwards compatibility is only important for bad
past decisions.

Of the 39 changes from R5RS to R6RS enumerated in the latter
document, 22 were adopted as a whole or in part, 11 rejected
as a whole or in part, and 6 received some other treatment.
See <http://trac.sacrideo.us/wg/wiki/FiveToSixToSeven> for details.
That hardly constitutes wholesale rejection of R6RS by R7RS.

[Vassil Nikolov | Васил Николов]

Post by John Cowan
...
the language of 80 divergent implementations, in which
pairs are mutable, lists are built from them, and arbitrarily large
numbers of arguments are expressed using lists. Are those decisions
ideal? No.

Moreover, there is no such thing as an
ideal decision in language design. It is
always a trade-off.

Post by John Cowan
But they are part of what makes "naš jezik" what it is.

"Šta je Scheme, to je lepo!" :- )

---Vassil.

[John Cowan]

Post by Vassil Nikolov | Васил Николов
"Šta je Scheme, to je lepo!" :- )

Google Translate thought that was Czech until I told it otherwise. :-)
But then a friend of mine told me about a conversation between a Croat
and a Pole that ended thus:

"Nie rozumiemy się!" [We don't understand each other!]

"Razumjemo se!" [We do!]

[Vassil Nikolov | Васил Николов]

Post by John Cowan

Post by Michael Montague
I suggest that immutable pairs should use the same names (cons, car,
cdr, pair?, etc) as mutable pairs. A programmer can control which
implementation of pairs they use in a particular module using import.

That's exactly what I thought when I started this effort, but after
all, some Schemes don't have modules, so I figured I'd just go with the
minimal name changes. So I wrote a script to refactor all the names in
the code (a few names of local variables got missed, I think), wrote a
bunch of tests, and started debugging. I figured it would be a doddle.
Only not.
What I wasn't thinking of was that the mechanism of procedures with
arbitrary numbers of arguments, of which SRFI-1 and SRFI-116 have many,
involves the use of lists, not ilists. In Racket, ordinary Scheme
lists were immutable and there was no problem. But to make the code
work in Chicken and Chibi, where I do most of my development, I had to
scrutinize all of the converted code for map and for-each and many other
routines in order to decide when I was dealing with immutable lists and
when with mutable argument lists.

I think the general case, or one general
case, is like this. A program (or
library) uses libraries A1, A2, ...,
which process and return structures made
of mutable pairs, as well as libraries
B1, B2, ..., which process and return
structures made of immutable pairs.
Therefore, the program must use both
kinds of procedures, possibly within the
same expression. I think some practical
experience with this kind of programming
is necessary before being able to say
what are the most significant issues in
this area.

---Vassil.

[Michael Montague]

I did not see where the specification said anything about:

(pair? (ipair 'a 'b)) ==> ???
(ipair? (cons 'a 'b)) ==> ???

Was this deliberate or an omission?

Post by John Cowan
Note: The SRFI number is not yet official and is therefore subject to change.
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 and efficient.
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
* Removed all linear-update procedures ending in !
* Removed all references to circular lists (there will be a future SRFI for
immutable bidirectional cycles).
* Removed first, second , etc., which are mostly used for poor man's records.
* Removed the O(n2) lists-as-sets procedures (there will be a future SRFI
supporting O(n 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.
SRFI: http://www.ccil.org/~cowan/temp/srfi-116.html
Implementation: http://www.ccil.org/~cowan/temp/ilists.tar.gz
or to this list in the meantime.
--
Schlingt dreifach einen Kreis vom dies!
Schliesst euer Aug vor heiliger Schau,
Denn er genoss vom Honig-Tau,
Und trank die Milch vom Paradies.
_______________________________________________
Scheme-reports mailing list
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports

[John Cowan]

Post by Michael Montague
(pair? (ipair 'a 'b)) ==> ???
(ipair? (cons 'a 'b)) ==> ???

You're right, it doesn't and that was an oversight. As noted in the new
Rationale, pairs and ipairs have to be disjoint. There are now notes
to that effect under `ipair` and `ipair?`.

Post by Michael Montague
The case insensitive versions of the char and string comparison
procedures have a -ci suffix. Did you consider using a -i or -im suffix?

I didn't think about a suffix, but it seems to me that in this
case a shorter prefix is better than a longer one. These are
some of the most commonly used identifiers in Scheme, and
it pays to keep them short. In addition, Kevin Wortman is
developing an API and implementation of immutable (and truly
persistent) deques, sets, and maps, which also use the i- prefix.
See <http://trac.sacrideo.us/wg/wiki/ImmutableDataStructuresWortman>
for an early draft.

[Michael Montague]

The case insensitive versions of the char and string comparison procedures
have a -ci suffix. Did you consider using a -i or -im suffix?
Or a i- or im- prefix?

cons-i
cons-im
i-cons
im-cons

Post by John Cowan
Note: The SRFI number is not yet official and is therefore subject to change.
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 and efficient.
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
* Removed all linear-update procedures ending in !
* Removed all references to circular lists (there will be a future SRFI for
immutable bidirectional cycles).
* Removed first, second , etc., which are mostly used for poor man's records.
* Removed the O(n2) lists-as-sets procedures (there will be a future SRFI
supporting O(n 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.
SRFI: http://www.ccil.org/~cowan/temp/srfi-116.html
Implementation: http://www.ccil.org/~cowan/temp/ilists.tar.gz
or to this list in the meantime.
--
Schlingt dreifach einen Kreis vom dies!
Schliesst euer Aug vor heiliger Schau,
Denn er genoss vom Honig-Tau,
Und trank die Milch vom Paradies.
_______________________________________________
Scheme-reports mailing list
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports