Lambda-dropping: transforming recursive equations into programs with block structure

ABSTRACT

Lambda-lifting a functional program transforms it into a set of recursive equations. We present the symmetric transformation: lambda-dropping. Lambda-dropping a set of recursive equations restores block structure and lexical scope.For lack of scope, recursive equations must carry around all the parameters that any of their callees might possibly need. Both lambda-lifting and lambda-dropping thus require one to compute a transitive closure over the call graph:• for lambda-lifting: to establish the Def/Use path of each free variable (these free variables are then added as parameters to each of the functions in the call path);• for lambda-dropping: to establish the Def/Use path of each parameter (parameters whose use occurs in the same scope as their definition do not need to be passed along in the call path).Without free variables, a program is scope-insensitive. Its blocks are then free to float (for lambda-lifting) or to sink (for lambda-dropping) along the vertices of the scope tree.We believe lambda-lifting and lambda-dropping are interesting per se, both in principle and in practice, but our prime application is partial evaluation: except for Malmkjær and Ørbæk's case study presented at PEPM '95, most polyvariant specializers for procedural programs operate on recursive equations. To this end, in a pre-processing phase, they lambda-lift source programs into recursive equations, As a result, residual programs are also expressed as recursive equations, often with dozens of parameters, which most compilers do not handle efficiently. Lambda-dropping in a post-processing phase restores their block structure and lexical scope thereby significantly reducing both the compile time and the run time of residual programs.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 3: Lennart Augustsson. Compiling Lazy Functional Languages, part II. PhD thesis, Department of Computer Sciences, Chalmers University of Technology, GSteborg, Sweden, 1988.
• 4: Anindya Banerjee , David A. Schmidt, A Categorical Interpretation of Landin's Correspondence Principle, Proceedings of the 9th International Conference on Mathematical Foundations of Programming Semantics, p.587-602, April 07-10, 1993
• 5: Henk Barendregt. The Lambda Calculus -- Its Syntax and Semantics. North-Holland, 1984.
• 6: Lars Birkedal and Morten Welinder. Partial evaluation of Standard ML. Master's thesis, DIKU, Computer Science Department, University of Copenhagen, August 1993. DIKU Rapport 93/22.
• 7: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, February 1994
• 8: Anders Bondorf and Jesper Jorgensen. Efficient analyses for realistic off-line partial evaluation. Journal of Functional Programming, 3(3):315-346, 1993.
• 9: William D. Clinger , Lars Thomas Hansen, Lambda, the ultimate label or a simple optimizing compiler for Scheme, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.128-139, July-Sept. 1994
• 10: Charles Consel, A tour of Schism: a partial evaluation system for higher-order applicative languages, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.145-154, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154645]
• 11: Charles Consel , Olivier Danvy, Static and dynamic semantics processing, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.14-24, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99588]
• 12: Charles Consel , Olivier Danvy, Tutorial notes on partial evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.493-501, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158707]
• 13: Olivier Danvy, Type-directed partial evaluation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-257, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237784]
• 14: Olivier Danvy , Nevin Hentze , Karoline Malmkjær, Resource-bounded partial evaluation, ACM Computing Surveys (CSUR), v.28 n.2, p.329-332, June 1996 [doi>10.1145/234528.234741]
• 15: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, ACM SIGPLAN Notices, v.28 n.6, p.237-247, June 1993
• 16: Pascal Fradet, Syntactic detection of single-threading using continuations, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.241-258, June 1991, Cambridge, Massachusetts, United States
• 17: Carsten K. Gomaxd and Nell D. Jones. A partial evaluator for the untyped lambda-calculus. Journal of Functional Programming, 1(1):21-69, 1991.
• 18: R. J. M. Hughes, Super-combinators a new implementation method for applicative languages, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.1-10, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802129]
• 19: 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
• 20: Thomas Johnsson. Compiling Lazy Functional Languages. PhD thesis, Department of Computer Sciences, Chalmers University of Technology, GSteborg, Sweden, 1987.
• 21: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 22: Nell D. Jones, Peter Sestoft, and Harald Sondergaard. MIX: A self-applicable partial evaluator for experiments in compiler generation. LISP and Symbolic Computation, 2(1):9-50, 1989.
• 23: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• 24: Kaxoline Malmkj~er, Nevin Heintze, and Olivier Danvy. ML partial evaluation using set-based analysis. In John Reppy, editor, Record of the 199,4 A CM SIG- PLAN Workshop on ML and its Applications, Rapport de recherche N~ 2,265, INRIA, pages 112-119, Orlando, Florida, June 1994. Also appears as Technical report CMU-CS-94-129.
• 25: Karoline Malmkjær , Peter Ørbæk, Polyvariant specialisation for higher-order, block-structured languages, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.66-76, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215558]
• 26: Simon Peyton Jones , Will Partain , André Santos, Let-floating: moving bindings to give faster programs, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.1-12, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 27: S L Peyton Jones, An introduction to fully-lazy supercombinators, Proc. of the thirteenth spring school of the LITP on Combinators and functional programming languages, p.176-208, October 1986, Val d'Ajol, France
• 28: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 29: Simon L. Peyton Jones , David R. Lester, Implementing functional languages, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 30: Erik Ruff Topzes in Online Partial Evaluation. PhD thesis, Stanford University, Stanford. California, February 1993. Technical report CSL-TR-93-563.
• 31: David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
• 32: Ulrik P. Schultz. Master's thesis, DAIMI, Department of Computer Science, University of Aarhus, Aarhus, Denmark, June 1997. Forthcoming.
• 33: Peter Sestoft, Replacing function parameters by global variables, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.39-53, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99374]
• 34: Zhong Shao , Andrew W. Appel, Space-efficient closure representations, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.150-161, July-Sept. 1994
• 35: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 36: Carolyn L. TaIcott, editor. Proceedings of the 1994 A CM Conference on Lisp and Functional Programming, LISP Pointers, Vol. VII, No. 3, Orlando, Florida, June 1994. ACM Press.
• 37: Mads Tofte , Jean-Pierre Talpin, Implementation of the typed call-by-value λ-calculus using a stack of regions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.188-201, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177855]
• 38: Philip Wadler, Deforestation: transforming programs to eliminate trees, Proceedings of the Second European Symposium on Programming, p.231-248, January 1988, Nancy, France
• 39: Mitchell Wand , Paul Steckler, Selective and lightweight closure conversion, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.435-445, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178044]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Theory