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

Re: remarks, questions



On Tue, Apr 29, 2003 at 10:27:25AM +0200, sebastian.egner@xxxxxxxxxxx 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

Attachment: pgpBuZN9gx6oB.pgp
Description: PGP signature