Annotated Bibliography
of Related Work

The following bibliography lists some related material. We have divided the entries into various sub-categories, although the division is inherently imprecise. Many citations could reasonably have been placed in multiple groups.

It should be stressed that this is, at best, only a partial bibliography of related work. There is a great deal more material to explore. This list was chosen to be representative, not exhaustive.

A Sampler

These references represent an initial core of related reading, some related directly to the material in this book, and others showing a history of software engineering notions that ultimately gave rise to open implementations.

Dijkstra's levels of abstraction and Parnas's information hiding notions are early and very influential attempts at managing the complexity of software. These ideas play a large role in the informal notion of black-box abstraction. CLU, for example, was a language firmly based on these ideas. Similarly, the ISO reference model for open systems interconnection took a clearly layered approach which has dominated thinking in the network community:

Edsger W. Dijkstra. The structure of the THE-multiprogramming system. Communications of the ACM, 11(5):341-346, May 1968.

D. L. Parnas. On the criteria to be used in decomposing systems into modules. Communications of the ACM, 15(12):1053-1058, December 1972.

B. Liskov, A. Snyder, R. Atkinson, and C. Schaffert. Abstraction mechanisms in CLU. In Programming languages: A grand tour. Computer Science Press, Rockville, MD, USA, 1983.

International Organization for Standardization. Basic reference model for open systems interconnection, 1984.

Niklaus Wirth. On the Design of Programming Languages, pages 386-393. 1974.

The concept of reflection was first put forth explicitly by Smith, in a long PhD thesis, and was summarized in a shorter paper. Subsequently, the concept of the reflective tower received a great deal of attention from other researchers.

Brian Cantwell Smith. Reflection and semantics in a procedural language. LCS Technical Report TR-272, M.I.T., Cambridge, MA, 1982.

Brian Cantwell Smith. Reflection and semantics in Lisp. In Proceedings of the 1984 ACM Principles of Programming Language Conference, pages 23-35. ACM, Dec 1984.

Mitchell Wand and Daniel P. Friedman. The mystery of the tower revealed: A non-reflective description of the reflective tower. In Pattie Maes and Daniele Nardi, editors, Meta-Level Architectures and Reflection, pages 111-134. North-Holland, 1988.

Smalltalk was the first major language to have an explicit meta-level representation of programs.

Adele Goldberg and Dave Robson. Smalltalk-80: The Language and its Implementation. Addison-Wesley, Reading, MA, 1983.

Brian Foote and Ralph E. Johnson. Reflective facilities in Smalltalk-80. In Proceedings of the ACM Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA), SIGPLAN Notices, 24(10), pages 327-335, October 1989.

The following book presents a general overview of metaobject protocols. A number of other references are included in the sections further down:

Gregor Kiczales, Jim des Rivières, and Daniel G. Bobrow. The Art of the Metaobject Protocol . MIT Press, 1991.

The broader notion of open implementations is discussed in the following:

Gregor Kiczales. Towards a new model of abstraction in software engineering. Proceedings of the International Workshop on Reflection and Meta-Level Architecture, November 1992.

Gregor Kiczales. Why are Black Boxes so Hard to Reuse? (Towards a New Model of Abstraction in the Engineering of Software) Invited Talk at OOPSLA'94

These papers provide early glimpses of the motivations underlying open implementations, particularly the need to open the implementation for application-specific performance optimization. The third paper, by Clark and Tennenhouse is newer, and provides the motivation for the open implementations response to the OSI network model. The forth one addresses a distinction between ``hints that disclose'' and ``hints that advise'' in the file system.

R. Levin, E. Cohen, W. Corwin, F. Pollack, and W. Wulf. Policy/mechanism separation in hydra. In Proceedings of The Fifth Symposium on Operating Systems Principles, pages 132-140. SIGOPS and ACM, Association for Computing Machinery, 1975.

Mary Shaw and Wm. A. Wulf. Towards relaxing assumptions in languages and their implementations. SIGPLAN Notices, 15(3), 1980.

David D. Clark and David L. Tennenhouse. Architectural considerations for a new generation of protocols. In Proceedings of the ACM Symposium on Communications Architectures and Protocols, pages 200-208, September 1990.

R. Hugo Patterson et al. A status report on research in transparent informed prefetching. ACM Operating Systems Review. 27(2):21-34, April 1993.

Guy L. Steele Jr. High performance fortran: Status report. ACM SIGPlan Notices, 28(1), January 1993.

The remaining sections of references provide broader sets of pointers to particular relevant areas.

Theoretical and Other Basic Issues in Reflection

Alan Bawden. Reification without Evaluation. In Proceedings of the ACM Conference on LISP and Functional Programming, pages 342-351. ACM, 1988.

Olivier Danvy and Karoline Malmkjær. Intentions and extensions in a reflective tower. In Proceedings of the ACM Conference on LISP and Functional Programming, pages 327-341. ACM, 1988.

Konstantin Läufer and Mantin Odersky. Reflection in type systems. In Proceedings of the OOPSLA Workshop on Reflection and Metalevel Architectures in Object-Oriented Programming, 1991.

P. Maes and D. Nardi, editors. Meta-Level Architectures and Reflection. North Holland, 1988.

Shin Nakajima. What makes a language reflective and how? (preliminary results). In Proceedings of the International Workshop on Reflection and Meta-Level Architecture, 1992.

How to simulate the infinite reflective tower with as few actual levels as possible:

Jim des Rivières and Brian Cantwell Smith. The implementation of procedurally reflective languages. In Proceedings of the ACM Conference on LISP and Functional Programming, pages 331-347. ACM, 1984.

Metaobject Protocols in Languages

Reflection is well suited for structuring object-oriented programs, and object-oriented programming works well for organizing reflective structures. The following are examples of reflective object-oriented languages.

D.G. Bobrow, K. Kahn, G. Kiczales, L. Masinter, M. Stefik, and F. Zdybel. Commonloops: Merging Lisp and object-oriented programming. In Proceedings of the ACM Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA). ACM, Nov 1986.

H. Bretthauer and J. Kopp. The Meta-Class-System MCS. A Portable Object System for Common Lisp. Arbeitspapiere der GMD 554, Gesellschaft für Mathematik und Datenverarbeitung (GMD), Sankt Augustin, July 1991.

Frank Buschmann, Konrad Kiefer, Frances Paulisch, and Michael Stal. The meta-information-protocol, run-time type information for C++. In Brian C. Smith Akinori Yonezawa, editor, Proceedings of the International Workshop on New Models for Software Architecture '92; Reflection and Meta-Level Architecture, pages 82-87, 1992.

Pierre Cointe. The ObjVlisp kernel: A reflexive Lisp architecture to define a uniform object-oriented system. In Pattie Maes and Daniele Nardi, editors, Meta-Level Architectures and Reflection, pages 155-176. North-Holland, 1987.

Pierre Cointe. Metaclasses are first class: The ObjVlisp model. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), Orlando, FL, pages 156-167, 1987.

Jacques Ferber. Computational reflection in class based object oriented languages. In Proceedings of the ACM Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA), SIGPLAN Notices 24(10), pages 317-326. ACM, October 1989.

Mamdouh H. Ibrahim and Fred A. Cummins. KSL: A Reflective Object-Oriented Programming Language. in Proceedings of the IEEE International Conference on Computer Languages, pages 186-193, 1988.

Peter Madany, Panos Kougiouris, Nayeem Islam, and Roy H. Campbell. Practical examples of reification and reflection in C++. In Proceedings of the International Workshop on New Models for Software Architecture '92; Reflection and Meta-Level Architecture, 1992.

Pattie Maes. Concepts and experiments in computational reflection. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), pages 147-155, 1987.

J. Malenfant, P. Cointe, and C. Dony. Reflection in prototype-based object-oriented programming languages. In Proceedings of the OOPSLA Workshop on Reflection and Metalevel Architectures in Object-Oriented Programming, 1991.

Part II of the following book deals with various aspects of metaobject protocols for languages, with a particular focus on the CLOS MOP. Other parts of the book provide good information about CLOS for readers who want to study its MOP in more detail.

Andreas Paepcke, editor. Object-Oriented Programming - The CLOS Perspective. MIT Press, 1993.

The following are major languages that include some sort of MOP:

Daniel G. Bobrow, Linda G. DeMichiel, Richard P. Gabriel, Sonya Keene, Gregor Kiczales, and David A. Moon. Common Lisp Object System Specification. Technical Report 88-002R, X3J13 Standards Committee, 1988. (Also published in SIGPLAN Notices, Vol. 23, special issue, Sept. 1988, and in Guy Steele: Common Lisp, The Language, 2nd ed., Digital Press, 1990.).

Harry Bretthauer, Harley Davis, Jurgen Kopp, and Keith Playford. Balancing the EuLisp metaobject protocol. In Proceedings of the International Workshop on Reflection and Meta-Level Architecture, 1992.

Apple Computer, 1 Main Street, Cambridge, MA 02142. Dylan: an Object-Oriented Dynamic Language, 1992.

The EuLisp Definition, April 1992. Draft.

J. Malenfant, C. Dony, and P. Cointe. Behavioral reflection in a prototype-based language. In Proceedings of the International Workshop on Reflection and Meta-Level Architecture, 1992.

Experiments With Meta-Architectures

A prevalent theme of research in the reflection community has to do with alternative meta-level architectures. The simple ``classes are the metaobjects'' structure presented in this book is not always the most useful one, particularly in distributed computing applications.

Jacques Ferber. Conceptual reflection and actor language. In Pattie Maes and Daniele Nardi, editors, Meta-Level Architectures and Reflection, pages 177-193. North-Holland, 1988.

Satoshi Matsuoka and Takuo Watanabe and Akinori Yonezawa. Hybrid Group Reflective Architecture for Object-Oriented Concurrent Reflective Programming. In Proceedings of the European Conference on Object Oriented Programming, pages 231-250, 1991.

Hideaki Okamura, Yutaka Ishikawa, and Mario Tokoro. Metalevel decomposition in AL-1/D. In Nishio and Yonezawa, editors, Proceedings of the International Symposium on Object Technologies for Advanced Software, volume 742 of LNCS. Springer-Verlag, 1993.

Hiroyasu Sugano. Modeling group reflection in a simple concurrent constraint language. In Proceedings of the OOPSLA Workshop on Reflection and Metalevel Architectures in Object-Oriented Programming, 1991.

Takuo Watanabe and Akinori Yonezawa. Reflection in an Object-Oriented Concurrent Language. In Proceedings of the Conference on Object-Oriented Programming: Systems, Languages, and Applications, pages 306-315, 1988.

Yasuhiko Yokote. The new mechanism for object-oriented system programming. In Proceedings of the International Workshop on New Models for Software Architecture '92; Reflection and Meta-Level Architecture, 1992.

Reflection For Control of Concurrency and Distribution

Many of the references in the previous section deal with concurrency and and distribution. Here are some more on that topic:

Hideaki Okamura and Yutaka Ishikawa. Object Location Control Using Meta-level Programming. In Mario Tokoro and Remo Pareschi, editors, LNCS 821, Object-Oriented Programming, Proceedings of ECOOP'94, July 1994.

Takuo Watanabe and Akinori Yonezawa. An actor-based metalevel architecture for group-wide reflection. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors, Proceedings of REX School/Workshop on Foundations of Object-Oriented Languages (REX/FOOL), Noordwijkerhout, the Netherlands, May, 1990, number 489 in Lecture Notes in Computer Science, pages 405-425. Springer Verlag, 1991.

Yasuhiko Yokote, Fumio Teraoka, and Mario Tokoro. A reflective architecture for an object-oriented distributed operating system. In Proceedings of European Conference on Object-Oriented Programming (ECOOP), July 1989. (also available as a technical report SCSL-TR-89-001, Sony Computer Science Laboratory Inc.).

Yasuhiko Yokote. The Apertos reflective operating system: The concept and its implementation. In Proceedings of the ACM Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA), pages 414-434, October 1992.

Non-Procedural Reflection

Most of the work on reflection has been on procedural reflection, where the meta-level directly implements the base-level. The following work is a notable exception.

Rok Sosic. Dynascope: A tool for program directing. In Proceedings of the 1992 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 12-21, 1992.

Rok Sosic. The Many Faces of Introspection. PhD thesis, The University of Utah, 1992.

Implementation Techniques

Partial evaluation and runtime code generation can play an important role in open implementations.

These papers provide examples of the use of special-purpose partial evaluators, and as such are useful in thinking about how to apply these techniques to a particular OI architecture.

Andrew Berlin. Partial evaluation applied to numerical computation. In Lisp and Functional Programming Conference, 1990.

Andrew Berlin and Daniel Weise. Compiling scientific code using partial evaluation. IEEE Computer, December 1990.

The PEPM conference proceedings are a good place to learn about the latest in PE techniques and their applications. Some of the proceedings are distributed as SIGPLAN notices:

ACM. Partial Evaluation and Semantics-Based Program Manipulation. Technical Report 94/9. Department of Computer Science, University of Melbourne. 1994.

These systems show how very late code generation, mixed with some amount of partial evaluation techniques can be used to advantage. In particular, the papers by Kiczales et. al., Masuhara et. al., and by Rose show techniques for making reflection efficient:

C. Chambers and D. Ungar. Customization: Optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language. In ACM SIGPLAN '89 Conference on Programming Language Design and Implementation, 1989.

Keith D. Cooper, Mary W. Hall and Ken Kennedy. Procedure Cloning. in Proceedings of the IEEE International Conference on Computer Languages, 1992.

Gregor J. Kiczales and Luis H. Rodriguez Jr. Efficient method dispatch in PCL. In Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, pages 99-105, 1990.

Henry Massalin and Calton Pu. Threads and input/output in the Synthesis kernel. In Proceedings of the 12th ACM Symposium on Operating Systems Principles, pages 191-201, December 1989.

Henry Massalin and Calton Pu. Fine-grain scheduling. Technical Report CUCS-381-88, Columbia University, 1988.

Hidehiko Masuhara, Satoshi Matsuoka, Takuo Watanabe, and Akinori Yonezaw. OO concurrent reflective languages can be implemented efficiently. In Proceedings of the ACM Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA), 1992.

Calton Pu, Henry Massalin, and John Ioannidis. The Synthesis kernel. Computing Systems, 1(1):11-32, Winter 1988.

Calton Pu and Henry Massalin. An overview of the Synthesis operating system. Technical Report CUCS-470-89, Columbia University, 1989.

John R. Rose. A minimal metaobject protocol for dynamic dispatch. In Proceedings of the OOPSLA Workshop on Reflection and Metalevel Architectures in Object-Oriented Programming, 1991.

Uses of MOPs

The paper by Bennett et. al. describes how CLOS applications were developed with the full language, and how the language's MOP was then used to strip the deliverable system down to the minimum subset of the language. The paper by Lee et. al. describes adding persistence to CLOS using its metaobject protocol for a real-world application.

James Bennett, John Dawes, and Reed Hastings. Cleaning CLOS applications with the MOP. In Gregor Kiczales, editor, Proceedings of the Second CLOS Users and Implementors Workshop, 1989.

Andreas Paepcke. PCLOS: A flexible implementation of CLOS persistence. In Proceedings of the European Conference on Object-Oriented Programming, pages 374-389, 1988.

Arthur H. Lee and Joseph L. Zachary. Using Metaprogramming to Add Persistence to CLOS. In 1994 International Conference on Computer Languages, IEEE Computer Society Press, May 1994.

Non-Language Metaobject Protocols and Open Implementations

These papers show the applications of MOPs and other techniques to making a variety of systems more open. In some cases, the focus on open implementations and/or meta-level techniques is explicit, in other cases it is more implicit or even ad-hoc.

Thomas E. Anderson et al. Scheduler activations: Effective kernel support for the user-level management of parallelism. ACM Transactions on Computer Systems, 10(1):53-79, February 1992.

Bruce Cohen. Transformation and reflection: Metaprogramming as a software process tool. In Proceedings of the OOPSLA Workshop on Reflection and Metalevel Architectures in Object-Oriented Programming, 1991.

Scott Danforth and Ira Forman. Reflections on metaclass programming in SOM. In Proceedings of the ACM Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA). ACM, 1994.

Paul Dourish. Computational reflection and CSCW design. Technical Report EPC-92-102, Rank Xerox EuroPARC, March 1992.

Graham Hamilton and Panos Kougiouris. The Spring nucleus: A microkernel for objects. Technical Report SMLI TR-93-14, Sun Microsystems Laboratories, Inc., April 1993.

Yasuaki Honda and Mario Tokoro. Soft real-time programming through reflection. In Proceedings of the International Workshop on New Models for Software Architecture '92; Reflection and Meta-Level Architecture, pages 12-23, 1992.

Yutaka Ishikawa and Hideaki Okamura. A new reflective architecture: AL-1 approach. In Proceedings of the OOPSLA Workshop on Reflection and Metalevel Architectures in Object-Oriented Programming, 1991.

Yousef A. Khalidi and Michael N. Nelson. The Spring virtual memory system. Technical Report SMLI TR-93-09, Sun Microsystems Laboratories, Inc., February 1993.

Victor P. Lortz and Kang G. Shin. Combining contracts and exemplar-based programming for class hiding and customization. In Proceedings of the ACM Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA), 1994.

Dylan McNamee and Katherine Armstrong. Extending the Mach external pager interface to allow user-level page replacement policies. Technical Report 90-09-05, University of Washington, 1990.

Michaell N. Nelson, Yousef A. Khalidi, and Peter W. Madany. The Spring file system. Technical Report SMLI TR-93-10, Sun Microsystems Laboratories, Inc., February 1993.

Hideaki Okamura, Yutaka Ishikawa, and Mario Tokoro. AL-1/D: A distributed programming system with multi-model reflection framework. In Proceedings of the International Workshop on New Models for Software Architecture '92; Reflection and Meta-Level Architecture, 1992.

Keith Krueger, David Loftesness, Amin Vahdat, and Thomas Anderson. Tools for the development of application-specific virtual memory management. In Andreas Paepcke, editor, Proceedings of the Conference on Object-Oriented Programming: Systems, Languages, and Applications, pages 48-64. ACM/SIGPLAN, ACM Press, October 1993. Volume 28, Number 10.

John B. Carter, Bryan Ford, Mike Hibler, Ravindra Kuramkote, Jeffrey Law, Jay Lepreau, Douglas B. Orr, Leigh Stoller, and Mark Swanson. Flex: A tool for building efficient and flexible systems. In Fourth Workshop on Workstation Operating Systems, pages 198-202. IEEE Computer Society Technical Committee on Operating Systems and Application Environments, IEEE Computer Society Press, October 1993.

Richard Draves. The case for run-time replaceable kernel modules. In Fourth Workshop on Workstation Operating Systems, pages 160-164. IEEE Computer Society Technical Committee on Operating Systems and Application Environments, IEEE Computer Society Press, October 1993.

Chris Maeda and Brian N. Bershad. Service without servers. In Fourth Workshop on Workstation Operating Systems, pages 170-176. IEEE Computer Society Technical Committee on Operating Systems and Application Environments, IEEE Computer Society Press, October 1993.

The following paper describes a parallelizing Scheme compiler:

Luis H. Rodriguez Jr. Coarse-grained parallelism using metaobject protocols. Master's thesis, Massachusetts Institute of Technology, 1991.

Steve Rowley, Howard Shrobe, and Robert Cassels. Joshua: Uniform access to heterogeneous knowledge structures or Why Joshing is better than conniving or planning. In Proceedings of the Sixth National Conference on Artificial Intelligence, pages 48-58, 1987.

Chandramohan A. Thekkath, Thu D. Nguyen, Evelyn Moy, and Edward D. Lazowska. Implementing network protocols at user level. Technical Report 93-03-01, University of Washington, 1993.

J. Allen Yang and Young il Choo. Meta-crystal - a metalanguage for parallel-program optimization. Technical Report YALEU/DCS/TR-786, Yale University, April 1990.

Yasuhiko Yokote, Fumio Teraoka, Atsushi Mitsuzawa, Nobuhisa Fujinami, and Mario Tokoro. The Muse object architecture: A new operating system structuring concept. Operating Systems Review, 25(2), April 1991. (also available as a technical report SCSL-TR-91-002, Sony Computer Science Laboratory Inc.).

Yasuhiko Yokote, Atsushi Mitsuzawa, Nobuhisa Fujinami, and Mario Tokoro. Evaluation of Muse reflective object management. In Proceedings of the 8th Conference of Japan Society for Software Science and Technology, September 1991. (in Japanese, also available as a technical report SCSL-TM-91-019, Sony Computer Science Laboratory Inc.).

M. Young, A. Tevanian, R. Rashid, D. Golub, J. Eppinger, J. Chew, W. Bolosky, D. Black, and R. Baron. The duality of memory and communication in the implementation of a multiprocessor operating system. In Proceedings of the 11th Symposium on Operating Systems Principles, 1987.

The following describes customizable garbage collection.

Giuseppe Attardi and Tito Flagella. Customising object allocation. In Proceedings of the 8th European Conference on Object-Oriented Programming, pages 320-343, 1994.

Return to the Open Implementation Site Guide Return to the Open Implementation Home Page