[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
ADT Lib (5)
TT> [...] However name are not the most important thing so lets take
TT> Rider.
Ah, but names are an essential. I have put down this module naming
convention in our code of conduct:
--begin quote Rules.txt--
For module names the following rules apply:
A module specifiying an abstract class `Foo' is called "AcFoo". A
module implementing a concrete implementation of an abstract type
`Foo' adds a suffix to the type name. For example, an implementation
of a class `List' in form of a double-linked list could use the module
name "ListDL". The suffix should be based on a distinctive feature of
the implementation.
--end quote Rules.txt--
While I am at it, here is another set of rules:
--begin quote Rules.txt--
The book "Objektorientierte Programmierung in Oberon-2", by Hanspeter
Moessenboeck, lists a number of typical design mistakes. I am
summarizing the chapter of his book here, based on the German text. I
agree with every point made by Moessenboeck. If someone decides to
violate any of these rules, he should give an _extremely_ good reason
for doing so.
- Too many trivial cases
Do not create classes for even the most trivial concepts.
- Confusing the "is a" relationship with "has a"
Inheritance establishes a "is a" relationship between the sub class
and the super class.
- Exchanging super class and sub class
The sub class is a specialization of the super class. The class
hierarchie has to reflect the "is a" relationship.
- Creating variants with same structure and behaviour
Avoid creating sub classes, that only differ in the value of a
record field.
- Wrong receiver type
The receiver of a type-bound procedure is always the object, that
is modified by the operation.
- A class hierarchie that is either too deep or to shallow
A too deep class hierarchie is often the result of a design, that
extends not just abstract classes, but also concrete classes. Such
a design, which tries to reuse code as much as possible, can lead
to a situation, where a single operation is doing very little on
its own before passing control to the base method in the super
class.
A too shallow hierarchie develops, if derived classes do not reuse
a small part of the super class, or nothing at all.
Summary: Inner nodes of a class hierarchie should be abstract, the
leaves concrete. Many concrete classes can be derived from an
abstract base class, broadening the tree. The degree of branching
is typically small, when deriving a abstract classes from other
abstract classes.
--end quote Rules.txt--
TT> > For every implementation of a container there are uncountable ways to
TT> > enumerate its elements: forward, backward, sideways, random, etc. If
TT> > we distinguish between classes of enumerations, we better chose a
TT> > criterion whose semantics are firmly established in the library.
TT>
TT> I think one has to abstract a littele bit more. The basic iterator
TT> (sequential) only has a next method, how this method is defined in
TT> time and space is completely irrelevant. The next class has
TT> bidirectional movement, an third one random-acces by indexing
TT> movement. Note for example that an iteraotr to goes from start to end
TT> and one that goes from end to start share the same interface, you will
TT> *not* implement a Forward iterator with method "forward" and a
TT> backward iterator with method "backward". You iteraotr should *not*
TT> show how the ADT stores its data. A general iterator implemented for a
TT> tree should not show the specific details.
By now we have identified a number of characteristics to differenciate
between riders:
- access method (read/write)
- positioning (forward, bidirectional, indexed)
- manipulation (allows insertion, removal, etc.)
Since Oberon-2 has no interface class (like Objective-C and Java), no
multiple inheritance (like C++), nor the immensely powerful mechanisms
of CLOS (which is short for Common Lisp Object System, I believe), we
are somewhat restricted in our design choices.
We could do a hierarchy like this:
Rider +---- Reader +---- ReaderForward +---- ReaderForwardModifier
| +---- ReaderBidirect +---- ReaderBidirectModifier
| +---- ReaderIndexed +---- ReaderIndexedModifier
+---- Writer +---- WriterForward +---- WriterForwardModifier
+---- WriterBidirect +---- WriterBidirectModifier
+---- WriterIndexed +---- WriterIndexedModifier
We get 2*3*2 concrete classes, with the ugly property that the
`Modifier' classes have no common direct ancestor, likewise `Forward',
`Bidirect`, nor `Indexed'.
Additionally, this layout violates several of the OOP design rules I
quoted above. Therefore I prefer to integrate the access method and
positioning into the basic rider, and create only one sub class
`Modifier' (to use Eric's term).
So my all new rider proposal from `AcContainer.Mod' looks like this:
--begin quote AcContainer.Mod--
TYPE
Rider = POINTER TO RiderDesc;
RiderDesc = RECORD
positonable-: SHORTINT; (* positioing capability, see `posXXX' below *)
res-: INTEGER; (* result of last operation *)
type-: INTEGER; (* type of object "beneath" rider, see `typeXXX' below *)
END;
CONST (* symbolic names for values of `Rider.positionable': *)
posForward* = 0; (* can only forward *)
posBidirect* = 1; (* can additionally move backward *)
posIndexed* = 2; (* can additionally be positioned using an index *)
CONST (* symbolic names for values of `Rider.type': *)
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;
[...]
PROCEDURE (c: Container) NewRider*(): Rider;
(* Creates new rider, positioned at the "beginning" of the container. *)
END NewRider;
PROCEDURE (r: Rider) ReadBool* (VAR b: BOOLEAN);
END ReadBool;
(* ... variants for all basic types *)
PROCEDURE (r: Rider) ReadObj*(VAR obj: AcObject.Object);
END ReadObj;
(* Gets value at current position and moves rider forward. If the rider
is not positioned on a data element of the requested type, the field
`r. res' is changed to indicate an error. *)
PROCEDURE (r: Rider) WriteBool* (b: BOOLEAN);
END WriteBool;
(* ... variants for all basic types *)
PROCEDURE (r: Rider) WriteObj* (obj: AcObject.Object);
END WriteObj;
(* Sets value at current position and moves rider forward. If the rider
is not positioned on a data element of the requested type, the field
`r. res' is changed to indicate an error. In general, a container
cannot be extended by using a `Write' procedure. If the rider is
positioned at the end of the container, calling `Write' will report
an error. Note that some specializations of `Container' do not
allow to replace element values this way (e.g., to maintain order
invariants). *)
PROCEDURE (r: Rider) Skip* (n: LONGINT);
(* Moves `r' forward over `n' objects. If `r' permits backward positioning
(i.e., if r.positionable >= posBackward), then negative `n' will move the
rider backward. *)
END Skip;
PROCEDURE (r: Rider) SetPos* (pos: LONGINT);
(* Sets the position of `r' to `pos'. Only available if `r' permits indexed
access (i.e., if r.positionable = posIndexed). *)
--end quote AcContainer.Mod--
TT> > I have the same reservations about rider base insertion/removal.
TT> > Therefore Container.Rider (see below) only provides the means to
TT> > replace the value of an existing element with a new value. I don't
TT> > see a way to use a rider to do (e.g.) insertion in the _general_
TT> > case -- in the special case of a double linked list it is not a
TT> > problem, of course.
TT>
TT> Yes. Insertion is a problem because of the very different semantics.
TT> However writers are necessary for a number of generic algorithms like
TT> copying, moving and sorting. You will have problems to define a general
TT> way to move data from a ADT instance to an instance of another ADT type
TT> (for example copying a list to an array for better sorting or storring
TT> data in two ADTs (e.g. tree and hash) to get the best of both worlds).
Is there a general way to move data from one ADT instance to a
instance of a another ADT? As a side note, now `Container' does not
even provide the methods `Add' and `Remove' anymore (see below).
TT> > This is the first argument for an distinction between "reader" and
TT> > "writer" riders I have seen on this mailing list. I agree, that
TT> > anything "sorted" (but also other ADTs) cannot even have a replacing
TT> > rider. If we do not split riders into two classes, we could have the
TT> > `WriteX' procedures return an error code like "operation not
TT> > permitted".
TT>
TT> If a method returns a "not supported" error your class hierachie is
TT> wrong. You then have to inherit from a baseclass without this feature
TT> and implement it in a specialized class.
I believe, this point of view incompatible with the language Oberon-2
(single inheritance, no interface class). If you have a valid
alternative to the 2*3*2 class hierachy from above, please speak out.
TT> > IR> 4. Riders should have a Reset function that moves them back to the
TT> > IR> beginning
TT>
TT> > I have put it into Container.Mod. By now it is halfway on its way out
TT> > again. Reason: The LISP-style list implementation "list1", described
TT> > by Tim. With these kinds of lists, all list elements are lists of
TT> > their own, and a list element can be part of more that one list.
TT> > Under these circumstances, it is impossible to do a proper reset.
TT> > Because we do not gain much with this method, I am in favor of
TT> > removing it again.
TT>
TT> This is no problem, if reseting is not a method of the rider itself but
TT> of the container. A container then has two methods: Create a new
TT> iterator and reuse and reinitialize an old one.
This would be a severe case of bad design. `Reset' is a rider method,
not a method of the container. Therefore it conflicts with this rule:
- Wrong receiver type
The receiver of a type-bound procedure is always the object, that
is modified by the operation.
For this reason I have removed `Rider.Reset' from `AcContainer.Mod'
again.
TT> > MODULE Container;
TT> > (* Characteristics of the abstract(!) class Container:
TT>
TT> I'm yet not sure, if a baseclass for containers is a good thing.
Without a `Container', I have nothing to attach the `Rider' to.
TT> I already gave some arguments against it for my expiriences with my own
TT> library. We should build up a list of possible ADTs (including the more
TT> esoteric ones like directed and undirected graphs) to see if a basecass
TT> for all containers makes sense. There is a rather complete list of ADTs
TT> as part of my library sources on the VO homepage.
TT>
TT> > - objects can be added to and removed from the container; an object
TT> > can be added to a container multiple times, each addition will
TT> > create a new, distinct, container element
TT>
TT> Adding one object multiple times is not permitted on all ADTs. F.e.
TT> hashtable are normaly not designed for multiple versions of the same
TT> entry.
The current proposal "AcContainer.Mod" encompasses basically anything
that can be enumerated. It does no longer have "Add" or "Remove"
methods, and does not conflict with, e.g. set semantics.
TT>
TT> > TYPE
TT> > Rider = RECORD
TT> > res-: INTEGER; (* result of last operation *)
TT> > type-: INTEGER; (* type of object "beneath" rider, see `typeXXX' below *)
TT> > END;
TT> >
TT> > CONST
TT> > typeUndef* = 0;
TT> > typeBool* = 1; typeChar* = 2; typeShortInt* = 3;
TT> > (* ... symbolic names for all basic types, and (with
TT> > meta-programming capabilits) also for type constructors *)
TT> > typeObject* = 99;
TT>
TT> Reading and writing of build in datatypes is a fine feature but how do
TT> you want to implement storing of basic types in your ADTs. Think of own
TT> pseudo implementation of a double linked list! Is this realy a feature
TT> we can support?
They are provided for two reasons:
1) If there are ever "introspection" capabilites added to the OOC
run-time system, we will need them.
2) While the our class hierarchy is `Object'-centric (and therefore
unsuited to handle types like simple integers efficiently), the user
can still decide to implement his own "integer list" as a stand-alone
module, using the same semantics (e.g. rider), but without inheriting
from "AcList". The current "AcContainer" does permit this.
TT> > PROCEDURE Init* (c: Container);
TT> > END Init;
TT>
TT> > PROCEDURE New*(): Container;
TT> > END New;
TT>
TT> here starts the problem. You proposed in an earlier message that each
TT> ADTs should exacly have one constructor. What about constructoras with
TT> parameters. E.g. a array implementation of a stack? Don't define
TT> constructros in the container baseclass.
Actually it was a stupid idea of mine to put `New' into the interface
of the abstract module. Per definition, an instance of an abstract
class is unusable. So, New() is gone by now. Init() stays, of
course.
TT> > (* Riders
TT> > ======================================================================== *)
TT> >
TT> > PROCEDURE (c: Container) NewRider*(): Rider;
TT> > (* Creates new rider, positioned at the "beginning" of the container. *)
TT> > END NewRider;
TT> >
TT>
TT> What about ADTs which do not support riders? I don't thing that the
TT> implementation of a specific rider should be part of the baseclass.
First: "AcContainer" is abstract. It does not provide any
implementations whatsoever. Where would you introduce the data type
rider, if not for `Container'?
Second: If an ADT is not a container, then it is not derived from
"AcContainer". It is as simple as that.
MG> A couple of suggestions for the class libraries:
MG>
MG> 1) A "Set" module which represents the mathematical concept of a set
MG> with an arbitrary number of unique elements. Something like this is useful in
MG> compiler register allocation algorithms and other places. Every
MG> Ada ADT has one of these. Sets contain unique elements of
MG> something. In Oberon-2 we're probably limited to integers although
MG> Ada allows enumerated types.
Go ahead. Peter has some ideas into this direction, too. Although I
am not sure how he differentiates between the "abstract" type, and a
"concrete" implementation. Even his "abstraction" seems awfully
specialized to me, not to mention his implementation. Maybe I am
jumping to conclusions, before he has presented some "hard" evidence.
So: Come up with a module outline, and we will see.
MG> 2) A "Bag" module represents a collection of entities which could be
MG> repeating. As a real-life example, a bag of marbles would be a close
MG> match to how the software implementation would work. Bags are
MG> useful in statiscal applications where one is counting the occurrences
MG> of some event or maybe in an execution profiler.
Looks like a specialization of `Container' to me.
MG> As well, there appears to be some confusion over the levels of abstraction
MG> which should be used in an ADT module. The examples I've seen in Ada have
MG> been fairly high-level concepts which could be mapped to several different
MG> software implementations. For example, a Queue is an abstract concept.
MG> Typically, implementations will define modules such as BoundedQueue
MG> and UnboundedQueue. The bounded queue will typically be statically
MG> based while the unbounded queue will be dynamically resizeable. A List
MG> would also be an abstract concept. You would then have BoundedList
MG> and UnboundedList modules. It is entirely irrelevant whether the list is
MG> doubly-linked or singly-linked or implemented in an array. Of course, the
MG> BoundedList is most likely an array implementation. Operations on Lists
MG> would be to Remove, Insert, Iterate. The iterator would be passed a
MG> procedure parameter which is applied to each element in the List. This
MG> isn't intended to be an exhaustive list but just to give an idea of what is
MG> being done with Ada.
Your are decribing an abstract type `List'. Well, I have encouraged
people on the mailing list to come up with the specs of an abstract
list type (read: a module outline "AcList.Mod"). I can only repeat
myself here.
-- mva