This is the mail archive of the kawa@sources.redhat.com mailing list for the Kawa project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Class to use for lists from Java?


Jocelyn Paine <popx@pop3.ifs.org.uk> writes:

> I think that's one of the things that confused me when I was looking at
> the libraries. In an unoptimised implementation of lists, I'd expect all
> lists to be implemented as chains of pairs (assuming that 'pair' is
> understood in the Lisp sense, namely a structure with two fields used for
> car and cdr respectively). So in Scheme, why are pairs a subclass of
> lists? Can't a lisp-linked list always be represented as a Pair?

It boils down to:  How do you represent an empty list?  So you
have (in Java) the following choises:
(1) Represent an empty list using null.
(2) Represent an empty list by some special "magic" Pair value.
(3) Represent an empty list by some special "magic" non-Pair value.

Option (2) could be made to work, but it feels obviously "wrong",
as the empty list is clearly not a pair.

Option (1) is plausible, but there are reasons to not like it.
A minor reason is that I wanted all standard Scheme values to
be presented by Java objects, not by null.  Perhaps the biggest
reason is that I wanted Kawa to be an object-oriented Scheme,
using sub-classing where it made sense.  Specifically, I wanted
to use a "sequence" abstraction, like Common Lisp does, and
having the various sequence types (list, vector, string, etc)
be sub-classes of a common Sequence class.  I also wanted "list"
(in the Lisp sense) to also be a Java class.  If you use null
for empty then (Empty instanceof Pair) is false - i.e. the
empty list is not a list.

We solve the problem by having Pair and the empty list share a
common superclass - LList.  Rather than definecreate a separate
singleton class for the empty list, we create a single instance
of LList.  So there is only one instance of LList that is not
also an instance of Pair.

Making the empty list be a non-null value that is an instance of
LList make it possible that both pairs and the empty list can
implement java.util.List from the collections framework, which
is planned at some point.  (The only thing holding us back as
that would require Java2.)

> It sounds as though if I want to write Java methods that accept Scheme
> lists, I need to use gnu.kawa.util.LList as the method parameter

Yes.

> (and perhaps be prepared to cope with some weird non-chain-of-pairs
> representation),

Huh?  The only LLists are the empty list and instances of Pair.

> but if I'm creating the lists from scratch inside Java, I
> can use the subclass gnu.kawa.util.Pair.

To create them, yes of course you use Pairs.  But if you need to be
able to handle the empty list, use LList.

> > >I'm sure I could find these by looking through 
> > >the source libraries, but I'd like to use an interface 
> > >that's guaranteed to remain the same as new versions 
> > >of Kawa are released.
> > 
> > There are very few parts of Kawa like that at the moment. I know that
> > Per is working on reducing dependancies in Kawa and this could involve
> > things moving package. That's the most that's going to happen to these
> > classes I would have thought.

As Nic said.  I'm not comfortable making guarantees at the Java level.
It is easier to keep the Scheme interface stable, as I can always
change the implementation underneath.  But while the Java interface
to lists is in principle stable, soem things may change.  For example,
I may rename the length() method to size() for compatibility with
the Collections framework (though I may keep a length() method in
there for compatibility for a bit).  And I have been doing some
thinking on a new collections framework that handles trees (think XML)
efficiently.  If that turns out well, I may propose it as a general
GNU package, in which case the package name is likely to change. 

(Aside: Unfortuantely, Sun left out from Java a mechanism for type
aliases.  This is a major problem - just look at how the Swing package
moved back and forth, and the problems people have with using the
collections framework.)
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/~per/

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]