Heirarchical name space allocation /Trees

[Robert Will]

On Wed, 31 Mar 2004, Christian Maeder wrote:
>
> Rather than enforcing uniformity by a collection class (as proposed
> elsewhere), I would like uniformity at the module level wrt. exported
> functions and types. The hierarchy should allow for several different
> implemenations of one type with (almost) the same module interface.

Well, since this is a direct rival to the approach of Abstract Collections
I should hit you with some hard arguments here.

When I was young I also thought it was overkill to use dynamic binding to
allow different implementations of one and the same specification.  It
seemed to me that a good way would be to choose at linking-time, so you
always use the same interface-file and choose the implementation via the
-l option.  But modern programming methodology has abandoned the notion of
separate interface files -- according to the "all in one document"
principle we give the contracts and export lists directly in the code.
The resulting question of how to "factor out" common specifications is
answered by a simple, new mechanism that allows to factor our
specifications _and_ code: that's inheritance.

Deferred (jave lingo: abstract) classes in OO and type classes in Haskell
can be used to _express formally_ the design of an interface (with
semantics!) and this formal expression allows various automatic treatments
that would otherwise have to be done by hand: it is used in type-checking,
it is used to provide default implementations, it is used in the creation
of documentation, and with DbC in Haskell it will be used for automatic
tests.

The module-based approach is simpler when you start small, but it just
doesn't scale as well.  E.g., where do I put a general-purpose function
that works on all kinds of Sequences?  And what should be its type?  Not
using inheritance leads to much redundance and no automatic way to check
consistency.

Of course, having huge contexts in types and sometimes ambigous types is a
bit annoying, but that's no major problem, just the typical "formal noise"
you'll always have in programming.  Btw, approaches with subtyping don't
have those problems, but they have others.  What is astonishing:  both
approaches allow the same _designs_ to be expressed.  That's why a can
cite Bertrand Meyer's "Object-oriented software construction"  (Prentice
Hall, 1988) as the still up-to-date reference to design, even for (large)
functional programs.  Inheritance when used as a method is no fashion of
the OO mode: it is an intrinsic part of software design.  Without
inheritance of implementation (default methods...) we'd need to choose for
every function whether to implement it generically (using some primitives)
or separately for each instance.  Inheritance makes this choice oblivious
(w?).


People are complaining about too big classes, but where's the problem of
this?  Have you ever heard about Bertrand Meyer's "shopping cart" approach
(not sure, whether that's the exact name)?  The idea is, that if a class
embodies a suitable abstraction, we can add as many features (functions)
as we want as long as they fit the abstraction.  Good abstraction ensures
that we have no feature creep (i.e. complex monolithic features, instead
of simple, composable ones).  In object-orientation this is especially
important, since any functions that are outside the class have to be
called in a different way.  For FP, on the other hand, users don't care at
all whether a function is a class member or polymorphic: we can change
that any time without the user noticing.  And even implementors won't care
much, since we'll have the default implementation.

Who doesn't get at least a bit uneasy when looking at all the redundancy,
in e.g. Edison's code?  Okasaki has written some generic functions, but
they have to be renamed manually in each module.  All for the sake of
efficiency!  Bertrand Meyer did not propose to handle this via inheritance
without ensuring that the compiler would eliminate all the indirections.
And that was in 1985!


> The current problem is agreeing on interfaces, while there exist quite a
> few implementations (from which we can pick all the good ones).

I think that Dessy at moment provides the best interface (with respect to
generality and ease of use) and also some of the best implementations (in
terms of algorithmic coverage, simplicity, little redundance, albeit not
specific optimisations).  Of course anyone may disagree.  (Btw,
documenting all the really innovative stuff in official publications will
take some time, so if you want to wait...).


Robert