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

A possible solution?

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.

I've been thinking about this; yesterday I quit brooding about
how much the situation annoys me and started trying to think
constructively.  So...  I've got a suggestion.  I'm going to
propose a change that might meet your goals here without running
afoul of the issues that seem to be making problems.

I do dispatch and OO programming all the time in scheme, and I don't
use any of the popular "OO" frameworks because it's so simple to do
OO programming that there's really no need for them.  SRFI-44 does
not need to depend on any OO framework or library to get dynamic
dispatch based on the collection type.

If it is desired to have a "generic" interface that can work on
collections yet to be defined, then we have to specify how those
collections can assume a form that will make sense to that interface.
And that doesn't necessarily mean function names, it just means
ways to find the functions themselves programmatically.  In scheme,
that's easy; we can store functions in local variables or structures,
just like anything else.

Therefore consider as a possibility, a vector a few dozen elements
long.  Let the first element, at index zero, contain a symbol that
gives the type of the collection.  Let the element at index 1 contain
a pointer to the actual data of the collection, whether it's a hash
table or a btree or an association list or whatever.  Let the element
at index 2 contain whichever procedure can be used to insert! an
element into the collection.

Then you have the possibility of a generic interface for  collections
of the form,

(define coll-insert!
  (lambda (coll addition)
    ((vector-ref coll 2)(vector-ref coll 1) addition)))

(define coll-type
   (lambda (coll)
     (vector-ref coll 0)))

and so on...

You wouldn't really write raw index numbers; this would happen
inside a let-syntax that associated nice symbolic names with
index numbers to simplify maintenance.

And any future collection author, if they provide the same
vector of functions and the same initial pointer to the data
structure, can provide a collection that uses coll-insert!
and coll-type.

This wipes out your name and argument conflicts; you don't need
individual names for all the functions on all the collection
types, you just need a few dozen names, all of the form "coll-*"
or "dict-*", that nobody else is using.  Future collection
and dictionary authors will need to use one name only, a name
of the form "make-*-collection" or "make-*-dictionary," that
returns a collection or dictionary "object" (which is just
a vector of data and functions).

The mechanism is extensible; you may develop only 20-30 "generic"
functions and then let future SRFI authors add more as needs are

For performance reasons, let there always be a constant vector
index at compile time, so the function lookups can always be
O(1) - even inlined if the compiler is smart - and then maybe
bitgrinders like me won't be too disgusted with its efficiency
to use it.  This avoids type-checking overhead for sequential
checks against various collection types entirely, replacing all
of them with a single O(1) vector lookup.

The mechanism allows default implementations for "efficiency"
functions (functions that can be implemented more efficiently
on some structures than your generic few operators allow):
They can be coded using the generic operators and provided
by a make-collection function.  Then the implementor of, say,
make-olist-collection will start with the vector returned from
make-collection and, if she doesn't override whichever functions
are profoundly stupid for olists, then she "inherits" generic
versions of them from the collection SRFI that will work anyway,
however slowly. In fact he could just copy the minimal form he
gets back from make-collection into a longer vector and
define a few new "coll-*" or "dict-*" functions himself if
there wasn't any place for his new stuff in the vector you

It becomes the responsibility of the implementors of future
collections to provide at least the few generic functions that
will make the "generics" work, but they could still override
any stupidities in a very well-defined way without breaking the
structure of the collection interface.

And it'll work.  Immediately.  And it'll be totally clear to
everybody how to write collections that this interface can use.