More Web Proxy on the site http://driver.im/

research-article

A cost semantics for self-adjusting computation

Authors:

Matthew FluetAuthors Info & Claims

POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 186 - 199

https://doi.org/10.1145/1480881.1480907

Published: 21 January 2009 Publication History

Abstract

Self-adjusting computation is an evaluation model in which programs can respond efficiently to small changes to their input data by using a change-propagation mechanism that updates computation by re-building only the parts affected by changes. Previous work has proposed language techniques for self-adjusting computation and showed the approach to be effective in a number of application areas. However, due to the complex semantics of change propagation and the indirect nature of previously proposed language techniques, it remains difficult to reason about the efficiency of self-adjusting programs and change propagation.

In this paper, we propose a cost semantics for self-adjusting computation that enables reasoning about its effectiveness. As our source language, we consider a direct-style λ-calculus with first-class mutable references and develop a notion of trace distance for source programs. To facilitate asymptotic analysis, we propose techniques for composing and generalizing concrete distances via trace contexts (traces with holes). We then show how to translate the source language into a self-adjusting target language such that the translation (1) preserves the extensional semantics of the source programs and the cost of from-scratch runs, and (2) ensures that change propagation between two evaluations takes time bounded by their relative distance. We consider several examples and analyze their effectiveness by considering upper and lower bounds.

References

[1]

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

[2]

Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Maverick Woo. Dynamizing static algorithms with applications to dynamic trees and history independence. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.

Digital Library

[3]

Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes. An experimental analysis of change propagation in dynamic trees. In Workshop on Algorithm Engineering and Experimentation (ALENEX), 2005.

[4]

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), 2006.

Digital Library

[5]

Umut A. Acar, Guy E. Blelloch, and Robert Harper. Adaptive functional programming. ACM Transactions on Programming Languages and Systems (TOPLAS), 28 (6): 990--1034, 2006.

Digital Library

[6]

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 2006.

Digital Library

[7]

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), 2008.

Digital Library

[8]

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 2008.

Digital Library

[9]

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

[10]

Pankaj K. Agarwal, Leonidas J. Guibas, Herbert Edelsbrunner, Jeff Erickson, Michael Isard, Sariel Har-Peled, John Hershberger, Christian Jensen, Lydia Kavraki, Patrice Koehl, Ming Lin, Dinesh Manocha, Dimitris Metaxas, Brian Mirtich, David Mount, S. Muthukrishnan, Dinesh Pai, Elisha Sacks, Jack Snoeyink, Subhash Suri, and Ouri Wolefson. Algorithmic issues in modeling motion. ACM Comput. Surv., 34 (4): 550--572, 2002.

Digital Library

[11]

Guy Blelloch and John Greiner. Parallelism in sequential functional languages. In FPCA '95: Proceedings of the seventh international conference on Functional programming languages and computer architecture, pages 226--237, 1995. ISBN 0-89791-719-7.

Digital Library

[12]

Guy E. Blelloch and John Greiner. A provable time and space efficient implementation of nesl. In ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programming, pages 213--225. ACM, 1996.

Digital Library

[13]

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

[14]

Y.-J. Chiang and R. Tamassia. Dynamic algorithms in computational geometry. Proceedings of the IEEE, 80 (9): 1412--1434, 1992.

[15]

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

[16]

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

[17]

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

[18]

David Eppstein, Zvi Galil, and Giuseppe F. Italiano. Dynamic graph algorithms. In Mikhail J. Atallah, editor, Algorithms and Theory of Computation Handbook, chapter 8. CRC Press, 1999.

[19]

Leonidas J. Guibas. Kinetic data structures: a state of the art report. In WAFR '98: Proceedings of the third workshop on the algorithmic foundations of robotics, pages 191--209, 1998.

Digital Library

[20]

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

Digital Library

[21]

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

[22]

Ruy Ley-Wild, Umut A. Acar, and Matthew Fluet. A Cost Semantics for Self-Adjusting Computation. Technical Report CMU-CS-08-141, Department of Computer Science, Carnegie Mellon University, July 2008.

Digital Library

[23]

Ruy Ley-Wild, Matthew Fluet, and Umut A. Acar. Compiling self-adjusting programs with continuations. In Proceedings of the International Conference on Functional Programming (ICFP), 2008.

Digital Library

[24]

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

[25]

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

[26]

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

[27]

Mads Rosendahl. Automatic complexity analysis. In FPCA '89: Proceedings of the fourth international conference on Functional programming languages and computer architecture, pages 144--156. ACM, 1989.

Digital Library

[28]

David Sands. Calculi for Time Analysis of Functional Programs. PhD thesis, University of London, Imperial College, September 1990.

[29]

David Sands. Complexity analysis for a lazy higher-order language. In ESOP '90: Proceedings of the 3rd European Symposium on Programming, pages 361--376. Springer-Verlag, 1990.

Digital Library

[30]

Patrick M. Sansom and Simon L. Peyton Jones. Time and space profiling for non-strict, higher-order functional languages. In POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 355--366, 1995.

Digital Library

[31]

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

[32]

Daniel Spoonhower, Guy E. Blelloch, Robert Harper, and Phillip B. Gibbons. Space profiling for parallel functional programs. In Proceedings of the International Conference on Functional Programming (ICFP), 2008.

Digital Library

[33]

Philip Wadler and R. J. M. Hughes. Projections for strictness analysis. In Proc. of Functional programming languages and computer architecture, pages 385--407. Springer-Verlag, 1987.

Digital Library

[34]

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

Quoc DKrishnan DBhatotia PFetzer CRodrigues R(2018)Incremental Approximate ComputingEncyclopedia of Big Data Technologies10.1007/978-3-319-63962-8_151-1(1-8)Online publication date: 1-Feb-2018
https://doi.org/10.1007/978-3-319-63962-8_151-1
Muller SAcar UHarper R(2017)Responsive parallel computation: bridging competitive and cooperative threadingACM SIGPLAN Notices10.1145/3140587.306237052:6(677-692)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062370
Muller SAcar UHarper RCohen AVechev M(2017)Responsive parallel computation: bridging competitive and cooperative threadingProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062370(677-692)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062370
Show More Cited By

Index Terms

A cost semantics for self-adjusting computation
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

A cost semantics for self-adjusting computation
POPL '09

Self-adjusting computation is an evaluation model in which programs can respond efficiently to small changes to their input data by using a change-propagation mechanism that updates computation by re-building only the parts affected by changes. Previous ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 2009

464 pages

ISBN:9781605583792

DOI:10.1145/1480881

General Chair:
Zhong Shao
Yale University, USA
,
Program Chair:
Benjamin C. Pierce
University of Pennsylvania, USA

ACM SIGPLAN Notices Volume 44, Issue 1
POPL '09
January 2009
453 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1594834
Issue’s Table of Contents

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: 21 January 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

self-adjusting computation

Qualifiers

Research-article

Conference

POPL09

Sponsor:

POPL09: The 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 21 - 23, 2009

GA, Savannah, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
379
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Quoc DKrishnan DBhatotia PFetzer CRodrigues R(2018)Incremental Approximate ComputingEncyclopedia of Big Data Technologies10.1007/978-3-319-63962-8_151-1(1-8)Online publication date: 1-Feb-2018
https://doi.org/10.1007/978-3-319-63962-8_151-1
Muller SAcar UHarper R(2017)Responsive parallel computation: bridging competitive and cooperative threadingACM SIGPLAN Notices10.1145/3140587.306237052:6(677-692)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062370
Muller SAcar UHarper RCohen AVechev M(2017)Responsive parallel computation: bridging competitive and cooperative threadingProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062370(677-692)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062370
Çiçek EParaskevopoulou ZGarg D(2016)A type theory for incremental computational complexity with control flow changesACM SIGPLAN Notices10.1145/3022670.295195051:9(132-145)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/3022670.2951950
Çiçek EParaskevopoulou ZGarg DGarrigue JKeller GSumii E(2016)A type theory for incremental computational complexity with control flow changesProceedings of the 21st ACM SIGPLAN International Conference on Functional Programming10.1145/2951913.2951950(132-145)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/2951913.2951950
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
Bhatotia PWieder AAcar URodrigues R(2014)Incremental MapReduce ComputationsLarge Scale and Big Data10.1201/b17112-5(127-150)Online publication date: 12-Jun-2014
https://doi.org/10.1201/b17112-5
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