Re: Containers: The REALLY difficult stuff...

[Brian Hawley <brian.hawley@bigfoot.com>]

Peter Froehlich <pfroehli@ics.uci.edu> asked:
>   How can we separate abstract and concrete structure in a general way?
>
>Let me give one example of what I mean: Consider a "Set" abstraction. It
>can be defined (informally) as having elementary operations "Insert",
>"Remove", "In" and "Empty", as well as "higher-order" operations "Union",
>"Difference", and so on.
>
>Now these can of course be implemented in various ways, eg. by using a
>"java.util.Vector" like class, by a linked list, by various trees, etc. The
>problem is how we combine "abstract" behaviour with a "concrete"
>implementation. I would like to be able to do the following:
>
>   VAR s: Set; l: List;
>   ...
>   BEGIN
>     NEW (s); NEW (l);
>     s.UseImplementation (l);
>     ...

Before I get into your general question, let me point out that Oberon-2
doesn't have automatic constructors the way C++ does, so the standard way
to do this is to use a construction procedure. For example:

  VAR s: Set;
  ...
  BEGIN
    s := Sets.NewSetAs(Lists.NewList());

>So how do we do that? I have that strange feeling that this is next to
>unsolvable with the Oberon-2 context in which we are operating...

Not at all. The easy way is to have your abstract container simply use
an instance of your concrete container, but have a generic interface to
concrete containers defined as an abstract base class of all of them.
But since the short answer is obtuse, I'll give a longer answer.

You create an abstract base type called List, which doesn't specify the
implementation of a list, just its interface in the form of type-bound
procedures that (claim to) implement the necessary operations. With the
operations that only string together other operations you may actually
be able to implement them in the base type. Other operations are just
provided as empty procedures (if they are optional) or traps (if not).

You then create (several?) extensions of the base type with real code
in the overriden type-bound procedures and new fields that implement
the actual behavior of the List, called LinkedList, VectorList, etc.
These can be implemented in the same module as List, or not, depending
on how concerned you are with code bloat and how smart your dead code
eliminator is (or your linker). You can provide additional interfaces
to the concrete implementations for faster use of the specific method
of implementation if you wish, for those who don't need generic Lists.

You then create a type called Set that uses a List (the generic one)
to store its stuff. Don't have it create the List though; instead pass
the List (or a procedure to create it) to the construction procedure.

If you really want to, you could create (hidden) extensions of the Set
type that are optimized for the use of specific List types, perhaps by
the use of additional interfaces in the List extensions that aren't
included in the base List type. You would then type-test (the result of)
the parameter of the Set constructor and then construct the appropriate
extended type. For example:

MODULE Sets;
IMPORT Lists, LinkedLists, VectorLists;
...
TYPE
  (* Visible abstract base class *)
  Set* = POINTER TO SetDesc
  SetDesc* = RECORD END;
  (* Invisible generic implementation *)
  SetAsList = POINTER TO SetAsListDesc;
  SetAsListDesc = RECORD (SetDesc) END;
  (* Invisible implementations, optimized for various kinds of list *)
  SetAsLinked = POINTER TO SetAsLinkedDesc;
  SetAsLinkedDesc = RECORD (SetDesc) END;
  SetAsVector = POINTER TO SetAsVectorDesc;
  SetAsVectorDesc = RECORD (SetDesc) END;
...
PROCEDURE NewSetAsLinked*(aList: LinkedLists.LinkedList): Set;
VAR s: SetAsLinked;
BEGIN
  NEW(s); IF aList = NIL THEN aList := LinkedLists.NewList END;
  ...
  RETURN s
END NewSetAsLinked;

PROCEDURE NewSetAsVector*(aList: VectorLists.VectorList): Set;
...

PROCEDURE NewSetAs*(aList: Lists.List): Set;
VAR s: SetAsList;
BEGIN
  ASSERT(aList <> NIL);
  WITH aList: LinkedLists.LinkedList DO
    RETURN NewSetAsLinked(aList)
  | aList: VectorLists.VectorList DO
    RETURN NewSetAsVector(aList)
  ELSE
    NEW(s);
    ...
    RETURN s
  END
END NewSetAs;
...
(* Set operations ... *)
END Sets.

It's not really hard at all, just time consuming. On the other hand, if
you need to have a higher level container implemented using more than
one type of lower level container, all of the alternate methods are just
as time consuming.

It's good to keep in mind that there are some disadvantages to generics
(speed, possible code bloat) just as there are to specialized containers
(maintainability, code bloat if too many specializations).

- Brian Hawley -