[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Procedures (interfaces)




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