Re: Procedures (interfaces)

[Taylor Campbell <campbell@xxxxxxxxxxxx>]

On Tuesday, Oct 21, 2003, at 03:20 US/Eastern, Bradd W. Szonye wrote:

> As promised, here is my suggestion for revising the collection
> procedures. I tried to remain faithful to the original, and I tried to
> avoid even minor changes. No, really! Nevertheless, I'm sure that it
> will look like a big change. Therefore, let me preface my revision with
> some rationales. Feel free to question or reject them -- as you've
> already seen, I'm amenable to leaving things the way they are if you
> have a good reason to do so.
>
> Organization - With the new attributes like reversible, it was too
> difficult to organize procedures by collection type. Instead, I list
> them all by procedure type (constructor, accessor, etc.) with a 
> "defined
> for:" clause below each usage example. I think I correctly specified 
> all
> of the interfaces, but please double-check them if you decide to use
> this.
>
> Dictionaries - I generalized the collection-building procedures to work
> well with dictionaries. For example, *-add can now build a dictionary;
> just give it a (cons key value) pair, like you do in the dictionary
> constructor. Likewise, *-remove can remove a mapped value; it returns
> the removed key and value as a pair. There's also a specialized
> *-add-key (for convenience's sake) and *-remove-key (for necessity's
> sake). I removed the *-put function, but added a note to *-set-key that
> some dictionaries may permit key addition via that procedure. In other
> words, the "add-or-set" operation is optional.
>
> Removal and deletion - All remove-type procedures now return the
> modified collection and the removed value. If it's a dictionary, remove
> returns a key-value pair.
>
> Set! compatible with R5RS - The original specification for *-set! was
> incompatible with R5RS vector-set!, which modifies the vector in-place
> and returns an unspecified value. I changed *-set! to match that, and I
> changed *-set (the functional version) to return the modified 
> collection
> and the previous value.

This doesn't work at all, because *-SET! is _linear_update_, not
purely mutable.  I am _adamantly_ against removing linear update
procedures and replacing them with purely mutable ones, because it
just _doesn't_work_ with some kinds of collections, e.g. lists, where
the empty list can't be mutated.  (This applies to all of the other
*-foo! procedures as well.)

> *=? and <=?: I added question marks for consistency with functions like
> string=?. I also removed the elt= argument and changed the definition 
> so
> that it was no longer necessary. I was reluctant to make this change,
> but I felt that the original version just wasn't viable.

I don't like this at all.  Removing ELT= is removing a _lot_ of
functionality.  The reason the ? wasn't there was _because_ the
procedures were not comparable to STRING=?, CHAR=?, et cetera.

I don't understand the rationale for having ordering functions on
_collections_.  Can you explain this in more detail?  (or in any
detail at all: I can't find any)

>                                                          The main
> problem, once again, is that a single equivalence predicate just 
> doesn't
> work for dictionaries.

It _does_ make sense for dictionaries: if all the keys are equal, _by_
the_dictionary's_key_equivalence_function_, then test to see if all
the

>                        I considered passing (cons key=? val=?) to the
> procedure, but that wouldn't work for non-dictionaries.

Er, I don't get this.  You didn't mind changing the add and remove
operations to accept pairs for dictionaries, but you do for the
comparison operations?

>                                                         In the end, I
> went with the *=? interface, partly because it makes for a trivial
> implementation of string=?.

(define (string=? . strings)
  (apply string= char=? strings))

That looks pretty trivial to me!

> I think that's all of the major changes. Here's the revision:
>
>
> PROCEDURES
>
> Many procedures accept an optional procedure (thunk) to handle failure.
> If a procedure cannot perform the requested operation (because the
> collection has a fixed size, is immutable, does not permit duplicate
> values, does not contain a requested value, would become unordered,
> etc.), it returns the value of invoking the thunk with no arguments. 
> The
> default thunk signals an error.
>
> CONSTRUCTORS
> [...]
> procedure: % {key<? | key=?} {val<? | val=?} value ... => %
> defined for: all collections
>
> Constructs a new % collection with the values as its contents. Some
> collections may require ordering or equivalence functions during
> construction. Dictionaries may require comparison functions for both
> keys and values. (Ordered collections should derive their equivalence
> functions from the ordering function whenever possible.)

The ordering functions here sort of make sense, I guess...but I don't
like how they work with these two constructors.  It's ambiguous what
argument corresponds to what; for example, is (list = 1 2 3) a list
with = for a comparison function and (1 2 3) for contents, or a list
(#{Procedure} 1 2 3)?  (where '#{Procedure}' indicates an abstract
procedure value)

> procedure: *-copy * => *
> defined for: all collections
>
> Returns a new collection of the same type as the argument with the same
> contents but distinct storage. The copy is shallow; that is, it copies
> values in a way that preserves object identity.

I should like a *-COPY for sequences that also accepts optional start
and end arguments.

> TYPE PREDICATES
>
> procedure: collection? value => value
> procedure: %? value => value
> defined for: all collections
>
> Returns a true value iff the provided value supports the interface for
> the type (%) named in the predicate.

Why %? and not *??

> CARDINALITY OPERATORS
>
> procedure: *-empty? collection => boolean

Don't forget the 'defined for: all collections' bit.

> [...]
> procedure: *-size collection => exact integer
> defined for: all collections
>
> If the collection has a concept of size, this function returns the
> number of values or mappings in the collection. If it does not, #f must
> be returned. If possible, this should return the number of times
> collection-fold will call the fold-function before halting.

Have we decided on the issues of infiniteness and circularity yet?

> [...]
>
> EQUIVALENCE AND TOTAL ORDERING RELATIONS
>
> procedure: *=? *... => boolean
> procedure: *<? *... => boolean

(see far above)

> procedure: *-equivalence-function * => procedure
> defined for: bags, sets, and dictionaries

Where's the rationale for defining this _and_
*-KEY-EQUIVALENCE-FUNCTION on dictionaries?

> Returns the value equivalence function for the collection.
>
> procedure: *-key-equivalence-function * => procedure
> defined for: dictionaries
>
> Returns the key equivalence function for the dictionary.
>
> procedure: *-ordering-function * => procedure
> defined for: ordered bags, sets, and dictionaries

Again, I don't see why this is defined on dictionaries when there is
*-KEY-ORDERING-FUNCTION.

> Returns the value ordering function for the collection.
>
> procedure: *-key-ordering-function * => procedure
> defined for: ordered dictionaries
>
> Returns the key ordering function for the dictionary.
>
> ENUMERATIONS
> [...]
>
> ACCESSORS
> [...]
>
> VALUE MUTATORS

See near the top of this email about this.

> procedure: *-update * position f [thunk] => *
> procedure: *-update! * position f [thunk] => unspecified
> defined for: sequences and ordered collections
>
> procedure: *-update-key * key f [thunk] => *
> procedure: *-update-key! * key f [thunk] => unspecified
> defined for: sequences and ordered collections

I don't understand why you're differentiating between these two, and
why they aren't defined for dictionaries.

> COLLECTION MUTATORS
>
> When adding or inserting a value into a dictionary, the new value must
> be a key-value pair, unless the procedure is specifically defined for
> dictionaries. Likewise, when removing or deleting a dictionary value,
> the returned value is a key-value pair. A key-value pair is a Scheme
> pair whose car is the key and whose cdr is the mapped value:
> (cons key value).
>
> procedure: *-clear[!] * [thunk] => *
> defined for: all collections
>
> Returns an empty collection of the same type as the argument.

[the next bit is permutated and abbreviated bit]

> procedure: *-add-key[!] * new-key mapped-value [thunk] => *
> defined for: dictionaries
>
> Returns a collection of the same type with the new key mapped to the
> given value.

Why have *-ADD with key/value pairs _and_ this?

> procedure: *-add-each[!] * source-collection [thunk] => *
> procedure: *-remove-every[!] * value => * list
> procedure: *-remove-each-from[!] * source-collection [thunk] => % list
> procedure: *-remove-every-from[!] * source-collection [thunk] => % list
> procedure: *-remove-key[!] * key [thunk] => * pair

Why differentiate between removing and removing keys?

> procedure: *-remove-every-key[!] * key [thunk] => * list
> procedure: *-remove-each-key-from[!] * source [thunk] => * list
> procedure: *-remove-every-key-from[!] * source [thunk] => * list

Er, why all of the name changes?

> [...]
> procedure: *-insert-right * new-value [thunk] => *
> defined for: reversible sequences

Don't you mean 'reversible _flexible_ sequences?'

> [...]
> procedure: *-delete-right * [thunk] => *
> defined for: reversible sequences and reversible ordered collections

[flexible]

> As *-delete, except that it deletes the value at the end of the
> sequence.
>
> SET OPERATIONS
> [...]
> --
> Bradd W. Szonye
> http://www.szonye.com/bradd