ADT Lib (3)

[Michael van Acken <mvacken@t-online.de>]

TT> [...] I also want to announce that I'll be away on holiday
TT> from saturday this week to friday next week. So dont be suprised when
TT> I suddenly stop argumenting ;-)

I am sorry to hear that.  This will remove a full third from our
discussion.  Btw, I am still a little bit disappointed with the number
of responses.  I thought that more people than just Tim and Peter were
interested in a ADT library.

TT> 
TT> > What would we gain with this approach?  Obviously, it is very
TT> 
TT> I also asked for this.
PF> 
PF>    I was not arguing that we "gain" anything in particular. I was just
PF> making a point that the original statement by Michael was wrong: You can
PF> have "method based constructors" with extensible parameterlists. He claimed
PF> you can not.

Ok, I lied :-)  Since you see no benefit from your method based
constructor approach, I think we can set this in stone:

--begin quote rules.txt--
An implementation of an ADT `T' provides two procedures:

PROCEDURE Init* (t: T; ...);
Initializes the given instance `t' of the ADT `T' to a valid state.
Prior to calling `Init' all operations on `t' are undefined.  The
procedure is required to call `Init' for T's base class, and then to
fill in all fields that `T' defines for itself.  The procedure may
take an arbitrary number of arguments to parameterize the creation of
the new object.

PROCEDURE New* (...): T;
Creates a new instance of `T', initializes it, and returns it as the
functions result.

[Note: When I write undefined, I really do mean undefined.  Everything
is permitted as result of a undefined operation, e.g., reformatting
the hard drive, dumping core, or booting MS-DOS.]
--end quote rules.txt--

TT> > provided by the ADT implementation itself.  For convenience and
TT> > efficiency.  That is, we don't need a minimal set of procedures, but a
TT> > minimal _convenient_ set.
TT> 
TT> That is my understanding of "confortable", too.
PF>    Okay, okay! Of course I was not arguing for a "theoretically sound
PF> minimal interface" but for a "usable/convinient but not bloated/fat
PF> interface".

I was hoping for a more precise statement.  But in this case we have
to rely on the discretion of the ADT designer.  Here is another
candidate for our "set in stone" section of rules.txt:

--begin quote rules.txt--
The level of detail provided by the procedural interface of an ADT is
up to the discretion of its designer.  The interface should be small
and efficient.  As a guideline, the following rules should be applied:

 - Methods for the elementary operations on the ADT must be provided.
   (ok, I'm being obvious here.)

 - Where applicable, methods must be provided to implement
   functionality that has been defined common to all classes of the
   OOC ADT library.  (Example: Load/Store methods for persistent
   objects.)

 - The interface should provide often used methods for the users
   convenience, even if they can be constructed in a simple way from
   elementary methods.  Of course, a balance has to be found between
   convenience and interface bloat.

 - The interface must restrict itself to operations that are native to
   the ADT.  As an example: the LISP function mapcar is a native
   operation on lists, but somewhat out of place for trees.

--end quote rules.txt--

TT> > list has a number of properties.  Of course, these properties can be
TT> > used to make the use of a list more efficient.  That is the reason
TT> > why, e.g., the fields `prev' and `next' are visible to the user.
TT> 
TT> These fields are special to this special implementation of a list (one
TT> could implement a gap list or a list using nodes of short arrays...).
TT> So you can export them, the user can use them but he must be aware that
TT> he cannot exchange the implementation on the fly a sa result.
PF> 
PF>    Okay, from this point of view I have to agree. However I thought we were
PF> arguing design policies in general. And the *general* list container class
PF> should not export these things. It should only provide an interface that
PF> all other list classes must adhere to.

Obviously I am starting with a concrete implementation of a particular
List.  I am not claiming any general properties, nor am I propagating
a framework of classes.  This needs to be derived from the agreement
we reach on the mailing list.

TT> > Correct.  The operations provided by a ADT should be based on its
TT> > "characteristics" sheet.
TT> 
TT> True. No "Last" for stacks only "First".

The naming conventions for stacks prefer `Top'.  It is the same, of
course. 

TT> > This is certainly worth consideration.  Of course, this can only be
TT> > decided once the general form of the whole library is less hazy.
TT> 
TT> True. So just fix now that abstract interfaces have the name of the
TT> datatype and derived class that implement functionality have some
TT> suffix or prefix.

Agreed.  I propose to have all implementations of a type have the same
prefix, e.g. all implementations of List are called ListSomewhat.

Then we need to agree on the level of verbosity.  
Abstract class: ListA? ListAbs? ListAbtract? Or just List?
  (I'm strongle against "just List", because our user might actually
   try to use it as a concrete data type.)

Which suffix to choose for the various implementations?  Using things
like "Dynamic" and "Static" do not characterize a particular
implementation very well.  Most will be dynamic or static to an
extend.  

TT> > TT> > Currently, ADT List is a direct descendant of the type `Object'.
TT> > TT> > Should we define a intermediate (possibly abstract) type
TT> > TT> > Container/Collection/Bag?  And what properties should this
TT> > TT> > intermediate type have?  [If anyone answers to this with "let's
TT> > TT> > introduce xyz" WITHOUT giving a detailed outline and a module
TT> > TT> > interface, I am seriously annoyed.]
TT> 
TT> > For now, we can ignore any ADTs that need a half order between
TT> > objects.  
TT> 
TT> What do you mean?

[Please note: I only know the German terms for the mathematical
concepts that apply here.  Please correct me if my ad hoc translation
for "Relation" and "Halbordnung" is wrong.]

If you have a sorted tree or list, you need a relation (commonly
denoted by something like "<") describing the order between objects in
the list or tree.

TT> > Also, your statements confuse me.  Is it worthwhile to introduce
TT> > intermediate classes?  Should they be abstract or concrete?  How
TT> > should these classes look like? 
TT> 
TT> Ok. As a result of my own implementation I would state that some base
TT> classes are usefull while others are not. Exspecially good was the
TT> introduction of a Comparable Object, that implements comparisons, I
TT> would sugest to implement this again. 

Ok, let us discuss sorted lists (as an example only, this should
easily extend to trees).  I wanted to delay this topic, but obviously
we cannot separate it that easily.

In my point of view, a sorted list is a list that is sorted with
respect to a particular relation (i.e., some "<" operator) all the
time.  Being "sorted" is an invariant of this particular list.  This
means that operations like InsertPrev, InsertNext, and Replace are not
available, just a plain Insert and Remove.

The < relation of a particular list is fixed over the entire
lifetime of the list, but not over the lifetime of the objects that
are part of the list.  Conceptionally, if a list should be reordered
to a different relation <', this should be done by creating a new
list, destroying the first one in the process.  I am proposing this
strange approach to avoid any inconsistent "in between" states.

Being comparable, and how, is a property of the list, not of the
objects it holds.  Introducing a type "Comparable", derived from
"Object", is a dead end.  Also note that we run into trouble if we
encode more than one property this way.  Suppose we introduce a type
"Persistent", derived from "Object".  Then we cannot have comparable,
persistent objects, unless we derive "Persistent" from "Comparable" or
vice versa.

TT> I would also suggest to implement
TT> the evaluation of a hashvalue (LONGINT) somewhere in the baseclass.
TT> This way you can heasily hash any objects not only string. hashtables
TT> get simpler.

Please, one step at a time.  I am having a hard time holding the
threads together as it is...

TT> > TT> Different Lists (dynamic-, array
TT> > TT> implementation) should derive from List and implement the needed
TT> > TT> methods.
TT> 
TT> > Based on the current List outline, how would you define the common
TT> > base class of all lists?  Or would you suggest to create the base
TT> > class by simply defining ListDesc to the empty record, and replace
TT> > the Element data types with generic navigation methods?  Mh, maybe you
TT> > should provide a module interface!
TT> 
TT> Yes. We should implement a module List, that defines all methods common
TT> to all List implementations. This methods should be abstract (empty, or
TT> using HALT).

Another option is to provide some sort of default functionality.
After implementing some Channel specializations I was tempted to
provide defaults at this level, at least as far as certain
capabilities were concerned.

For some methods, the default action should be HALT(), of course.

TT> MODULE Iterator;
[Thank you, Tim, for the module outline; I can reuse such kind of
 information much better than prose.]
PF>    Well the basic Iterator design is quite straightforward: You provide
PF> something like

It looks like Tim and Peter agree remarkably on this topic.  Being a
spoilsport, I want to break this unity and introduce a variant of my
own.  Actually I do not propose something all new, but rather a change
of name and (maybe) a slight change in semantics.

I prefer the name `Rider' over `Iterator', because it is firmly
established in the Oberon community, and extends also more readily to
other areas.  We already have riders in the form of the Reader and
Writer classes of the IO subsystem.  As another example, Templ's diss
uses riders to provide access to the data structures of a program.
Instead of using an altogether new name with pretty hazy semantics, I
propose to reuse an existing concept.

The following is based on the mails of Peter and Tim, with a little
renaming.  I believe it is a true superset of the iterators proposed
by them.  Based on this we can start discussing the operations and
their exact semantics.

Rider State:
TYPE
  Rider = RECORD
    res-: INTEGER;  (* result of last operation *)
  END;

[I had a field like 
    obj-: Object;   (* more convenient than method?! *)
in Rider, too, but had some second thoughts about this.]

Constructor:
PROCEDURE (c: Container) NewRider*(): Rider;
(* Creates new rider, positioned at the "beginning" of the container. *)

Accessing and Changing:
PROCEDURE (r: Rider) Read*(): Object;
(* Gets value at current position and moves rider forward.  *)
PROCEDURE (r: Rider) Write*(obj: Object);
(* Sets value at current position and moves rider forward.  *)

Positioning:
PROCEDURE (r: Rider) Forward* (n: LONGINT);
(* Moves `r' forward over `n' objects.  Maybe a simple "forward by
   one" is sufficient here?  *)

Error Reporting:
A method sets `res' to done on success, and to another value upon
failure. 



PF>    Note that it should be a matter of the container to decide if it
PF> supports multiple iterators. Whether the policy of what happens on deletes
PF> should be defined by each container or if we should provide a general rule
PF> still remains to be discussed.

Do mean, different kinds of iterators, e.g., doing different tree
traversal strategies?  Or do you mean multiple iterators operating on
a single list at the same time?

TT> Btw., we are currently defining a datatype List, that is made for
TT> implementing it as a double list. Note, that there are slightly
TT> different datatypes List that use a Lisp/single linked like definition.
TT> Their structure is by design far more recursive. In fact our datatype
TT> should not be named List but should be given a more special name. Not
TT> that that special name is for the abstract baseclass (formally called
TT> List). The derived implementations then must get another pre/suffix.

Do we really need two different list implementations that differ in
only such a small detail?  What would we gain from an additional list
that has no `next' pointer?  And, if we decide to provide parts of the
library as "low-cost" variants, should they do single&double linked
lists, too?  This would make four variants of linked lists.

TT> I also propose to write some paper to post to
TT> comp.lang.oberon *as soon as we can show some results*. This may gave use
TT> some additional help.

I agree with the general idea, but I would be very surprised if we
actually get help from this.  I guess the ADT lib will turn out to be
quite portable across the various Oberon systems.  This will appeal to
many people on c.l.o.  But I want some kind of armor against the well
intended, but mostly unusable and frustrating, storm of "why not...?",
"I want...!", "look at XYZ how ... is done best" messages, that a
posting to c.l.o would trigger. 

The armor I want is a sound and solid library design, with companion
documents detailing the design decisions that were made, possibly with
explanations why certain things were _not_ done.

TT> > PROCEDURE (l: List) Apply* (op: StdTypes.Operator);
TT> > PROCEDURE (l: List) Map* (fct: StdTypes.Function): List;
TT> > PROCEDURE (l: List) Select* (pred: StdTypes.Predicate);
TT> 
TT> Am I correct that argument parsing will be implemented by deriving from the
TT> Stdtypes classes?

I am not sure where you see any argument parsing here.

--------

That's it.  No final remark this time ;-)

-- mva