{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T02:10:52Z","timestamp":1769047852212,"version":"3.49.0"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2009,10]]},"abstract":"<jats:p>\n            Recent work on adaptive functional programming (AFP) developed techniques for writing programs that can respond to modifications to their data by performing\n            <jats:italic>change propagation<\/jats:italic>\n            . To achieve this, executions of programs are represented with\n            <jats:italic>dynamic dependence graphs<\/jats:italic>\n            (DDGs) that record data dependences and control dependences in a way that a change-propagation algorithm can update the computation as if the program were from scratch, by re-executing only the parts of the computation affected by the changes. Since change-propagation only re-executes parts of the computation, it can respond to certain incremental modifications asymptotically faster than recomputing from scratch, potentially offering significant speedups. Such asymptotic speedups, however, are rare: for many computations and modifications, change propagation is no faster than recomputing from scratch.\n          <\/jats:p>\n          <jats:p>In this article, we realize a duality between dynamic dependence graphs and memoization, and combine them to give a change-propagation algorithm that can dramatically increase computation reuse. The key idea is to use DDGs to identify and re-execute the parts of the computation that are affected by modifications, while using memoization to identify the parts of the computation that remain unaffected by the changes. We refer to this approach as self-adjusting computation. Since DDGs are imperative, but (traditional) memoization requires purely functional computation, reusing computation correctly via memoization becomes a challenge. We overcome this challenge with a technique for remembering and reusing not just the results of function calls (as in conventional memoization), but their executions represented with DDGs. We show that the proposed approach is realistic by describing a library for self-adjusting computation, presenting efficient algorithms for realizing the library, and describing and evaluating an implementation. Our experimental evaluation with a variety of applications, ranging from simple list primitives to more sophisticated computational geometry algorithms, shows that the approach is effective in practice: compared to recomputing from-scratch; self-adjusting programs respond to small modifications to their data orders of magnitude faster.<\/jats:p>","DOI":"10.1145\/1596527.1596530","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T18:28:31Z","timestamp":1257359311000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":53,"title":["An experimental analysis of self-adjusting computation"],"prefix":"10.1145","volume":"32","author":[{"given":"Umut A.","family":"Acar","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago"}]},{"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"Matthias","family":"Blume","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago"}]},{"given":"Robert","family":"Harper","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"Kanat","family":"Tangwongsan","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}]}],"member":"320","published-online":{"date-parts":[[2009,11,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/232627.232638"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480945.1480946"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328476"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_3"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 16th Annual European Symposium on Programming (ESOP).","author":"Acar U. A.","unstructured":"Acar , U. A. , Blume , M. , and Donham , J . 2007a. A consistent semantics of self-adjusting computation . In Proceedings of the 16th Annual European Symposium on Programming (ESOP). Acar, U. A., Blume, M., and Donham, J. 2007a. A consistent semantics of self-adjusting computation. In Proceedings of the 16th Annual European Symposium on Programming (ESOP)."},{"key":"e_1_2_1_7_1","unstructured":"Acar U. A. Ihler A. Mettu R. and S\u00fcmer O. 2007b. Adaptive Bayesian Inference. In Neural Information Processing Systems (NIPS).  Acar U. A. Ihler A. Mettu R. and S\u00fcmer O. 2007b. Adaptive Bayesian Inference. In Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.11.043"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1133993"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186632.1186634"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Acar U. A.","unstructured":"Acar , U. A. , Blelloch , G. E. , Harper , R. , Vittes , J. L. , and Woo , M . 2004. Dynamizing static algorithms with applications to dynamic trees and history independence . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM , New York. Acar, U. A., Blelloch, G. E., Harper, R., Vittes, J. L., and Woo, M. 2004. Dynamizing static algorithms with applications to dynamic trees and history independence. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM, New York."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604133"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/503272.503296"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/592642.592647"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_24"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Alstrup S. Holm J. de Lichtenberg K. and Thorup M. 1997. Minimizing diameters of dynamic trees. In Automata Languages and Programming 270--280.   Alstrup S. Holm J. de Lichtenberg K. and Thorup M. 1997. Minimizing diameters of dynamic trees. In Automata Languages and Programming 270--280.","DOI":"10.1007\/3-540-63165-8_184"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0988"},{"key":"e_1_2_1_20_1","volume-title":"Dynamic Programming","author":"Bellman R.","unstructured":"Bellman , R. 1957. Dynamic Programming . Princeton University Press , Princeton, NJ . Bellman, R. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 10th European Symposium on Algorithms (ESA","volume":"2461","author":"Bender M. A.","year":"2002","unstructured":"Bender , M. A. , Cole , R. , Demaine , E. D. , Farach-Colton , M. , and Zito , J . 2002. Two simplified algorithms for maintaining order in a list . In Proceedings of the 10th European Symposium on Algorithms (ESA 2002 ). Lecture Notes in Computer Science , vol. 2461 , 219--223. Bender, M. A., Cole, R., Demaine, E. D., Farach-Colton, M., and Zito, J. 2002. Two simplified algorithms for maintaining order in a list. In Proceedings of the 10th European Symposium on Algorithms (ESA 2002). Lecture Notes in Computer Science, vol. 2461, 219--223."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0869"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Boissonnat J.-D. and Yvinec M. 1998. Algorithmic Geometry. Cambridge Press.   Boissonnat J.-D. and Yvinec M. 1998. Algorithmic Geometry. Cambridge Press.","DOI":"10.1017\/CBO9781139172998"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 43 rd Annual IEEE Symposium on Foundations of Computer Science. 617--626","author":"Brodal G. S.","unstructured":"Brodal , G. S. and Jacob , R . 2002. Dynamic planar convex hull . In Proceedings of the 43 rd Annual IEEE Symposium on Foundations of Computer Science. 617--626 . Brodal, G. S. and Jacob, R. 2002. Dynamic planar convex hull. In Proceedings of the 43 rd Annual IEEE Symposium on Foundations of Computer Science. 617--626."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/581478.581482"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712873"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796513"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163409"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Cohen R. F.","unstructured":"Cohen , R. F. and Tamassia , R . 1991. Dynamic expression trees and their applications . In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 52--61. Cohen, R. F. and Tamassia, R. 1991. Dynamic expression trees and their applications. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 52--61."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/567532.567544"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28434"},{"key":"e_1_2_1_33_1","volume-title":"Readings in Nonmonotonic Reasoning, Morgan Kaufmann","author":"Doyle J.","unstructured":"Doyle , J. 1987. A truth maintenance system . In Readings in Nonmonotonic Reasoning, Morgan Kaufmann , Palo Alto, CA , 259--279. Doyle, J. 1987. A truth maintenance system. In Readings in Nonmonotonic Reasoning, Morgan Kaufmann, Palo Alto, CA, 259--279."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Eppstein D. Galil Z. and Italiano G. F. 1999. Dynamic graph algorithms. In Algorithms and Theory of Computation Handbook CRC Press Ch. 8.  Eppstein D. Galil Z. and Italiano G. F. 1999. Dynamic graph algorithms. In Algorithms and Theory of Computation Handbook CRC Press Ch. 8.","DOI":"10.1201\/9781420049503-c9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/91556.91679"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0835"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90045-2"},{"key":"e_1_2_1_41_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Guibas L.","unstructured":"Guibas , L. 2004. Modeling motion . In Handbook of Discrete and Computational Geometry , 2 nd ed., J. Goodman and J. O'Rourke, Eds . Chapman and Hall\/CRC , 1117--1134. Guibas, L. 2004. Modeling motion. In Handbook of Discrete and Computational Geometry, 2nd ed., J. Goodman and J. O'Rourke, Eds. Chapman and Hall\/CRC, 1117--1134.","edition":"2"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997846"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics (WAFR'98)","author":"Guibas L. J.","year":"1998","unstructured":"Guibas , L. J. 1998 . Kinetic data structures: A state of the art report . In Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics (WAFR'98) . 191--209. Guibas, L. J. 1998. Kinetic data structures: A state of the art report. In Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics (WAFR'98). 191--209."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375634.1375642"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542480"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97)","author":"Henzinger M. R.","unstructured":"Henzinger , M. R. and King , V . 1997. Maintaining minimum spanning trees in dynamic graphs . In Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97) . Springer, Berlin, 594--604. Henzinger, M. R. and King, V. 1997. Maintaining minimum spanning trees in dynamic graphs. In Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97). Springer, Berlin, 594--604."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349341"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_51_1","volume-title":"Garbage Collection: Algorithms for Automatic Dynamic Memory Management","author":"Jones R. E.","year":"1996","unstructured":"Jones , R. E. 1996 . Garbage Collection: Algorithms for Automatic Dynamic Memory Management . Wiley , New York . (With a chapter on distributed garbage collection by R. Lins.) Jones, R. E. 1996. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, New York. (With a chapter on distributed garbage collection by R. Lins.)"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215021"},{"key":"e_1_2_1_53_1","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1998. The Art of Computer Programming: Sorting and Searching , vol. 3 , 2 nd ed. Addison-Wesley , Ch . 6, 481--489. Knuth, D. E. 1998. The Art of Computer Programming: Sorting and Searching, vol. 3, 2nd ed. Addison-Wesley, Ch. 6, 481--489.","edition":"2"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480907"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411204.1411249"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/291889.291895"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 8th National Conference on Artificial Intelligence. 1109--1116","author":"McAllester D.","year":"1990","unstructured":"McAllester , D. 1990 . Truth maintenance . In Proceedings of the 8th National Conference on Artificial Intelligence. 1109--1116 . McAllester, D. 1990. Truth maintenance. In Proceedings of the 8th National Conference on Artificial Intelligence. 1109--1116."},{"key":"e_1_2_1_58_1","volume-title":"A basis for a mathematical theory of computation","author":"McCarthy J.","unstructured":"McCarthy , J. 1963. A basis for a mathematical theory of computation . In Computer Programming and Formal Systems, P. Braffort and D. Hirschberg, Eds. North-Holland, Amsterdam , 33--70. McCarthy, J. 1963. A basis for a mathematical theory of computation. In Computer Programming and Formal Systems, P. Braffort and D. Hirschberg, Eds. North-Holland, Amsterdam, 33--70."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1038\/218019a0"},{"key":"e_1_2_1_60_1","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"Mulmuley K.","year":"1994","unstructured":"Mulmuley , K. 1994 . Computational Geometry: An Introduction Through Randomized Algorithms . Prentice Hall, Englewood Cliffs , NJ. Mulmuley, K. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90012-X"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75305"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297144"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158710"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/582153.582172"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.11.006"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.47"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250770"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(77)90029-7"},{"key":"e_1_2_1_74_1","volume-title":"Conference Record of the 18th Annual ACM Symposium on Principles of Programming Languages. ACM","author":"Sundaresh R. S.","unstructured":"Sundaresh , R. S. and Hudak , P . 1991. Incremental compilation via partial evaluation . In Conference Record of the 18th Annual ACM Symposium on Principles of Programming Languages. ACM , New York, 1--13. Sundaresh, R. S. and Hudak, P. 1991. Incremental compilation via partial evaluation. In Conference Record of the 18th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, 1--13."},{"key":"e_1_2_1_75_1","first-page":"80","volume-title":"Proceeding of the 6th Workshop on Experimental Algorithms (WEA'07)","author":"Tarjan R.","unstructured":"Tarjan , R. and Werneck , R . 2005a. Dynamic trees in practice . In Proceeding of the 6th Workshop on Experimental Algorithms (WEA'07) . 80 - 93 . Tarjan, R. and Werneck, R. 2005a. Dynamic trees in practice. In Proceeding of the 6th Workshop on Experimental Algorithms (WEA'07). 80-93."},{"key":"e_1_2_1_76_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms.","author":"Tarjan R.","unstructured":"Tarjan , R. and Werneck , R . 2005b. Self-adjusting top trees . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. Tarjan, R. and Werneck, R. 2005b. Self-adjusting top trees. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614369"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.26"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523195"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/103135.103137"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1596527.1596530","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1596527.1596530","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:32Z","timestamp":1750249412000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1596527.1596530"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":75,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1145\/1596527.1596530"],"URL":"https:\/\/doi.org\/10.1145\/1596527.1596530","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10]]},"assertion":[{"value":"2007-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}