On Tue, Apr 29, 2003 at 10:27:25AM +0200, xxxxxx@philips.com wrote:
> Scott,
>
> There are a number of remarks
>
> 1. Two frequent operations
>
> I am missing the two frequent methods *-clear!  and *-copy.

Yes of course.

>
> 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?

Perhaps it needs to be made more clear in the document itself, but the
intention is that specific collection SRFIs are allowed to make more
specific, or even moderately conflicting definitions collection specific
functions.  Nevertheless, it may be desirable to add an
[additional-options ...] to the specification of make-%.

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

Actually, there are polymorphic calls as well. *-remove!, for example,
mandates the existence of dict-remove! and alist-remove!.

I hope that specific Scheme systems solve this problem more
cleanly than the current portable implementation does.  The rationale
for distinct functions for a specific datastructure as well as the
categories it lives in is to allow code to be written which is
datastructure agnostic, code to be written which is datastructure
sensitive (using a more specific function would cause an error with the
wrong specific type), and for implementors to both improve the
efficiency of the specific calls, and to be able to dispatch to the
specific calls from the generic ones.

>
> 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.?

If iterators were monomorphic, it would prevent one from writing
collection agnostic code, which I perceive as a real benefit to the
collections APIs of most languages that have them.  A fine example in
this SRFI is the *-add-all! function, which is specified to take any bag
as input to any other bag (including sequences).  This is trivially
implemented using an iterator and the *-add! function, but only if
iterators are polymorphic.

> 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

I have some familiarity with the STL, but I'll give LEDA a look.

	Scott