research-article

Shifting the stage: staging with delimited control

Authors:

Yukiyoshi Kameyama,

Chung-chieh ShanAuthors Info & Claims

PEPM '09: Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation

Pages 111 - 120

https://doi.org/10.1145/1480945.1480962

Published: 19 January 2009 Publication History

Abstract

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_: a well-typed code generator neither goes wrong nor generates code that goes wrong. Side effects such as state and control ease correctness: 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. However, adding effects blindly renders multilevel types unsound.

We introduce the first two-level calculus with control effects and a sound type system. We give small-step operational semantics as well as a continuation-passing style (CPS) 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 CPS or monadic style.

References

[1]

Asai, Kenichi, and Yukiyoshi Kameyama. 2007. Polymorphic delimited continuations. In APLAS, 239--254. LNCS 4807.

Digital Library

[2]

Bondorf, Anders. 1992. Improving binding times without explicit CPS-conversion. In Lisp & functional programming, 1--10.

Digital Library

[3]

Bondorf, Anders, and Olivier Danvy. 1991. Automatic autoprojection of recursive equations with global variables and abstract data types. Science of Computer Programming 16(2):151--195.

Digital Library

[4]

Calcagno, Cristiano, Eugenio Moggi, and Walid Taha. 2000. Closed types as a simple approach to safe imperative multi-stage programming. In ICALP, 25--36. LNCS 1853.

Digital Library

[5]

Carette, Jacques, and Oleg Kiselyov. 2008. Multi-stage programming with functors and monads: Eliminating abstraction overhead from generic code. Science of Computer Programming.

Digital Library

[6]

Cohen, Albert, Sébastien Donadio, María Jesuós Garzarán, Christoph Armin Herrmann, Oleg Kiselyov, and David A. Padua. 2006. In search of a program generator to implement generic transformations for high--performance computing. Science of Computer Programming 62(1):25--46.

Digital Library

[7]

Czarnecki, Krzysztof, John T. O'Donnell, Jörg Striegnitz, and Walid Taha. 2004. DSL implementation in MetaOCaml, Template Haskell, and C++. In DSPG 2003, 51--72. LNCS 3016.

[8]

Danvy, Olivier, and Andrzej Filinski. 1989. A functional abstraction of typed contexts. Tech. Rep. 89/12, DIKU, University of Copenhagen, Denmark. http://www.daimi.au.dk/~danvy/Papers/fatc.ps.gz.

[9]

Danvy, Olivier. 1990. Abstracting control. In Lisp & functional program ming, 151--160.

Digital Library

[10]

Danvy, Olivier. 1992. Representing control: A study of the CPS transformation. Mathematical Structures in Computer Science 2(4): 361--391.

[11]

Davies, Rowan. 1996. A temporal logic approach to binding-time analysis. In LICS, 184--195.

Digital Library

[12]

Eckhardt, Jason, Roumen Kaiabachev, Emir Pašalic, Kedar N. Swadi, and Walid Taha. 2005. Implicitly heterogeneous multistage programming. In GPCE, 275--292. LNCS 3676.

Digital Library

[13]

Elliott, Conal. 2004. Programming graphics processors functionally. In Haskell workshop, 45--56.

Digital Library

[14]

Felleisen, Matthias, and Daniel P. Friedman. 1987. A reduction semantics for imperative higher-order languages. In PARLE: Parallel architectures and languages Europe. Volume II: Parallel languages, 206--223. LNCS 259.

Digital Library

[15]

Filinski, Andrzej. 1994. Representing monads. In POPL, 446--457.

Digital Library

[16]

Frigo, Matteo, and Steven G. Johnson. 2005. The design and implementation of FFTW3. Proceedings of the IEEE 93(2):216--231.

[17]

Gomard, Carsten K., and Neil D. Jones. 1991. A partial evaluator for the untyped lambda calculus. Journal of Functional Programming 1(1):21--69.

[18]

Hammond, Kevin, and Greg Michaelson. 2003. Hume: A domain-specific language for real-time embedded systems. In GPCE, 37--56. LNCS 2830.

Digital Library

[19]

Kameyama, Yukiyoshi, Oleg Kiselyov, and Chung-chieh Shan. 2008. Closing the stage: From staged code to typed closures. In PEPM, 147--157.

Digital Library

[20]

Kiselyov, Oleg. 2006. Native delimited continuations in (byte-code) OCaml. http://okmij.org/ftp/Computation/Continuations.html#caml-shift.

[21]

Kiselyov, Oleg, Chung-chieh Shan, and Amr Sabry. 2006. Delimited dynamic binding. In ICFP, 26--37.

Digital Library

[22]

Kiselyov, Oleg, and Walid Taha. 2005. Relating FFTW and split-radix. In ICESS, 488--493. LNCS 3605.

Digital Library

[23]

Lawall, Julia L., and Olivier Danvy. 1994. Continuation-based partial evaluation. In Lisp & functional programming, 227--238.

Digital Library

[24]

Lengauer, Christian, and Walid Taha, eds. 2006. Special issue on the 1st MetaOCaml workshop (2004), vol. 62(1) of Science of Computer Programming.

[25]

Leroy, Xavier, and François Pessaux. 2000. Type-based analysis of uncaught exceptions. ACM Transactions on Programming Languages and Systems 22(2):340--377.

Digital Library

[26]

McAdam, Bruce J. 2001. Y in practical programs. Workshop on fixed points in computer science; http://www.dsi.uniroma1.it/~labella/absMcAdam.ps.

[27]

MetaOCaml. 2006. MetaOCaml. http://www.metaocaml.org.

[28]

Michie, Donald. 1968. "Memo" functions and machine learning. Nature 218:19--22.

[29]

Moreau, Luc. 1998. A syntactic theory of dynamic binding. Higher-Order and Symbolic Computation 11(3):233--279.

Digital Library

[30]

Nielson, Flemming, and Hanne Riis Nielson. 1988. Automatic binding time analysis for a typed »-calculus. In POPL, 98--106.

Digital Library

[31]

Nielson, Flemming. 1992. Two-level functional languages. Cambridge University Press.

Digital Library

[32]

Parigot, Michel. 1992. »¼-calculus: An algorithmic interpretation of classical natural deduction. In LPAR, 190--201. LNAI 624.

Digital Library

[33]

Pušchel, Emir, Walid Taha, and Tim Sheard. 2002. Tagless staged interpreters for typed languages. In ICFP, 157--166.

[34]

Peyton Jones, Simon L. 2003. The Haskell 98 language and libraries. Journal of Functional Programming 13(1):1--255.

Digital Library

[35]

Pušchel, Markus, José M. F. Moura, Jeremy Johnson, David Padua, Manuela Veloso, Bryan W. Singer, Jianxin Xiong, Franz Franchetti, Aca Gačić, Yevgen Voronenko, Kang Chen, Robert W. Johnson, and Nick Rizzolo. 2005. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE 93(2): 232--275.

[36]

Sørensen, Morten Heine B., Robert Glück, and Neil D. Jones. 1994. Towards unifying deforestation, supercompilation, partial evaluation, and generalized partial computation. In ESOP, 485--500. LNCS 788.

[37]

Sumii, Eijiro, and Naoki Kobayashi. 2001. A hybrid approach to online and offline partial evaluation. Higher-Order and Symbolic Computation 14(2-3):101--142.

Digital Library

[38]

Swadi, Kedar, Walid Taha, and Oleg Kiselyov. 2005. Dynamic programming benchmark. http://www.metaocaml.org/examples/dp/

[39]

Swadi, Kedar, Walid Taha, Oleg Kiselyov, and Emir Pašalić. 2006. A monadic approach for avoiding code duplication when staging memoized functions. In PEPM, 160--169.

Digital Library

[40]

Taha, Walid. 2000. A sound reduction semantics for untyped CBN multi-stage computation. In PEPM, 34--43.

Digital Library

[41]

Taha, Walid. 2005. Resource-aware programming. In ICESS, 38--43. LNCS 3605.

Digital Library

[42]

Taha, Walid, and Michael Florentin Nielsen. 2003. Environment classifiers. In POPL, 26--37.

Digital Library

[43]

Talpin, Jean-Pierre, and Pierre Jouvelot. 1992. Polymorphic type, region and effect inference. Journal of Functional Programming 2(3):245--271.

[44]

Thielecke, Hayo. 2003. From control effects to typed continuation passing. In POPL, 139--149.

Digital Library

[45]

Thiemann, Peter. 1999. Combinators for program generation. Journal of Functional Programming 9(5):483--525.

Digital Library

[46]

Thiemann, Peter, and Dirk Dussart. 1999. Partial evaluation for higher-order languages with state. http://www.informatik.uni-freiburg.de/~thiemann/papers/mlpe.ps.gz.

[47]

Wadler, Philip L. 1992. Comprehending monads. Mathematical Structures in Computer Science 2(4):461--493.

Cited By

Brahmakshatriya AAmarasinghe S(2022)GraphIt to CUDA Compiler in 2021 LOC: A Case for High-Performance DSL Implementation via Staging with BuilDSL2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO53902.2022.9741280(53-65)Online publication date: 2-Apr-2022
https://doi.org/10.1109/CGO53902.2022.9741280
Brahmakshatriya AAmarasinghe SLee J(2021)BuildItProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370333(39-51)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370333
Stucki NBiboudis AOdersky M(2020)A practical unification of multi-stage programming and macrosACM SIGPLAN Notices10.1145/3393934.327813953:9(14-27)Online publication date: 7-Apr-2020
https://dl.acm.org/doi/10.1145/3393934.3278139
Show More Cited By

Index Terms

Shifting the stage: staging with delimited control
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
    2. General programming languages
      1. Language features
        Control structures
2. Theory of computation
  1. Formal languages and automata theory
  2. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Making monads first-class with template haskell
HASKELL '08

Monads as an organizing principle for programming and semantics are notoriously difficult to grasp, yet they are a central and powerful abstraction in Haskell. This paper introduces a domain-specific language, MonadLab, that simplifies the construction ...
On the expressive power of user-defined effects: effect handlers, monadic reflection, delimited control

We compare the expressive power of three programming abstractions for user-defined computational effects: Plotkin and Pretnar's effect handlers, Filinski's monadic reflection, and delimited control without answer-type-modification. This comparison ...
Liberating effects with rows and handlers
TyDe 2016: Proceedings of the 1st International Workshop on Type-Driven Development

Algebraic effects and effect handlers provide a modular abstraction for effectful programming. They support user-defined effects, as in Haskell, in conjunction with direct-style effectful programming, as in ML. They also present a structured interface ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '09: Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation

January 2009

208 pages

ISBN:9781605583273

DOI:10.1145/1480945

Program Chairs:
Germán Puebla
Technical University of Madrid, Spain
,
Germán Vidal
Technical University of Valencia, Spain

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 January 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PEPM '09

Sponsor:

PEPM '09: Partial Evaluation and Program Manipulation

January 19 - 20, 2009

GA, Savannah, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
262
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)6

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brahmakshatriya AAmarasinghe S(2022)GraphIt to CUDA Compiler in 2021 LOC: A Case for High-Performance DSL Implementation via Staging with BuilDSL2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO53902.2022.9741280(53-65)Online publication date: 2-Apr-2022
https://doi.org/10.1109/CGO53902.2022.9741280
Brahmakshatriya AAmarasinghe SLee J(2021)BuildItProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370333(39-51)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370333
Stucki NBiboudis AOdersky M(2020)A practical unification of multi-stage programming and macrosACM SIGPLAN Notices10.1145/3393934.327813953:9(14-27)Online publication date: 7-Apr-2020
https://dl.acm.org/doi/10.1145/3393934.3278139
Stucki NBiboudis AOdersky MVan Wyk ERompf T(2018)A practical unification of multi-stage programming and macrosProceedings of the 17th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3278122.3278139(14-27)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3278122.3278139
Cong YAsai K(2018)Handling delimited continuations with dependent typesProceedings of the ACM on Programming Languages10.1145/32367642:ICFP(1-31)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236764
Oishi JKameyama Y(2017)Staging with control: type-safe multi-stage programming with control operatorsACM SIGPLAN Notices10.1145/3170492.313604952:12(29-40)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3170492.3136049
Ge RGarcia R(2017)Refining semantics for multi-stage programmingACM SIGPLAN Notices10.1145/3170492.313604752:12(2-14)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3170492.3136047
Oishi JKameyama YFlatt MErdweg S(2017)Staging with control: type-safe multi-stage programming with control operatorsProceedings of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3136040.3136049(29-40)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136040.3136049
Ge RGarcia RFlatt MErdweg S(2017)Refining semantics for multi-stage programmingProceedings of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3136040.3136047(2-14)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136040.3136047
Kameyama YKiselyov OShan C(2015)Combinators for impure yet hygienic code generationScience of Computer Programming10.1016/j.scico.2015.08.007112(120-144)Online publication date: Nov-2015
https://doi.org/10.1016/j.scico.2015.08.007
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents