Re: ADT List

[Tim Teulings <tim@edge.ping.de>]

Hallo!

> this vacancy, this means I am immediately accepted for this job ;-)

Congratulations! Where to send the flowers :-)?

> Notes:
> ======

> Naming of entities in the module is open for discussion.

As metnioned below it is likely to one will several modules that do
implement same datatypes different. All modules should have the type of
the ADT in its name (e.g. 'List'). The 'special feature' of the
specific implementation should be mentioned. These suffixes or prefixes
should be standarizised as much as possible. E.g. 'Dyn' for a dynamic
implementation, 'A' or 'Static' for an array implementation. So you
will have an abstract interface module List.Mod, the classical dynamic
implementation 'DynList' and the more esoteric 'ArrayList' or better
'StaticList'. Names or open to discussion, the given examples should
only give a hint. Perhaps one should uses Suffixes? 'ListArray.Mod'?
This would give you all implementations beneeth when doing a 'ls'.

> Because other ADTs may need further procedure arguments, `Init' and
> `New' are implemented as normal procedures.  If they would be a
> type-bound procedures, we would be forced to have parameterless `Init'
> and `New' for all out ADTs.

Correct. I've done that the same in my implementation. However one can
think of a parameterless Init method that will initialize the datatype
to some kind of default state? Hmm...

> Should we allow to store the NIL object in a list?

No. That will complicate handling e.g. when sorting iterating etc..
The user always has the possibility to add non-initialized or specially
flaged objects instead of NIL.

> How many specializations should be provide in the module interface?
> E.g., `Append' and `Prepend' are simple specializations of
> `InsertAfter' and `InsertBefore'.  We have `Remove'.  Do we need
> specialized procedures to remove the first/last element?

Peter is right when he states, that interfaces should be as small as
possible. On the other hand specialized methods give you much more room
for internal optimisation. It gives you also a feel of comfort. Also
the datatype can always maped spezialized methods to non-specialized.
Will the compiler optimize such things like the following?

PROCEDURE (bla : Bla) Append(blub : Blub);

BEGIN
  bla.InsertAfter(bla.last,blub);
END;

> Currently, ADT List is a direct descendant of the type `Object'.
> Should we define a intermediate (possibly abstract) type
> Container/Collection/Bag?  And what properties should this
> intermediate type have?  [If anyone answers to this with "let's
> introduce xyz" WITHOUT giving a detailed outline and a module
> interface, I am seriously annoyed.]

I implemented this aproach in the published sources analog to some
implemention as part of the AmigaOberon compiler. Implementing some
type Collection gives you the possibility to switch within your sources
between differnet container types (List, Tree, Hashtable). However
there are problems: The container defines onyl simple acces methods
like Add and Remove. Exchangablility is only given, if you do reduce
yourself to calling non-specialized methods. Most baseclass methods
like "Add" need parameter. The baseclass will define them of type
Object. Derived classes (e.g. Trees) need a specialized object with
f.e. does implement comparison methods. This results in heavy casting
when implementing such methods in derived classes. You can study this
in my published sources.

> Persistence.  Should we integrate generic load/store mechanisms into

Persisstance should be supported at least in a general way. Else you
will have difficulties to nicely implement persistance since you cannot
link yourself into the class hierachie (you will need multiple inheritance
of interfaces for this). AFAIK this is known as the fragile base class
problem!?

> Another thing: I wondered why we should not provide two

Definitely. There should be e.g an abstract interface for
implementations of the datatype List. This interface should implement
basic methods common for all lists. Different Lists (dynamic-, array
implementation) should derive from List and implement the needed
methods. Note, that due to this you must hide all helper classes from
the user since they cannot defined in the baseclass. What I mean is,
for a list "Node" must not be visible to the user (it can be visible,
but the user must be able to live without it). "Node" is diffeerent for
different implementations (an array implementation may even not need
one) so the user, when using "Node" would have to rewrite code when
switching between different implementations. This results into the need
for Iterators. Note that iterators also have other advantages since
they allow us to define generic operations like deep-copying and
sorting on every datatype.

> TYPE
>   Object* = POINTER TO ObjectDesc;
>   ObjectDesc* = RECORD
>   END;

Type object is a difficult thing. It must be small, since they may be
many instances around but on the other hand any features it misses will
need double the code somewhere else to implement (persistance...). As a
result it should define a number of methods but at least as possible
members.

VisualObero (which defines Object, too) implements the following
things:

Methods:
  Init, Load, Store, Free (abstract datatypes should always call free
when possible, thus we can f.e. add file handles and that like to an
container). VO also implements generic message passing in a class
directly derived from Object.

> PROCEDURE (l: List) IsEmpty* (): BOOLEAN;
>   END IsEmpty;

We should specify if methods should have suffixes like "is", "has" and
that like where it makes sense or if they should be generally left out.

> PROCEDURE (l: List) Length* (): LONGINT;
>   END Length;

What about Size? Is Length possibly to specific? What about methods
"Clear" and Count" as name alternatives.

-- 
Gru...
       Tim.