Re: ADT Lib (3)

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

Hallo!

> 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

Sorry, but I will not cancel my holiday for that ;-)

> of responses.  I thought that more people than just Tim and Peter were
> interested in a ADT library.

True. Come on, people, make some noise. We definitely do need some help
here.

> PROCEDURE Init* (t: T; ...);
> Initializes the given instance `t' of the ADT `T' to a valid state.
> PROCEDURE New* (...): T;
> Creates a new instance of `T', initializes it, and returns it as the
> functions result.

What about a nameing sheme when multiple "constructors" exist?

> 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.

We should discuss another, "orthogonal" datatype then, too, to be sure
we found a solution suitable for all/many datatypes. I would suggest a
tree or a hashtable as next datatype.

> 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.)

We could use "Base" e.g. "ListBase" for that.

> 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.  

ListDoubleLinked, StackList, StackArray... sorry, I also have
difficulties finding good names.

> 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.

<Mp> Do you mean, we should implement a list class and a sorted
list class? Ist the state of been sorted really permanent? Shouldn't
one just add a sort method, that sorts the list ones. Adding entries
will then not guarantee that the list will be sorted afterwards.
Perhaps we could add a InsertSorted method?


> 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

> 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.

Yes, I was aware of the problem. I know have another solution somehow
borrowed from the STL of C++. Beeing comparable is not a feature of an
object per se. Instead we define a special comparison objects that
simply has one method that compares objects (for sorting and comparing
we need in fact two comparssions: less (or Greater) and equal. We can
discuss if we define different objects for this or if we define one
object that has both methods). It interface would be:

TYPE
 Compare*     = POINTER TO CompareDesc;
 CompareDesc* = RECORD
                END;

                
  PROCEDURE (c : compare) Less*(a,b : StdTypes.Object):BOOLEAN;
  PROCEDURE (c : compare) Equal*(a,b : StdTypes.Object):BOOLEAN;

The user then would implement a special comparison object for his
objects  (by doing type checks he can even compare objects of
differnet types. by using WITH he can asure thant only certain objects
are comparable). He then would assign this comparison object to his
datastructure (Tree, List, etc...) which in turn will use it for
further operations or for a one-shot sort. Note also that acomparsion
object must be defined for every datatype once. It is reuseable for
every datatype.

> 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...

Ok. Remove that suggestion, too. Just implement a Hash object similar
to the compare object.

> 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.

Yes. default operations may make sense. We should allow them if they
are apropiate.

> 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

Yes. Wirth also used the Name Rider for hist Array-Iterators used in
his hardware-near subset of Oberon-2 (forgot the name) AFAIK. Howver
while beeing common to the Oberon-community their name leaves out all
other users which are conditioned to "Iterators". Are we introvertive
or extrovertive ;-)?

> 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.]

That would not make sense. An Rider/Iterator for a array-like structure
would not store areference to the value but it would only store an
index. One could of course force storing the value in the iterator to
improve speed. However this will not give us a senseable speed increase
and it make the iterator invalid in more cases (exchaging the value of
a list entry would not make the iterator invalid, if the value is only
stored in the node).

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

Havn't we killed Container? Or is it just added for illustrations?

> 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?  *)

We should not only define one class but a class hierachie. Note, that
there are different kinds of iterators. Readers and Writes (as stated.
Sidenote: Often the executions of the Writer invalidates some/all
Readers for the same datatype instance. We should also discuss, if the
datatype should store a list of all iterators it has allocated. This of
course forces manuall freeing of the iterators by the user). But there
are also other Iterator types: STL of C++ at least differenciates
between serial (go once from start to end) and random-access iterators
(back and forth). A random access iterator for a tree or hashtable is
no senseable or at least not easy to implement. I also must admit that
the methods are not that easy to understand than my counterparts. We
also must add a method "Value", returning the current value without
moving.

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

Ok. We should of course make a list of error cnditions.

> 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?

Not my quote, aber nevertheless :-) Both. A tree e.g. has differnt
methods of traversal. It the will implement differnet Iterators and
differently named constructors for them. However it should also be
possible to use multiple iterators (at least Readers, multiple Writers
are in most cases not that easy to implement) at the same time. This
will be possible, when the iterator itself stores the possition it is at
(Node, Index...).

> 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.

Yes. Of course. There is no "one datatype fits it all" implementation.
Not even one list for all purposes. Even different list implementations
have their differences (used memory (single/double), Interface
(LISP-a-like, "normal" double linked). Ssome implementations have a
special head object (double) others not (LIPS)).

> 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.

Yes. We should at least have implemented a fixed core. This way one
need not to discuss all the implementations. It is just "make it the
same" or "write our own library".

> 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.

If you want to apply a function to each element of a contaner, it is
likely thatthe user wants to hand parameter to this function to make it
configurable. How can I parse parameter to my operator for the Apply
method?

-- 
Gru...
       Tim.