Re: ADT Lib (3)

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

I don't have the time for a summary today.  I also want to collect
additional opinions on the iterator/rider business before I continue.

TT> > > What about a nameing sheme when multiple "constructors" exist?
TT> 
TT> > Example?
TT> 
TT> Good question! Lets take a skip list,Hash or a BTree: You will have one
TT> default constructor that uses internal defaults (defaults that a normaly
TT> *good* and proven to work, e.g. the size of a hashtable using a
TT> convinient prime number of medium size) and a constructor that enables
TT> you to configure that parameter.

If the data type needs parameters, then they should be explicit in the
constructor.  If there are suggestions or restrictions for some of the
parameters, then they should be described in the documentation,
together with examples.  I see little need for a safety net in form of
a parameterless constructor.  Also, I do not want to encourage this
kind of interface bloat.

TT> > If I'm defining a SortedList, then "being sorted" is an invariant.
TT> > You can only add to a sorted list by calling Insert.  And Insert will
TT> > kept the invariant.  Besides: a sorted list and a tree have a lot in
TT> > common.  I want them to share as many properties as possible.
TT> > Obviously, a temporarily unsorted tree is impossible.
TT> 
TT> Ok, than you are defining another abstract datatype besides our
TT> proposed List. That is ok. However I would also implement a sort method
TT> as proposed in our List.

Why don't we wait until we have a abstraction for a sorted list, and
see at which cost we can convert an instance of `ListUnsorted' into an
instance of `ListSorted'?  If this turns out to cost too much, we can
always go back to your suggestion.

TT> > You are defining a relation.  We are talking abourt the same thing.  I
TT> > would have it return a SHORTINT, though.
TT> 
TT> Yes. The trick is, that our relation is not part of our value but can
TT> be defined else wehere. This way be can drop some intermediate Type
TT> "Comparable" inheriting from Object.

Defining an intermediate type "Comparable" was never an option.

TT> > Why make an distinction here?  You have "write-only" files, and
TT> > "read-only" files for applications quite often.  But in-memory data
TT> > structure are usually read-write.  I don't understand the "hierarchy"
TT> > remark.  Examples?
TT> 
TT> Yes. A sorting algorithm (we are speeking of a algorithm implemented in
TT> form of a datastructure/operator and not as part of a datatype) can
TT> only work on random access iterators. A array datatype for example does
TT> support random access (in O(1)) and thus can be sorted. A hashtable
TT> naturally does not support random access (in fact a serial access is
TT> also on the edge between usefull and "not really part of the datatype")
TT> and thus cannot be sorted. The differentiation is part of the Standard
TT> template library, which is now part of the standard C++ library. I know
TT> that the design of the STL is debatable. However the diverentiation
TT> between various iterators does not show its usefullness when only
TT> working with ADTs (there you may only need Readers and Writers) but
TT> when implementing algorithms working on generic dadatypes trough
TT> iterators and operators. You can check if a algorithm can be applied to
TT> a datastructure by simply see if offered and used iterators match.

Call me stupid, but I don't see how you classify iterators, at least
beyond the reader/writer distinction.  A container is probably the
lowest level on which a iterator (or rider) can be defined.  And a
definition would look like this:

 - a rider can be connected to the container
 - data associated with the current rider position can be retrieved
 - the rider can be moved forward

In particular, no assumptions are made over the particular order in
which data elements are visited.  The only guarantee is this: as long
as the container is not modified between rider init and the rider
reaching the end, all elements are enumerated.  A rider is no index,
and it is not a bookmark for the container.  In fact, any changes to
the container leave the rider in an undefined state, because the
guarantee does no longer exist, that all elements will eventually be
visited.

TT> > > We also must add a method "Value", returning the current value
TT> > > without moving.
TT> 
TT> > Why?
TT> 
TT> It is simply convinient and common practice. This way you need not to
TT> store the result of a read. I think you are driving similarities
TT> between iterators and file access too far.

1. Having separate GetValue/Next methods gives more problems with
   multi-threading.  With multiple threads there is no guarantee, that
   two invocations of GetValue will deliver the same value, even if
   no Next was invoked in between.

2. I am following a design pattern established by the various papers
   on the subject of meta programming (e.g. by Steindl or Templ).
   They use riders to access data in variables, array, records, etc.
   Their rider has a field that identifies that type of the value
   "beneath" the current rider position, and they have procedures
   ReadInt, ReadReal, ReadBool, etc. to access the value "beneath" the
   rider and, at the same time, move the rider forward. 
   Assuming that we may disover the need for a such a more flexible
   rider later on, I hesitate to provide a method GetValue/Value/Curr
   or whatever, because this would be an invitation to interface
   bloat.

TT> > All of which are recursive.  The "real" (to quote Peter) iterator
TT> > concept can only be provided at large cost, both in memory space and
TT> > computation time.  "Iteration" vs "Recursion".
TT> 
TT> Sure? I'm not sure, but I think that itertaors can be applied to trees
TT> without problem if you reduce the functionality of the iterator to be a
TT> serial one. I must think about that, I admit. Tree are long ago :-)
TT> A serial iterator lets you just go once from the start to the end, you
TT> cannot skip nor you can go back.

Yes.  Check your trees again.  And I want to remind you, that both of
you stated, that a module interface should not contain any things
unnatural to the type.  The sequential iterator/rider we are
discussing here is unnatural to, say, a binary tree, and to include it
into the tree's module interface is very questionable.

TT> > And you have not answered my question: Why do we need a single-linked
TT> > list in addition to a double-linked one?
TT> 
TT> A single list needs less ressources, which is always good if one can
TT> work with the reduced interface. Also a single list - in the special
TT> form of the LISP-like recursive list with no spcial head element - has
TT> a different interface than a "normal" double list. It is in fact
TT> a (slightly) different ADT.
TT> 
TT> Gting, Datenstrukturen und Algorithmen implements defined two ADTs
TT> 
TT> list1:
TT> algebra list1
TT> sorts   list, elem
TT> opts    empty  : -> list
TT>         first  : list -> elem
TT>         rest   : list -> list
TT>         append : list x elem ->list
TT>         concat : list x list -> list
TT>         isEmpty: list -> bool
TT> ...
TT> 
TT> list2:
TT> algebra list2
TT> sorts   list, elem, pos
TT> opts    empty   : -> list
TT>         front,
TT>         last    : list -> pos
TT>         next,
TT>         previous: list x pos -> pos (or NULL)
TT>         bol,
TT>         eol     : list x pos -> bool
TT>         insert  : list x pos x elem -> list
TT>         delete  : list x pos -> list
TT>         concat  : list x list -> list
TT>         isEmpty : list -> bool
TT>         find    : list x (elem -> bool) -> pos (or NULL)
TT>         retrieve: list x pos -> elem
TT> ...

Thanks for this information.  Seen this way, your proposed single
linked list is an altogether different data type, with a different set
of operations (e.g., the list1 has no concept of a position).  I
agree, that we cannot call both of them "List".