On compiling embedded languages in LISP

ABSTRACT

In INTERLISP we find a number of embedded languages such as the iterative statement and the pattern match facility in the CLISP package, the editor and makefile languages and so forth. We will in this paper concentrate on the problem of extending the LISP language and discuss a method to compile such extensions. We propose the language to be implemented through an interpreter (written in LISP) and that compilation of statements in such an embedded language is done through partial evaluation. The interpreter is partially evaluated with respect to the actual statements, and an object program in LISP is obtained. This LISP code can further be compiled to machine code by the standard LISP compiler. We have implemented the iterative statement and a CLISP-like pattern matcher and used a program manipulation system to generate object programs in LISP. Comparisons will be made with the corresponding INTERLISP implementations, which use special purpose compilers in order to generate the LISP code.

REFERENCES

• 1: Allen, F. et al. The experimental compiling systems project, IBM Research Report, RC 6718, T.J. Watson Research Center, Yorktown Heights, New York, 1977.
• 2: Jacques J. Arsac, Syntactic source to source transforms and program manipulation, Communications of the ACM, v.22 n.1, p.43-54, Jan. 1979 [doi>10.1145/359046.359057]
• 3: Beckman, L., Haraldson, A., Oskarsson, &Obreve;., Sandewall, E. A. partial evaluator and its use as a programming tool, Artificial Intelligence Journal 7, 1976, 319-357.
• 4: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 5: J. Lawrence Carter, A case study of a new code generation technique for compilers, Communications of the ACM, v.20 n.12, p.914-920, Dec. 1977 [doi>10.1145/359897.359902]
• 6: Thomas E. Cheatham, Jr. , Judy A. Townley , Glenn H. Holloway, A system for program refinement, Proceedings of the 4th international conference on Software engineering, p.53-62, September 17-19, 1979, Munich, Germany
• 7: Emanuelson P. (under preparation), Informatics Laboratory, Linköping University, Sweden, 1980.
• 8: Ershov, A.P. On the partial computation principle, Information Processing Letters, no 2, 1977.
• 9: Ershov, A.P. On the essence of compilation, IFIP Working Conference on formal description of programming concepts, S. Andrews, Canada, aug 1977.
• 10: Futamura, Y. Partial evaluation of computer programs: An approach to a compiler-compiler. J. Inst. Electronics and Communication Engineers, 1971.
• 11: Haraldsson, A. A program manipulation system based on partial evaluation, Ph.D. Thesis, Informatics Laboratory, Linköping University, Sweden, 1977.
• 12: Anders Haraldsson, A partial evaluator, and its use for compiling iterative statements in LISP, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.195-202, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512781]
• 13: Haraldsson, A. Experiences from a program manipulation system, Informatics Laboratory, Linköping University, Sweden, 1980.
• 14: Harrison, W. A new strategy for code generation - The general-purpose optimizing compiler, IEEE transactions on software engineering, vol SE-4, 4, july 1979.
• 15: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 16: Komorowski, H.J. and Goodwin, J. W. Embedding Prolog in Lisp: An example of a Lisp Craft Tradition, Informatics Laboratory, Linköping University, Sweden, 1980.
• 17: David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
• 18: Rich, C. and Shrobe, H. Design of a programmers apprentice, Artificial intelligence: An MIT perspective, vol 1, The MIT Press, 1979.
• 19: Erik Sandewall, Programming in an Interactive Environment: the ``Lisp'' Experience, ACM Computing Surveys (CSUR), v.10 n.1, p.35-71, March 1978 [doi>10.1145/356715.356719]
• 20: Teitelman, W. INTERLISP Reference Manual, Xerox, Palo Alto Research Center, Calif, 1978.
• 21: Ben Wegbreit, Goal-directed program transformation, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.153-170, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811549]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

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

          Nouns: LISP; INTERLISP

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Languages, Performance