Re: ADT Lib (4)

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

Hallo!

> The term is widely used.  With Sather the language provides a "real"
> iterator construct (in comparison to the "fake" iterator we are using
> here).  When comparing our "iterator" with the iterator concept of
> Sather, the term `rider' is very appropriate.

I'm speaking of widly known languages like C++ :-) However name are
not the most important thing so lets take Rider.

> This all is true.  Peter mentioned that very same thing in one of his
> first mails.  When I wrote "class of iterator", I meant an iterator
> class with different semantics.  A tree iterator of type "in order" is
> just an implementation of the general iterator class, not a new class
> of iterators with new semantics.  I wrote down the specs for one class
> of iterators in the attached Container module (attached to this mail).

Yes. All that in/pre/post order iterators will have the same interface
because they inherit from the same baseclass. It is up to the
implementor if he decided to define a new class for every order or if
he uses the same class configured by a flag but they wil have the same
interface, the same methods.

> Do we need a additional general iterator concept with different
> semantics?  E.g. one Rider2, with the additional property that it can
> move backwards?

I already proposed a possible hierachie for read only iterators.

> For every implementation of a container there are uncountable ways to
> enumerate its elements: forward, backward, sideways, random, etc.  If
> we distinguish between classes of enumerations, we better chose a
> criterion whose semantics are firmly established in the library.

I think one has to abstract a littele bit more. The basic iterator
(sequential) only has a next method, how this method is defined in time and
space is completely irrelevant. The next class has bidirectional movement, an
third one random-acces by indexing movement. Note for example that an
iteraotr to goes from start to end and one that goes from end to start
share the same interface, you will *not* implement a Forward iterator
with method "forward" and a backward iterator with method "backward".
You iteraotr should *not* show how the ADT stores its data. A general iterator
implemented for a tree should not show the specific details.

> True.  But the cost for a simple iteration using this mechanism may be
> high.  Take e.g. the most simple binary tree with links to two
> descendants, but no link towards the root.  For such a tree the
> iterator/rider has to keep a stack of visited nodes.  In the worst
> case this stack may grow to a length of O(n), where n is the number of
> nodes in the tree.

True. However we should try to implement at least a sequential iterator
for each ADT.

> I have the same reservations about rider base insertion/removal.
> Therefore Container.Rider (see below) only provides the means to
> replace the value of an existing element with a new value.  I don't
> see a way to use a rider to do (e.g.) insertion in the _general_
> case -- in the special case of a double linked list it is not a
> problem, of course.

Yes. Insertion is a problem because of the very different semantics.
However writers are necessary for a number of generic algorithms like
copying, moving and sorting. You will have problems to define a general
way to move data from a ADT instance to an instance of another ADT type
(for example copying a list to an array for better sorting or storring
data in two ADTs (e.g. tree and hash) to get the best of both worlds).
So we should definitely find a solution.

> BH> Even if Write has replacement semantics, how would that affect
[...]

> Yes.  :-)

Perhaps the baseclass of the Write should not define that much position
information as a reader does? F.e. a writer to a sorted list or tree
will not have any usefull position information.

> This is the first argument for an distinction between "reader" and
> "writer" riders I have seen on this mailing list.  I agree, that
> anything "sorted" (but also other ADTs) cannot even have a replacing
> rider.  If we do not split riders into two classes, we could have the
> `WriteX' procedures return an error code like "operation not
> permitted".

If a method returns a "not supported" error your class hierachie is
wrong. You then have to inherit from a baseclass without this feature
and implement it in a specialized class.

> Could you write a module outline for this data type, once you are back
> from your holiday?  With `List.Mod' and `Container.Mod' we have enough
> of a framework to make this worthwhile.

Yes, at the end of the next week. Remind me of that, please.

> specific implementations.  The basic `Rider' does not impose any
> ordering constraints.  It only requires that a specific Container's
> implementation enumerates all items.

True.

> IR> 4. Riders should have a Reset function that moves them back to the
> IR> beginning

> I have put it into Container.Mod.  By now it is halfway on its way out
> again.  Reason: The LISP-style list implementation "list1",  described
> by Tim.  With these kinds of lists, all list elements are lists of
> their own, and a list element can be part of more that one list.
> Under these circumstances, it is impossible to do a proper reset.
> Because we do not gain much with this method, I am in favor of
> removing it again.

This is no problem, if reseting is not a method of the rider itself but
of the container. A container then has two methods: Create a new
iterator and reuse and reinitialize an old one.

> I suggest we wait with a decision until Tim gives us a module for
> LISPish lists.

You can go on, this this aproach will wok with the LISP list, too.

> Please note: this iterator business is one part of the library I
> consider "low-priority" for myself.  This means, someone else has to
> take over active coordination for that part, or it will never grow
> beyond the minimal stuff in Container.Mod.  Suggestion: Create an
> abstract class `List' (an ancestor to the double-linked list I posted
> earlier), and with it more specialized iterators (i.e., with more
> properties than Container.Rider).

I see the strong need for iterators (as mentioned several times now!)
and are willing to do some for stuff for it. Shit, that I must go in
holiday at this time ;-)

> MODULE Container;
> (* Characteristics of the abstract(!) class Container:

I'm yet not sure, if a baseclass for containers is a good thing. I
already gave some arguments against it for my expiriences with my own
library. We should build up a list of possible ADTs (including the more
esoteric ones like directed and undirected graphs) to see if a basecass
for all containers makes sense. There is a rather complete list of ADTs
as part of my library sources on the VO homepage.

>   - objects can be added to and removed from the container; an object 
>     can be added to a container multiple times, each addition will
>     create a new, distinct, container element

Adding one object multiple times is not permitted on all ADTs. F.e.
hashtable are normaly not designed for multiple versions of the same
entry.

> TYPE
>   Rider = RECORD
>     res-: INTEGER;  (* result of last operation *)
>     type-: INTEGER; (* type of object "beneath" rider, see `typeXXX' below *)
>   END;
> 
> CONST
>   typeUndef* = 0;
>   typeBool* = 1; typeChar* = 2; typeShortInt* = 3; 
>   (* ... symbolic names for all basic types, and (with
>      meta-programming capabilits) also for type constructors *)
>   typeObject* = 99;

Reading and writing of build in datatypes is a fine feature but how do
you want to implement storing of basic types in your ADTs. Think of own
pseudo implementation of a double linked list! Is this realy a feature
we can support?

> PROCEDURE Init* (c: Container);
>   END Init;

> PROCEDURE New*(): Container;
>   END New;

here starts the problem. You proposed in an earlier message that each
ADTs should exacly have one constructor. What about constructoras with
parameters. E.g. a array implementation of a stack? Don't define
constructros in the container baseclass.

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

What about ADTs which do not support riders? I don't thing that the
implementation of a specific rider should be part of the baseclass.

> PROCEDURE (r: Rider) Reset*;
> (* Resets the rider to the element at which a newly created riders
>    start.  *)
>   END Reset;

Put this into the container.

I will write some more comments later (I have to go to my 70ties
disco to meed some long haired man and woman ;-)). I wished I work ad
work to offer some C++ iterator examples. I think this would give us
some creative imput.

-- 
Gru...
       Tim.