Response by Andrew Black

Response by Andrew P. Black

This is written in the form of notes rather than polished text. I had oringinally intended these notes to be for my own use, and to write a response that would select some themes from them and discuss them more fully. But, given the purpose of this discussion, I decided that it would actually be more useful to mail out the notes as ``unfinished thoughts'' to promote discussion.

Overview

Thought provoking document; I enjoyed reading it and am lookng forward to the Workshop, and continuting the discussion.

Makes me want to re-examine a lot of our traditional wisdom on software structuring.

In the end, however, I think that much of that traditional wisdom will survive, and Open Implementation will be a useful and powerful addition to our toolbox, not a replacement for black-box abstraction.

Black Box Abstractions

The foil says that black-box abstraction is intended to simplify client code because the client code can't get ``caught up'' in the implementation details.

I don't think that this is quite right. The idea of black-box abstraction is that the designer of a module makes explicit what a client is allowed to know (and thus depend on) and what it is not.

There is no a priori rule that says all implementation details must be hidden. In fact, this is almost always impossible. What the methodology says is that we must be explicit about what is hidden and what is not.

Being explicit about the interfaces has several benefits:

We can re-use a module, because the requirements that it has on other modules are explicit, and thus we have some hope of satisfying them.
We can re-implement a module, because the service that it must provide is described explicitly. This lets us determine which aspects of the `old' implementation must be preserved, and which must be changed.
We can distinguish which aspects of the behavior of a module are bugs, and which are features. In the absence of a module interface, we can't specify that interface, and if we can't specify it, we can't answer this question. I'm thinking back to my days hacking an OS6 derivative at Oxford, where the code was the documentation; it was some of the most clearly written and modular code that I have ever seen, and it was very easy to figure out what it was doing. But there was no way to figure out what it should be doing, in the view of its clients.
In essence, the advantage of having an explicitly defined interface is that people can use it. The best example of this that I can think of is the Unix system call interface. It gets re-implemented all over the place because it is used, and it gets used because it is implemented all over the place.
The disadvantage of having an explicitly defined interface is also that people use it. Once enough people use it, it is impossible to change it. Plan 9 is a bold attempt to throw away a good interface and start again, trying to build a better one. The Unix file read interface is a great example of a bad interface, given modern hardware. The system would be faster and easier to use if the kernel allocated a buffer when the client requests a file open, and tells the client where it is, and how big it is.
I think that the discussion paper mis-characterizes information hiding as necessarily requiring that all implementation is hidden the essence of the black-box approach is that the designer makes careful decisions as to what is hidden and what is exposed, and documents the interfaces of the box. It does not proscribe exposing any particular facet of the module through those interfaces.
I think that it inaccurate to say that the attempt to support wide-reuse with only black-box abstraction has had a crippling effect on operating system engineering.
What has been crippling is the success of the field; the abstractions have been so widely adopted that they cannot be replaced by improved abstractions. The result is either stasis, or a proliferation of different abstractions (since new ones can be added, but old ones cannot be taken away.)

Mapping Dilemmas

I prefer this term to ``Mapping Conflicts.''

A mapping dilemma occurs when a designer sees two or more good ways of implementing some specified functionality and no one implementation clearly dominates all of the others clients may use the module's functionality in several different patterns, and each of the implementations work well with some patterns and abysmally with the others.

Thus, there is no ``right'' implementation, and not even a ``mostly right'' implementation. Instead, whatever I do is going to be really wrong for some clients.

I love the term ``coding between the lines.'' The practice comes up again and again when trying to get performance out of general-purpose systems. Jon Walpole, Calton Pu and I came up with a wonderful example today looking at cache behaviour in HPUX, but I'll leave that to Jon to describe.

What is Open Implementation?

I realise that part of the objective of the workshop is to clarify the meaning of ``Open Implementation,'' so I'm not surprised to find that the term is imprecise. I think that it will be useful to discuss the imprecision, so we know what we have to clarify. In the examples, Open Implementation plays two roles:

To improve performance, while leaving the function of a module unchanged example: tiling window system.
To change the semantics of a component, sometimes in major ways example: the Mach external pager.

There are several implementation techniques suggested. At one extreme, choosing from a number of pre-defined implementations (example: tiling window system). At the other extreme, writing arbitrary code in a low-level imperative programming language.

This is just too wide a spectrum; what isn't an open implementation? Is the defining characteristic the existence of two separate interfaces to a component?

base-interface: ``functionality only''
meta-interface: ``adjusts'' the implementation

This distinction seems to me to be very subjective: is changing the sort routine used to establish the ordering of a sorted list an adjustment of the implementation?

If it makes the implementation faster?
If it changes the ordering of the list?

Inheritance and Open Implementation

Is inheritance (as found in Smalltalk) an example of OI?

implementation can be changed by a subclass overriding some (or all) of the implementation of the parent class.
hence, the subclassing mechanism provides a meta-interface
there is clear separation of the meta-interface from the normal interface

What inheritance does not provide is appropriately abstract access to the implementation.

there is no way for the implementor to control what may later be changed
dependencies are not documented, so the effects of any change are hard to ascertain, and are likely to extend far beyond those that the meta-programmer intends

Other Observations

The dichotomy between declarative and imperative meta-interfaces is a false one. Both declarative and imperative languages can be Turing-complete. The real dichotomy is between choosing from a pre-defined set of alternatives on the one hand, and being able to create new alternatives on the other hand.

Meta-interfaces must be well-designed too; Open Implementation does not eliminate the need for good design.

The discussion paper makes the observation that we have no good communications abstraction at a higher level than the datagram but at a lower level than the reliable stream. This is true, in spite of having spend much of the last 15 years looking for a suitable abstraction.

I don't see how Open implementation will help.

Back to Alphabetical List of Responses

Back to Main OI Workshop Page

Back to OI Home Page

Andrew P. Black
Department of Computer Science and Engineering
Oregon Graduate Institute

black@cse.ogi.edu

(Last Revised October 1994)