research-article

Compiling self-adjusting programs with continuations

Authors:

Umut A. AcarAuthors Info & Claims

ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programming

Pages 321 - 334

https://doi.org/10.1145/1411204.1411249

Published: 20 September 2008 Publication History

Abstract

Self-adjusting programs respond automatically and efficiently to input changes by tracking the dynamic data dependences of the computation and incrementally updating the output as needed. In order to identify data dependences, previously proposed approaches require the user to make use of a set of monadic primitives. Rewriting an ordinary program into a self-adjusting program with these primitives, however, can be difficult and error-prone due to various monadic and proper-usage restrictions, some of which cannot be enforced statically. Previous work therefore suggests that self-adjusting computation would benefit from direct language and compiler support.

In this paper, we propose a language-based technique for writing and compiling self-adjusting programs from ordinary programs. To compile self-adjusting programs, we use a continuation-passing style (cps) transformation to automatically infer a conservative approximation of the dynamic data dependences. To prevent the inferred, approximate dependences from degrading the performance of change propagation, we generate memoized versions of cps functions that can reuse previous work even when they are invoked with different continuations. The approach offers a natural programming style that requires minimal changes to existing code, while statically enforcing the invariants required by self-adjusting computation.

We validate the feasibility of our proposal by extending Standard ML and by integrating the transformation into MLton, a whole-program optimizing compiler for Standard ML. Our experiments indicate that the proposed compilation technique can produce self-adjusting programs whose performance is consistent with the asymptotic bounds and experimental results obtained via manual rewriting (up to a constant factor).

Supplementary Material

JPG File (1411249.jpg)

Download
15.87 KB

index.html (index.html)

Slides from the presentation

Download
.97 KB

ZIP File (p321-slides.zip)

Supplemental material for: Compiling self-adjusting programs with continuations

Download
8.27 MB

Audio only (1411249.mp3)

Download
9.48 MB

Video (1411249.mp4)

Download
131.09 MB

References

[1]

MLton. http://mlton.org/.

[2]

Flapjax programming language. www.flapjax-lang.org.

[3]

Martín Abadi, Butler W. Lampson, and Jean-Jacques Lévy. Analysis and Caching of Dependencies. In Proceedings of the International Conference on Functional Programming (ICFP), pages 83--91, 1996.

Digital Library

[4]

Umut A. Acar, Guy E. Blelloch, and Robert Harper. Adaptive Functional Programming. In Proceedings of the 29th Annual ACM Symposium on Principles of Programming Languages, pages 247--259, 2002.

Digital Library

[5]

Umut A. Acar, Guy E. Blelloch, and Robert Harper. Selective memoization. In Proceedings of the 30th Annual ACM Symposium on Principles of Programming Languages (POPL), 2003.

Digital Library

[6]

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper, and Kanat Tangwongsan. A Library for Self-Adjusting Computation. Electronic Notes in Theoretical Computer Science, 148(2), 2006a.

Digital Library

[7]

Umut A. Acar, Guy E. Blelloch, Matthias Blume, and Kanat Tangwongsan. An experimental analysis of self-adjusting computation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2006b.

Digital Library

[8]

Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, and Jorge L. Vittes. Kinetic Algorithms via Self-Adjusting Computation. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pages 636--647, September 2006c.

Digital Library

[9]

Umut A. Acar, Alexander Ihler, Ramgopal Mettu, and Özgür Sümer. Adaptive Bayesian Inference. In Neural Information Processing Systems (NIPS), 2007.

[10]

Umut A. Acar, Amal Ahmed, and Matthias Blume. Imperative self-adjusting computation. In Proceedings of the 25th Annual ACM Symposium on Principles of Programming Languages (POPL), 2008a.

Digital Library

[11]

Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, and Duru Türkoglu. Robust Kinetic Convex Hulls in 3D. In Proceedings of the 16th Annual European Symposium on Algorithms (ESA), September 2008b.

Digital Library

[12]

Umut A. Acar, Alexander Ihler, Ramgopal Mettu, and Özgür Sümer. Adaptive Inference on General Graphical Models. In Uncertainty in Artificial Intelligence (UAI), 2008c.

[13]

C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. The Quickhull Algorithm for Convex Hulls. ACM Trans. Math. Softw., 22 (4): 469--483, 1996.

Digital Library

[14]

Richard Bellman. Dynamic Programming. Princeton University Press, 1957.

Digital Library

[15]

Kimberley Burchett, Gregory H. Cooper, and Shriram Krishnamurthi. Lowering: A Static Optimization Technique for Transparent Functional Reactivity. In PEPM '07: Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, pages 71--80. ACM, 2007.

Digital Library

[16]

Magnus Carlsson. Monads for Incremental Computing. In Proceedings of the 7th ACM SIGPLAN International Conference on Functional programming (ICFP), pages 26--35. ACM Press, 2002.

Digital Library

[17]

Gregory H. Cooper and Shriram Krishnamurthi. FrTime: Functional Reactive Programming in PLT Scheme. Technical Report CS-03-20, Department of Computer Science, Brown University, April 2004.

[18]

Gregory H. Cooper and Shriram Krishnamurthi. Embedding Dynamic Dataflow in a Call-by-Value Language. In Proceedings of the 15th Annual European Symposium on Programming (ESOP), 2006.

Digital Library

[19]

Antony Courtney. Frappé: Functional Reactive Programming in Java. In PADL '01: Proceedings of the Third International Symposium on Practical Aspects of Declarative Languages, pages 29--44. Springer-Verlag, 2001.

Digital Library

[20]

Olivier Danvy and John Hatcliff. CPS Transformation after Strictness Analysis. Letters on Programming Languages and Systems (LOPLS), 1 (3): 195--212, 1993a.

Digital Library

[21]

Olivier Danvy and John Hatcliff. On the Transformation between Direct and Continuation Semantics. In Proceedings of the Ninth Conference on Mathematical Foundations of Programming Semantics (MFPS), pages 627--648, 1993b.

Digital Library

[22]

Alan Demers, Thomas Reps, and Tim Teitelbaum. Incremental Evaluation of Attribute Grammars with Application to Syntax-directed Editors. In Proceedings of the 8th Annual ACM Symposium on Principles of Programming Languages, pages 105--116, 1981.

Digital Library

[23]

Conal Elliott. Functional Implementations of Continuous Modeled Animation. Lecture Notes in Computer Science, 1490: 284--299, 1998.

Digital Library

[24]

Conal Elliott and Paul Hudak. Functional Reactive Animation. In ICFP '97: Proceedings of the second ACM SIGPLAN international conference on Functional programming, pages 263--273. ACM, 1997.

Digital Library

[25]

Matthew Hammer and Umut A. Acar. Memory Management for Self-Adjusting Computation. In The 2008 International Symposium on Memory Management, 2008.

Digital Library

[26]

Fritz Henglein, Henning Makholm, and Henning Niss. Effect Types and Region-based Memory Management. In Benjamin Pierce, editor, Advanced Topics in Types and Programming Languages, chapter 3, pages 87--135. MIT Press, Cambridge, MA, 2005.

[27]

Allan Heydon, Roy Levin, and Yuan Yu. Caching Function Calls Using Precise Dependencies. In Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 311--320, 2000.

Digital Library

[28]

Jung-taek Kim and Kwangkeun Yi. Interconnecting Between CPS Terms and Non-CPS Terms. In Proceedings of the Third ACM SIGPLAN Workshop on Continuations (CW), pages 7--16, 2001.

[29]

Jung-taek Kim, Kwangkeun Yi, and Olivier Danvy. Assessing the Overhead of ML Exceptions. In Proceedings of the ACM SIGPLAN Workshop on ML, pages 112--119, 1998.

[30]

Yanhong A. Liu, Scott Stoller, and Tim Teitelbaum. Static Caching for Incremental Computation. ACM Transactions on Programming Languages and Systems, 20 (3): 546--585, 1998.

Digital Library

[31]

John McCarthy. A Basis for a Mathematical Theory of Computation. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems, pages 33--70. North-Holland, Amsterdam, 1963.

[32]

D. Michie. "Memo" Functions and Machine Learning. Nature, 218: 19--22, 1968.

[33]

Lasse Nielsen. A Selective CPS Transformation. In Proceedings of the Seventeenth Conference on the Mathematical Foundations of Programming Semantics (MFPS), volume 45 of Electronic Notes in Theoretical Computer Science (ENTCS), pages 311--331. Elsevier, November 2001.

[34]

Henrik Nilsson, Antony Courtney, and John Peterson. Functional Reactive Programming, Continued. In Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell'02), pages 51--64, Pittsburgh, Pennsylvania, USA, October 2002. ACM Press.

Digital Library

[35]

F. P. Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag Inc., 1985.

Digital Library

[36]

William Pugh and Tim Teitelbaum. Incremental computation via function caching. In Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages, pages 315--328, 1989.

Digital Library

[37]

G. Ramalingam and T. Reps. A Categorized Bibliography on Incremental Computation. In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages (POPL), pages 502--510, 1993.

Digital Library

[38]

Thomas Reps. Optimal-time incremental semantic analysis for syntax-directed editors. In Proceedings of the 9th Annual Symposium on Principles of Programming Languages (POPL), pages 169--176, 1982.

Digital Library

[39]

Ajeet Shankar and Rastislav Bodik. DITTO: Automatic Incrementalization of Data Structure Invariant Checks (in Java). In Proceedings of the ACM SIGPLAN 2007 Conference on Programming language Design and Implementation (PLDI), 2007.

Digital Library

[40]

Hayo Thielecke. Comparing Control Constructs by Double-barrelled CPS. Higher-Order and Symbolic Computation, 15 (2/3): 367--412, 2002.

Digital Library

[41]

D. M. Yellin and R. E. Strom. INC: A Language for Incremental Computations. ACM Transactions on Programming Languages and Systems, 13 (2): 211--236, April 1991.

Digital Library

Cited By

Dou XChen PFlinn JBrecht TWilliamson C(2019)ShortCutProceedings of the 27th ACM Symposium on Operating Systems Principles10.1145/3341301.3359659(570-585)Online publication date: 27-Oct-2019
https://dl.acm.org/doi/10.1145/3341301.3359659
Germane KMight M(2019)Relatively Complete Pushdown Analysis of Escape ContinuationsVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-11245-5_10(205-225)Online publication date: 11-Jan-2019
https://doi.org/10.1007/978-3-030-11245-5_10
Bhatotia PFonseca PAcar UBrandenburg BRodrigues R(2015)iThreadsACM SIGARCH Computer Architecture News10.1145/2786763.269437143:1(645-659)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2786763.2694371
Show More Cited By

Index Terms

Compiling self-adjusting programs with continuations
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

Imperative self-adjusting computation
POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Self-adjusting computation enables writing programs that can automatically and efficiently respond to changes to their data (e.g., inputs). The idea behind the approach is to store all data that can change over time in modifiable references and to let ...
Compiling self-adjusting programs with continuations
ICFP '08

Self-adjusting programs respond automatically and efficiently to input changes by tracking the dynamic data dependences of the computation and incrementally updating the output as needed. In order to identify data dependences, previously proposed ...
Imperative self-adjusting computation
POPL '08

Self-adjusting computation enables writing programs that can automatically and efficiently respond to changes to their data (e.g., inputs). The idea behind the approach is to store all data that can change over time in modifiable references and to let ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programming

September 2008

422 pages

ISBN:9781595939197

DOI:10.1145/1411204

General Chair:
James Hook
Portland State University, USA
,
Program Chair:
Peter Thiemann
Universität Freiburg, Germany

ACM SIGPLAN Notices Volume 43, Issue 9
ICFP '08
September 2008
399 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1411203
Issue’s Table of Contents

Copyright © 2008 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: 20 September 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP08

Sponsor:

ICFP08: ACM SIGPLAN International Conference on Functional Programming

September 20 - 28, 2008

BC, Victoria, Canada

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
431
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dou XChen PFlinn JBrecht TWilliamson C(2019)ShortCutProceedings of the 27th ACM Symposium on Operating Systems Principles10.1145/3341301.3359659(570-585)Online publication date: 27-Oct-2019
https://dl.acm.org/doi/10.1145/3341301.3359659
Germane KMight M(2019)Relatively Complete Pushdown Analysis of Escape ContinuationsVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-11245-5_10(205-225)Online publication date: 11-Jan-2019
https://doi.org/10.1007/978-3-030-11245-5_10
Bhatotia PFonseca PAcar UBrandenburg BRodrigues R(2015)iThreadsACM SIGARCH Computer Architecture News10.1145/2786763.269437143:1(645-659)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2786763.2694371
Bhatotia PFonseca PAcar UBrandenburg BRodrigues R(2015)iThreadsACM SIGPLAN Notices10.1145/2775054.269437150:4(645-659)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2775054.2694371
Bhatotia PFonseca PAcar UBrandenburg BRodrigues ROzturk OEbcioglu KDwarkadas S(2015)iThreadsProceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/2694344.2694371(645-659)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2694344.2694371
Çiçek EGarg DAcar U(2015)Refinement Types for Incremental Computational ComplexityProgramming Languages and Systems10.1007/978-3-662-46669-8_17(406-431)Online publication date: 2015
https://doi.org/10.1007/978-3-662-46669-8_17
Chen YDunfield JAcar U(2012)Type-directed automatic incrementalizationACM SIGPLAN Notices10.1145/2345156.225410047:6(299-310)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2345156.2254100
Chen YDunfield JAcar UVitek JLin HTip F(2012)Type-directed automatic incrementalizationProceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2254064.2254100(299-310)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2254064.2254100
Gorbovitski MLiu YStoller SRothamel TKiselyov OThompson S(2012)Composing transformations for instrumentation and optimizationProceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation10.1145/2103746.2103759(53-62)Online publication date: 23-Jan-2012
https://dl.acm.org/doi/10.1145/2103746.2103759
Ley-Wild RAcar UBlelloch G(2012)Non-monotonic self-adjusting computationProceedings of the 21st European conference on Programming Languages and Systems10.1007/978-3-642-28869-2_24(476-496)Online publication date: 24-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28869-2_24
Show More Cited By

View Options

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