Re: ADT Lib (3)

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

Some quick remarks:

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

Example?

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

If I'm defining a SortedList, then "being sorted" is an invariant.
You can only add to a sorted list by calling Insert.  And Insert will
kept the invariant.  Besides: a sorted list and a tree have a lot in
common.  I want them to share as many properties as possible.
Obviously, a temporarily unsorted tree is impossible.

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

You are defining a relation.  We are talking abourt the same thing.  I
would have it return a SHORTINT, though.

> > TYPE
> >   Rider = RECORD
> [...]
> We should not only define one class but a class hierachie. Note, that
> there are different kinds of iterators. Readers and Writes (as
> stated.

Why make an distinction here?  You have "write-only" files, and
"read-only" files for applications quite often.  But in-memory data
structure are usually read-write.  I don't understand the "hierarchy"
remark.  Examples?

> We also must add a method "Value", returning the current value
> without moving.

Why?

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

All of which are recursive.  The "real" (to quote Peter) iterator
concept can only be provided at large cost, both in memory space and
computation time.  "Iteration" vs "Recursion".

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

I don't like this statement, mostly it is just a bunch of truisms
without any use.  Is the idea of a ADT library that pointless, because
we cannot provide all possible implementations?

And you have not answered my question: Why do we need a single-linked
list in addition to a double-linked one?

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

That is the reason why all operations are type-bound procedures.  The
base record can be extended to provide parameter (in, out, or mixed)
to the applied functions.

-- mva
P.S. I will try to restrict myself to one answer a day in the future ;-)