Environments as first class objects

ABSTRACT

We describe a programming language called Symmetric Lisp that treats environments as first-class objects. Symmetric Lisp allows programmers to write expressions that evaluate to environments, and to create and denote variables and constants of type environment as well. One consequence is that the roles filled in other languages by a variety of limited, special purpose environment forms like records, structures, closures, modules, classes and abstract data types are filled instead by a single versatile and powerful structure. In addition to being its fundamental structuring tool, environments also serve as the basic functional object in the language. Because the elements of an environment are evaluated in parallel, Symmetric Lisp is a parallel programming language; because they may be assembled dynamically as well as statically, Symmetric Lisp accommodates an unusually flexible and simple (parallel) interpreter as well as other history-sensitive applications requiring dynamic environments. We show that first-class environments bring about fundamental changes in a language's structure: conventional distinctions between declarations and expressions, data structures and program structures, passive modules and active processes disappear.

REFERENCES

• 1: Reference Manual for the ADA Programming Language. United States Dept. of Defense, 1982.
• 2: E. A. Ashcroft , W. W. Wadge, Lucid, a nonprocedural language with iteration, Communications of the ACM, v.20 n.7, p.519-526, July 1977 [doi>10.1145/359636.359715]
• 3: M. Atkinson and R. Morrison. Types, Bindings, and Parameters in a Persistent Environment. in Persistence and Data Types Papers for the Appin Workshop, University of St. Andrews, August 1985.
• 4: Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.17-29, September 29-October 02, 1986, Portland, Oregon, United States
• 5: Nicholas Carriero , David Gelernter , Jerrold Leichter, Distributed data structures in Linda, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.236-242, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512666]
• 6: William Clinger and et. al. The Revised Revised Revised Report on Scheme or An UnCommon Lisp. Technical Report AI-TM 848, MIT Artifical Intelligence Laboratory, 1985.
• 7: Richard P. Gabriel , John McCarthy, Queue-based multi-processing LISP, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.25-44, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802019]
• 8: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 9: David Gelernter. Symmetric Programming Languages. Technical Report TR 353, Yale University Dept. of Computer Science, December 1984.
• 10: David Gelernter. Symmetry and the Non- Evolution of Programming Languages. Technical Report TR 486, Yale University Dept. of Computer Science, June 1986.
• 11: David Gelernter, Nick Carriero, Sarat Chandran, and Silvia Chang. Parallel programming in Linda. In Int. Conf. Parallel Processing, August 1985.
• 12: David Gelernter, Suresh Jagannathan, and Thomas London. Parallelism, Persistence and Meta-Cleanliness in the Symmetric Lisp Interpreter. Technical Report, Yale University Dept. of Computer Science, 1986.
• 13: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 14: R. Greenblat, T. Knight, $. Holoway, D. Moon, and D. Weirtreb. The LISP Machine. In Interactive Programming Environments, pages 326- 352, McGraw-Hill.
• 15: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 16: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 17: W. Daniel Hillis, The connection machine, MIT Press, Cambridge, MA, 1986
• 18: Robert Keller, Gary Lindstrom, and Suhas Patil. A Loosely-Coupled Applicative Multi- Processing System. in A FIPS Conference Proceedings, pages 613-622, June 1979.
• 19: 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]
• 20: Guy L Steele , Gerald J Sussman, Lambda: The Ultimate Imperative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 21: Guy L. Steele, Jr., Common LISP: the language, Digital Press, Newton, MA, 1984
• 22: Guy L. Steele, Jr. , W. Daniel Hillis, Connection Machine Lisp: fine-grained parallel symbolic processing, Proceedings of the 1986 ACM conference on LISP and functional programming, p.279-297, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319870]
• 23: 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
• 24: D. A. Turner. A New Implementation Technique for Applicative Languages. Software - Practice and Experience, (9):31-49, 1979.
• 25: Mitchell Wand , Daniel P. Friedman, The mystery of the tower revealed: a non-reflective description of the reflective tower, Proceedings of the 1986 ACM conference on LISP and functional programming, p.298-307, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319871]
• 26: K. S. Weng, AN ABSTRACT IMPLEMENTATION FOR A GENERALIZED DATA FLOW LANGUAGE, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 27: Niklaus Wirth. The Design and Implementation of Modula. Software Practice and Experience, 1980.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Languages, Theory