Response by Suresh Jagannathan

Factoring is one means by which a complex structure can be made tractable. I think of factoring as the ability to recognize a set of program elements or program functionality that may occur repeatedly in some program text; often, it occurs across a set of programs. Factoring takes on two manifestations in most languages. Time-wise factoring is simple procedural abstraction; space-wise factoring is simple inheritance/delegation. Black-box abstractions encompass (among other things) space-wise and time-wise factoring.

Languages which provide mechanisms to compose and create new abstractions make it easy to use factoring techniques easily. In the spreadsheet example, it is easy to imagine a richer framework in which a window-system creator is simply a ``glue'' procedure that combines its input arguments in a reasonable way. For example, we might specify the following:

  (define (window-system wakeup queue relate)
    (lambda (name x-coord-u y-coord-u x-coord-l y-coord-l)
      [return a window that provides operations
       closed over wakeup queue and relate]))

Window systems aren't constructed this way, and the foil makes clear that lack of parameterization and customizability is often the main culprit in a program's inability to be applied in contexts other than the often narrow one for which it was originally conceived. Whether we need a new methodology to address this problem is not so clear though. I'm of the opinion that existing methodologies (e.g., decomposition, layering, etc.) used witin programming languages that support composition of space-wise and time-wise factored objects would address the justified criticisms raised in the foil. For example, giving controlled access to meta-level structures such as environments is one way to enrich modularity without necessarily complicating a language. Rascal is an experiment that tests this hypothesis.

For the past several years, we have been applying implementation techniques similar to those prescribed in the paper to build a highly customizable operating system and multi-threaded programming environment. Sting allows users to provide their own schedulers and topology abstractions but guarantees correctness invariants on the kernel itself. Kernel routines closed over a given instance of a scheduler can be used to optimize applications. Using factoring and procedural abstractions liberally, it's possible to build customized kernels that use different schedulers based on the application they're executing.

For example, if we build a scheduler data structure that contained procedures for enqueueing and dequeuing threads, running a new application using a new scheduler is simply a matter of installing these new procedures. The kernel code itself never needs to be modified since it references these procedures via the scheduler data structure. So long as the provided procedures adhere to kernel invariants, different concrete implementations can exist with no loss in efficiency.

One might argue that this example is in fact a instance of an open implementation, but I'm more inclined to think of it as just good software engineering. There are no pragmas introduced here, and no new metaphors are needed to understand what's going on. The essential interface is still preserved in the scheduler data structure; the implementation of the scheduler is encapsulated within the enqueue and dequeue procedures. The only things exported are kernel invariants given in terms of the semantics of enqueue and dequeue. Different schedulers can use different representations with no adverse results. There is a contract between the scheduler and the kernel, but the specification of the contract does not require knowing anything about how the kernel works other than the interface to a thread.

One last related example -- we have been experimenting with a topology abstraction to provide a means for a parallel program's logical task structure to be mapped onto a physical topology. A virtual topology can be thought of as a scheduler and thread placement manager parameterized over logical and concrete algebraic structures whose elements are processors. For example, one can construct a virtual topology that maps logical trees to concrete meshes; the nodes in the tree and mesh correspond to virtual and physical processors, respectively. The role of a topology is to provide a mapping that optimizes communication among related threads in a program's logical task structure with respect to an underlying physical interconnect.

Is this an example of an open implementation? It seems to be in the same spirit as the examples given in the foil, but I never considered it in this light; rather, I've just viewed topologies as another example of how one can use factoring techniques to build customizable and extensible software.

Back to Alphabetical List of Responses

Back to Main OI Workshop Page

Back to OI Home Page

(Last Revised Febuary 1995)