> I am new to oberon, but am an experienced C/C++ developer. While trying to
> learn Oberon-2 (in the blackbox environment) I have a few newbie questions,
> hope you can shed some light.
> ...
> 2) generic programming: In C++ we have Templates, in Eiffel Genericity. Is
> there a programming mechanism or trick that can enable generic programming
> in Oberon? You know, so that I can develop a List once and for all, and use
> this list for all kinds of record types for ever after?
Oberon-2 does not support parametric polymorphism (ie. generics). The
only way to develop general purpose containers (eg. Lists) and other
data structures (eg. B-Trees) is to use inclusion polymorphism (ie.
sub-typing). Thus, you would define your general purpose list as a
collection of some abstract type (eg. Object). By making your new types
subtypes of Object, you make them candidates for list membership. For
example:
TYPE
Object = POINTER TO ABSTRACT RECORD
END;
ListElem = POINTER TO RECORD
data : Object;
next : ListElem;
END;
List = POINTER TO RECORD
first : ListElem;
END;
MyType = POINTER TO RECORD (Object)
... type extensions
END;
etc.
The OOC project has developed a collection of abstract data types using
this technique. These include various types of lists, sets, queues. All
types support internalisation and externalisation, including an "Alien"
type mechanism similar to that of BlackBox Stores (this means that you
can fully internalise and externalise container contents, even if you
don't have the object code for a particular member). The ADT library is
available from:
http://home.t-online.de/home/mvacken/
As far as I know, the only attempt to provide "generics" for Oberon is
reported in "Lightweight Parametric Polymorphism for Oberon", by Paul
Roe and Clemens Szyperski. This is described at:
http://www.fit.qut.edu.au/~szypersk/pub/JMLC97.ps.gz
Their implementation has several advantages over the C++ template
approach:
1) It works using static checks on pointer types, which means that the
"generic" and its client can be compiled separately. C++ templates are
basically macros, which means that you need the source for a template to
be able to instantiate it.
2) There is no run-time overhead. (see my comments below)
3) There is no duplication of object code. C++ implementations vary in
the way that templates are managed. The Borland approach for automatic
instantiation (also used by Microsoft?) uses an intelligent linker to
remove duplicates of the template object code. If you try to port such
code to gcc (for example), code size can grow dramatically. The
alternative of manually maintaining a single instance of each template
can be tedious.
In his book "Component Software", Clemens says:
"Paremeterisation of types to express parametric polymorphism is a
proposed language extension (Roe and Szyperski, 1997) and is currently
under consideration for Component Pascal"
I would argue STRONGLY that parametric polymorphism should be included
in Component Pascal. The reasons listed above are all good ones, but
basically I don't like having to needlessly re-implement subtle
variations of the same data type. Here's one example:
The first exercise I set for myself to learn Oberon-2 was to adapt a
force-directed graph-layout algorithm from C++. The algorithm is
computationally expensive, being O(n^2) where n is the number of nodes
in the graph. I thought that I could be clever and use sub-typing to
make generic lists to manage collections of edges and nodes. I was
immediately disappointed because the resulting algorithm seemed to be
about twice as slow as the C++ version. As I ultimately discovered, in
traversing the lists the program spent as much time evaluating type
guards as it did doing the actual calculations. After re-writing the
algorithm (using separate lists types with explicit pointer types,
duplicating the list-management code) the performance was comparable to
the C++ version.
These results would probably transfer to many other algorithms that do
intensive client-specific operations on generic containers. If you
attempt to write code using inclusion polymorphism, you will probably
find it eventually littered with type guards, each of which requires a
run-time check. This is not only messy, but it can lead to some severe
performance costs. Parametric types are the answer, as has been clearly
demonstrated in many other languages. The proposed approach is a good
one (although limited to pointer types), and solves many of the problems
with existing implementations.
(crossposted to the Blackbox mailing list)
Regards,
Stewart
-- Stewart Greenhill (greenhil@murdoch.edu.au)