 |
||
 |
 |
 |
|
||
|
|
|
Edited by: Gregor Kiczales
Contributions by: Shigeru Chiba, Rob DeLine, Gregor Kiczales, John Lamping, Chris Maeda, Dylan McNamee, Anurag Mendhekar, Gail Murphy, Luis Rodriguez and Ellen Siegel
(c) Copyright 1994, Xerox Corporation. All Rights Reserved.
This document, called ``The Foil'' was circulated in advance of the workshop, and attendees were asked to write short responses to the argument in the foil. This had the effect of catalyzing and focusing discussion at the workshop itself.
The principles we present run counter to some existing tenets of software design, and may initially even seem to violate the crucial design principles of abstraction, modularity and information hiding. Instead, we believe that what we are suggesting is a new approach to abstraction, modularity and information hiding, not a repudiation of those ideas. Above all, we believe that the benefits of working out this new approach will outweigh the costs, since we believe that it can make a major contribution towards wide-spread software reusability.
Black-box
abstraction is, we claim, just one such abstraction framework - one in which
we break a system down into functional modules, with interfaces that abstract
away implementation and keep only functionality explicit.
Figure 1: A black-box abstraction presents a single interface - denoted by the thick horizontal (blue) line in the figure. The goal for the design of this interface is to expose functionality, but hide implementation, so that the client code remains simple - denoted by the neat horizontal (blue) lines.
Designing modules to be black-box abstractions is also intended to allow substitution of the implementation, without the client having to be involved. This is the basis of portability of code: the lowest level service can be reimplemented for the new environment (processor etc.), and the rest can ``just run'' on top of it in the new world.
The reason black-box abstraction doesn't always work is that there are times when the best implementation strategy for a module cannot be determined without knowing how the module will be used in a particular situation. In other words, the client often knows best how the service should be implemented. But, because black-box abstractions leads implementors to decide early on what the implementation will be, and then lock that decision in the black-box, it can lead to conflicts when the implementor makes a choice that a client can't tolerate.
The more different clients try to use a module implementation for more different uses, the greater the likelihood of this kind of problem becomes. That is why the OI approach is so critical to extensive reusability of performance critical software.
As an example, consider a window system and one particular client, the display portion of a spreadsheet application. According to the principle of black-box abstraction, the window system interface would be designed to expose the functionality of windowing (sharing of the screen), display, mouse-tracking etc. Hidden issues would include what data structures are used to store window system state, how mouse tracking is implemented etc.
According to the black-box abstraction story, it should be an easy matter to implement a spreadsheet on top of a clean, powerful window system. What the spreadsheet application needs is just a rectangular array of boxes in which to display and in which the user can click the mouse. Since this is exactly the functionality a window system provides, the simplest way to code the spreadsheet would be to use one window for each cell. This takes advantage of the high-level window system interface to cleanly express what is desired, and makes maximal reuse of the existing window system code. A program written in this fashion is shown in Figure 2.
Figure 2: A spreadsheet looks like a rectangular array of cells. The simplest way to implement it is to use one window for each cell.
This is black-box abstraction at its best. The code is simple and clear, and we can read it without having to know anything about the inner workings of the underlying implementation. It is doing just what our limited minds need: making it possible to think about important properties of our program - its behavior - without having to think about the entirety of the operations the underlying hardware is having to perform to get it to run. In this sense, it truly reflects the black-box dream captured in Figure 1.
As wonderful as this may sound, few experienced programmers would be surprised to learn that this way of implementing a spreadsheet display on top of a window system wouldn't quite work. That is, it might work, but its performance would be so bad as to render it, in any practical sense, worthless.
Why? Well, this can happen if the window system implementation is not tuned for this kind of use. As part of writing the window system, the implementor is faced with a number of performance tradeoffs, in the face of which they must make decisions. No matter what they do, the window system will end up tuned for some applications and against others. In this case, the implementor might have assumed that 25 to 50 windows was a more typical number for an application to use than 10,000. Having made that assumption, the implementor would have made design decisions such as:
In the spreadsheet case however, a much better set of tradeoffs could be made in the window system implementation, if only the implementor had more information about the client - and was implementing the window system for just that one client. In particular, the highly regular arrangment of the children windows, and the fact that whenever the main window is exposed all the children will be exposed with it, means that the following implementation decisions could be made instead:
The problem with the black-box approach in this case is that if the implementor
chooses the first set of implementation decisions, and locks them away inside
the black-box, the client faces a conflict when they try to use the window
system this way.
What happens when a client programmer is confronted with such a conflict? They have to find some way to ``code around'' the problem. This generally takes one of two forms, which we call hematomas of duplication and coding between the lines.
A hematoma of duplication is what would happen in the spreadsheet case. The
spreadsheet programmer would be forced to write their own ``little window
system,'' that could draw boxes on the screen, display in them, and handle
mouse events. Reimplementing would allow the the programmer to ensure that
the performance properties met their needs. As shown in
Figure 3: Two ways that a client program can become more complex as a
result of coding around mapping conflicts. On the left, a hematoma of
duplication. On the right, coding between the lines.
In addition to making the application strictly larger, hematomas can also
cause the non-hematoma part of an application to become more complex. This
can happen if the functionality the hematoma duplicates doesn't interoperate
well with the original implementation. That can cause the client to become
contorted.
Coding between the lines is what happens when the application programmer
writes their code in a particularly contorted way in order to get better
performance. A classic example is in the use of virtual memory. In a program
that allocates a number of objects, there is often an order to allocating
those objects that is ``natural'' to the program. But, if there are so many
objects that paging behavior becomes critical, people will often rewrite
the application to ``allocate the objects close to each other'' and thereby
get better performance. This is coding between the lines because the documented
virtual memory abstraction makes no mention about the physical locality of
objects - it is only because the programmer knows something about the internals
of the implementation that they can write the code to obtain better performance.
The spreadsheet example, and others like it, have led us
to conclude that:
Mapping conflicts arise because different applications require very different
qualities of service. For example, an application sending payroll information
wants all the data to arrive, even if it delays the overall transmission.
On the other hand, for an application sending JPEG data, some packets are
less significant, and it isn't worth their being retransmitted if that would
delay processing on the receiver.
In each case, the question is how to give clients given access to mapping
decisions in a principled way, without causing more problems than we're trying
to solve. Put another way, how can we fix the problems with the black-box
approach without giving up what is right about it?
What was good about the black-box approach was that it led us to simple,
easy to understand interfaces by encouraging us to ``leave a lot of issues
out of the interface.'' Specifically, it suggested that we should leave out
all implementation issues. But now, if we need to expose more issues to client
control, we run the risk of designing overly complex and confusing interfaces.
To address this, we propose a revised abstraction principle, based jointly
on two contributions:
By blending these two, together with a study of a number of systems that
have tackled these problems, we propose the notion of a reflective
module, which is one that not only provides its primary functionality
but also provides functionality for negotiating the way in which it provides
the primary functionality. We call those two functionalities the base- and
meta-functionalities, and the interfaces that provide them the base- and
meta-interfaces. We suggest that access to mapping decisions be localized
in the meta-interface of systems.
In the case of opening up the window system to client control, an elegant
approach, that fits our notion of a reflective module, might take the form
of pragmas, something like:
In this case, the base-interface is the same as the original one, it is about
windows that occupy a region of the screen, have parents and children, can
be drawn in etc. Clients of the window system module write a base-program
that builds on top of the base-interface in the traditional way.
Even this simple example demonstrates what we believe to be a fundamental
property of a well-designed reflective module. Because the design makes a
clear separation between the base- and meta-functionalities -- between requesting
windowing behavior and negotiating the implementation of that windowing behavior
-- it makes it easy for the client programmer to focus on just the windowing
functionality independent of the tuning. It supports independent readings
of the program, as a way for the client to cope with its total complexity.
In this case, this could be done just by covering the right part of the page.
(One could of course imagine more sophisticated programming tools to help
with hiding the meta-interface, and this is an important aspect of research
in reflective modules.)
Figure 4: A reflective module presents two kinds of interfaces. The
base-interface provides the primary functionality, the meta-interface allows
the client to negotiate aspects of how the primary functionality is provided
that are normally hidden by (or implicit in) the base interface.
One basic point is worth repeating at this point: instances of reflective
modules already exist. What is new here is a crisp identification of the
need for open implementation, the basic idea of a reflective module, and
important associated design principles. The problems reflective modules address
are not new, and there are certainly a number of systems that, to varying
degrees, fit our characterization of reflective modules. Our goal is one
of giving clear words to emerging practice to make it easier to take the
next step. Several additional points about our notion of reflective modules
are important to note:
Again, the basic goals in making a principled base/meta distinction are to
allow the client programmer to: (i) use the base interface alone, in many
common cases where the default implementation is adequate; (ii) control the
module implementation when they need to; and (iii) when they need to do so,
be able to deal with functionality and implementation in largely separable
ways.
The goal is not simply to foist responsibility for implementing the service
onto the client. Mostly, the client programmer should just write in terms
of the base-interface -- they should not need to consider the meta-interface
at all. But, for those performance-critical sections of their code that encounter
mapping conflicts with the default service implementation, they can turn
to the meta-interface and change the mapping decisions accordingly.
To meet these goals, the base and meta interfaces must both be designed in
such a way as to make this switch in the client programmer's focus as easy
possible. Clearly client programmers will need to use some knowledge of their
base program when writing the meta program, but the goal is for them to not
need to be emmeshed in its details. The idea is that they should be able
to analyze their base program to discern what mapping decisions it needs,
and then turn to the meta interface with only those mapping decisions in
mind, not the full details of the base program.
The key point here is that while clients are provided with access to the
implementation, that access is: (i) separated from the primary functionality
in a principled way; and (ii) itself provided in an appropriately abstract
form. The main difference between this approach and black-box abstraction
is that rather than attempting to control complexity by
hiding the implementation of underlying modules, we are
proposing to control complexity by providing principled,
separate, appropriately abstract access to the implementation
of underlying modules.
Note that a client of a properly designed OI can often be more reliable
than the client of a black-box module approach, because the small meta-programs
reduce the occurrence of large failure-prone hematomas that may otherwise
be present.
With the preceding analysis and terminology in hand, the next three sections
show how the need for open implementation plays out in the domains of programming
languages, operating systems and communication. Stepping through these will
provide a clearer picture of the basic issues, as well as examining the kinds
of specific techniques that have been used.
Unfortunately the higher the abstraction level is raised,
the more serious the problems with mapping dilemmas become.
This way of helping out a language implementation
with mapping decisions is not a new idea. It has existed in the form of
declarative pragmas for many years now.
Pragmas can be very specific, such as in the HPF example above, or as in
C++'s inline which directs the compiler to inline a function.
Or they can be more vague, such as the speed and
space declarations supported by (most) C compilers which
direct the compiler to do whatever it can to increase the speed or decrease
the space utilization.
As another example, note that arrays don't have to be split across
multi-processors to cause mapping dilemmas. As discussed in
[SW80], a similar problem
can happen if a programmer tries to use a standard matrix package for matrices
that are inherently triangular. Hermes provides a pragma mechanism for
controlling the implementation of built in data structures.
Many pragmas, including those mentioned above, are ``semantics preserving.''
Others act to reduce the semantics of the language somewhat. An example of
this is the Common Lisp FIXNUM declaration, that restricts
arithmetic operations to be integers no greater than a certain (usually
relatively large) size.
An important aspect of most pragma facilities is their declarative nature.
This permits them to be carefully checked and makes for a very reliable
meta-interface. But, their declarative nature also means that they are of
limited power. They provide the programmer with the ability to select from
a fixed --- although possibly quite large --- set of options. To address
this problem, some pragma mechanisms have provided a mix of declarative and
tightly checkable imperative interface, as in the HPF example above.
CommonLoops
[BKK] and 3KRS
[Mae87] were the first languages to
use metaobject protocols (MOPs). MOPs have been developed for a number of
other languages since then, including CLOS
[BDG], TELOS [???], Open C++
[CM93], as well as a number of
research languages for concurrent and distributed computing, including ABCL/R
[WY88], RbCl
[IMY92] and AL-1/D
[OIT92].
The essence of a Metaobject Protocol is simple: every aspect of a program's
mapping down onto the lower level substrate (i.e. its compilation and runtime
support) is controlled by some object or set of objects following a well-defined
protocol. These objects are called metaobjects, because they are about the
mapping of the program, rather than objects in the program's primary subject
domain. Client programmers can replace one or more of these objects with
specialized ones to affect specific aspects of the implementation of specific
parts of their program.
Returning to the HPF example, in a MOP-based solution there would likely
be an object responsible for the distribution of the elements of each array.
The protocol would make this object responsible for allocating the array
memory across processors and implementing each access to array elements.
Client programmers could substitute a new metaobject for a specific array,
that provided alternative implementations of these operations.
Metaobject protocols are more powerful than declarative meta-interfaces because
they allow imperative meta-code --- that is meta-code that can perform arbitrary
computations. The metaobject for an HPF array would be able to produce any
arbitrary mapping from array elements to processors. Depending on the type
of MOP, this mapping could also depend on non-local program properties (e.g.
liveness of data) and on run-time values (e.g. sparseness of the array).
But this power can, in and of itself, be a problem. It can be more difficult
to use because programmers may introduce bugs into the meta-code whose symptoms
are hard to reproduce. It may also require the programmers to have knowledge
of the underlying system which is much more detailed with respect to the
simple array distribution scheme they may have in mind.
The first approach can be done
using a variety of partial evaluation
[Har77], caching, lazy
evaluation and late code generation techniques. Implementations of the CLOS
MOP do this [KR93].
Implementations of the Self language demonstrate more extensive use of similar
techniques [CUL89].
Designing MOPs so that metaobjects are consulted less often typically means
designing the protocol so that the client meta-program runs ``earlier in
time,'' and with access to somewhat different information. For example, in
the array protocol case, rather than having an operation in the protocol
that is called at the time of access, with the array and the index as arguments,
there would be an operation, perhaps called at compile time, with a description
of the array as an argument, that would return code to do actual runtime
access. That code would then be inlined where appropriate.
This shifting in time of protocol operations leads to a distinction between
runtime MOPs (RTMOPs) and compile-time MOPs (CTMOPs). In an RTMOP, the
meta-program has access to arbitrary values which have been computed by the
base program. In CTMOP, the meta-program doesn't have access to runtime values,
instead it has access to various kinds of global program analysis.
Many problems remain open. First of all to what extent the issues raised
in this section are inherent in process of opening a language's implementation,
or whether they are simply an artifact of the open implementation technology
currently available.
One issue is that the power provided by an open language implementation is
usually enough to let programmers ``shoot themselves in the foot.'' But,
should the designer try to prevent programmers from shooting themselves in
the foot? Is there even any way to prevent programmers from violating safety
if they are allowed arbitrary control over decisions made by a compiler?
(One might argue that there is no way to keep a programmer who is given such
arbitrary control from violating safety, since determining the "correctness"
of a programmer's code is not a computable problem.)
Intuitively, the answer is ``no.'' Instead of working to restrict the extra
power provided to prevent programmers from introducing bugs, current work
should focus on:
As we shall see in the following sections, these issues are not specific
to programming langauages. The other areas we will discuss have similar problems.
The notion of ``process'' denotes a program in execution and
provides an abstraction of units of computation
[Den71]. It also provides a way
to express synchronization and other dependencies between processes. Some
variants incorporate a resource container (Unix Process), while others treat
the resource container separately (Tasks and Threads in Mach).
Programmers manage storage via interfaces to virtual memory, files, and segments.
The ``virtual memory'' interface hides the details of how the memory used
by a program maps onto the available physical memory of the machine.
File descriptors, message queues, and ports represent interprocess communication
and I/O channels. The programmer may initiate and tear down the channels,
read from and write to them, and map their contents into virtual memory.
``Streams'' (a refinement of Unix file
descriptors)[Rit84] represent
a layered network protocol stack and provide a way for the programmer to
configure the layers of the stack at runtime.
Instead, the meta-interface must take
on a more advisory nature. One powerful way to do this is for the meta-interface
to allow the client to inform the OS about aspects of the module's behavior
that can help the OS better allocate the resources. For example, Transparent
Informed Prefetching [PGS93] uses
information about likely application behavior (e.g. a particular file being
opened will be read linearly and only once) to perform better resource allocation
than would otherwise be possible. Such an informing approach allows the OS
to apply a more global perspective to the decision making process.
The distinction
between an inform and a direct meta-interface is whether
the client is providing information about its own (likely) behavior, or whether
it is providing instructions about how the module should behave. The
imperative/declarative distinction made in Section
3 concerns the form of the directive, whether it is phrased as an imperative
command or as a more declarative goal state. Inform/direct and
declarative/imperative are orthogonal distinctions among meta-interfaces:
all four combinations are possible.
The abstraction mapping function usually occurs after resource allocation
has taken place. For example, file system access methods map a high level
concept (tuple of a relation) to a lower level concept (file record). These
are often layered; file records are themselves abstractions layered on file
blocks. Since abstraction mapping functions do not involve resource allocation,
the OS can provide a directive meta-interface for these issues. For example,
the UNIX OS provides no file access methods except for a minimal file offset
interface. This minimal interface is sufficient to implement any other access
method, with varying degrees of efficiency.
In the OS literature, the term ``policy'' has been widely used to mean something
close to a mapping decision.
We have already mentioned the page fetch and page replacement policies in
virtual memory managers. The scheduling algorithm used by the process
abstraction, the disk placement and disk scheduling used by the file abstraction,
the bandwidth allocation policy used by any of the I/O abstractions, and
the retransmission and flow control policies in networking are other examples
of mapping dilemmas in operating systems.
A common approach in OS research has been to try to strike a balance between
special-purpose and general-purpose implementations by developing policies
which work well for a ``representative'' set of applications. A typical technique
has been to profile a particular application workload and formulate a policy
that provides good performance for this workload
[Bel66,
BJ81,
NWO88]. However, mapping
conflicts occur when the policy fails to perform adequately under a pathological
workload. For example, virtual memory managers often implement an LRU page
replacement policy, but LRU fails when a program does a sequential scan of
memory. In this case, MRU is a more appropriate policy. Another example is
the slow-start congestion control algorithm in TCP, which was formulated
when TCP's previous retransmission and flow control policies were resulting
in catastrophic congestion problems on the Internet
[Jac88].
Increasing numbers of OS systems have been moving away from the search for
general-purpose implementations that satisfy representative workloads and
toward the domain of open implementation. These new systems are able to take
advantage of the body of knowledge that the OS community has amassed about
the behavior of various classes of systems under a variety of conditions,
and to use it to help choose the crucial mapping dilemmas to expose.
Meta-interfaces have been developed to make various
OS functionalities adaptable to a wider range of program behavior. Process
meta-interfaces are used to tell the scheduler when a new process should
be selected (e.g. the yield function in a threads package), which
process should be run next (e.g. handoff scheduling), or the relative importance
of processes (e.g. the nice program in Unix). Abstractions with
meta-interfaces have also been developed for CPU allocation in multiprocessors
[ABLL92,
Bla90]. Applications use the
meta-interface to provide hints to the OS when fewer or more processors are
needed. The meta-interface also provides a back-channel for the OS to communicate
its processor allocation decisions to applications, and for applications
to make use of this information.
Meta-interfaces have been used to provide increasingly fine-grained control
over virtual memory. In order to support applications requiring memory
persistence, early systems provided ways to control pinning and flushing
of resident memory. The Mach External Memory-Management Interface (EMMI)
[You89] exposes pagein and pageout
events to user-level backing store managers. This is essentially a metaobject
protocol as discussed in the section on metaobject
protocols. The metaobjects are regions of memory and the operations in
the protocol are the pagein and pageout events.
As an example of the power of this meta-interface, only a few dozen lines
of code were required to port Mach to an environment in which paging is done
over an infra-red link. The pagein and pageout operations were simply changed
to (substantially) compress and decompress the pages.
File system meta-interfaces have been used to control buffering strategies,
and naming and access control of files. System calls to flush disk buffers
(e.g. sync) provide a way to override the OS's buffer management
policies. AFS takes advantage of a lightweight file naming interface (AFS
names files by inode number instead of using the normal file namespace) to
implement a new file namespace and file access control lists
[HKM]. Transparent Informed Prefetching
[PGS93] uses hints from applications
as already mentioned. Cao et al [CFL94]
investigate global buffer allocation policies in support of user-level buffer
cache management.
The attempt to support wide reuse with only black-box abstraction techniques
has had a crippling effect on operating system software engineering. The
increasing mismatch in performance of the various hardware components of
computer systems combined with the wider range of new application requirements
(e.g. multimedia, databases, scientific computing) has triggered the evolution
of a new breed of operating systems, using the ideas behind open implementations
to provide operating systems built from the ground up to be flexible. This
trend is reflected by the increasing number of OS conferences and workshops
dedicated to or focusing on aspects of flexible or ``application-specific''
systems (SIGOPS European Workshop, HOTOS, OSDI, IWOOOS ...).
The fine-grained interactions with the OS required by flexible systems is
expensive, but it is nevertheless essential that resource management be more
adaptable to application needs. Current research is addressing this conflict
by building OS services which can be customized by applications via
meta-interfaces [MB93b], and by
building extensible kernels that enable clients to customize resource management
efficiently and safely [???].
There are, however, lots of mapping decisions required to make this simple
interface actually work. These include the formatting of the transmitted
data (``marshaling''), the choice of communication protocol, the choice between
synchronous and asynchronous communication (e.g. RPC vs. message passing),
message buffering and retry policies, synchronization and ordering constraints,
congestion control, and priorities or scheduling policies.
Consider a multimedia system, such as a videoconferencing system with whiteboard
capabilities. It is constructed on top of a communication system, but because
of the differing characteristics of its many data streams it needs several
different combinations of mapping decisions. For example, the whiteboard
may require reliable data transmission, but the audio and video components,
may tolerate packet loss and simply continue. There may also be tight
synchronization requirements between the audio and video streams, with looser
or non-existent constraints on the whiteboard data.
Application Level Framing
[CT90] (ALF) permits applications to
specify the size of the units of data transmitted over the network. Because
arriving data packets now correspond to these application data units (ADUs),
applications can take immediate control of their processing rather than having
to wait for the underlying system to reassemble some number of packets into
recognizable application-level data. To take advantage of this capability,
however, applications now require more control over mapping decisions such
as protocols for transmission and reception of data, and the associated
synchronization and retry mechanisms. With this mechanism in place, however,
it can be easier to structure applications like the multimedia example discussed
above.
Another approach that has been taken to allow more client customization has
been to hoist relevant aspects of the communications systems from the protected
operating system kernel into the user address space
[TNML93]. This approach provides
scope control as well as access, since any changes will involve only clients
which use the modified code. Some criticisms of this approach concern the
overheads due to context switching and less highly optimized user-level code,
and the security issues discussed in Section 4
which make it dangerous to accept imperative modifications. However many
of the protection issues are less serious if changes can be restricted to
the client's own address space. Furthermore, some approaches selectively
use the user-space path for infrequent operations such as connection set-up
and then revert to the more highly optimized kernel paths for the bulk of
the actual data transmission
[MB93a].
The x-kernel [OP92] approach
opens the implementation of the communication subsystem down to the granularity
of the protocol sub-module (``microprotocol''). The basic principle is that
protocols are divided into microprotocols which correspond to key protocol
operations, some of which may be application-specific. Clients then compose
tailored protocol graphs (primarily by hand) to achieve the optimal path
through the protocol processing for their particular application. Microprotocols
export a fixed interface so that there are no syntactic constraints on module
composition. Thus, by a careful construction of the protocol graph it is
possible to implicitly customize many of the key aspects of the communication
module implementation. FoxNet
[Bia94] extends the basic
x-kernel approach into the domain of high-level programming languages, achieving
increased scope control and incrementality primarily from the language
infrastructure.
Communication systems can be classified as ``reactive systems'', or deterministic
systems which react to input events by producing related output events. Such
systems allow a clean separation of the control and data flow, simplifying
the customization process. The HIPPARCH project
[CCD] attempts to resolve the dichotomy
of the flexibility-performance tradeoff in the domain of communication by
taking an automated approach. A set of application constraints on the basic
functionality and control flow of the desired communication subsystem are
used to generate a tailored protocol specification in a synchronous language.
This specification is then compiled into a control automaton. The final step
integrates the relevant sets of protocol and system libraries in order to
to generate a version of the final (optimized) communication protocol stack.
The concept of tuning the performance
of one process in isolation from the rest of its environment is deceptive,
since the actions of external agents can and will affect the availability
of resources such as CPU cycles, physical memory, or I/O bandwidth. OI cannot
afford to ignore the interaction and resolution of such potentially conflicting
constraints from concurrent processes, both local and remote.
An instance particularly relevant to the networking domain is group
communication, where a single logical communication occurs among a group
of communicating peers.
The purpose of this document is to provide an initial grounding for
the workshop's goals of discussing questions such as: why do we need open
implementations, what is the open implementation approach, and what needs
to be in place for the approach to be effectively applied?
Undoubtedly, this document misses many important issues related to these
(and many other) questions. We offer it in the hope that it can serve as
a basis for a fruitful discussion.
The Claim
It is impossible to hide all implementation issues behind
a module interface because not all of them are details. Instead, some involve
crucial strategy issues that inevitably bias the performance of the resulting
implementation. We call these issues mapping dilemmas, because they
involve a choice among several ways of mapping a higher-level functionality
down onto a lower level one. We call decisions by module implementors about
how to resolve mapping dilemmas mapping decisions. When a particular
client of a module performs poorly because the implementation embodies an
innappropriate mapping decision, we call it a mapping conflict.
Reflective Modules
main := mkwindow(root, 0, 0, 1000, 1000) {TILED_PARENT}
for i = 1 to 100
for j = 1 to 100
mkwindow(main, 10, 10, i*10, j* 10) {TILED_CHILD}
end
end
The meta-interface controls mapping decisions hidden by the base interface.
The client can write a meta-program, delineated by curly-brackets ({..}),
to re-negotiate the default mapping decisions.
Separation of Control
More Fine-Grained Qualities
Programming Languages and Parallelism
Because of this, there are many examples of programming languages that fit
our notion of reflective modules, that is that have more or less explicit
meta-interfaces.
The Evolution of High-Performance Fortran
REAL A(1000,1000),B(998,998)
!HPF$ ALIGN B(I,J) WITH A(I+1,J+1)
!HPF$ DISTRIBUTE A(*,BLOCK)
Pragmas
Other examples of languages with pragmas include C
[KR78], C++
[STR91], Hermes [???], Modula-3
[CDG et. al. 89,
Nel91], and Common Lisp
[Ste84].
Metaobject Protocols
Overhead
Semantic Dilemmas
Open Questions and Future Directions
Operating Systems
The Modules an OS Provides
In addition, virtual address spaces neatly solve the problem of providing
memory protection under multiprogramming. The use of ``files'' and ``segments''
allows persistent storage to be protected and shared, yet leaves low-level
storage management decisions to the OS.
The Implications of Resource Sharing
Mapping Dilemmas and Mapping Conflicts
We offer the new term mapping decision for two reasons: (i) the term policy
has evaded crisp definition; and (ii) we believe that the traditional use
of the term does not capture all of what we want to refer to.
Current Work on Meta-Interfaces in OS
This same meta-interface can also be used to glue the external pager to a
backing stores with richer semantics, such as recoverable storage
[Epp89]. (This is similar to ways
in which people have used the language MOPs to glue the language to persistent
storage.) More recent work has been aimed at providing meta-interfaces to
page replacement policies [MA90]
and to physical memory allocation
[HC92,
SP91].
Open Questions and Future Directions
Networking and Communication
Functionalities and Mapping Dilemmas
Open Implementation in
Communication
Open Questions and Future Directions
The concurrent use of meta-interfaces raises important questions about the
coordination of separated concerns with implicit interdependencies, and also
of multiple concurrent adjustments to the same concern by independent or
semi-independent entities.
Tuning the flow and synchronization of data over the network for receivers
physically dispersed throughout the network, with different speed links,
independent loss characteristics, and independent user constraints becomes
almost impossible to envision. Other issues such as membership, and message
ordering and reliability, must often be decided collectively even though
for efficiency reasons membership information is not expliclity available.
Software Engineering
Afterword
