John, I appreciate very much your initiative to share your thoughts with a greater public and to provide the informative background.

As to your proposed amendments:

1) An upvote from me; this makes SRFI 153 more consistent with SRFI 1, SRFI 113, and SRFI 146.

2) As implementers are only "encouraged" to provide an implementation solely based on hash tables, portable code will need some means to detect statically whether the implementation provides hash sets and bags. This could be done by providing an R7RS feature identifier (which, however, cannot be portably implemented, which is bad), or by providing the same interface under a different namespace (e.g. (srfi 113 hash) following the example of SRFI 146), whose existence can be statically tested via cond-expand.

In case the voters for the Orange Docket for the R7RS-large decide that hash sets and bags should be mandatory (and not just "encouraged"), a single namespace like (scheme sets) or (scheme hashsets) would be enough. Support for ordered sets could be dropped in that namespace if SRFI 153 is being voted into R7RS-large.

3) I will take care of the SRFI 113 implementation in SRFI 146, which I added precisely because there was no SRFI 113 implementation for ordering predicates. So in fact, that implementation belongs to SRFI 153. I think, we can leave it in the repo for the moment until it has found a better place, but I will remove references to this implementation in the spec.

That said: as soon as we have an implementation for (srfi 146 hash), we can use that and my implementation of (srfi 113) to have an alternative implementation of (srfi 113) with hash functions.

4) All that, and I am going to add "mapping-pop(!)" to make SRFI 146 complete as discussed on its mailing list.

5) Thank you very much for your effort!



John Cowan <> schrieb am Mi., 12. Juli 2017 um 01:01 Uhr:
(I apologize for the massive cross-posting, but I'm going to be talking about a fair number of SRFIs here.  I also apologize for the length of the background section below; if you want to skip to my proposals, search for "Proposed Amendments".)


A set may be defined as a collection of objects no two of which are equal, according to some equality predicate.  A mapping is a set of key-value pairs, and a bag can be understood as a mapping from the objects in the bag to the number of times in which they appear.

The roots of sets and mappings in Scheme are found in SRFI 1, which provides procedures for treating lists as sets and for treating lists of pairs as alists. (Alists themselves go back to Lisp 1.5, and the `assq`, `assv`, and `assoc` functions to R2RS.)   SRFI 1 introduces the idea of "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. [W]e 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.

For example, SRFI-1 provides a set procedure `lset-union` that is guaranteed not to mutate any of its arguments, and a corresponding `lset-union!` that may or may not do so.  Per contra, SRFI 125 provides mappings (known as hash tables) whose update operations *are* guaranteed to mutate them.  It is also possible to have objects which are completely immutable, like the ilists of SRFI 116.

A third dimension orthogonal to set/bag/mapping and immutable/mutable/linear-update is the question of what procedures operating on set members or mapping keys are required by the implementation.  For the definition of a set, or for the inefficient implementations provided by SRFI 1, an equality predicate suffices.  More efficient implementations require either an ordering predicate or a hash function as well (a SRFI 128 comparator packages these three procedures).  So we could have as many as 27 implementations of the three container types, such as immutable hash sets or linear-update ordered bags or mutable equality mappings.

What We Have

What we in fact have at present is this:

Lists as sets (SRFI 1):  linear-update equality sets
Alists (SRFI 1): linear-update equality mappings
Hash tables (SRFI 69, SRFI 125, SRFI 126): mutable hash mappings
General sets (SRFI 113): linear-update ordered-or-hash sets
General bags (SRFI 113): linear-update ordered-or-hash bags
Mappings (draft SRFI 146): linear-update ordered mappings
Hashmaps (draft SRFI 146): linear-update hash mappings
Immutable sets (draft SRFI 153): immutable ordered sets
Immutable bags (draft SRFI 153): immutable ordered bags

Proposed Amendments:

What I'd like to do is to make everything linear-update with the exception of SRFI 125 (and friends) hash tables.  This means that:

1) I will expand SRFI 153 to add linear-update functions.

Furthermore, I'd like to make SRFI 113 and SRFI 153 support hash and ordered sets/bags respectively.  This means that:

2) I'm proposing a third post-finalization note for SRFI 113, thus:

<p><b>Post-finalization note 3</b>: Because SRFI 153
supports sets and bags created using a comparator with
an ordering predicate, implementers of this SRFI are
encouraged to make sure to support comparators that
provide a hash function but not an ordering predicate.
The sample implementation already does so.</p>

The wording may need further improvement.  This change will have to be revoted by WG2 to become part of the Orange Edition.

This also means that:

3) The additional implementation of SRFI 113 provided with SRFI 146 is no longer compliant (it does not support hash-only comparators) and should be remove.  It can be recycled for the implementation of SRFI 153.

4) Finally, as discussed on the SRFI 146 mailing list, the following changes Marc has already agreed to must be consummated:  (a) the procedures in (srfi 146 hash) are now to be prefixed with hashmap- instead of -mapping, making it easy to use both types of container together; (b) (srfi 146 hash) is no longer optional (I am writing an implementation of it based on SRFI 125).

The results will be as follows:

Lists as sets (SRFI 1):  linear-update equality sets
Alists (SRFI 1): linear-update equality mappings
Hash tables (SRFI 69, SRFI 125, SRFI 126): mutable hash mappings

General sets (SRFI 113): linear-update hash sets
General bags (SRFI 113): linear-update hash bags
Mappings (draft SRFI 146): linear-update ordered mappings
Hashmaps (draft SRFI 146): linear-update hash mappings
Ordered sets (draft SRFI 153): linear-update ordered sets
Ordered bags (draft SRFI 153): linear-update ordered bags

5) I will write a future SRFI supplementing SRFI 1 to contain more alist and list-as-set procedures, as well as alist-as-bag procedures, to put these equality-based containers on a par programmatically with the ordering-based and hash-based varieties.

The result will be a full assortment of equality-, ordering-, and hash-based lists, sets, and bags, all of them linear-update.

John Cowan
Sir, I quite agree with you, but what are we two against so many?
    --George Bernard Shaw,
         to a man booing at the opening of _Arms and the Man_

You received this message because you are subscribed to the Google Groups "scheme-reports-wg2" group.
To unsubscribe from this group and stop receiving emails from it, send an email to
For more options, visit