Positive supercompilation for a higher order call-by-value language

ABSTRACT

Previous deforestation and supercompilation algorithms may introduce accidental termination when applied to call-by-value programs. This hides looping bugs from the programmer, and changes the behavior of a program depending on whether it is optimized or not. We present a supercompilation algorithm for a higher-order call-by-value language and we prove that the algorithm both terminates and preserves termination properties. This algorithm utilizes strictness information for deciding whether to substitute or not and compares favorably with previous call-by-name transformations.

REFERENCES

• 1: Elvira Albert , Germán Vidal, The narrowing-driven approach to functional logic program specialization, New Generation Computing, v.20 n.1, p.3-26, January 2002 [doi>10.1007/BF03037257]
• 2: A. Alimarine and S. Smetsers. Improved fusion for optimizing generics. In Manuel V. Hermenegildo and Daniel Cabeza, editors, Practical Aspects of Declarative Languages, 7th International Symposium, PADL 2005, Long Beach, CA, USA, January 10-11, 2005, Proceedings, volume 3350 of Lecture Notes in Computer Science, pages 203--218. Springer, 2005. ISBN 3-540-24362-3.
• 3: 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]
• 4: W.-N. Chin. Safe fusion of functional expressions II: Further improvements. J. Funct. Program, 4 (4): 515--555, 1994.
• 5: O. Chitil. Type-Inference Based Deforestation of Functional Programs. PhD thesis, RWTH Aachen, October 2000.
• 6: Nachum Dershowitz, Termination of rewriting, Journal of Symbolic Computation, v.3 n.1-2, p.69-116, Feb./April 1987 [doi>10.1016/S0747-7171(87)80022-6]
• 7: Y. Futamura and K. Nogi. Generalized partial computation. In D. Bjørner, A.P. Ershov, and N.D. Jones, editors, Partial Evaluation and Mixed Computation, pages 133--151. Amsterdam: North-Holland, 1988.
• 8: Yoshihiko Futamura , Zenjiro Konishi , Robert Glück, Program transformation system based on generalized partial computation, New Generation Computing, v.20 n.1, p.75-99, January 2002 [doi>10.1007/BF03037260]
• 9: N. Ghani and P. Johann. Short cut fusion of recursive programs with computational effects. In P. Achten, P. Koopman, and M. T. Morazán, editors, Draft Proceedings of The Ninth Symposium on Trends in Functional Programming (TFP), number ICIS-R08007, 2008.
• 10: Andrew Gill , John Launchbury , Simon L. Peyton Jones, A short cut to deforestation, Proceedings of the conference on Functional programming languages and computer architecture, p.223-232, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165214]
• 11: A. J. Gill. Cheap Deforestation for Non-strict Functional Languages. PhD thesis, Univ. of Glasgow, January 1996.
• 12: G. W. Hamilton, Higher Order Deforestation, Proceedings of the 8th International Symposium on Programming Languages: Implementations, Logics, and Programs, p.213-227, September 24-27, 1996
• 13: Geoff W. Hamilton, Higher Order Deforestation, Fundamenta Informaticae, v.69 n.1-2, p.39-61, July 2005
• 14: R. Hinze. Generic Programs and Proofs. PhD thesis, Habilitationsschrift, Bonn University, 2000.
• 15: 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
• 16: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 17: S. L. Peyton Jones, A. Tolmach, and T. Hoare. Playing by the rules: Rewriting as a practical optimisation technique in GHC. In Ralf Hinze, editor, Proceedings of the 2001 ACM SIGPLAN Haskell Workshop (HW'2001), 2nd September 2001, Firenze, Italy., Electronic Notes in Theoretical Computer Science, Vol 59. Utrecht University, September 28 2001. UU-CS-2001-23.
• 18: P. A. Jonsson. Positive supercompilation for a higher-order call-by-value language. Licentiate thesis, Luleå University of Technology, Sweden, Jun 2008.
• 19: P. A. Jonsson and J. Nordlander. Positive Supercompilation for a Higher Order Call-By-Value Language: Extended Proofs. Technical Report 2008:17, Department of Computer science and Electrical engineering, Luleå University of Technology, October 2008.
• 20: J. Kort. Deforestation of a raytracer. Master's thesis, University of Amsterdam, 1996.
• 21: J.-L. Lassez , M. J. Maher , K. Marriott, Unification revisited, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 22: X. Leroy. The Objective Caml system: Documentation and user's manual, 2008. With D. Doligez, J. Garrigue, D. Rémy, and J. Vouillon. Available from http://caml.inria.fr (1996-2008).
• 23: Simon Marlow , Philip Wadler, Deforestation for Higher-Order Functions, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.154-165, July 06-08, 1992
• 24: S. D. Marlow. Deforestation for Higher-Order Functional Programs. PhD thesis, Department of Computing Science, University of Glasgow, April 27 1995.
• 25: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 26: Neil Mitchell , Colin Runciman, A Supercompiler for Core Haskell, Implementation and Application of Functional Languages: 19th International Workshop, IFL 2007, Freiburg, Germany, September 27-29, 2007. Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-85373-2_9]
• 27: P. Narendran and J. Stillman. On the Complexity of Homeomorphic Embeddings. Technical Report 87-8, Computer Science Department, State Univeristy of New York at Albany, March 1987.
• 28: TimberJ. Nordlander, M. Carlsson, A. Gill, P. Lindgren, and B. von Sydow. The Timber home page, 2008. URL http://www.timber-lang.org.
• 29: Atsushi Ohori , Isao Sasano, Lightweight fusion by fixed point promotion, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 30: Will Partain, The nofib Benchmark Suite of Haskell Programs, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.195-202, July 06-08, 1992
• 31: David Sands, Proving the correctness of recursion-based automatic program transformations, Theoretical Computer Science, v.167 n.1-2, p.193-233, Oct. 30, 1996
• 32: David Sands, From SOS rules to proof principles: an operational metatheory for functional languages, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.428-441, January 15-17, 1997, Paris, France [doi>10.1145/263699.263760]
• 33: J. P. Secher. Perfect supercompilation. Technical Report DIKU-TR-99/1, Department of Computer Science (DIKU), University of Copenhagen, February 1999.
• 34: Jens P. Secher , Morten Heine Sørensen, On Perfect Supercompilation, Proceedings of the Third International Andrei Ershov Memorial Conference on Perspectives of System Informatics, p.113-127, July 06-09, 1999
• 35: Morten Heine B. Sørensen, Convergence of program transformers in the metric space of trees, Science of Computer Programming, v.37 n.1-3, p.163-205, May 2000 [doi>10.1016/S0167-6423(99)00026-X]
• 36: M.H. Sørensen and R. Glück. An algorithm of generalization in positive supercompilation. In J.W. Lloyd, editor, International Logic Programming Symposium, pages 465--479. Cambridge, MA: MIT Press, 1995.
• 37: Morten Heine Sørensen , Robert Glück , Neil D. Jones, Towards Unifying Partial Evaluation, Deforestation, Supercompilation, and GPC, Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, p.485-500, April 11-13, 1994
• 38: M.H. Sørensen, R. Glück, and N.D. Jones. A positive supercompiler. Journal of Functional Programming, 6 (6): 811--838, 1996.
• 39: Josef Svenningsson, Shortcut fusion for accumulating parameters & zip-like functions, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.124-132, October 04-06, 2002, Pittsburgh, PA, USA
• 40: D. Syme. The F# programming language, Jun 2008. URL http://research.microsoft.com/fsharp.
• 41: Akihiko Takano, Generalized partial computation for a lazy functional language, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.1-11, June 17-19, 1991, New Haven, Connecticut, United States
• 42: Akihiko Takano , Erik Meijer, Shortcut deforestation in calculational form, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.306-313, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224221]
• 43: V. F. Turchin, A supercompiler system based on the language REFAL, ACM SIGPLAN Notices, v.14 n.2, p.46-54, February 1979 [doi>10.1145/954063.954069]
• 44: Valentin F. Turchin, Semantic definitions in REFAL and the automatic production of compilers, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.441-474, January 14-18, 1980
• 45: Valentin. F. Turchin, Program transformation by supercompilation, on Programs as data objects, p.257-281, April 1986, Copenhagen, Denmark
• 46: Valentin F. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.292-325, July 1986 [doi>10.1145/5956.5957]
• 47: V.F. Turchin. Refal-5, Programming Guide & Reference Manual. Holyoke, MA: New England Publishing Co., 1989.
• 48: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Languages, Theory

Keywords:
call-by-value, deforestation, supercompilation