Hostname: page-component-6b989bf9dc-llglr Total loading time: 0 Render date: 2024-04-15T03:36:41.684Z Has data issue: false hasContentIssue false
  • English
  • Français

Shifting the stage

Staging with delimited control

Part of: JFP Research Articles

Published online by Cambridge University Press:  23 November 2011

YUKIYOSHI KAMEYAMA ,
OLEG KISELYOV  and
CHUNG-CHIEH SHAN
YUKIYOSHI KAMEYAMA
Affiliation:
Department of Computer Science, University of Tsukuba (e-mail: kameyama@acm.org)
OLEG KISELYOV
Affiliation:
Monterey, CA, USA (e-mail: oleg@okmij.org)
CHUNG-CHIEH SHAN
Affiliation:
Cornell University (e-mail: ccshan@post.harvard.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

It is often hard to write programs that are efficient yet reusable. For example, an efficient implementation of Gaussian elimination should be specialized to the structure and known static properties of the input matrix. The most profitable optimizations, such as choosing the best pivoting or memoization, cannot be expected of even an advanced compiler because they are specific to the domain, but expressing these optimizations directly makes for ungainly source code. Instead, a promising and popular way to reconcile efficiency with reusability is for a domain expert to write code generators.

Two pillars of this approach are types and effects. Typed multilevel languages such as MetaOCaml ensure safety and early error reporting: a well-typed code generator neither goes wrong nor generates code that goes wrong. Side effects such as state and control ease correctness and expressivity: An effectful generator can resemble the textbook presentation of an algorithm, as is familiar to domain experts, yet insert let for memoization and if for bounds checking, as is necessary for efficiency. Together, types and effects enable structuring code generators as compositions of modules with well-defined interfaces, and hence scaling to large programs. However, blindly adding effects renders multilevel types unsound.

We introduce the first multilevel calculus with control effects and a sound type system. We give small-step operational semantics as well as a one-pass continuation-passing-style translation. For soundness, our calculus restricts the code generator's effects to the scope of generated binders. Even with this restriction, we can finally write efficient code generators for dynamic programming and numerical methods in direct style, like in algorithm textbooks, rather than in continuation-passing or monadic style.

Type
Articles
Information
Journal of Functional Programming , Volume 21 , Issue 6 , November 2011 , pp. 617 - 662
Copyright
Copyright © Cambridge University Press 2011

References

Asai, K. (2009) On typing delimited continuations: Three new solutions to the printf problem. Higher-Order Symb. Comput. 22 (3), 275–291.CrossRefGoogle Scholar
Asai, K. & Kameyama, Y. (2007) Polymorphic delimited continuations. In Proceedings of APLAS'07, LNCS, vol. 4807, pp. 239–254.CrossRefGoogle Scholar
Balat, V., Di Cosmo, R. & Fiore, M. P. (2004) Extensional normalisation and type-directed partial evaluation for typed lambda calculus with sums. In Proceedings of Annual Symposium on Principles of Programming Languages (POPL), pp. 64–76.CrossRefGoogle Scholar
Bondorf, A. (1992). Improving binding times without explicit CPS-conversion. In Proceedings of LISP & Functional Programming, pp. 1–10.CrossRefGoogle Scholar
Bondorf, A. & Danvy, O. (1991) Automatic autoprojection of recursive equations with global variables and abstract data types. Sci. Comput. Program. 16 (2), 151–195.CrossRefGoogle Scholar
Calcagno, C., Moggi, E. & Taha, W. (2000) Closed types as a simple approach to safe imperative multi-stage programming. In Proceedings of ICALP, LNCS, vol. 1853, pp. 25–36.CrossRefGoogle Scholar
Calcagno, C., Moggi, E. & Taha, W. (2004) ML-like inference for classifiers. In Proceedings of ESOP, LNCS, vol. 2986, pp. 79–93.CrossRefGoogle Scholar
Carette, J. (2006) Gaussian Elimination: A case study in efficient genericity with MetaOCaml. Sci. Comput. Program. 62 (1), 3–24 (special issue on the First MetaOCaml Workshop 2004).CrossRefGoogle Scholar
Carette, J. & Kiselyov, O. (2011) Multi-stage programming with functors and monads: Eliminating abstraction overhead from generic code. Sci. Comput. Program. 76 (5), 349–375.CrossRefGoogle Scholar
Choi, W., Aktemur, B., Yi, K. & Tatsuta, M. (2011) Static analysis of multi-staged programs via unstaging translation. In Proceedings of POPL '11: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, Ball, T. & Sagiv, M. (eds). New York: ACM Press, pp. 81–92.Google Scholar
Cohen, A., Donadio, S., Garzarán, M. J., Herrmann, C. A., Kiselyov, O. & Padua, D. A. (2006) In search of a program generator to implement generic transformations for high-performance computing. Sci. Comput. Program. 62 (1), 25–46.CrossRefGoogle Scholar
Czarnecki, K., O'Donnell, J. T., Striegnitz, J. & Taha, W. (2004) DSL implementation in MetaOCaml, Template Haskell, and C++. In Proceedings of DSPG 2003, LNCS, vol. 3016, pp. 51–72.CrossRefGoogle Scholar
Danvy, O. (1998) Functional unparsing. J. Funct. Program. 8 (6), 621–625.CrossRefGoogle Scholar
Danvy, O. & Filinski, A. (1989) A Functional Abstraction of Typed Contexts. typeTech. Rep. 89/12, institutionDIKU, University of Copenhagen, Denmark. Available at: http://www.daimi.au.dk/~danvy/Papers/fatc.ps.gz Accessed 8 November 2011.Google Scholar
Danvy, O. & Filinski, A. (1990) Abstracting control. In Proceedings of LISP & Functional Programming, Nice, France, June 1990, pp. 151–160.Google Scholar
Danvy, O. & Filinski, A. (1992) Representing control: A study of the CPS transformation. Math. Struct. Comput. Sci. 2 (4), 361–391.CrossRefGoogle Scholar
Davies, R. (1996) A temporal logic approach to binding-time analysis. In Proceedings of LICS, New Brunswick, New Jersey, July 27–30, pp. 184–195.Google Scholar
Davies, R. & Pfenning, F. (2001) A modal analysis of staged computation. J. ACM 48 (3), 555–604.CrossRefGoogle Scholar
Dussart, D. & Thiemann, P. (1996). Imperative Functional Specialization. typeTech. Rep. WSI-96-28. institutionUniversität Tübingen.Google Scholar
Eckhardt, J., Kaiabachev, R., Pašalić, E., Swadi, K. N. & Taha, W. (2005) Implicitly heterogeneous multi-stage programming. In Proceedings of GPCE, LNCS, vol. 3676, pp. 275–292.CrossRefGoogle Scholar
Elliott, C. (2004) Programming graphics processors functionally. In Proceedings of Haskell Workshop, Snowbird, UT, USA, September 22, pp. 45–56.Google Scholar
Felleisen, M. (1991) On the expressive power of programming languages. Sci. Comput. Program. 17 (1–3), 35–75.CrossRefGoogle Scholar
Felleisen, M., Friedman, D. P., Kohlbecker, E. E. & Duba, B. F.. (1986) Reasoning with continuations. In Proceedings of the 1st Symposium on Logic in Computer Science, Cambridge, MA, USA, June 16–18, pp. 131–141.Google Scholar
Filinski, A. (1994) Representing monads. In Proceedings of POPL, Portland, Oregon, USA, January 17–21, pp. 446–457.Google Scholar
Fluet, M. & Morrisett, J. G. (2006) Monadic regions. J. Funct. Program. 16 (4–5), 485–545.CrossRefGoogle Scholar
Frigo, M. & Johnson, S. G. (2005) The design and implementation of FFTW3. Proc. IEEE 93 (2), 216–231.CrossRefGoogle Scholar
Ganz, S. E. (2006). Encapsulation of State with Monad Transformers. Ph.D. thesis, Computer Science Department, Indiana University.Google Scholar
Gomard, C. K. & Jones, N. D. (1991) A partial evaluator for the untyped lambda calculus. J. Funct. Program. 1 (1), 21–69.CrossRefGoogle Scholar
Hammond, K. & Michaelson, G. (2003) Hume: A domain-specific language for real-time embedded systems. In Proceedings of GPCE, LNCS, vol. 2830, pp. 37–56.CrossRefGoogle Scholar
Igarashi, A. & Iwaki, M. (2007) Deriving compilers and virtual machines for a multi-level language. In Proceedings of APLAS, LNCS, vol. 4807, pp. 206–221.CrossRefGoogle Scholar
Kagawa, K. (2001) Monadic encapsulation with stack of regions. In Proceedings of FLOPS, LNCS, vol. 2024, pp. 264–279.CrossRefGoogle Scholar
Kameyama, Y., Kiselyov, O. & Shan, C.-c. (2008) Closing the stage: From staged code to typed closures. In Proceedings of PEPM, San Francisco, CA, USA, pp. 147–157.CrossRefGoogle Scholar
Kameyama, Y., Kiselyov, O. & Shan, C.-c. (2009) Shifting the stage: Staging with delimited control. In Proceedings of PEPM. New York: ACM Press, pp. 111–120.CrossRefGoogle Scholar
Kameyama, Y., Kiselyov, O. & Shan, C.-c. (2010) Mechanizing multilevel metatheory with control effects. In Proceedings of 5th ACM SIGPLAN Workshop on Mechanizing Metatheory. Available at: http://www.cis.upenn.edu/~bcpierce/wmm/wmm10-program.html Accessed 8 November 2011.Google Scholar
Kamin, S. (1996) Standard ML as a meta-programming language. Available at: http://loome.cs.uiuc.edu/pubs.html Accessed 8 November 2011.Google Scholar
Kiselyov, O. (2010) Delimited control in OCaml, abstractly and concretely: System description. In Proceedings of FLOPS, LNCS, vol. 6009, pp. 304–320. Extended version to appear in Theor. Comput. Sci.CrossRefGoogle Scholar
Kiselyov, O., Shan, C.-c. & Sabry, A. (2006) Delimited dynamic binding. In Proceedings of ICFP, Portland, OR, USA, pp. 26–37.Google Scholar
Kiselyov, O. & Taha, W. (2005) Relating FFTW and split-radix. In Proceedings of ICESS, LNCS, vol. 3605, pp. 488–493.CrossRefGoogle Scholar
Lawall, J. L. & Danvy, O. (1994) Continuation-based partial evaluation. In Proceedings of LISP & Functional Programming, Austin, TX, USA, August 5–8, pp. 227–238.Google Scholar
Lengauer, C. & Taha, W. (eds). (2006) Special issue on the 1st MetaOCaml workshop (2004), Sci. Comput. Program. 62 (1).Google Scholar
Leone, M. & Lee, P. (1998) Dynamic specialization in the Fabius system. ACM Comput. Surv, 30(3es), article 23:1–23:6.CrossRefGoogle Scholar
Leroy, X. & Pessaux, F. (2000) Type-based analysis of uncaught exceptions. ACM Tran. Prog. Lang. Syst. 22 (2), 340–377.CrossRefGoogle Scholar
Masuko, M. & Asai, K. (2009) Direct implementation of shift and reset in the MinCaml compiler. In Proceedings of ACM SIGPLAN Workshop on ML. New York: ACM Press, pp. 49–60.Google Scholar
McAdam, B. J. (2001) Y in practical programs. Proceedings of Workshop on Fixed Points in Computer Science. Available at: http://www.dsi.uniroma1.it/~labella/absMcAdam.ps Accessed 8 November 2011.Google Scholar
MetaOCaml, . (2006) MetaOCaml. Available at: http://www.metaocaml.org Accessed 8 November 2011.Google Scholar
Michie, D. (1968) “Memo” functions and machine learning. Nature 218: 19–22.CrossRefGoogle Scholar
Minsky, Y. (2008) Bind without tears. Available at: http://ocaml.janestreet.com/?q=node/23 Accessed 8 November 2011.Google Scholar
Moreau, L. (1998) A syntactic theory of dynamic binding. Higher-Order Symb. Comput. 11 (3), 233–279.CrossRefGoogle Scholar
Morrisett, J. G. (1993) Refining first-class stores. In Proceedings of the ACM SIGPLAN Workshop on State in Programming Languages, pp. 73–87.Google Scholar
Nielson, F. & Nielson, H. R. (1988) Automatic binding time analysis for a typed λ-calculus. In Proceedings of POPL, San Diego, CA, USA, pp. 98–106.Google Scholar
Parigot, M. (1992) λμ-calculus: An algorithmic interpretation of classical natural deduction. In Proceedings of LPAR, LNAI, vol. 624, pp. 190–201.CrossRefGoogle Scholar
Pašalić, E., Taha, W. & Sheard, T. (2002) Tagless staged interpreters for typed languages. In Proceedings of ICFP, pp. 157–166.CrossRefGoogle Scholar
Peyton Jones, S. L. (2003) The Haskell 98 language and libraries. J. Funct. Program. 13 (1), 1–255.Google Scholar
Püschel, M., Moura, J. M. F., Johnson, J., Padua, D., Veloso, M., Singer, B. W., Xiong, J., Franchetti, F., Gačić, A., Voronenko, Y., Chen, K., Johnson, R. W. & Rizzolo, N. (2005) SPIRAL: Code generation for DSP transforms. Proc. IEEE 93 (2), 232–275.CrossRefGoogle Scholar
Sørensen, M. H. B., Glück, R. & Jones, N. D. (1994) Towards unifying deforestation, supercompilation, partial evaluation, and generalized partial computation. In Proceedings of ESOP, LNCS, vol. 788, pp. 485–500.Google Scholar
Sumii, E. and Kobayashi, N. (2001) A hybrid approach to online and offline partial evaluation. Higher-Order Symb. Comput. 14 (2–3), 101–142.CrossRefGoogle Scholar
Swadi, K., Taha, W. & Kiselyov, O. (2005) Dynamic programming benchmark. Available at: http://www.metaocaml.org/examples/dp/ Accessed 8 November 2011.Google Scholar
Swadi, K., Taha, W., Kiselyov, O. & Pašalić, E. (2006) A monadic approach for avoiding code duplication when staging memoized functions. In Proceedings of PEPM, Charleston, SC, USA, January 9–10, pp. 160–169.CrossRefGoogle Scholar
Taha, W. (2000). A sound reduction semantics for untyped CBN multi-stage computation. In Proceedings of PEPM, Boston, MA, USA, pp. 34–43.Google Scholar
Taha, W. (2005) Resource-aware programming. In Proceedings of ICESS, LNCS, vol. 3605, pp. 38–43.CrossRefGoogle Scholar
Taha, W. & Nielsen, M. F. (2003) Environment classifiers. In Proceedings of POPL, New Orleans, LA, USA, January 15–17, pp. 26–37.CrossRefGoogle Scholar
Talpin, J.-P. & Jouvelot, P. (1992) Polymorphic type, region and effect inference. J. Funct. Program. 2 (3), 245–271.CrossRefGoogle Scholar
Thielecke, H. (2003) From control effects to typed continuation passing. In Proceedings of POPL, New Orleans, LA, USA, January 15–17, pp. 139–149.CrossRefGoogle Scholar
Thiemann, P. (1999) Combinators for program generation. J. Funct. Program. 9 (5), 483–525.CrossRefGoogle Scholar
Thiemann, P. & Dussart, D. (1999) Partial evaluation for higher-order languages with state. Available at: http://www.informatik.uni-freiburg.de/~thiemann/papers/mlpe.ps.gz Accessed 8 November 2011.Google Scholar
Tofte, M., Birkedal, L., Elsman, M. & Hallenberg, N. (2004) A retrospective on region-based memory management. Higher-Order Symb. Comput. 17 (3), 245–265.CrossRefGoogle Scholar
Wadler, P. L. (1992) Comprehending monads. Math. Struct. Comput. Sci. 2 (4), 461–493.CrossRefGoogle Scholar
Whaley, R. C. & Petitet, A. (2005) Minimizing development and maintenance costs in supporting persistently optimized BLAS. Softw. Pract. Exp. 35 (2), 101–121.CrossRefGoogle Scholar
Supplementary material: File

Kameyama Supplementary Material

Kameyama Supplementary Material

Download Kameyama Supplementary Material(File)
File 60.5 KB
Submit a response

Discussions

No Discussions have been published for this article.