Cheap eagerness: speculative evaluation in a lazy functional language

ABSTRACT

Cheap eagerness is an optimization where cheap and safe expressions are evaluated before it is known that their values are needed. Many compilers for lazy functional languages implement this optimization, but they are limited by a lack of information about the global flow of control and about which variables are already evaluated. Without this information, even a variable reference is a potentially unsafe expression!In this paper we show that significant speedups are achievable by cheap eagerness. Our cheapness analysis uses the results of a program-wide data and control flow analysis to find out which variables may be unevaluated and which variables may be bound to functions which are dangerous to call.

REFERENCES

• 1: S. Abramsky. Abstract interpretation, logical relations and Kan extensions. Journal of Logic and Computation, 1(1):5-39, 1990.
• 2: Karl-Filip Faxén, Optimizing Lazy Functional Programs Using Flow Inference, Proceedings of the Second International Symposium on Static Analysis, p.136-153, September 25-27, 1995
• 3: Karl-Filip Faxen. Analysing, Transforming and Compiling Lazy Functional Programs. PhD thesis, Department ofTeleinformatics, Royal Institute of Technology, June 1997.
• 4: Karl-Filip Faxen. Representation analysis for coercion placement. In Konstantinos Sagonas and Paul Tarau, editors, Proceedings of the International Workshop on Implementation of Declarative Languages, September 1999.
• 5: Karl-Filip Faxén, The costs and benefits of cloning in a lazy functional language, Selected papers from the 2nd Scottish Functional Programming Workshop (SFP00), p.1-12, July 26-28, 2000
• 6: Pieter H. Hartel , Koen G. Langendoen, Benchmarking implementations of lazy functional languages, Proceedings of the conference on Functional programming languages and computer architecture, p.341-349, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165230]
• 7: Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
• 8: Suresh Jagannathan , Stephen Weeks, A unified treatment of flow analysis in higher-order languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.393-407, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199536]
• 9: Thomas Johnsson, Efficient compilation of lazy evaluation, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.58-69, June 17-22, 1984, Montreal, Canada
• 10: Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
• 11: Simon Peyton Jones and John Hughes. Report on the programming language Haskell 98. Downloadable from www.haskell.org, February 1999.
• 12: Simon L. Peyton Jones , John Launchbury, Unboxed values as first class citizens in a non-strict functional language, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.636-666, June 1991, Cambridge, Massachusetts, United States
• 13: David Sands, Total correctness by local improvement in the transformation of functional programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.2, p.175-234, March 1996 [doi>10.1145/227699.227716]
• 14: Andr~e Santos. Compilation by Transformation in Non-Strict Functional Languages. PhD thesis, Glasgow University, Department of Computing Science, 1995.
• 15: Peter Sestoft. Analysis and efficient implementation of functional programs. PhD thesis, DIKU, University of Copenhagen, Denmark, October 1991.
• 16: Olin Shivers, The semantics of Scheme control-flow analysis, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-198, June 17-19, 1991, New Haven, Connecticut, United States
• 17: Kirsten Lackner Solberg, Strictness and Totality Analysis with Conjunction, Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.501-515, May 22-26, 1995
• 18: Philip Wadler, Deforestation: transforming programs to eliminate trees, Proceedings of the Second European Symposium on Programming, p.231-248, January 1988, Nancy, France
• 19: Philip Wadler , R. J. M. Hughes, Projections for strictness analysis, Proc. of a conference on Functional programming languages and computer architecture, p.385-407, October 1987, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance, Reliability, Theory, Verification