Re: Class to use for lists from Java?

[Jocelyn Paine <popx at pop3 dot ifs dot org dot uk>]

On 21 Jan 2001, Per Bothner wrote:

> 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.
>
The above all makes sense now.
 
> > (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.
> 
I wondered whether LList might be the abstract ancestor of some completely
different representation, for example dynamic lists, if Scheme has such
things, or lists which have for some reason been implemented as vectors. 

> > 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.)
> 
Yes, I agree. In my view, this is part of a fundamental problem with OOP
languages, which is that classes are compiled in isolation.
Class-level operations such as type aliasing, inclusion of one class
within another, and general method renaming then become horribly
difficult, because the compiler does not have access to the program as a
whole. Compare and contrast the module-composition mechanism of an
algebraic-specification language such as OBJ, which handles such
operations with consummate ease and categorical elegance. That's how it
should have been done in OOP. 
 
> 	--Per Bothner
> per@bothner.com   http://www.bothner.com/~per/
>