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

Re: Interface view of dictionaries

This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 contain all messages, not just those from before July 7th, 2015.



scgmille@xxxxxxxxxxxxxxxxxx wrote:
> Perhaps you should read treatise linked in [Oleg's] post which shows
> how a cursor is trivially created from an enumeration?

Yes, I should, and I will do so when I have time.

Bradd wrote:
>> But you should be more careful about your design to make sure that it
>> isn't incompatible with them. You seem to have a mental filter that
>> shuts out anything performance-related, even if it has design
>> implications.

> Can you point out how it currently is not?  That would be a concrete 
> criticism worth addressing.

I've been trying to point it out, but you keep waving your hand and
saying that you don't believe us, even when we back it up with
interfaces and algorithmic details.

> > >> (*-fetchfirst dict number) ;; returns number entries
> > > [B] Trivially implemented with collection-fold-left

>> Trivially and VERY SLOWLY .... You can do this for a tree ADT in
>> O(log N + K) time, where N is the dictionary size and K is the number
>> of elements returned.

> I frankly don't see this at all ....

My mistake -- I misunderstood what "fetchfirst" does. However, this
criticism does apply to another operation: fetching the first K elements
that match a given key.

>> But SRFI-44 doesn't include those interfaces, so you're stuck with
>> the O(N) enumeration algorithm. Sure, you could leave this for later,
>> but what's the point in having an inefficient dictionary interface at
>> all? There's no need for it.

> The point is to describe the set of functionality need to use 
> dictionaries at all.

That's not a useful goal, especially if it omits common convenience and
performance interfaces. You'll end up standardizing only the trivial
parts of the interface, not the "interesting" parts. Thus, you get the
same proliferation of names.

> Again this SRFI does not attempt to be the last word on APIs for any
> of the collection types.  Take sets for example, where many operations
> are omitted.  

Yeah, what's up with that? Seriously, what's the point? If every
implementor will need to extend the interface to cover common
operations, then you've lost the advantage of a standard interface.

>> Which is ridiculous, because efficiency is the whole point of having
>> collections, and usability (including naming) is the whole point of
>> having a standard interface. I don't know what your design goals
>> were, but I'd be curious to hear them.

> The design goals are stated pretty clearly at the beginning of the
> SRFI. To provide a structure for agnostic use of collections and a
> framework in which to define them, providing for the necessary set of
> operations on them, and for interaction between them.

We're trying to tell you that your theoretical "necessary set" is too
primitive, that it doesn't reflect the *practical* necessary set of
operations. That leads to what Bear calls "stupid programming" --
without the performance-related interfaces, library implementors will
only be able to rely on the naive, low-performance interfaces. Either
that or extend the interface and lose the benefits of standardization.

And there's still the problem that you haven't even implemented the
limited set of primitives you do supply, nor shown the relationships
with prior art. Plus the usability problems with some of the names you
chose.

> It is not a document to specify all possible operations on all
> possible datastructures.

It should at least specify all important operations on the data types it
does describe.
-- 
Bradd W. Szonye
http://www.szonye.com/bradd