Re: Result of research into optimizing implementation of association lists

[Per Bothner <per at bothner dot com>]

"Nic Ferrier" <nferrier@tapsellferrier.co.uk> writes:

> Overload isn't quite the right word - reimplement is more like it. 
> It's a bit tricky since Kawa has no "instanceof" equivalent. 

Of course it does - and has for a long time.  It's called "instance?"
- and Kawa can usually inline to a instanceof VM instruction.
(I think I have picked the name "instance?" because some other Scheme
implementation used that name - but I don't remember for sure.)

> There is another possible implementation but it would require that
> Kawa supported overloading of core procedures (eg: cons) and to my
> knowledge Kawa doesn't support that and it looks like it would be
> quite a major change.

Well, Kawa does support overloading using GenericProc (acessible from
SCheme using make-procedure).  However, it is not tuned nor stable.
> 
> The implementation would involve building equivalent hash procedures
> of (cons) and all the other procs that might be called to work on
> association lists. The compiler could then make a descision about
> which method to choose.

But how does the run time system know when a pair is a pair and
when it is an association list?

> Another problem with this is that it would require the procedure:
> 
>   (define (cons car :: <Pair> cdr :: <EmptyList>) :: <Hash>
>    ...)
> 
> and this looks likely to get in the way of a general list
> constructor.

Yep.

> I did actually start to implement option 2 inside Kawa but I got
> bored with the idea of implementing all the methods of java.util.Map.

gnu.mapping.NameMap will eventually implement java.util.Map, when I'm
ready to require te collections framework.

I'm fairly sure that I will never accept anything remotely
like either option 1 or option 2 - but of course it's free software,
so do what you want.

The solution to your problem as I see it:  Design or pick some existing
hashtable api.  For Kawa, implement the api using Object's hashCode
method, optionally using java.util.Hashtable.  For other Scheme
implementations, usie whatever hash interface they provide.
As a fall-back, write a portable, implementation, perhaps using
association lists.

However, trying to overload a hashtable implementation on the association
list api seems like a big mistake, because the association list api
is *defined* as working on lists - and lists are not hashtables.
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/~per/