A monadic approach for avoiding code duplication when staging memoized functions

ABSTRACT

Building program generators that do not duplicate generated code can be challenging. At the same time, code duplication can easily increase both generation time and runtime of generated programs by an exponential factor. We identify an instance of this problem that can arise when memoized functions are staged. Without addressing this problem, it would be impossible to effectively stage dynamic programming algorithms. Intuitively, direct staging undoes the effect of memoization. To solve this problem once and for all, and for any function that uses memoization, we propose a staged monadic combinator library. Experimental results confirm that the library works as expected. Preliminary results also indicate that the library is useful even when memoization is not used.

REFERENCES

• 1: Umut A. A. Acar , Guy E. Blelloch , Robert Harper, Selective memoization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.14-25, January 15-17, 2003, New Orleans, Louisiana, USA
• 2: Mads Sig Ager , Olivier Danvy , Henning Korsholm Rohde, Fast partial evaluation of pattern matching in strings, Proceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.3-9, June 07-07, 2003, San Diego, California, USA
• 3: J. Aldrich. Open modules: A foundation for modular aspect-oriented programming. Available online from http://www-2.cs.cmu.edu/~aldrich/papers/tinyaspect.pdf, Jan. 2003.
• 4: Anders Bondorf, Improving binding times without explicit CPS-conversion, Proceedings of the 1992 ACM conference on LISP and functional programming, p.1-10, June 22-24, 1992, San Francisco, California, United States
• 5: C. Calcagno , E. Moggi , T. Sheard, Closed types for a safe imperative MetaML, Journal of Functional Programming, v.13 n.3, p.545-571, May 2003 [doi>10.1017/S0956796802004598]
• 6: Cristiano Calcagno , Eugenio Moggi , Walid Taha, Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.25-36, July 09-15, 2000
• 7: C. Calcagno, E. Moggi, and W. Taha. ML-like inference for classifiers. In Proceedings of the European Symposium on Programming (ESOP '04), volume 2986 of Lecture Notes in Computer Science, Springer-Verlag, Mar. 2004.
• 8: Cristiano Calcagno , Walid Taha , Liwen Huang , Xavier Leroy, Implementing multi-stage languages using ASTs, Gensym, and reflection, Proceedings of the second international conference on Generative programming and component engineering, p.57-76, September 22-25, 2003, Erfurt, Germany
• 9: J. Carette and O. Kiselyov. Multi-stage programming with functors and monads: Eliminating abstraction overhead from generic code. In R. Glück and M. Lowry, editors, Proceedings of the ACM International Conference on Generative Programming and Component Engineering (GPCE'05), volume 3676 of Lecture Notes In Computer Science. Springer-Verlag, Sept. 2005.
• 10: Charles Consel , Olivier Danvy, For a Better Support of Static Data Flow, Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture, p.496-519, August 26-30, 1991
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: Søren Debois, Imperative program optimization by partial evaluation, Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.113-122, August 24-25, 2004, Verona, Italy [doi>10.1145/1014007.1014019]
• 13: W. DeMeuter. Monads as a theoretical foundation for AOP. In Proceedings of the International Workshop on Aspect-Oriented Programming at ECOOP, volume 1357 of Lecture Notes in Computer Science, page 25. Springer-Verlag, 1997.
• 14: Dynamic Programming Benchmark. Available online from http://www.metaocaml.org/examples/dp, 2005.
• 15: Dirk Dussart , John Hughes , Peter Thiemann, Type specialisation for imperative languages, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.204-216, June 09-11, 1997, Amsterdam, The Netherlands
• 16: J. Eckhardt, R. Kaiabachev, E. Pasalic, K. Swadi, and W. Taha. Implicitly heterogeneous multi-stage programming. In R. Glück and M. Lowry, editors, Proceedings of the ACM International Conference on Generative Programming and Component Engineering (GPCE'05), volume 3676 of Lecture Notes In Computer Science. Springer-Verlag, September 2005.
• 17: Conal Elliott , Sigbjørn Finne , Oege De Moor, Compiling embedded languages, Journal of Functional Programming, v.13 n.3, p.455-481, May 2003 [doi>10.1017/S0956796802004574]
• 18: A. Filinski. Normalization by evaluation for the computational lambda-calculus. In S. Abramsky, editor, Proceedings of the International Conference on Typed Lambda Calculi and Applications (TLCA '01), volume 2044 of Lecture Notes in Computer Science, pages 151--165. Springer-Verlag, May 2001.
• 19: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.237-247, June 21-25, 1993, Albuquerque, New Mexico, United States
• 20: Matteo Frigo, A fast Fourier transform compiler, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.169-180, May 01-04, 1999, Atlanta, Georgia, United States
• 21: William L. Harrison , Samuel N. Kamin, Modular Compilers Based on Monad Transformers, Proceedings of the 1998 International Conference on Computer Languages, p.122, May 14-16, 1998
• 22: John Hatcliff , Olivier Danvy, A computational formalization for partial evaluation, Mathematical Structures in Computer Science, v.7 n.5, p.507-541, October 1997 [doi>10.1017/S0960129597002405]
• 23: Carsten Kehler Holst , Darsten Krogh Gomard, Partial evaluation is fuller laziness, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.223-233, June 17-19, 1991, New Haven, Connecticut, United States
• 24: John Hughes, Generalising monads to arrows, Science of Computer Programming, v.37 n.1-3, p.67-111, May 2000 [doi>10.1016/S0167-6423(99)00023-4]
• 25: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 26: Oleg Kiselyov , Kedar N. Swadi , Walid Taha, A methodology for generating verified combinatorial circuits, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017794]
• 27: O. Kiselyov and W. Taha. Relating FFTW and split radix. In Z. Wu, M. Guo, C. Chen, and J. Bu, editors, Proceedings of the International Conference on Embedded Software and Systems (ICESS '04), volume 3605 of Lecture Notes in Computer Science. Springer-Verlag, Dec. 2004.
• 28: John Launchbury , Simon L. Peyton Jones, State in Haskell, Lisp and Symbolic Computation, v.8 n.4, p.293-341, Dec. 1995 [doi>10.1007/BF01018827]
• 29: Julia L. Lawall , Olivier Danvy, Continuation-based partial evaluation, Proceedings of the 1994 ACM conference on LISP and functional programming, p.227-238, June 27-29, 1994, Orlando, Florida, United States
• 30: Sheng Liang , Paul Hudak , Mark Jones, Monad transformers and modular interpreters, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-343, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199528]
• 31: Yanhong A. Liu , Scott D. Stoller, From recursion to iteration: what are the optimizations?, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.73-82, January 22-23, 2000, Boston, Massachusetts, United States
• 32: Yanhong A. Liu , Scott D. Stoller, Dynamic Programming via Static Incrementalization, Higher-Order and Symbolic Computation, v.16 n.1-2, p.37-62, March-June 2003 [doi>10.1023/A:1023068020483]
• 33: B. McAdam. Y in practical programs (extended abstract). Unpublished manuscript.
• 34: Nicholas McKay , Satnam Singh, Dynamic Specialisation of XC6200 FPGAs by Parial Evaluation, Proceedings of the 8th International Workshop on Field-Programmable Logic and Applications, From FPGAs to Computing Paradigm, p.298-307, August 31-September 03, 1998
• 35: MetaOCaml: A compiled, type-safe multi-stage programming language. Available online from http://www.metaocaml.org/.
• 36: E. Moggi, Computational lambda-calculus and monads, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.14-23, June 1989, Pacific Grove, California, United States
• 37: Eugenio Moggi, Notions of computation and monads, Information and Computation, v.93 n.1, p.55-92, July 1991 [doi>10.1016/0890-5401(91)90052-4]
• 38: E. Moggi and S. Fagorzi. A monadic multi-stage metalanguage. In A. Gordon, editor, Proceedings of Foundations of Software Science and Computation Structures (FOSSACS '03), volume 2620 of Lecture Notes in Computer Science. Springer-Verlag, Apr. 2003.
• 39: Flemming Nielson , Hanne Riis Nielson, Two-level functional languages, Cambridge University Press, New York, NY, 1992
• 40: Oregon Graduate Institute Technical Reports. P.O. Box 91000, Portland, OR 97291-1000, USA. Available online from http://www.cse.ogi.edu/tech-reports/.
• 41: Tim Sheard , Zine-el-abidine Benaissa , Emir Pasalic, DSL implementation using staging and monads, Proceedings of the 2nd conference on Domain-specific languages, p.81-94, October 03-06, 1999, Austin, Texas, United States
• 42: Michael Sperber , Peter Thiemann, The essence of LR parsing, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.146-155, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215579]
• 43: Eijiro Sumii , Naoki Kobayashi, A Hybrid Approach to Online and Offline Partial Evaluation, Higher-Order and Symbolic Computation, v.14 n.2-3, p.101-142, September 2001 [doi>10.1023/A:1012984529382]
• 44: Walid Mohamed Taha , Tim Sheard, Multistage programming: its theory and applications, 1999
• 45: Walid Taha, A sound reduction semantics for untyped CBN mutli-stage computation. Or, the theory of MetaML is non-trival (extended abstract), Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.34-43, January 22-23, 2000, Boston, Massachusetts, United States
• 46: Walid Taha, ‘Semantics, Applications, and Implementation of Program Generation’, Journal of Functional Programming, v.13 n.3, p.453-454, May 2003 [doi>10.1017/S0956796802004677]
• 47: Walid Taha , Michael Florentin Nielsen, Environment classifiers, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.26-37, January 15-17, 2003, New Orleans, Louisiana, USA
• 48: Walid Taha , Tim Sheard, Multi-stage programming with explicit annotations, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.203-217, June 12-13, 1997, Amsterdam, The Netherlands
• 49: P. Thiemann. Continuation-based partial evaluation without continuations. In R. Cousot, editor, Proceedings of the International Symposium on Static Analysis (SAS '03), volume 2694 of Lecture Notes in Computer Science, pages 366--382. Springer-Verlag, 2003.
• 50: Philip Wadler, The essence of functional programming, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143169]
• 51: Daniel Weise , Roland Conybeare , Erik Ruf , Scott Seligman, Automatic online partial evaluation, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.165-191, June 1991, Cambridge, Massachusetts, United States

INDEX TERMS

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

Keywords:
code duplication, fixed points, monads, multi-stage programming, partial evaluation, program generation, program specialization, staging