This is the mail archive of the
kawa@sourceware.cygnus.com
mailing list for the Kawa project.
Re: Result of research into optimizing implementation of association lists
- To: "Nic Ferrier" <nferrier at tapsellferrier dot co dot uk>
- Subject: Re: Result of research into optimizing implementation of association lists
- From: Per Bothner <per at bothner dot com>
- Date: 24 Jun 2000 12:24:19 -0700
- Cc: kawa at sourceware dot cygnus dot com
- References: <s9550a1c.064@tapsellferrier.co.uk>
"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/