AN OBJECT-ORIENTED FRAMEWORK

FOR

REFLECTIVE METALEVEL ARCHITECTURES

 

 

 

 

 

 

BY

 

BRIAN FOOTE

 

B.S., University of Illinois at Urbana-Champaign, 1977

M.S., University of Illinois at Urbana-Champaign, 1988

 

 

 

 

 

 

 

THESIS PROPOSAL

 

Submitted in partial fulfillment of the requirements

for the degree of Doctor of Philosophy in Computer Science

in the Graduate College of the

University of Illinois at Urbana-Champaign, 1994

 

 

 

 

 

 

 

Urbana, Illinois


 


 

 

AN OBJECT-ORIENTED FRAMEWORK

FOR

REFLECTIVE METALEVEL ARCHITECTURES

 

Brian Foote

Department of Computer Science

University of Illinois at Urbana-Champaign, 1993

Ralph E. Johnson, Advisor

 

The marriage of reflection with object-oriented programming and design techniques has the potential to dramatically change the way that we think about, organize, implement, and use programming languages and systems.  Object-oriented languages that are themselves built  out of objects are easy to customize and extend.  Unfortunately, no existing programming language has a rich enough set of reflective facilities to allow this potential to be fully demonstrated.

The set of objects out of which a language is built constitute that language's metalevel architecture.  A reflective object-oriented language allows a running program to look at or change these objects.  A well-designed metalevel architecture can address a wide range of linguistic needs.  The principal goal of my research is to develop an architecture that effectively demonstrates the full power of objects and reflection. 

In order to find these objects, I have undertaken the construction of an object-oriented framework for reflective metalevel architectures.  An object-oriented framework is a set of abstract classes that together comprise a generic solution to a family of related problems drawn from a specific domain.  Reusable frameworks typically emerge as the result of an iterative, evolutionary process during which they successively address a range of different requirements.

This document describes the work that I have completed, as well as the additional steps that I am proposing to take to explore how to build object-oriented languages out of first-class objects.


Table of Contents

INTRODUCTION........................................................................................................... 1

Object-Oriented Object-Oriented Languages......................................................... 1

Terminology.......................................................................................................... 2

The Problem.......................................................................................................... 3

The Solution.......................................................................................................... 4

The Methodology.................................................................................................. 4

Remaining Work.................................................................................................... 5

HISTORY........................................................................................................................ 6

Lisp....................................................................................................................... 6

Smalltalk............................................................................................................... 7

Actors................................................................................................................... 9

3-Lisp................................................................................................................... 9

Brown and Blond.................................................................................................. 10

3-KRS.................................................................................................................. 11

ABCL/R............................................................................................................... 11

Common Lisp, CLOS, and the Metaobject Protocol.............................................. 11

ARCHITECTURE............................................................................................................ 12

Methodology......................................................................................................... 13

Prototypes............................................................................................................. 14

Self........................................................................................................... 14

Id.............................................................................................................. 15

Ego........................................................................................................... 15

Superego................................................................................................... 15

Roles..................................................................................................................... 16

State......................................................................................................... 17

Sharing...................................................................................................... 17

Scripts....................................................................................................... 18

Context..................................................................................................... 19

Closures.................................................................................................... 20

Semantics.................................................................................................. 21

Animus...................................................................................................... 21

Dispatching in Superego............................................................................. 22

Dispatching in Other Languages................................................................. 23

Dispatching Participants............................................................................. 25

Namespace............................................................................................... 26

Control...................................................................................................... 27

Issues.................................................................................................................... 27

Regress................................................................................................................. 28

Requirements......................................................................................................... 30

CONCLUSION............................................................................................................... 31

REFERENCES................................................................................................................. 32

 


INTRODUCTION

Object-Oriented Object-Oriented Languages

The marriage of reflection with object-oriented programming and design techniques has the potential to dramatically change the way that we think about, organize, implement, and use programming languages and systems.  However, for this potential to be realized, we must better understand what it means to build object-oriented languages and systems out of objects. 

Building programming languages out of objects brings the full power of the object-oriented approach to bear on object-oriented languages themselves  A metalevel architecture that is based on a set of interacting objects thereby permits these objects to be specialized or preempted in the same way that objects in application programs are.  As a result, programming languages built out of objects are easy to extend. 

New features are added to a suitably designed reflective object-oriented language by building a set of objects to support them.  These objects may, of course, be specializations of existing objects.  Reflective facilities have been used to add backtracking [LaLonde & Van Gulik 1987], futures [Foote & Johnson 1989] and persistence [Paepke 1990] to existing languages.  A well designed reflective metalevel architecture can limit the scope of extensions to a single object, class, or computation, or allow them to be in effect system wide. 

A reflective system shall allow programmers to create new metalevel objects and selectively substitute them for an existing part of the running system.  This ability allows programmers to add objects to trace a program's execution, for example, from within the language.  Support for debugging in most languages is usually treated in an ad-hoc fashion by individual implementations.  An object-oriented reflective metalevel architecture allows support for debugging to be provided at the language level.

It is easy to dynamically introduce new objects and object types into a running reflective program, since these objects, as well as the objects that define them, are themselves first-class, dynamic objects.  By contrast, it is difficult to add a new type of object in a C++ [Stroustrop 1991] program that has already been compiled.

Because programming systems with object-oriented reflective metalevel architectures have a model of themselves embedded within them, they exhibit a substantial capacity for metamorphosis.  Reflection has the potential to extend the runtime reach of a programming system inward into the definition of the language itself, downward into its implementation, and outward into realms currently considered the provinces of operating systems, programming environments and database systems.  Reflection has the potential to bring areas as disparate as programming language design, compiler construction, code generation, debugging, tracing, concurrent programming, and semantics together under a single umbrella.

Constructing the elements of programming systems out of dynamic first class objects can lead to a reassessment of where the walls between objects, environments, operating systems, databases, and command languages should be placed.  A comprehensive reexamination of how a system supports running objects could permit autonomous objects to break free of the processes that spawned them and migrate unencumbered among other processes, processors, and persistent object bases. 

A good sign that a programming language feature is needed is when a lot of people go to a great deal of effort to build it themselves atop existing languages.  There is abundant evidence that dynamic metalevel objects are such a feature.  Open systems need open languages.

Terminology

Like other emerging subdisciplines, the reflection community lacks a standard vocabulary.  Allow me, therefore, to establish working definitions for the following terms. 

A programming language with an object-oriented metalevel architecture is one in which programs are constructed out of first-class objects.  For instance, classes are themselves objects in Smalltalk-80 and CLOS, while they are not in C++.  Hence, Smalltalk-80 and CLOS can be said to have metalevel architectures that support classes, while C++ does not.

Metalevel objects, or metaobjects are objects that define, implement, or otherwise support the execution of application, or base level programs.  For example, instances of Context and Class are examples of metalevel objects in Smalltalk-80 [Goldberg & Robson 1983], while CLOS's metaarchitecture [Kiczales, des Rivieres, & Bobrow 1991] includes instances of class, slot-definition, generic-function, method, and method-combination.

A reflective object-oriented language allows a running program to look at or change the objects out of which it is built.  Introspection is ability to inspect, but not alter, the objects that implement a system.  The objects out of which a language is built constitute its self-representation. 

A reflective object-oriented program can access the objects that define how it works, and can alter them dynamically if necessary.  Changes made to these objects are immediately reflected in the actual dynamic state of the state of the system, and vice versa.  The requirement that this dynamic consistency be maintained is sometimes referred to as the causal connection requirement.

A language that supports the dynamic redefinition of existing parts of the system is said to be mutable.  A language that supports the addition of new features, but not allow the redefinition of old ones is said to be extensible [Stroustrup 1991].  The ability to exploit the existing definition of a system to augment its behavior gives the programmer considerable leverage over the rest of the system.  C++ is extensible, but not mutable.  Much of Smalltalk-80 is mutable, though the Virtual Machine is off-limits.  The CLOS MOP does not define the behavior of programs that attempt to change standard metaobjects.  However, some implementations have allowed such changes.

An object-oriented framework  (or, henceforth, framework) is composed of a set of abstract classes and components that together comprise an abstract design or generic solution for a range of potential application requirements.  The framework's abstract classes and components must be customized by the framework's clients to suit the requirements of specific applications. 

The Problem

The reflective facilities of contemporary object-oriented languages are incomplete.  As a result, the full power of object-oriented reflection is difficult to demonstrate.  To demonstrate this power, as much of a language as is possible must be built out of first-class objects.  The challenge is to find the right objects.

Smalltalk-80 is usually considered to be a pure object-oriented language, and indeed, most of Smalltalk is built out of first-class Smalltalk objects.  In Smalltalk, for instance, classes, contexts, processes, global namespaces, and even the Smalltalk-80 compiler are all themselves objects.   However, Smalltalk-80 is built atop of a virtual machine that is inaccessible to programmers.  As a result, a number of vital facilities are not accessible as objects [Foote & Johnson 1989].  The most important of these are the method lookup and dispatching mechanisms, variables, the basic storage layout and management mechanisms, and byte code semantics.

The CLOS Metaobject Protocol, by contrast, allows much better access to dispatching and variable access mechanisms than does Smalltalk-80.  CLOS itself also provides a powerful collection of mechanisms for constructing and combining methods.  The CLOS generic function facility allows for multimethods and per-instance specialization.  CLOS also provides built-in support for multiple inheritance.  However, since it is built on top of Common Lisp [Steele 1990], CLOS provides relatively weak facilities for accessing runtime control information.  CLOS's namespace manipulation facilities are derived from the pre-CLOS Common Lisp package mechanism.

While Smalltalk and CLOS are most widely known languages with comprehensive object-oriented metalevel architectures, a number of languages in the research community have successfully addressed specific metaarchitectural issues.  For instance, 3-KRS [Maes 1987] was the first object-oriented language designed with reflection as its guiding architectural principle.  ObjVLisp [Cointe 1987] explored implications of broader structural flexibility in a language's metalevel.  ABCL/R [Watanabe & Yonezawa 1988] demonstrated how a reflective metalevel architecture could address concurrency.  By contrast, Smalltalk's facilities for supporting concurrency are rudimentary, and CLOS has none.

The metalevel architectures of Smalltalk-80, CLOS, and ABCL/R can be seen as having complimentary strengths and weaknesses.  The purpose of my research is to find a set of objects that combines their strengths. 

The Solution

Because of the characteristic fashion in which object-oriented frameworks evolve, a good way to find a suitable set of objects for building systems for a given application domain is to build one.  There is no reason why object-oriented languages themselves are any less suited to this approach than any other domain.  Therefore, I am investigating the architecture of object-oriented reflective programming languages by constructing an object-oriented framework for reflective metalevel architectures. 

Reusable object-oriented frameworks cannot be constructed in a top-down fashion.  They are the result of an iterative, evolutionary process that unfolds at all levels of a system as objects are successively reapplied to address changing requirements [Foote 1988] [Johnson & Foote 1988].  Truly reusable objects emerge only as real application requirements are confronted.

This framework can be thought of as a set of generic building blocks for object-oriented languages.  It will allow individual languages to be constructed by specializing its abstract classes and components.  Because of the lifecycle characteristics of object-oriented frameworks, the construction of this structure is both the means by which this investigation is proceeding, and the end toward which it is striving. 

The Methodology

Building a framework requires domain expertise as well as familiarity with framework construction itself.  I have been working with domain-specific frameworks since 1985.  My 1988 Masters Thesis [Foote 1988], was one of the first comprehensive examinations of a domain-specific framework, that is, a framework for a domain outside of traditional  computer science domains like programming environments and graphics.  A number of our insights regarding how reusable objects emerge and evolve were presented in [Johnson & Foote 1988].  These, in turn, constitute the methodological foundation for this investigation.

[Foote 1988] also contained our first forays into metaarchitectural territory.  AccessableObjects and AccessableDictionaries demonstrated how new fields could be added dynamically to individual Smalltalk instances, and how these fields could in turn be referenced using the same syntax that is usually used for static accessors.

Our work with object-oriented reflection and metalevel architectures continued with an investigation of the reflective facilities in Smalltalk-80 [Foote & Johnson 1989].  This effort resulted in a detailed understanding of both the power and limitations of Smalltalk-80's metaarchitecture.  It also demonstrated how adding first-class access to Smalltalk's dispatching mechanisms could allow futures and object-composition mechanisms to be constructed.

To understand an application domain, particularly if one is interested in building a framework, one must examine as many solutions to problems in that domain as is possible.  Hence, I undertook detailed case studies of two additional metalevel architectures:  ABCL/R [Watanable & Yonezawa 1988] and the CLOS MOP [Kiczales, des Rivieres & Bobrow 1991][1]. 

The construction of a framework begins with a prototype.  A prototyping effort gives the framework architect an opportunity to learn his or her way around an application domain by solving a single, simple problem drawn from it.  The prototype can be thought of as a rough draft that is intended to reveal the coarse structure of a typical solution for a given application domain.  The objects that result from this effort are said to seed the framework.  It is important that the problem selected during this phase of a framework's construction be simple, yet representative of others to follow. 

We elected to seed our framework by implementing a series of object-oriented subdialects based on Self [Ungar & Smith 1987].  The first of these interpreters was Id.  Id demonstrated how a Self-like language could itself constructed out of objects.  In the case of Id, these objects were built using CLOS. 

The next iteration in this process produced Ego.  Ego dispensed with Id's CLOS scaffolding, and implemented the infrastructure needed to support itself either in straight, classic Common Lisp [Steele 1984] or in Ego itself. 

Superego added a set of reflective facilities to Ego.  In Superego, each significant element of Ego's architecture is reified.  One novel element of this architecture is the Ensemble object, which provides selective, dynamic control over Superego's runtime semantics.

Remaining Work

The Superego prototype showed how to make a reflective metalevel architecture for a Self-like language.  In order to show how this prototype might evolve into a truly general, reusable framework, we must show how it might confront a wider, more demanding range of linguistic requirements. 

Superego also had an unwieldy syntax and an inefficient implementation that made it difficult to work with.  The bottom-up nature of the bootstrapping process also forced functionality into the Superego primitives that ought better to reside in Superego itself.

Frameworks, like ecosystems, evolve when they are stressed.  A framework is stressed when it must address a requirement that falls outside the range of problems it can currently address.  Hence, architectural evolution can be encouraged by presenting a framework with novel requirements.

The following requirements will be used to drive the evolution of the framework, and will also demonstrate its utility:

     A unified dispatching model that can support Smalltalk-80, CLOS, and aspects of ABCL/R

     Object composition and dynamic aggregate support

     Automatic future generation

     Reusable variable-level constraint support

     Distributed object beachhead or stub code

     Customizable control and exception code

As these requirements are addressed, the elements of the framework will come to embody a collection of common structural insights into this application domain.

HISTORY

One possible explanation for the current popularity of reflection, particularly in the object-oriented community, is that it is heir to a long tradition of trying to make programming languages as open as possible.  Indeed, the notion of programs as potentially mutable data can be traced to Von Neumann himself.  This section attempts to trace this impulse from its emergence in the Lisp community, through Smalltalk, on into the contemporary landmarks in object-oriented metaarchitectural research.

Lisp

Nowhere has the open languages tradition flourished more than in the Lisp community.  Indeed, Self, Smalltalk, 3-Lisp, 3-KRS, CLOS, ObjVLisp, Scheme, the Actor languages, and ABCL/R can all trace their ancestry either directly or indirectly to Lisp. 

A metacircular definition was given for Lisp in [McCarthy et. al. 1962].  This definition gave a blueprint for a program that could take other Lisp programs in the form of Lisp data structures and execute them.  This program, in turn, allowed Lisp data structures (s-expressions) to be passed to a function (eval) and executed as code.  In [McCarthy 1978] McCarthy recalls the following about the preparation of [McCarthy 1960]: 

...Another way to show that LISP was neater than Turning machines was to write a universal LISP function and show that it was briefer and more comprehensible than the description of a universal Turing machine.  This was the LISP function eval[e,a], which computes the value of a Lisp expression e -- the second argument a being a list of assignments to variables.  (a is required to make the recursion work).  Writing eval required inventing a notation representing LISP functions as LISP data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express LISP programs in practice...

It is clear that McCarthy recognized that a programming language could be at least as effective as alternative formal approaches for defining how a programming language works.  McCarthy and his group did not at first foresee the practical potential that their approach had for actual metaprogramming.  However, the composition and execution of lists that represented programs soon became an indispensable part of the advanced Lisp programmer's bag of tricks.

The tradition of interpretation surrounding Lisp gave rise to image and snapshot-style programming environments.  These environments have stood in contrast to the batch-style compile/link/load approach that is still characteristic of most programming systems today. 

[Sussman & Steele 1978] investigated the properties of Lisp-style metacircular interpreters during the 1970s.  Among the issues this work explored were the roles that continuation-passing style, or CPS, and continuations could play in constructing interpreters for programming languages.

Smalltalk

In Smalltalk-72 [Goldberg & Kay 1976] [Ingalls 1983] code was viewed by the interpreter as simply a stream of tokens.  All of a class's methods were stored using a single code vector.  This vector served as a pattern that was used to match incoming messages.  The object returned by any computation could take control the local message stream, and gobble down as many tokens as it saw fit.  In Smalltalk-72, an instance was created when a Class name was evaluated.  Note that Classes themselves were not first-class objects in Smalltalk-72.

Smalltalk-74 [Ingalls 1983] introduced a programmer accessible object that represented the incoming message stream.  Not only could all the message stream operations be examined in Smalltalk, but the user could also define extensions to the message stream semantics.  While this was a local success, in Ingall's view, it did not solve either of the real problems:  token interpretation overhead, and the non-modularity of receiver dependent message parsing.  Smalltalk-74 also added method dictionaries, which allowed methods to be compiled.

With Smalltalk-76 [Ingalls 1983], the designers of Smalltalk began a retreat from dynamic token and message parsing and dispatching in the name of efficiency.  Still, it retained the imperative that elements of the system itself be aggressively promoted to first-class status.  Smalltalk-76 was the first language to cast the elements of an object-oriented language itself, such as classes, as first-class objects.  Smalltalk-76 was also the first version of Smalltalk to support full inheritance.  Ingalls referred to the following as the Smalltalk Philosophy: 

Choose a small number of general principles and apply them uniformly.[2]

On the topic of kernel size and openness, Ingalls stated:

We have always sought to reduce the size of the Smalltalk kernel.  This is not only an aesthetic desideratum; kernel code is inaccessible to the normal user, and we have always tried to minimize the parts of our system that can not be examined and altered by the curious user."

This requirement that the user be able to examine or alter as much of the system as possible  meshes nicely with our contemporary working definitions for reflection.  Indeed, the extensive set of metaobjects in Smalltalk-80 [Goldberg & Robson 1983] is one of the best existing examples of the power of such objects.  Nearly every significant facet of the Smalltalk-80 system was represented using first-class objects.  For instance, in Smalltalk-80, Classes, Processes, Methods, MethodDictionaries, CompiledMethods, Contexts, Blocks, and the Compiler itself were are themselves built out of objects.  As a result, Smalltalk has a rich set of what we now call reflective facilities. 

Of the effort to encompass as much system functionality as possible in language level objects, Ingalls [Ingalls 1981] remarked:

An operating systems is a collection of things that don't fit into a language.  There shouldn't be one.

[Deutsch and Shiffman 1984] describes a strategy for efficiently implementing what we now call Smalltalk's highly reflective Context objects. 

It is important to note that long before we had a name for it, the Smalltalk community was doing the seminal work on what we are now calling object-oriented reflective metalevel architectures.  The reflection community has, I believe, inherited significant portions of the original underlying Smalltalk agenda.

However, even in Smalltalk-80, the virtual machine still stands as a monolithic barrier that the programmer may not breach [Foote & Johnson 1989].  For example, in Smalltalk-80, gaining control of the message dispatching process is cumbersome at best.  Pascoe [Pascoe 1986] described a clever scheme for customizing message dispatching in Smalltalk-80.  His approach, rather than relying on compiler and code modifications, involved the creation of a parallel hierarchy of classes called Encapsulators.  An Encapsulator is an object that is wrapped around another (single) object.  Pascoe exploited Smalltalk-80's doesNotUnderstand: mechanism to construct these objects.

Pascoe's approach, in effect, used message forwarding to an encapsulated component to effect method lookup customization.  This is message forwarding, and not true delegation, because the self problem [Liebermann 1986] is not addressed.

Encapsulators are good for building objects like distributed objects [Bennett 1987] [McCullough 1987], since the object being forwarded to is in another address space from the original object receiving the message.  However, they do not work as well for atomic objects, since it is possible for the object being encapsulated to escape from the encapsulator and allow other objects to send it messages directly.

Actors

The goal of aggressively promoting elements of the language to first-class status, as well a recognition of the perils of regress, can be seen in the Actor community in this passage from [Liebermann 1986]:

Many object-oriented systems supply linguistic mechanisms for creating objects with methods, variables and extensions.  An alternative approach, which is advocated in the actor formalism, is to define methods, variables, and extensions as objects in their own right, with their behavior determined by a message passing protocol among them.  Obviously, an object representing a method cannot itself have a methods, otherwise infinite recursion would result.

This passage from the same paper also recognizes the merits of a small, highly extensible object-oriented kernel:

The mechanisms for sharing knowledge in object-oriented languages have now grown so complicated that it is impossible to reach universal consensus on the best mechanism.  Using object-oriented programming itself to implement the basic building blocks of state and behavior is the best approach for allowing experimentation and coexistence among competing formalisms.

3-Lisp

The notion of reflection was introduced in  [Smith 1982] and [Smith 1983] .  Smith's 3-Lisp permitted running programs to inspect and alter representations of the very interpreter under which they were running.  Subsequent work explored methods for implementing reflective towers [Smith 1984].

A system's metalevel is comprised of those entities that pertain to, represent, or support other computational objects.  An evaluator that is written in the same language that it evaluates is said to be metacircular [Abelson & Sussman 1985] [McCarthy et. al. 1962] [Sussman & Steele 1978].  Traditional metacircular interpreters do not expose their metalevels to user scrutiny or modification.  Hence, a running program cannot dynamically change the way in which subsequent evaluations are performed, except, perhaps, by running such code using yet a another interpreter, that is run atop the one that is currently executing.

The 3-LISP language incorporated reflection into a Lisp-based language.  In 3-LISP, user level code may specify code that is run at the level of its interpreter (i.e. the metalevel).  This code can access and change aspects of its state at this level that are implicit at the user (or base) level  Conceptually, each level is part of an infinite tower of simultaneous computations.  In practice, actual execution may be performed by the underlying implementation when processing reaches a level where no reflective processing is being carried out .

For instance, 3-Lisp's (LAMBDA REFLECT ...) form is passed a list of arguments, as well as an environment and continuation.  When the body of this form is executed, it can make changes to the current environment or continuation that may change the course of the subsequent base level computation.  The manipulation of these metalevel objects is thought of as metalevel computation.  One consequence of the way that 3-Lisp handles reflective lambdas is that if the programmer fails to invoke the base-level continuation, the interpreter will proceed through to a new prompt one level up the reflective tower from where the computation began. 

Smith also points out that in order for reflective functions to work, the base and metalevels must speak a common language.  It is not enough that objects that are accessed at several levels be denizens of a common structural field.  There must also be agreement that certain base level data structures have a certain meaning when they are treated as programs at the metalevel.

Smith identified three issues that a reflective system must address.  The first is self-representation.  A reflective system must have an account of itself embedded in itself.  This account must be accompanied by a theory in terms of which the referenced domain can be understood.  Second, there must be a systematic relationship between the embedded account and the system it describes.  This is the causal connection requirement.  It simply means that manipulating the self-representation must directly affect that which it represents, and that the system must, in turn, keep this representation consistent with the actual state of the system.  The third issue a reflective system must deal with is vantage point.  For a system to operate on itself, it must have a stable place to stand.  They who would remove their own hearts had better know how to hook up a heart/lung machine.

Brown and Blond

During the mid-80s, interest in reflection surfaced in the Scheme community.  [Friedman & Wand 1984] and [Wand & Friedman 1986] explored the semantics and potential implementation strategies for reflective towers.  These papers presented a reflective variant of Scheme called Brown.  [Danvy & Malmkjaer 1988] describes another variant called Blond.  These systems provide contrasting, useful perspectives on metalevel semantics that can inform the design of metalevel control objects.

3-KRS

The current surge of interest in reflection in the object-oriented community began with the work by [Cointe 1987] and [Maes 1987b].  Maes's 3-KRS experiment [Maes 1987a] [Maes 1987b] was the first explicit effort to integrate reflection and object-orientation.  The combination of reflection with an object-oriented metalevel architecture dramatically increases the practicality and power of reflection.  The metalevel of an object-oriented system can be distributed across a constellation of objects, each of which is responsible for a specific part of the overall system.  By contrast, Lisp-based metacircular interpreters must often funnel the interpretation process through a single monolithic case statement in their basic eval functions.

Maes observed that in languages like Smalltalk-80, domain specific computation and computation about computational objects themselves were often mixed together at the same level.  3-KRS introduced a strict architectural separation between domain level and metalevel code.  In 3-KRS, a unique metaobject is associated with each object in the system.  This metaobject houses code pertaining to its referent object's computational responsibilities.  For instance, a 3-KRS metaobject might support methods that determine how an object handles messages, inheritance, and printing.  Since metaobjects are themselves objects, they must be allocated lazily to avoid infinite regress.

Ferber observed [Ferber 1989] that 3-KRS was not itself a conventional class-based object-oriented language, and demonstrated how its architectural principles could be incorporated into a class-based language based on ObjVLisp [Cointe 1987]. 

3-KRS programs are themselves collections of first-class objects.  Maes called these objects program objects.   These objects, in turn, contain slots that define evaluators for these objects.  Since 3-KRS, was built atop a Lisp substrate, they do not deal comprehensively with issues such as activation and control.

ABCL/R

[Watanabe & Yonezawa 1988] showed how reflective architectures could be used to address concurrency.  ABCL/R is a member of the ABCL family of languages [Yonezawa 1989].  ABCL/R demonstrated how addressing concurrent communication explicitly at the metalevel could lay the groundwork for useful reflective customization.  As an example, an implementation of the Time Warp mechanism [Jefferson 1985] was added to an existing simulation program using only metalevel code.  ABCL/R also presented an elegant metaobject architecture in which metalevel slots were used to represent code, communication, state, and semantics.

Common Lisp, CLOS, and the Metaobject Protocol

Common Lisp [Steele 1984] is an amalgam of a number of Lisp dialects, and became something of a catch-basin for exotic linguistic features drawn from many of them.  Among these is a rich set of reflective facilities, including runtime evaluation, a powerful macro facility in which user code controls expansion, closures, and reader macros that allow dynamic transformation of the language's syntax.  Despite all this, modern Common Lisp implementations are, in many cases, able to generate efficient compiled code.

The Common Lisp Object System [Bobrow 1988a] is an object-oriented extension to Common Lisp.  Common Lisp, as defined in [Steele 1990] is itself, as a result, an object-oriented language.  (It is still common to refer to CLOS as if it were a distinct language when one is discussing the object-oriented features of Common Lisp.)  Common Lisp with CLOS is a hybrid object-oriented language in which the traditional non-object oriented part of the language is absorbed into the object-oriented part more or less by fiat.

CLOS programs are constructed of the following metaobjects:  generic-functions, methods, method-combinations, classes, and slot-definitions.  Generic functions are polymorphic generalizations of traditional Lisp functions.  Generic functions may specialized using one or more of their required parameters.  Generic functions that are specialized on more than one argument are sometimes referred to as multimethods.  Multimethod dispatching is fully dynamic.  By contrast, C++ functions may be overloaded according to the types of other than their first parameters, but only the first parameter can be used to dynamically bind a virtual function to a method.

Because dispatching is conceptually associated as much, if not more, with generic functions than with classes, the coupling between methods and classes is looser in CLOS than in Smalltalk.  CLOS also allows programmers to redefine the ways in which applicable methods associated with a given generic function call are combined.  This mechanism permits programmers to change the ways in which existing methods are called, and allows new kinds of methods to be defined, using method qualifiers.  Method-combination objects are good illustrations of how a new declarative mechanisms can be built into a language using reflective facilities.

The CLOS Metaobject Protocol [Bobrow 1988b] gave a brief snapshot of the work in progress on the CLOS Metaobject Protocol.  The Art of the Metaobject Protocol [Kiczales, des Rivieres & Bobrow 1991] gives a detailed presentation of the CLOS Metaobject Protocol, or MOP.  The MOP describes how the core metaobject out of which CLOS programs are built work.  By describing the protocols through which the system operates, the MOP sets the stage for user customization and extension of these objects.  [Paepke 1990] showed how the CLOS MOP could be used to extend CLOS to add persistent objects.

The reflective facilities in the CLOS MOP complement those of Smalltalk-80 in many respects.  For example, manipulating the CLOS dispatching mechanism is easy using the MOP.  However, since runtime context and control information is absorbed into "classic" [Steele 1984] Common Lisp, CLOS cannot provide object-oriented access to these facilities, while Smalltalk can.

ARCHITECTURE

I am exploring how to build object-oriented object-oriented languages and systems by constructing a framework for object-oriented reflective metalevel architectures.  The goal of this enterprise is to identify a set of (meta-)objects that can serve as building blocks for solutions to a wider range of linguistic applications than can those in existing metaarchitectures.  Such a set of objects would consitute an object-oriented framework for the domain of object-oriented reflective languages. 

The classes in a framework together define an architecture for its domain.  Each application built from such a framework is an instance of that architecture.

This investigation is exploiting the evolutionary characteristics of object-oriented frameworks by introducing specific requirements that will stress the framework and force it to evolve.  This section begins with an examination of this methodology.

The goal is that the resulting architecture be as open and reflective as possible.  Each element of the system should be built out of accessible and changeable first-class objects.

To construct a framework, one begins with a prototype.  I have constructed a series of three prototypes to set the foundation for this framework:  Id, Ego, and Superego.  This section will examine these prototypes, the set of objects that has emerged as the result of their construction, and their contributions to the overall effort.

This section examines the set of objects uncovered during the development of the three prototypes, and of the metaarchitectural roles that these and other objects must play as the framework evolves.

Methodology

Object-oriented programming languages and systems are having a profound impact on the way that we organize, design, implement, and maintain software.  These techniques allow us to treat software components and systems alike as durable[3], yet malleable artifacts, which evolve along with their requirements  Object-oriented languages make it much easier to design software components and systems that can adapt as requirements evolve and change [Foote 1988a].  Object-oriented techniques can promote the emergence of reusable abstract classes, components, and object-oriented frameworks [Foote 1988b] [Johnson & Foote 1988]. 

An object-oriented framework is composed of a set of abstract classes and components that together comprise an abstract or generic solution to a range of potential application requirements.  The framework's abstract classes and components must be customized by the framework's clients to suit the requirements of specific applications.  Frameworks, unlike abstract classes, are often characterized by an inversion of control.  That is, rather than calling framework elements directly, the client sometimes supplies the framework with components that are "called-back" from within the framework at an appropriate time.

There is a standard methodology for making frameworks, but most people don't use it.  Durable, reusable object-oriented artifacts emerge most readily from an iterative reapplication of existing abstract classes, components, and frameworks to successive, related requirements [Foote 1991b].  Object-oriented entities evolve at every level along a trajectory that takes them through an initial prototype phase, and expansionary exploratory phase, and a consolidation phase[4].   During the consolidation phase, structural insight gained during successive reapplications is exploited to increase the generality, structural integrity, and reusability of these entities.  As entities evolve, many will progress from loosely structured, application specific, inheritance-based white-box entities to fully encapsulated, relatively general, component-based black box entities.

This investigation seeks to exploit the evolutionary characteristics of object-oriented frameworks by stressing the framework with a series of requirements selected to force the framework to become more general.  Rather than waiting for requirements to arise to make the framework evolve, a designer with substantial domain expertise can select requirements that are likely to drive the framework's evolution in new, more general directions.  This approach can be thought of as a methodology for finding a general set of objects that encompass the requirements posed by a given domain.

Prototypes

The basis of the framework is a set of objectsdesigned to implement a metaarchitecture for Superego, a simple object-oriented language based on Self.  Superego, in turn, was preceded by two simpler interpreters:  Id and Ego.  Each interpreter implements a simple language based on Self.

Self

Ungar and Smith's Self language [Ungar & Smith 1987] [Hoeltze, Chang, Chambers & Ungar 1990] is a simple, elegant object-oriented language in the Smalltalk tradition.  Self dispenses with the instance/class distinction, and uses prototypes and cloning to create new objects.  Self's simple design made it an appropriate choice for the prototyping effort that seeded our framework.

In Self, an object is simply a table that maps names to other objects.  These objects, in turn, can be primitive values, such as numbers, other objects, or executable methods.  An object may have one[5] slot designated as a parent slot.

New objects are created by cloning, or making an exact copy of, an existing object.  The cloned object is said to be the new object's prototype.  Since any parent slots in the prototype are copied as well, such slots will be shared by all the objects cloned from a given prototype.  Class-like shared behavior repositories can be created by ensuring that the direct parent of an object that is to be used as a prototype contains the information that is to be shared.  Such objects are referred to as trait objects.

Self uses a name resolution scheme that begins with a computation's current context, and continues with the receiving object itself.  If this object does not contain a match, the parent chain is searched until a match is found.  If no match is found, an exception occurs.

If a match is found, and the matched slot contains a value, that value is returned as the result of the computation.  If the value of the slot is a method, the method is called, using arguments supplied during the computation of the current context. 

A consequence of this implicit eta conversion [Church 1941] of method data is that treating a method as data is quite awkward in Self.  This makes it hard to write metaarchitectural code to manipulate methods.

Id

The first language in this series, Id, was a simple implementation of a subset of Self in CLOS.  The implementation of Id was undertaken as an exercise to determine what sort of objects I might build an object-oriented language out of given that I had another powerful object-oriented language with which to build it.  The set of CLOS objects identified during the construction of Id served as a road map for the design of Ego and Superego.

Ego

The second language in this series, Ego, showed how the bulk of the metalevel responsibilities of the Id CLOS kernel could be implemented at the metalevel in Ego itself.  The Ego kernel was written in pure, old-fashioned Common Lisp, rather than CLOS.  The goal was to abandon all the comforts of CLOS so as to force the object-oriented facilities that I had come to depend on to appear in Ego itself.

Superego

Superego built upon Ego by adding more complete reflective facilities to Ego.  In Superego, the way the language works is defined by the objects out of which it is implemented.  These objects, in turn, can be manipulated from running Superego programs. 

The Superego prototype also contained the beginnings of a fully metacircular interpreter for Superego in Superego.  Two of the more demanding elements of Superego's architecture, blocks, and the reflect$ form, which demonstrates how 3-Lisp's REFLECT form might be implemented in Superego, were presented as first-class Superego scripts.  Note that Superego is more circular than typical Lisp-based languages, because its meta-architecture requires that instances, as well as the runtime kernel objects such as the method dispatching objects, be potentially first class objects, which may themselves initiate non-primitive computation.

Roles

I have identified a set of architectural concerns, or roles, that can categorize the elements of the framework.  These are divided into two groups, using a distinction proposed by Ferber [Ferber 1989].  Structural objects tend to be the static data that an interpreter might manipulate.  Computational objects are the dynamic structures that an interpreter might create, or static elements of the interpreter itself. 

Of course, with the metaarchitecture of a system distributed among a variety of objects, each can be thought of as a distinct reflective dimension, and distinctions such as structural, computational, and even metalevel are less significant than they might be in a non-object-oriented architecture.

The Superego kernel is constructed from a set of fully accessible first class objects.  The kernel objects include objects that define how scripts and other dynamic objects will be interpreted, as well as how the kernel itself represents its state.  They also provide access to primitive computations, so that operations beyond the scope of the language, such as arithmetic, may be brought into it.

The Superego Kernel is built of the following objects:

            method                       Result of evaluating a method script

            primitive                      Result of evaluating a primitive script

            block                           Result of evaluating a block script

            send                           Result of evaluating a send script

 

            scene                         A context-like object

            performance              A control context

            environment              The current namespace

 

            process                      A processor/process abstraction

 

            performer                   An object that executes (defines meaning for) a script

            ensemble                   A set of performers that work together

 

The Superego prototype showed that a Self-like object-oriented language with an metalevel architecture could extend and modify its own definition.  However, Superego does not have a full reflective metalevel architecture.  The full default set of objects that define Superego's semantics has yet to be implemented in Superego itself.  Several of the most demanding parts of the language, including Blocks, do have working metacircular implementations. 

State

Like the Smalltalk-80 Virtual Machine, Superego presupposes the existence of an Object Memory that provides chunks of memory that can be used to represent higher level objects.  The OM's job is to provide objects that can be asked, in turn, to store and retrieve other objects.  The OM is also responsible for garbage collection.  Superego derives this functionality from Common Lisp.

Any slot may be designated as a parent, using a special primitive operation.  Superego does not support multiple parents.  The identity of the active parent slot is cached by the kernel for each instance.

Objects can be constructed in two ways.  One is to execute a clone primitive, as in Self.  The other is to create an empty object, and add slots to it. 

Like Smalltalk-80, Superego permits indexable, or array parts to be associated with instances.  In Superego, every instance can respond to messages to manipulate an indexable part.  This part may be treated as a stack using the push/pop-style protocol.

All objects in the system will usually be located in the default object memory, or store.  This store will be responsible for garbage collecting objects in it that are no longer in use.

Nothing prohibits the use of multiple stores.  Variant stores might be created to facilitate interaction with distributed object bases or servers, or to allow different storage management schemes to be introduced.  Access to such stores might be regulated on a per-object basis.  Access to these sorts of facilities might also be handled at the level of the state management protocol.

Like Self, Superego represents both state and behavior using dictionary-like instance objects.  Superego allows base level programs to read slots by sending messages to themselves using a slot name as a selector.  They may write their variables using an explicit assignment operator.

Self tries not to distinguish state and behavior.  As a result, the framework's instance model will have to be extended.  Smalltalk uses an instance model that closely couples instance structure to an object's class, which in turn permits indexed rather than hashed access to fields.  Self, in fact, retains similar information in map objects that are inaccessible to the user.  CLOS also defines the layout of instances using class objects.  The nature of slots is defined by slot-definition objects.  ABCL/R instances uses a separate state parts to store information.

Sharing

Superego employs Self-style prototype and trait objects, instead of Smalltalk-style Classes, as repositories for shared behavior and state.  This organization is conceptually simple, and easy to bootstrap.  I expect, however, to be able to construct objects that more closely model Smalltalk Classes, and CLOS classes and specializers, as well as some novel mechanisms, as the framework evolves.

Traditional inheritance is an extremely useful static, per-class mechanisms.  There are problems that require dynamic, per-instance solutions.  Tracing access to an individual object for a period of time, or constraining it to notify a window of changes to its state are two applications that require dynamic, per-instance mechanisms.

Scripts

Superego represents programs using objects called Scripts.  Scripts are structured, first-class objects cast at about the level of abstract syntax trees.  Scripts are computed in Superego using a set of Common Lisp Macros that dynamically translate Superego's presentation language into Script Objects. 

The notion of a human readable presentation language that is distinct from a canonical syntactic representation of the same language is taken from Algol 68 [Lindsey 1969].   Scripts are designed so that first-class programs can be assembled by other programs, as well as by human programmers.  This notion, of course, is drawn from Lisp.  The mapping between the presentation and reference levels be two-way.  Smith called these two translations O and O-1.

Superego employs the following types of scripts:

Superego Atom Scripts

            Integer           1, 2, 3                         Integers

            Selector         dog, cat, mouse        Unique selectors (operators)

            Symbol           :dog, :cat                    Lisp-style unique tokens

            Boolean         (true, false)                Built into Superego namespace

 

Superego Compound Scripts

            Send               (send$ a0 a1 ... an)              Send a message

            Sequence      (sequence$ s0 ... sn)           Evaluate s0 ... sn, return sn

            Collection       (collection$ e0 ... en)            Construct a collection

            While              (while$ test body)                 Perform body while test is true

            Method           (method$ parm temp body) A method definition

            Primitive          (primitive$ parm temp body) A primitive method definition

            Block              (block$ parm temp body)     A block

            Return            (return$ value)                       A block or method return

 

The table above shows the Common Lisp macro representation for each of Superego's script types.  The send$ script represents a message send expression.  The sequence$ form evaluates one more other forms sequentially, and returns the result of the last form as its result.  The collection$ script provides a syntactic mechanism with which lists and arrays can be constructed.  The while$ form provides iterative functionality without resorting to tail-recursion.  The method$ form defines a method.  The primitive$ form defines a primitive, or native method, and may contain pure Lisp code.  The block$ form defines a Smalltalk or Self-style block.  The return$ form designates the result of a block or method.

Script objects represent programs.  In Lisp, lists representing programs play this role.  In Smalltalk, there are no direct analogs to scripts.  Instead, source code strings serve as a high-level program representation, and byte codes serve as a low-level representation.  Note that Common Lisp lists and strings, and Smalltalk byte codes are not first-class objects. 

Superego's representational scheme for programs most closely resembles that of 3-KRS.  Maes's program objects were first-class objects.  Bringing objects into play at this level makes building debugging, tracing, and metering tools easier.  For instance, one might trace a particular method by dynamically interposing a customized set of behaviors into the inheritance chain for that method object alone.

One of the best known reflective facilities in any programming language is the ability of most languages in the Lisp family to treat user composed data structures as code.  Lisp programmers are far less reluctant to devise solutions to problems that entail computing new code than are programmers in other languages.  One explanation for this is that Lisp's program representation  is couched at an appropriate level, that is, approximately that of an abstract syntax tree.  Of course, given the syntax of Lisp, this is relatively easy.  Lisp s-expressions are easy to compose, index, decompose, and inspect.

In contrast, Smalltalk-80 programs can, in principle, compute code as well.  However, to do so, they must manipulate either source strings, or byte codes.  The former representation is at too high a level, and the latter at too low a level to be convenient.  Smalltalk-80 employs parse trees, but they are not set up to play the role necessary to be useful as a reflective self-representation.  Such a representation, with a two-way mapping between it and source code (Smith's O and O-1), as well as between it and whatever machine level representations are used, seems desirable.  Examples of languages that explicitly represents abstract syntax level objects are 3-KRS and KSL [Ibrahim & Cummins 1988].

Context

In the process of executing scripts for application-level objects, the kernel must maintain the state of its own progress somewhere.  The kernel uses a number of objects to do this.  The kernel's primary state repository is its current Scene.  Together, Scene and Performance objects carry out many of the same functions as Self or Smalltalk Context objects.  However, they elevate responsibility for flow control and interpretation out of the virtual machine, and into the language itself, where these functions can be manipulated.

Scenes and Performances contain the following fields.  The names differ slightly from the current implementation of Superego, which combines these fields into a single Scene object.

Scene

            caller/sender              Who called us

            spotlight                     Current Performance

            rho                              Current environment

            home                          Place from which we return, if asked

            process                      The current process object

 

Performance

            script                           The current script

            place                           The element of the script currently being performed

            step                            The performer's current behavior

            performer                   The current performer

            scene                         The current scene

            previous                     The previous performance (control stack)

 

Process and Processor objects might allow a concurrent successor to Superego to handle multiple threads.

Closures

The execution of method$, primitive$, block$, and send$ scripts creates method, primitive, block, and send objects that are evaluated later.  This organization allows different kinds of runtime method, primitive, block, or send objects to be created using the same scripts as dynamic circumstances warrant.  In the case of block$, this organization closely resembles that of Smalltalk-80.  The execution of a Smalltalk block creates a BlockClosure object.  This object may subseqently be sent a value (or value: etc.) message to acutally execute the block and return a value.  In the case of a method$ and primitive$ scripts, the method and primitive objects are created when the scripts are bound to the objects to which they belong.  For example, the method object, and not the method$ object contains fields that tie the method to its owner.  Send objects are created from send$ scripts as a method executes and the send$ scripts are encountered. 

Because the current Ensemble object contains entries that define how send, method, primitive, and block objects will be created from their corresponding scripts, this factoring allows dynamic changes to be made to the behavior of certain objects without distrupting the original scripts.  For example, changing the way that send objects are created from their scripts is one way of selectively introducing tracing or debugging code at runtime.

Method and primitive objects will usually be computed during the construction of prototype or trait objects.  Superego uses Self's convention of factoring the responsibilities usually assumed by Smalltalk classes into two objects, a trait object, and a prototype object.  The trait object contains behaviors shared by all objects that inherit from it, while a prototype is a template that is cloned to generate per-instance slots, together with default values.

A method is defined by evaluating a method script object, and storing the result of this evaluation in a slot.  The method object contains the script object, along with information that ensures that the script will execute in the appropriate environment 

Block objects are closure-like objects that can subsequently be asked to perform the block's behaviors, much as in Smalltalk or Self.  A Send (message) object, on the other hand, is (usually) dispatched immediately.  This dispatching process performs method lookup.  Once a method is located, a new scene is created, and the method's body is executed.

Semantics

Unlike Smalltalk and Self, Superego distributes its semantics across a set of first-class objects.  These objects, Performers, dictate how scripts and other objects that define behaviors will be interpreted.  Each Performer defines how a particular script or kernel object is interpreted.  Performers are collected together into sets called Ensembles.  This grouping allows the machine's semantics to be modified using a single, atomic assignment, and hence allows Performers that depend on cooperating with certain fellow performers to be consistently introduced.

Each Ensemble must contain a performer for each type of Script in the system, as well as for each type of closure (method, block, primitive, and send).  Certain complex actions, such as message dispatching, are subdivided so that multiple performers may participate.

Animus

The state of the motive force, or animus, behind actual computation is maintained by kernel Processor objects.  The behavior of these objects is derived directly from the primitive computational thread provided by the underlying machine.

Computation proceeds as the result of an inner loop in which a running Processor object sends the message action to the current Scene.  The default behavior for Scenes in response to this request is to send the message proceed to the current Performance.  Scenes are similar to traditional Contexts, while Performances are inner control contexts.  Scene objects keep track of where they were invoked from, the current Performance, the current Namespace (or environment), the current home context, and the current Process. 

Performance objects keep track of the state of the progress of the execution individual scripts and closures.  They hold pointers to the Performer's place in the script, as well as which step in the performance the computation has progressed to.  They also contain back-links to the current Scene, the Current Performer, and the previous Performance.  The place and step fields can be thought of as a two-part program counter.  The reason for this division is that one Scene will be created for each method invocation, while a Performance will be created for each node in the abstract syntax tree.

Scene and Performance objects are distinguished for a number of reasons.  Scenes play the role of a semantic environment, in that they model the process namespace, while Performance objects take on some of the control responsibilities of continuations.  Performers correspond to the semantic behavior specifications themselves.  It seems likely that there will be circumstances where Scene objects will need to be reified, while Performances may not.  Since these are more plentiful than Scenes, fully reifying them would be very expensive.

Dispatching in Superego

Send Scripts are handled in Superego as follows.  First, all the expressions (sub-scripts) are evaluated, and these results are saved in the current Scene's environment.  Once all the elements of the send are determined, it is bundled together with the current Scene into a message, or Send object, and this object is sent the message dispatch.  Creating a Send object is useful in concurrent systems when it might need to be placed on a queue, or in distributed systems where it might be sent to another machine.

When a message (or Send) is dispatched, it must determine what computation it is supposed to undertake, and then take those steps that are necessary to stage and perform this computation.  Conceptually, this computation is determined jointly by all the elements of the computation.  That is to say, the selector, all of the arguments, as well as the context, and the current ensemble all have a potential say in determining what will be done.  The means by which an effective method is identified is determined by the current ensemble. 

Superego's dispatching scheme is modeled after Self.  The first expression in a send script is used as a key that is looked up in the instance object given by the second send script expression.  This search proceeds up the parent chain to the system's root object, if need be.  The result of this search is sent the invoke message.

Methods, Primitives, and other objects respond differently to the invoke message.  A primitive method  is invoked immediately, with expressions 1 through n as arguments.  A non-method object is returned as the result of the send.  A Superego method causes the system to stage and present a new Scene, and then return its result.

The execution of all non-primitive scripts and closures requires that control be handed over to a new Scene.  Scenes, in turn, are prepared by sending the stage message to the script or closure.  During the staging process, a new scene is created, and threaded into the current machine state.  Most scenes will require creating of a control context (a Performance) as well.  A process called casting identifies the appropriate member of the pertinent Ensemble and creates a Performance object.

Superego allows individual objects to override the default Ensemble.  The kernel sends the message ensemble to an object to determine how to evaluate it.  However, per-object customization is but one way to usefully specialize the language's semantics.  Certain applications, such as debugging, will require that specialized Ensembles are inherited dynamically from their calling contexts.

Dispatching in Other Languages

Message dispatching mechanisms differ significantly across object-oriented languages.  Hence, finding a set of abstract objects that encompass these differences is an interesting problem.  Dispatching also provides a very useful locus for linguistic customization and extension.  This section explores some if the differences among existing dispatching schemes, categorizes these mechanisms, and explores the potential utility of modifying them.

On the surface, a Smalltalk message send, a CLOS generic function call, and a C++ virtual member function call might seem to differ little from a simple function call in a language like C. In at least one fundamental sense, they differ not  at all.  In each language, a caller may interpret each sort of call as meaning something like:  perform some useful computation determined by the given operator and operands (I care not what) and get me a result.  That is to say, the call itself can be thought of as specifying an abstract operation.  The precise nature of the computation that implements the call is, from this standpoint, none of the caller's business.

Of course, the nature of what the programmer might expect to occur when such a call is made in each of these respective languages varies substantially from one to the next.  It is instructive to compare the programming models associated with following sorts of calls:

A typical Smalltalk message sends work as follows.  First, the expressions specifying the message's receiver and arguments are evaluated.  Then the receiver's class is ask to locate a method corresponding to the message's selector.  If the receiver's class's method dictionary contains an entry for the message's selector, the method entry corresponding to it is returned as the result of the method look up.  If there is no entry for the given selector, the search continues using the class and method objects of successive superclasses of the receiver.  If no method can be found, the receiver is sent the doesNotUnderstand: message, with an explicit Message object as its argument.

Once a method object has been located, a context is created, arguments are bound to parameter variables, temporary variables are created, and the code associated with the method is invoked.  This final part of the process resembles a traditional function call in many respects.  However, a striking difference between the Smalltalk model and traditional models is that in Smalltalk, most of the critical elements of the model are themselves first class objects.

Though many of the elements that participate in the message dispatching process are accessible to the programmer, Smalltalk-80 has a point beneath which the programmer cannot reach .  Smalltalk-80's virtual machine is responsible for looking up and dispatching messages.  It is possible, either through interpreter modification, or legerdemain involving doesNotUnderstand: to work around this architectural restriction.  This matter is addressed in quite a bit of detail in [Foote & Johnson 1988].  One of the principle observations made in this paper was that if one really wants to alter the way in which a pure object-oriented language works, then hijacking the message dispatching mechanism will allow one to intervene most anywhere in the system one wishes (particularly if efficiency is a tertiary concern).

The Common Lisp Object System employs a polymorphic calling model in which operators themselves, rather than operands, are responsible for figuring out what function to invoke.  A generic function is a CLOS object that is initially invoked in the same way as a standard Common Lisp function.  However, when a normal function is applied to a list of arguments, control is handed over to the code associated with function.  When a generic function is applied to a list of arguments, control is handed over to a discriminating function associated with the generic function object.  This discriminating function is responsible for computing and executing another piece of code, the effective method for this call. 

Method objects in CLOS are associated more closely with their generic functions than with class objects.  Any number of methods may be associated with a given generic function.  Each method is said to be specialized according to the classes or identities of its required arguments.  CLOS does not limit specialization to a distinguished "receiver".  Any required argument may specialize a CLOS method.  A method whose eligibility is determined by more than one of its arguments is called a multimethod.  Each method also has a qualifier associated with it.  This qualifier identifies the role the method is to play when it is combined with other applicable methods into an effective method.

When a generic function's discriminating function executes, it must first compute a list of all the methods that are potentially applicable given the identity of the generic function, and the list of all the arguments that were passed to  A method combination object is then invoked to produce an effective method.  This result corresponds roughly to the result of the method lookup process in Smalltalk.  From here, the rest is fairly simple.  The effective method is executed, and its result becomes the result of generic function call.

ABCL/R [Watanabe 1988] provides two different types of messages:  past and present.  (ABCL/R does not support ABCL/1's future message type.)  Past messages are sent along with an explicit reply destination.  The caller and callee both run in parallel.  Present messages suspend the caller until the callee has computed and returned a result.  ABCL/R messages are more than abstract function calls.  They are true communications between concurrent objects.

Each ABCL/R object is implemented using a metaobject with four parts:  a state part, a script set, a message queue, and an evaluator.  When an object is sent a message, that message is placed on the object's message queue.  Objects in the ABCL family of languages may process only one message at a time.  When an object dequeues a message, it searches its script set for a script that matches the selector pattern given in the message.  This script is then evaluated, using the metaobject's evaluator, and the arguments passed as part of the message.

To provide maximal flexibility and power, it is necessary to identify all the objects that might usefully benefit from overriding parts of the dispatching process, so that one can design a mechanism that permits them to do so.

Dispatching Particpants

When a message is to be sent, some object, a dispatcher, must be located and put in charge of making the computation happen.  Differences among models will be determined by the way the dispatcher works, and by the way in which it is determined  The following sorts of objects might all contribute to the process of nominating a dispatcher:

Instances

Classes

Contexts

Operators

Messages

 

The participants in the nomination process may nominate themselves, or another object as the current dispatcher.

The question of how the dispatcher is determined is important because it defines what object is given control when a message is sent.  For instance, if objects nominate their dispatchers, then constructing an operator (generic function) based dispatching model requires that each object employ a dispatcher that hands off control to a generic function style dispatcher.  Let's examine some options more closely:

In the per-object perspective each object (the a0 argument) is responsible for nominating a dispatcher for an message send in which it plays the receiving role.  This model yields a dispatching model that resembles Smalltalk's.  The case in which the receiver's class nominates the dispatcher is a special case of this one.  So is the per group case.  The per group case assumes that some number of individual objects have elected to use a common dispatcher to enforce some relationship among them.  The global dispatcher case is the one in which the dispatching mechanics can't be changed at all.

This model allows each object in the system to be in charge of what happens when it is sent a message, and to change its behavior on a dynamic, per instance basis.

This model complicates the construction of multimethods.  The story that must be told goes something like:  If my selector is a known multimethod, hand off to a secondary dispatcher that knows how do deal with this.  The model of secondary dispatching employed here could either use a distinct generic function style dispatcher, or distribute the secondary dispatching responsibility in a fashion reminiscent of double dispatching.

This per-operator perspective resembles the CLOS generic function model.  When a message is processed, control is handed over to a dispatcher nominated by the selector (operator).  This entity is referred to as a discriminating function in CLOS.  Multimethods are easier to construct given operator primacy, but this model makes defining the role of the arguments in the dispatching process more complex.

There are some hybrid variations on the above two possibilities.  For instance, the selector argument could be evaluated.  If it were a generic function in the current environment, control would be given to its dispatcher.  If it were a simple selector, control would be given to its dispatcher.  This dispatcher could then redispatch the message to the a per-object or per-class selector, if any, or perform in some default fashion itself.  In this way, object and operator based dispatching could coexist.  However, it is necessary to decide, at some level, whether an operator based dispatcher can preempt a per object dispatcher, or vice versa.  That is to say, the architect has do decide who gets the first chance to dispatch the message.  One way or other, someone must get priority.  This perspective is consistent with the observation that whether objects own a table of the operators they subscribe to, or operators own a table of the classes to which they are specialized, what the dispatching process is really confronted with in any case is a (perhaps multidimensional) table that maps operators and operands to methods.

The current dispatcher can also be determined by the calling environment.  This approach makes it easier to alter the system's behavior to provide debugging and tracing behavior.

In the end the determination of the correct dispatcher should probably be made as the result of a sort of negotiation among all the parties to the current transaction.  These include the operator, all of the operands (including the one in the distinguished "receiver" position), the environment, and perhaps the message object itself.

An approach that reconciles a number of these positions might be to think of the dispatcher as an environmentally determined object, which in turn enters into negotiations with the other objects.  Participants would be queried according to some subsidiary protocol that gave them an opportunity to affect what happens.

An interesting possibility might be to provide the potential for wrapping methods belonging to a given object or class not at the dispatcher level, but as an artifact of their retrieval from the method repositories.  A CLOS-like model might be particularly suited to this sort of approach.  This notion was motivated by the CLOS applicable method enumeration scheme, and the per-method wrapping mechanisms of Messick and Beck.

In a system where most computation is carried out by message sending, the ability to alter the mechanisms by which message sending is carried out is potentially very powerful.

Namespace

First class environments can be used to define the set of temporary or global values that is accessible at a given time.  Namespace manipulation might be applied to conventional objects or environments to allow iteration over all named fields by debuggers or inspectors.

Control

Metalevel code in Superego has a view of all the objects that define the control history of all active processes.  These objects can be manipulated to construct control mechanisms such as catch and throw, and exception mechanisms.  [LaLonde & Van Gulik] describes a backtracking mechanism constructed using the reflective capabilities of Smalltalk-80 Contexts.

Issues

The search for a more powerful set of objects out of which to build reflective object-oriented languages can be seen in the context of a number of broader architectural issues.  These are:

Extensibility

Mutability

Uniformity

Regress

Utility

Efficiency

 

An extensible object-oriented language allows its users to add new features to the language, but prohibits the alteration of existing features.  A mutable object-oriented language allows changes to be made to existing features as well.  Languages such as C++ are said to be extensible, but not mutable.  Much of Smalltalk-80 is mutable, but certain parts of the system are off limits to user modification.  CLOS does not define the result of attempts to mutate standard metaobjects, but does not forbid this either.  One of the goals of this effort has been, and will continue to be, to explore the limits of mutability, both in terms of feasibility, and utility.

A related architectural issue is reflective uniformity.  To what degree can every object in the system be itself reflective?  To what extent is this desirable?  There a clearly limits on reflective uniformity, since towers that reach to infinity can be envisioned along several dimensions.  The issue of how regress is resolved can have a major impact on the simplicity, power, and efficiency of the resulting architecture. 

I've identified three distinct strategies for resolving regress:

Induction

Circularity

Reify on Demand

 

Inductive regress terminates with a base-case object for which additional regress is not possible.  This might be thought of as a second-class object, since it does not play by the same rules as other objects for the property in question.  Such base cases are often considered primitive.

Circularity, or Idempotence, can be used to resolve structural regress.  A default Class object might be though of as its own class, or a cycle of two or more objects as in the Smalltalk-80 Class/Metaclass relation might be defined.  Idempotence can also be used to justify inductive-base cases, by arguing, for instance, that a primitive behaves the same way for each case from here to infinity.

Reification-on-demand, or Lazy Reification, can be used where every object in the system has, by definition, an implicit relationship with a certain short of metaobject.  These relationships can be such that the object need not be explicitly reified until an explicit request to access or modify them is made.  Lazy reification can permit conceptually infinite towers of metaobjects to be made available on an as-needed basis.  3-KRS uses this strategy to provide per-instance metaobjects.  Reify-on-demand strategies can be used to deny users access to second-class objects, by dynamically interposing a first-object when access to a base-case object is attempted. 

A variation on the inductive and lazy strategies is to manipulate or control access to the mechanisms by which first or second-classness might be determined.

The final tests that reflective architectures must confront are those of utility and efficiency.  That is to say, are they good for anything, and what impact do they have on performance?  The question of utility is best addressed by demonstrating how a reflective architecture can address practical problems.   The architectural requirements we will address with the framework were selected in part to address this issue.  These are discussed below.

Reflection is not inimical to efficiency.  A number of techniques have been explored to make reflective code more efficient.  [Foote & Johnson 1989] examined how inline caches might be used to efficiently implement customized dispatching.  [Kiczales & Lamping 1992] showed how properly designed protocols might provide opportunities to partially evaluate and cache metalevel code.

Regress

In the course of preparing to execute a method, Superego is itself implicitly executing the code for the performers that define how this process works.  Should any of this code itself be non-cached (not built-in) Superego code, the system must undergo a classical reflective level shift.  This process is like 3-Lisp's original level shifting scheme.

When a Superego interpreter needs to execute Superego code, it should not, in general, do so in the context of the current computation.  Instead, a new Scene, representing the state of the previously implicit interpreter, must be reified.  Such Scene objects are created lazily, on demand.  The newly created scene object should provide an appropriate namespace and control state for the newly explicit interpreter.  The computational state it represents is that of the execution of the metalevel code that  is in turn executing on the behalf of the original program.

Care must be taken to ensure that a performer that does not  require another level of performance (who can play him or herself, as it were) is eventually located, or the tower of reified scenes will climb unchecked towards infinity. 

If a performer performing a script of his or her own life can be located, then there is no need for another level of performance, since the performer and the performance should be behaviorally indistinguishable.  However, when the performance diverges from biography, as a result of scripted requirements, another level of casting must be invoked.

To demonstrate 3-Lisp-style reflection, we added the reflect$ form to Superego.  This form accepts an expression script, along with objects that represent the running Superego kernel.  The semantics of this reflect$ form is defined using actual Superego code, rather that a primitive method.  In order for this to work, new objects to represent the kernel that is running the expression that can see the objects passed to the expression must themselves be created.  This level-shift resembles the shift that takes place when a Smalltalk-80 debugger is invoked, in some respects.  The user must see the state of the kernel running his or her code when a reflect$ form is executed, and not the state of the kernel that is running the reflect$ form's definition itself.

Of course, in object-oriented systems, forms like reflect$ are superseded by mechanisms that provide more direct access to metalevel objects.  For instance, in Smalltalk-80, access to contexts is provided via the thisContext pseudo-variable.  Superego uses a widely visible primitive method to provide the same function.  A running computation can gain access to class objects in Smalltalk-80 or CLOS by sending direct queries to individual instances of those classes. 

Because a well-designed object-oriented metalevel architecture will distribute functionality across a constellation of objects, the notions of reflection and metalevel themselves are less importation that the identities and roles of each distinct kind of metaobject in these architectures.  To implement introspection, normal messages are sent to metaobjects that in turn provide access to other metalevel objects.  To alter these objects, one merely manipulates them directly.

A useful way to think about the relationship between the Superego kernel and the definitions of the language at the next level is to think of the kernel as simply a cached, compiled version of the Superego definition.  Using this perspective, the initial, bootstrapping kernel is nothing more than a hand-compiled version of the language's definition.  The causal connection requirement here is enforced by the implementor, who's hand compiled code must match the intended behavior of the defining code.

This caching philosophy also permits the kernel to pre-cache certain lookups.  For instance, when the kernel detects that it is being asked to send a message to an object it knows the identity of, it can retain a table of common methods, and skip the lookup.  This scheme permits the issue of regress in dispatching to be dealt with without compromising the conceptual reflectivity of the kernel.  Hence, reflective uniformity can be retained, and the kernel need not be treated (conceptually) as a special case.

Requirements

The following requirements will be used to drive the evolution of the framework, and will also demonstrate its utility:

     A unified dispatching model that can support Smalltalk-80, CLOS, and aspects of ABCL/R

     Object composition and dynamic aggregate support

     Automatic future generation

     Reusable variable-level constraint support

     Distributed object beachhead or stub code

     Customized exception code

The most demanding requirement is the first one.  It requires a mechanism with the power of the CLOS method combination scheme, along with the per-instance and per-class specialization capabilities discussed in [Foote & Johnson 1989].  This, in turn, requires that any refactoring of class responsibilities retain the specialization responsibilities of CLOS classes (as well as EQL-specializers) in some recognizable form.

Effective dynamic per-instance control of dispatch mechanisms should enable the construction of reusable mechanisms for dynamically composing objects.  One way to implement dynamic composition would be to provide a mechanism that allows the user to stipulate that all messages belonging to a given set of messages, or signature, should be forwarded to a given object.  An explicit notion of signature or protocol will have to be provided to implement such a mechanism.  Since individual objects may override their dispatching code in Superego, composite objects can exploit this mechanism to introduce tests for memberships in such message sets.  The inline caching schemes discussed in [Foote & Johnson 1989] might be extended to save and verify the identities of the targets for such forwarded sends.

It should be relatively easy to combine the Future objects of [Foote & Johnson 1989] with metalevel code to turn most any message send into a future-based computation.  Such a mechanism could customize the semantics for send$ forms to force the generation of a future object.

Constraints effectively change the semantics of assignment on a dynamic, variable by variable basis.  First-class Variable objects could themselves be customized to permit dynamic, user-specified functions to determine how variables may change, and to what other places in the system changes might propagate.  Such augmented variables could be dynamically introduced on a per-class or per-instance basis.

State level code also provides a convenient locus for dealing with stub code for distributed objects.  Proxies might also be built using the dispatching mechanisms.

The Smalltalk-80-style access to context objects in Superego should make the construction of exception mechanisms relatively easy.  Since Scene and Performance objects explicitly record a process's activation history, mechanisms to unwind them can be constructed directly.  These objects could be augmented with tags to designate where a stack frame should be unwound to.  The metalevel implementation for the return$ forms itself might be treated as a default special case of such a mechanism.

CONCLUSION

Just as objects are good for building applications, so too are they good for building programming languages.  A programming language with an reflective object-oriented metalevel architecture is one that is itself built out of first-class objects.  These objects are subject to extension and dynamic manipulation, just as normal objects are.  As a result, such a language is easy to modify and extend. 

Smalltalk-80 has a powerful set of reflective facilities.  However, the Smalltalk Virtual Machine stands as a barrier below which programmers may not reach.  We have identified a number useful facilities that a system with no such barriers might provide.  These have been documented in detail in [Foote & Johnson 1989].  CLOS and ABCL/R both exhibit reflective facilities not found in Smalltalk.  However, no single one of these languages can be said to have a full compliment of reflective facilities. 

A good way to find a set of objects suited to a given domain is to build an object-oriented framework.  Reusable frameworks emerge not as the result of any front-loaded design methodology, but from an evolutionary process that unfolds as successive application requirements are confronted.

To build a framework, one must start with a prototype.  We have constructed three:  Id, Ego, and Superego.  Superego demonstrates a viable reflective metalevel-architecture for a simple object-oriented language, and will provide a foundation for demonstrating the power and versatility of this architectural approach. 

To demonstrate this power, the framework must be further stressed to force it to evolve.  We have identified a set of requirements to do this.

The products of this enterprise will be a set of objects, along with a set of observations and conclusions about the architectural and methodological issues that this effort raises.


REFERENCES

 

[Abelson & Sussman 1985]

        Harold Abelson and Gerald Jay Sussman

        with Julie Susmann

        Structure and Interpretation of Computer

        Programs

        MIT Press, Cambridge, Mass.

        McGraw-Hill, New York, 1985

 

[Agha 1986]

        Gul Agha

        ACTORS:  A Model of Concurrent Computation

        in Distributed Systems

        MIT Press, 1986

 

[Bawden 1988]

        Alan Bawden

        Reification without Evaluation

        Proc. Symposium on Lisp and Functional

        Programming, 1988

        pages 342-248

 

[Bennett 1987]

        John K. Bennett

        The Design and Implementation of

        Distributed Smalltalk

        OOPSLA '87 Proceedings

        Orlando, FL, October 4-8 1977 pages 118-330

 

[Bobrow et. al. 1988]

        D. G. Bobrow, L. G. DeMichiel, R. P. Gabriel,

        S. E. Keene, G. Kiczales, and D. A. Moon

        Common Lisp Object System Specification

        X3J13 Document 88-002R

        SIGPLAN Notices, Volume 23,

        Special Issue, September 1988

 

[Bobrow & Kiczales 1988]

        Daniel G. Bobrow and Gregor Kiczales

        The Common Lisp Object System

        Metaobject Kernel -- A Status Report

        Proceedings of the 1988 Conference on Lisp

        and Functional Programming

 

[Borning 1979]

        Alan Borning

        ThingLab -- A Constraint Oriented

        Simulation Laboratory

        Technical Report No. SSL-79-3

        Xerox Palo Alto Research Center

        July 1979

 

[Borning & Ingalls 1982]

        A. H. Borning and D. H. H. Ingalls

        A Type Declaration and Inference System

        for Smalltalk

        9th POPL, 1982, pages 133-141

 

[Borning & O'Shea 1986]

        A. Borning and T. O'Shea

        DeltaTalk:  An Empirically and

        Aesthetically Motivated Simplification

        of the Smalltalk-80 Language

        (unpublished) 1986

 

[Borning 1986]

        Alan Borning

        Classes versus Prototypes in

        Object-Oriented Languages

        Proceedings of the ACM/IEEE

        Fall Joint Computer Conference

        Dallas, TX, November 1986, pages 36-40

 

[Briot 1989]

        Jean-Pierre Briot

        Actalk:  A Testbed for Classifying and

        Designing Actor Languages in the

        Smalltalk-80 Environment

        LITP 89-33 RXF, Rank Xerox

        ECOOP '89

 

[Chambers, Ungar & Lee 1989]

        Craig Chambers, David Ungar and Elgin Lee

        An Efficient Implementation of SELF

        a Dynamically-Typed Object-Oriented

        Language Based on Prototypes

        OOPSLA '89 Proceedings

        New Orleans, LA

        October 1-6 1989, pages 49-70

 

[Church 1941]

        Alonzo Church

        The Calculi of Lambda-Conversion

        Annals of Mathematical Studies, Number 6

        Princeton University Press

        Princeton, NJ, 1941

 

[Cointe 1987]

        Pierre Cointe

        Metaclasses are First Class:

        The ObjVlisp Model

        OOPSLA '87 Proceedings

        Orlando, FL, October 4-8 1977, pages 156-167

 

[Danvy & Malmkjaer 1988]

        Oliver Danvy and Karoline Malmkjaer

        Intensions and Extensions in a

        ReflectiveTower

        1988 ACM Conference on Lisp and Functional

        Programming, Snowbird, UT, July 1988

        pages 327-341

 

[des Rivieres & Smith 1984]

        Jim des Rivieres and Brian Cantwell Smith

        The Implementation of Procedurally

        Reflective Languages

        Proc. of the 1984 ACM Symposium

        on Lisp and Functional Programming

        August, 1984, pages 331-347

 

[des Rivieres 1988]

        Jim des Rivieres

        Control-Related Meta-Level Facilities in Lisp

        in Meta-Level Architectures and Reflection

        P. Maes and D. Nardi, editors

        Elsevier Science Publishers

        B. V. North-Holland, 1988, pages 101-110

 

[Deutsch 1983]

        L. Peter Deutsch

        Reusability in the Smalltalk-80

        Programming System

        ITT Proceedings of the Workshop on Reusability

        in Programming, 1983, pages 72-76

        (reprinted in Tutorial on Software Reusability,

        IEEE Computer Society Press, 1987)

 

[Deutsch & Schiffman 1984]

        L. Peter Deutsch and Allan M. Schiffman

        Efficient Implementation of the

        Smalltalk-80 System

        Proceedings of the Tenth Annual

        ACM Symposium

        on Principles of Programming Languages,

        1983, pages 297-302

 

[Drescher 1985]

        G. L. Dresher

        The ObjectLISP USER Manual (preliminary)

        Cambridge:  LMI Corporation

 

[Ellis & Stroustrup 1990]

        Margaret A. Ellis and Bjarne Stroustrup

        The Annotated C++ Reference Manual

        Addison-Wesley, Reading, MA, 1990

 

[Ferber 1989]

        Jacques Ferber

        Computational Reflection in Class-Based

        Object-Oriented Languages

        OOPSLA '89 Proceedings

        New Orleans, LA

        October 1-6 1989, pages 317-326

 

[Foote 1988a]

        Brian Foote

        Designing to Facilitate Change with

        Object-Oriented Frameworks

        Masters Thesis, 1988

        Department of Computer Science

        University of Illinois at Urbana-Champaign

 

[Foote 1988b]

        Brian Foote

        Domain Specific Frameworks Emerge as

        a System Evolves

        OOPSLA '88 Workshop on Methodologies

        and Object-Oriented Programming

        San Diego, CA

        Norman L. Kerth, organizer

 

[Foote 1988c]

        Brian Foote

        Designing Reusable Realtime Frameworks

        OOPSLA '88 Workshop on

        Realtime Systems

        San Diego, CA

        John Gilbert, organizer

 

[Foote 1989a]

        Brian Foote

        The Craftsmen vs. the Scavengers:

        The Ruminations of a Foot Soldier

        on the Reuse Revolution

        OOPSLA '89 Workshop on the

        Reusable Component Marketplace

        New Orleans, LA

        John T. Mason, organizer

 

[Foote 1989b]

        Brian Foote

        Reflective Facilities in Smalltalk-80

        Spring 1989 MAPLAS Presentation

        University of Wisconsin, Madison

 

[Foote & Johnson 1989]

        Brian Foote and Ralph E. Johnson

        Reflective Facilities in Smalltalk-80

        OOPSLA '89 Proceedings

        New Orleans, LA

        October 1-6 1989, pages 327-335

 

[Foote 1990]

        Brian Foote

        Object-Oriented Reflective Metalevel

        Architectures:  Pyrite or Panacea?

        OOPSLA/ECOOP '90 Workshop on

        Reflection and Metalevel Architectures

        Mamdouh Ibrahim, Brian Foote,

        Jean-Pierre Briot, Gregor Kiczales,

        Satoshi Matsuoka, and Takuo Watanabe,

        organizers

 

[Foote 1991a]

        Brian Foote

        Flexible Foundations and Movable Walls

        OOPSLA '91 Workshop on

        Reflection and Metalevel Architectures

        Phoenix, AZ

        Mamdouh Ibrahim, Brian Foote,

        Pierre Cointe, Gregor Kiczales,

        Satoshi Matsuoka, and Takuo Watanabe,

        organizers

 

[Foote 1991b]

        Brian Foote

        A Fractal Model of the Lifecyle

        of Reusable Objects

        OOPSLA '91 Workshop on Reuse

        Ottawa, Ontario, Canada

        Rebecca Joos and John D. McGregor,

        organizers

 

[Foote 1992a]

        Brian Foote

        Objects, Reflection, and Open Languages

        ECOOP '92 Workshop on Object-Oriented

        Reflection and Metalevel Architectures

        Utrecht, The Netherlands

        Brian Foote, chair

        Satoshi Matsuoka, Pierre Cointe, organizers

        Mamdouh Ibrahim, Gregor Kiczales, advisors

 

[Foote 1992b]

        Brian Foote

        Living Languages

        OOPSLA '92 Workshop on Progamming

        Languages:  The Next Generation

        Vancouver, British Columbia, Canada

        Mamdouh Ibrahim, chair

 

[Foote 1992c]

        Objects, Reflection, and Open Languages

        (abstract)

        IMSA 1992 Workshop on Reflection and

        Metalevel Architectures

        Tokyo, Japan

        Akinori Yonezawa and Brian C. Smith, editors

 

[Foote 1993a]

        Brian Foote

        A Fractal Model of the Lifecyle

        of Reusable Objects

        (abstract)

        OOPSLA '93 Workshop on Process

        Standards and Iteration

        Washington, DC

        Jim Coplein, Russel Winder, and

        Susan Hutz, organizers

 

[Foote 1993b]

        Architectural Balkanization in the

        Post-Linguistic Era

        OOPSLA '93 Workshop on Object-Oriented

        Reflection and Metalevel Architectures

        Washington, DC

        Brian Foote, chair

        Pierre Cointe, Dan Friedman, Jacques Malenfant,

        Dave Thomas, and Yasuhiko Yokote, organizers

 

[Friedman & Wand 1984]

        D. P. Friedman and M. Wand

        Reflection without Metaphysics

        Proc. Symposium on Lisp and Functional

        Programming, pages 348-355, August 1984

 

[Goldberg & Kay 1976]

        Adele Goldberg and Alan Kay, editors

        with the Learning Research Group

        Smalltalk-72 Instruction Manual

        Xerox Palo Alto Research Center

 

[Goldberg & Robson 1983]

        Adele Goldberg and David Robson

        Smalltalk-80:  The Language and

        its Implementation

        Addison-Wesley, Reading, MA, 1983

 

[Goldberg 1984]

        Adele Goldberg

        Smalltalk-80:  The Interactive

        Programming Environment

        Addison-Wesley, Reading, MA, 1984

 

[Halstead 1985]

        Robert H. Halstead, Jr.

        MultiLISP:  A language for Concurrent

        Symbolic Computation

        ACM Transactions on Programming Languages

        and Systems

        Volume 7,. Number 4

        October 1985, pages 501-538

 

[Hewitt & de Jong 1983]

        Carl Hewitt and Peter de Jong

        Analyzing the Role of Description and Actions

        in Open Systems

        AAAI '83, pages 162-167

 

[Hoeltze, Chang, Chambers & Ungar 1990]

        Urs Hoeltze, Bay-Wei Chang,

        Craig Chambers, and David Ungar

        The Self Papers, and the Self Manual

        (unpublished)

 

[Ibrahim & Cummins 1988]

        Mamdouh H. Ibrahim and Fred A. Cummins

        KSL:   A Reflective Object-Oriented

        Programming Language

        Proceedings of the International

        Conference on Computer Languages

        Miami, FL, October 9-13 1988

 

[Ingalls 1978]

        Daniel H. H. Ingalls

        The Smalltalk-76 Programming System

        Design and Implementation

        5th ACM Symposium on POPL, pages 9-15

        Tucson, AZ, USA, January 1978

 

[Ingalls 1981]

        Daniel H. H. Ingalls

        Design Principles Behind Smalltalk

        Byte, Volume 6, Number 8, August 1981

 

[Ingalls 1983]

        Daniel H. H. Ingalls

        The Evolution of the Smalltalk-80 Virtual

        Machine

        in Smalltalk 80:  Bits of History,

        Words of Advice

        Glenn Krasner, editor

        Addison-Wesley, Reading, MA

        1983

 

[Jefferson 1985]

        David. R. Jefferson

        Virtual Time

        ACM Transactions on Programming

        Langauges and Systems

        Volume 7, Number 3, pages 404-425, July 1985

 

[Johnson & Foote 1988]

        Ralph E. Johnson and Brian Foote

        Designing Reusable Classes

        Journal of Object-Oriented Programming

        Volume 1, Number 2, June/July 1988

        pages 22-35

 

[Johnson, Graver & Zurawski 1988]

        Ralph E. Johnson, Justin O. Graver, and

        Laurance W. Zurawski

        TS:  An Optimizing Compiler for Smalltalk

        OOPSLA '88 Proceedings

        San Diego, CA, September 25-30, 1988

        pages 18-26

 

[Kaiser & Garlan 1987]

        Gail E. Kaiser and David Garlan

        Melding Software Systems f

        rom Reusable Building Blocks

        IEEE Software, Volume 4 Number 4

        July 1987 pages 17-24

 

[Keene 1989]

        Sonya E. Keene

        Object-Oriented Programming in Common Lisp

        A Programmer's Introduction to CLOS

        Addison-Wesley, 1989

 

[Kempf, Harris, D'Souza & Snyer]

        James Kempf, Warren Harris, Roy D'Souza,

        and Alan Snyder

        Hewlett-Packard Laboratories

        Experience with CommonLoops

        OOPSLA '87 Proceedings

        Orlando, FL, October 4-8 1977, pages 214-226

 

[Kiczales & Rodriguez 1990]

        Gregor Kiczales and Luis Rodriguez

        Efficient Method Dispatch in PCL

        Proceedings of the 1990 ACM Conference

        on Lisp and Functional Programming

        Nice, France, June 1990, pages 99-105

 

[Kiczales, des Rivieres & Bobrow 1991]

        Gregor Kiczales, Jim des Rivieres,

        and Daniel G. Bobrow

        The Art of the Metaobject Protocol

        MIT Press, 1991

 

[Kiczales & Lamping 1992]

        Gregor Kiczales and John Lamping

        Issues in the Design and Implementation

        of Class Libraries

        OOPSLA '92, Vancouver, BC

        Sigplan Notices, Volume 27, Number 10

        October 1992

 

[Kim & Lochovsky 1989]

        Won Kim and Frederick H. Lochovsky, editors

        Object-Oriented Concepts, Databases,

        and Applications

        Addison-Wesley, Cambridge, MA, 1989

 

[Krasner 1983]

        Glenn Krasner, editor

        Smalltalk 80:  Bits of History,

        Words of Advice

        Addison-Wesley, Reading, MA

        1983

 

[LaLonde, Thomas & Pugh 1986]

        Wilf R. LaLonde, Dave A. Thomas

        and John R. Pugh

        An Exemplar Based Smalltalk

        OOPSLA '86 Proceedings

        Portland, OR, October 4-8 1977 pages 322-330

 

[LaLonde & Van Gulik 1988]

        Wilf R. LaLonde and Mark Van Gulik

        Building a  Backtracking Facility in Smalltalk

        Without Kernel Support

        OOPSLA '88 Proceedings

        San Diego, CA, September 25-30, 1988

        pages 105-122

 

[Lieberman 1986]

        Henry Lieberman

        Using Protypical Objects to Implement

        Shared Behavior

        in Object-Oriented Systems

        OOPSLA '86 Proceedings

        Portland, OR, October 4-8 1977 pages 214-223

 

[Lieberman, Stein & Ungar 1988]

        Henry Lieberman, Lynn A. Stein,

        and David Ungar

        Treaty of Orlando

        Special OOPSLA '87 Addendum to

        the Proceedings

        SIGPLAN Notices, May 1988

        Volume 23, Number 5

 

[Lindsey & van der Muelen 1973]

        C. H. Lindsey and S.G van der Muelen

        Informal Introduction to ALGOL 68

        North-Holland Publishing Co., Amsterdam

        American Elsevier Publishing Co., NY, 1973

 

[Maes 1987a]

        Pattie Maes

        Computational Reflection

        Artificial Intelligence Laboratory

        Vrije Universiteit Brussel

        Technical Report 87-2

 

[Maes 1987b]

        Pattie Maes

        Concepts and Experiments in

        Computational Reflection

        OOPSLA '87 Proceedings

        Orlando, FL, October 4-8 1977 pages 147-155

 

[Maes & Nardi 1988]

        Pattie Maes and Daniele Nardi, editors

        Meta-Level Architectures and Reflection

        Elsevier Science Publishers

        B. V. North-Holland, 1988

 

[McCarthy 1960]

        John McCarthy

        Recursive Functions of Symbolic Expressions

        and their Computation by Machine, part 1

        Communiations of the ACM

        Volume 3, Number 4, pages 184-185

 

[McCarthy et. al. 1962]

        John McCarthy, Paul W. Abrahams,

        Daniel J. Edwards, Timothy P. Hart,

        and Michael I. Levin

        Lisp 1.5 Programmer's Manual

        MIT Press, Cambridge, MA, 1962

 

[McCarthy 1978]

        John McCarthy

        History of Lisp

        ACM SIGPLAN History of Programming

        Languages Conference

        Los Angeles, CA  June 1-3 1978

        pages 217-223

 

[McCullough 1987]

        Paul L. McCullough

        Transparent Forwarding:  First Steps

        OOPSLA '87 Proceedings

        Orlando, FL, October 4-8 1987 pages 331-341

 

[Messick & Beck 1985]

        Steven L. Messick and Kent L. Beck

        Active Variables in Smalltalk-80

        Technical Report CR-85-09

        Computer Research Lab, Tektronix, Inc., 1985

 

[Paepcke 1990]

        Andreas Paepcke

        PCLOS:  Stress Testing CLOS

        OOPSLA/ECOOP  '90 Proceedings

        Ottawa, Ontario, Canada

        October 21-25, 1990 pages 194-221

 

[Pascoe 1986]

        Geoffrey A. Pascoe

        Encapsulators:  A New Software

        Paradigm in Smalltalk-80

        OOPSLA '86 Proceedings

        Portland, OR, September 29-October 2 1986,

        pages 341-346

 

[Smith 1982]

        Brian Cantwell Smith

        Reflection and Semantics in a

        Procedural Programming Language

        Ph. D. Thesis, MIT

        MIT/LCS/TR-272

 

[Smith 1984]

        Brian Cantwell Smith

        Reflection and Semantics in Lisp

        Proceedings of the 1984 ACM

        Principles of Programming Languages

        Conference

        pages 23-35

 

[Smith & des Rivieres 1984]

        Brian Cantwell Smith and Jim des Rivieres

        Interim 3-LISP Reference Manual

        Xerox Intelligent Systems Laboratory ISL-1

        Xerox Palo Alto Research Center

        June 1984

 

[Smith 1987]

        Randall B. Smith

        Experiences with the Alternate Reality Kit:

        An Example of the Tension Between Literalism

        and Magic.

        CHI+GI  1987 Conference Proceedings

 

[Steele & Sussmann 1976]

        Guy Lewis Steele Jr. and Gerald Jay Sussman

        Lambda:  The Ultimate Imperative

        MIT AI Memo 353

        March 10, 1976

 

[Steele 1976]

        Guy Lewis Steele Jr.

        Lambda:  The Ultimate Declarative

        MIT AI Memo 379

        November 1976

 

[Steele 1977]

        Guy Lewis Steele Jr.

        Debunking the "Expensive Procedure Call"

        Myth or,

        Procedure Call Implementations Considered

        Harmful, or Lambda:  The Ultimate GOTO

        MIT AI Memo 443

        October 1977

 

[Steele 1984]

        Guy L. Steele Jr.

        Common Lisp:  The Language

        Digital Press, 1984

 

[Steele 1990]

        Guy L. Steele Jr.

        Common Lisp:  The Language

        Second Edition

        Digital Press, 1990

 

[Stefik & Bobrow 1986]

        Mark Stefik and Daniel G. Bobrow

        Object-Oriented Programming: 

        Themes and Variations

        AI Magazine 6(4):  40-62, Winter, 1986

 

[Stefik, Bobrow & Kahn 1986]

        M. Stefik, D. Bobrow and K. Kahn

        Integrating Access-Oriented Programming into

        a Multiprogramming Environment

        IEEE Software, 3, 1 (January 1986), pages 10-18

 

[Stein 1987]

        Lynn Andea Stein

        Delegation is Inhertance

        OOPSLA '87 Proceedings

        Orlando, FL, October 4-8 1977 pages 138-146

 

[Stein, Lieberman & Ungar 1989]

        Lynn Andea Stein, Henry Lieberman,

        and David Ungar

        A Shared View of Sharing:

        The Treaty of Orlando

        in Object-Oriented Concepts, Databases,

        and Applications

        Won Kim and Frederick H. Lochovsky, editors

        Addison-Wesley, Reading, MA, 1989

 

[Stroustrup 1986]

        Bjarne Stroustrup

        The C++ Programming Language

        Addison-Wesley, Reading, MA, 1986

 

[Stroustrup 1991]

        Bjarne Stroustrup

        The C++ Programming Language

        Second Edition

        Addison-Wesley, Reading, MA, 1991

 

[Sussmann & Steele 1978]

        Guy Lewis Steele Jr. and Gerald Jay Sussman

        The Art of the Interpreter, or

        The Modularity Complex

        (Parts Zero, One, and Two)

        MIT AI Memo 453

        May 1978

 

[Tiemann 1988]

        Michael D. Tiemann

        Solving the RPC problem in GNU C++

        1988 USENIX C++ Conference

        Denver, CO, October 17-21 1988

 

[Ungar & Smith 1987]

        David Ungar and Randall B. Smith

        Self:  The Power of Simplicity

        OOPSLA '87 Proceedings

        Orlando, FL, October 4-8 1977, pages 227-242

 

[van Wijngaarden et. al. 1976]

        A. van Wijngaarden, B. J. Mailoux,

        J. E. L. Peck, C. H. A. Koster,

        M. Sintzoff, C. H. Lindsey,

        L. G. L. T. Meertens and R. J. Fisker

        Springer-Verlag, Berlin, Heidelberg, New York

        1976

 

[Yokote & Tokoro 1986]

        Yasuhiko Yokote and Mario Tokoro

        The Design and Implementation of

        ConcurrentSmalltalk

        OOPSLA '86 Proceedings

        Portland, OR, September 29-October 2 1986

        pages 331-340

 

[Wand & Friedman 1986]

        Mitchell Wand and Daniel P. Friedman

        The Mystery of the Tower Revealed:

        A Non-Reflective Description of

        the Reflective Tower

        ACM Conference on

        Lisp and Functional Programming

        Boston, MA, August 1986

 

[Watanabe & Yonezawa 1988]

        Takuo Watanabe and Akinori Yonezawa

        Reflection in an Object-Oriented Concurrent

        Language

        OOPSLA '88 Proceedings

        San Diego, CA, September 25-30, 1988

        pages 306-315

 

[Yonezawa 1989]

        Akinori Yonezawa, editor

        ABCL:  An Object-Oriented

        Concurrent System

        MIT Press, Cambridge, MA

        1989

 

 



[1]Both investigations involved porting these systems to Macintosh Common Lisp.

[2]This, in turn, resembles the notion of orthogonality found in the Revised Report on Algol 68 [van Wijngaarden et. al. 1976]:  "The number of independent primitive concepts has been minimized in order that the language be easy to describe, to learn, and to implement.  On the other hand, these concepts have been applied"orthogonally" in order to maximize the expressive power of the language while trying to aviod deleterious superfluities.

 

[3]The United States Commerce Department defines durable goods as those that are designed to last for more than three years.  In this context, a durable object would be one whose code was still itself subject to modification, adaptation, and evolution for at least three years, rather than one that was merely part of an executable program which was still in use after three years.

[4]Because of the self-similarity this pattern exhibits across levels in a system, from individual classes, up through abstract classes and frameworks, and across individual applications, I refer to this lifecycle perspective as the Fractal Model (by analogy with Boehm's Sprial Model).

[5]Multiple parents are possible, though as with Smalltalk, multiple inheritance is not well supported.