Metalevel building blocks for modular systems

ABSTRACT

The formal definition of any namespace device found in a programming language can be given in terms of transformations on a semantic environment. It is worthwhile, therefore, to consider the implications of incorporating environments as bona fide data objects in a programming system. In this article, we propose a treatment of environments and the mechanism by which they are reified and manipulated, that addresses these concerns. The language described below (Rascal) permits environments to be reified into data structures, and data structures to be reflected into environments, but gives users great flexibility to constrain the extent and scope of these processes. We argue that the techniques and operators developed define a cohesive basis for building large-scale modular systems using reflective programming techniques.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: Norman Adams , Jonathan Rees, Object-oriented programming in scheme, Proceedings of the 1988 ACM conference on LISP and functional programming, p.277-288, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62720]
• 3: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 4: R. Burstall , B. Lampson, A kernel language for abstract data types and modules., Proc. of the international symposium on Semantics of data types, p.1-50, July 1984, Sophia-Antipolis, France
• 5: L. Cardelli , J. Donahue , M. Jordan , B. Kalsow , G. Nelson, The Modula–3 type system, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.202-212, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75295]
• 6: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 7: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• 8: William Clinger , Jonathan Rees, Macros that work, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.155-162, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99607]
• 9: W. Cook , J. Palsberg, A denotational semantics of inheritance and its correctness, ACM SIGPLAN Notices, v.24 n.10, p.433-443, Oct. 1989
• 10: Pavel Curtis , James Rauen, A module system for scheme, Proceedings of the 1990 ACM conference on LISP and functional programming, p.13-19, June 27-29, 1990, Nice, France [doi>10.1145/91556.91573]
• 11: DAHL, O., MYHRHAUG, B., AND NYGAARD, K. 1970. The Simula67 base common base language. Tech. rep., Norwegien Computing Center.
• 12: Jim des Rivières , Brian Cantwell Smith, The implementation of procedurally reflective languages, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.331-347, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802050]
• 13: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 14: M. Felleisen, The theory and practice of first-class prompts, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.180-190, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73576]
• 15: Daniel P. Friedman , Mitchell Wand, Reification: Reflection without metaphysics, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.348-355, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802051]
• 16: D. Gelernter , S. Jagannathan , T. London, Environments as first class objects, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.98-110, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41634]
• 17: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 18: Robert Harper , Mark Lillibridge, A type-theoretic approach to higher-order modules with sharing, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.123-137, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.176927]
• 19: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 20: JAGANNATHAN, S. 1988. A programming language supporting first-class, parallel environments. Ph.D. thesis, MIT, Cambridge, Mass. (Also published as Tech. rep. LCS-TR 434.)
• 21: Thomas Johnsson, Lambda lifting: transforming programs to recursive equations, Proc. of a conference on Functional programming languages and computer architecture, p.190-203, January 1985, Nancy, France
• 22: S. Kamin, Inheritance in smalltalk-80: a denotational definition, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.80-87, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73567]
• 23: E. E. Kohlbecker , M. Wand, Macro-by-example: Deriving syntactic transformations from their specifications, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.77-84, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41632]
• 24: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, ACM SIGPLAN Notices, v.21 n.7, p.219-233, July 1986
• 25: John Lamping, A unified system of parameterization for programming languages, Proceedings of the 1988 ACM conference on LISP and functional programming, p.316-326, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62724]
• 26: Shinn-Der Lee , Daniel P. Friedman, Quasi-static scoping: sharing variable bindings across multiple lexical scopes, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.479-492, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158706]
• 27: Henry Lieberman, Using prototypical objects to implement shared behavior in object-oriented systems, Conference proceedings on Object-oriented programming systems, languages and applications, p.214-223, September 29-October 02, 1986, Portland, Oregon, United States
• 28: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 29: David MacQueen, An implementation of standard ML modules, Proceedings of the 1988 ACM conference on LISP and functional programming, p.212-223, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62704]
• 30: David B. MacQueen , Mads Tofte, A Semantics for Higher-Order Functors, Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, p.409-423, April 11-13, 1994
• 31: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 32: PEYTON-JONES, S. L. 1987. The Implementation of Funetwnal Programming Languages. Prentice Hall.
• 33: Uday Reddy, Objects as closures: abstract semantics of object-oriented languages, Proceedings of the 1988 ACM conference on LISP and functional programming, p.289-297, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62721]
• 34: REES 1993. Another Module System for Scheme Scheme48 documentation.
• 35: SMITH~ B. 1982. Reflection and Semantics in a Procedural Language. Ph. D. thesis, MIT, Cambridge, Mass. (Also published as Tech. rep. LCS TR-272.)
• 36: STEELE JR.~ G 1978. Rabbit: A Compiler for Scheme. Master's thesis, Massachusetts Institute of Technology, Cambridge, Mass.
• 37: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 38: Guy L Steele , Gerald J Sussman, The Art of the Interpreter or, The Modularity Complex (Parts Zero, One, and Two), Massachusetts Institute of Technology, Cambridge, MA, 1978
• 39: STRACHEY, C. AND WADSWORTH, C. 1974. Continuations: A mathematical semantics for handling full jumps. Technical Report PRG-11, Programming Research Group, Oxford University, Oxford, U.K.
• 40: Mads Tofte, Principal signatures for higher-order program modules, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.189-199, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143206]
• 41: David Ungar , Randall B. Smith, Self: The power of simplicity, ACM SIGPLAN Notices, v.22 n.12, p.227-242, Dec. 1987
• 42: David Ungar , Randall B. Smith , Craig Chambers , Urs Hölzle, Object, Message, and Performance: How they Coexist in Self, Computer, v.25 n.10, p.53-64, October 1992 [doi>10.1109/2.161280]
• 43: U.S. Dept. of Defense 1982. Reference Manual for the ADA Programmzn9 Language. U.S. Dept. of Defense, Washington, D.C.
• 44: WAND M. AND FRIEDMAN, D. P. 1988. The mystery of the tower revealed: A non-reflective description of the reflective tower. L~sp and Symbol. Comput 1, 1 (June), 11-38
• 45: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Denotational semantics

General Terms:
Languages

Keywords:
higher-order programming, modularity, reflection