remarks, questions

[sebastian.egner@xxxxxxxxxxx]

Scott,

There are a number of remarks

1. Two frequent operations

I am missing the two frequent methods *-clear!  and *-copy.

2. Passing options to the constructors

A major design challenge is passing options to the constructors (make-%). 

Your design only specifies an optional argument equivalence-function
for datatypes that require a notion of equality on their keys (Dictionaries).
However, for efficient data structures it is very important to know as
much as possible about the keys (e.g. a total order, a hash function, 
a range of possible keys or even their statistical distribution). This
holds in particular for Sets (= trivial applications of dictionaries).

In the current SRFI there is no mechanism to pass these options to the
constructors, the problem is left to subclasses. Is it your intention to add
a mechanism for this?

3. Polymorphic interface

Another major design challenge is a mechanism to choose the 
representation of the collections without modifying the interface.

The SRFI specifies a monomorphic interface, only. In other words,
each operation of each data type has a different name, so for
example alist-remove! and avl-tree-remove! both delete an
element from a dictionary but you have to know whether it is
implemented as an alist or an avl-tree. As the number of possible
data structures grows a problem might evolve here.

Iterators on the other hand are specified polymorphic; in other
words, *-iterator creates an object that can handle the messages
iterator-at-start? etc. independent of the underlying representation.
(Sorry for the OO-speak, but this language is widely known.)
If efficiency was the main design goal, wouldn't it be much more
efficient to specify alist-iterator-at-start? etc.?


Finally, you may want to check out two libraries for data structures
(if you haven't already) that I find myself very interesting. In any
case, they are worth a reference:
   * LEDA: http://www.algorithmic-solutions.com/enledadoku.htm
   * STL: http://www.cs.utexas.edu/users/lavender/courses/stl/stl.pdf

Cheers,

Sebastian.

----
Dr. Sebastian Egner
Senior Scientist
Philips Research Laboratories
Prof. Holstlaan 4 (postbox WY63, kamer WY 6-55)
5656 AA Eindhoven
The Netherlands
tel:       +31 40 27-42069  *** new telephone number
fax:      +31 40 27-42566  *** new fax number
email: sebastian.egner@xxxxxxxxxxx