🚀 go-pugleaf

Paul Sanders writes:
>There has been some discussion in comp.software-eng lately regarding
>reusable software components.   ...

>                                                  ...    I would like
>to spur some discussion on just what a reusable software component is.
>Following is (at the risk of doing some undergraduate's first-quarter Data
>Structures homework) an implementation of an in-memory B-tree.  What I'd
>like to discuss are:
>
>- Is this a reusable software component?
>- What are its characteristics that make it one?  Or don't make it one?
>- Is it a good one?  If so, why?  If not, why?
>- Would anyone use it?  Why or why not?
>- How can it be made better?
>- Anything else relevant to producing a good reusable component that is reused

At the risk of getting back into the discussion of why software development
isn't like the construction of other engineering artifacts, let me suggest
that, from a reusability perspective, a B-tree facility is rather like
a circuit board in a computer. You certainly can't argue that it's not an
electronic component, but it's not a very likely candidate for reuse in
the next computer you design. 

>- What are its characteristics that ...               don't make it one?

First, the conceptual interface that it presents to its clients is not
simple. Clients don't really want to fool around restructuring trees or
reclaiming storage; they just want a fast storage and retrieval facility.
Here they are forced to deal with details that shouldn't concern them
[poor information hiding].

Second, the client interface is inadequately specified. 
Descriptions of the various B-tree operations are supplied only in English, 
which is inherently either verbose or imprecise. 
Global constraints about keeping the tree height uniform, the branchyness from
dropping too low, the indices in left-to-right order, etc. are not spelled out.
Performance characteristics are not indicated. 
The type of the items stored in the B-tree is kept commendably general,
but no mention is made of the fact that correct operation depends on the
comparison procedure testing a <= relation which must be a TOTAL ordering
of the items. 
Etc.

>- How can it be made better?
>- Anything else relevant to producing a good reusable component that is reused

Just as with a circuit board, you may try to improve it, but it shouldn't
be done with an eye to creating a reusable component per se. The circuit
board contains reusable components, and it is part of a larger reusable
component. That is also the situation with the B-tree facility.

The reusable component upon which the B-tree facility should have been based
is the exploration-tree facility. It is a general purpose facility which
provides clients with trees and operations for navigating around in them.
In contrast to the B-tree, it can be used as a component in a wide variety
of situations.

The reusable component which the B-tree facility supports is the
almost-constant-function facility. Conceptually, it provides a
function F from an arbitrary totally ordered domain set to an arbitrary
range set. For all but a few values, F(x) = C, hence the name. A typical
application would be sparse matrices, where the domain would be pairs
of integers (lexicogphically ordered), the range would be floating point
numbers, and C = 0.0. Another might be symbol tables where the domain
would be character strings, the range would be say type names, and
C = Undefined_Type. Data bases, polynomials, etc. provide additional
applications. The <x,y> pairs where F(x) = y # C can be stored in a
B-tree. Note, however, that a wide variety of other implementations
are posible (e.g. AVL tree, linked list, hashing, etc.). Analogously,
a computer architecture can be realized using a variety of chips and
board layouts.

The exploration-tree and the almost-constant-function present clients
with simple interfaces which have clean specifications. That's
surely a necessary feature of a reusable component. 
Another important property is that, once you discover them, you find
that they could be used in a wide variety of current applications.
It's not so clear that you can design reusable components which are
only useful in future software.
/Bill