The impact of the LCC-optimization on the performance of a static scope LISP interpreter

ABSTRACT

The Low Cost Call - Optimization was introduced as a general approach to the optimization of function calls in shallow binding implementations of applicative static scope languages. The basic idea of the LCC-optimization is to avoid saving obsolete environments for a large class of function calls, thus exceeding the usual optimization of tailrecursive and covered tailrecursive calls. This paper describes how the new technique has been applied in the implementation of a portable static scope LISP interpreter for microcomputers, called LCINT. In a benchmark test we measure the impact of the LCC-optimization on the performance of LCINT. The results show that this technique is particularly valuable for small systems with a rather limited storage. Whereas some of the results fully meet our expectations, others are rather surprising and lead us to certain conclusions for further research.

REFERENCES

• Ba78: Henry G. Baker, Jr., Shallow binding in Lisp 1.5, Communications of the ACM, v.21 n.7, p.565-569, July 1978 [doi>10.1145/359545.359566]
• Ba80: Bauchrowitz, N. Comparing Operational and Denotational Semantics for LISP (German) M.S. Thesis, Institute of Computer Science, University of Kiel, 1980
• Be88: Beckmann, R. A LISP-Interpreter with LCC-Optimization - Implementation and Benchmark Tests (German) M.S. Thesis, Department of Computer Science, University of Miinster, 1987
• Ch80: Chailloux, J. Le-Lisp de l'Inria, Manuel de reference I.N.R.I.A. Le Chesnay Rocquencourt, November 1983
• Fe84: Felgentreu, K.-U. Implementation of a Fast LISP-Interpreter (German) M-S. Thesis, Institute of Computer Science, University of Kiel, February 1984 ,
• Fe/Li86a: K.-U. Felgentreu , W.-M. Lippe, Dynamic optimization of covered tail recursive functions in applicative languages, Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.293-299, February 1986, Cincinnati, Ohio, United States [doi>10.1145/324634.325437]
• Fe/Li86b: K U Felgentreu , W M Lippe, A general approach to the optimization of function calls, Proc. of the European symposium on programming on ESOP 86, p.41-52, March 1986, Saarbru:9Aicken, Germany
• Fe/Li86c: K U Felgentreu , W M Lippe, Low cost environment changing in a shallow binding system, New Generation Computing, v.4 n.3, p.245-272, 1986 [doi>10.1007/BF03037406]
• Fe/Li/Si87: Kay-Ulrich Felgentreu , Wolfram-M. Lippe , Friedemann H. Simon, Optimizing static scope LISP by repetitive interpretation of recursive functions calls, IEEE Transactions on Software Engineering, v.13 n.6, p.628-635, June 1987 [doi>10.1109/TSE.1987.233473]
• Fe87a: Felgentreu, K.-U. Optimizing Function Calls under Shallow Binding with Static Scoping (German) Doctoral dissertation, University of Miinster, 1987
• Fe87b: Felgentreu, K.-U. On the Decidability of Low Cost Function Calls submitted (preprint available from the author)
• Gr78: Greussay, P. Iterative Interpretation of Tailrecursive LISP Procedures in: Ecole de la Recherche, Universite de Paris, 1978
• Ho/Li/Si83: U. Honschopp , W. M. Lippe , F. Simon, Compiling functional languages for von Neumann machines, Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems, p.22-27, June 27-29, 1983, San Francisco, California, United States
• Ka/Sch86: U Kastens , M Schmidt, Lifetime analysis for procedure parameters, Proc. of the European symposium on programming on ESOP 86, p.53-69, March 1986, Saarbru:9Aicken, Germany
• Li/SiSO: Wolfram-Manfred Lippe , F. Simon, Semantics for LISP without Reference to an Interpreter, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.240-255, April 22-24, 1980
• Pe78: Perrot, J.F. Principes d'implementation de processus recursifs in: Ecole de la Recherche, Universite de Paris, 1978
• SaJa84: Emmanuel Saint-James, Recursion is more efficient than iteration, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.228-234, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802039]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP

General Terms:
Algorithms, Design, Performance