{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T11:43:10Z","timestamp":1770291790990,"version":"3.49.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T00:00:00Z","timestamp":1162339200000},"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":[[2006,11]]},"abstract":"<jats:p>\n            We present techniques for incremental computing by introducing adaptive functional programming. As an\n            <jats:italic>adaptive<\/jats:italic>\n            program executes, the underlying system represents the data and control dependences in the execution in the form of a\n            <jats:italic>dynamic dependence graph<\/jats:italic>\n            . When the input to the program changes, a change propagation algorithm updates the output and the dynamic dependence graph by propagating changes through the graph and re-executing code where necessary. Adaptive programs adapt their output to any change in the input, small or large.We show that adaptivity techniques are practical by giving an efficient implementation as a small ML library. The library consists of three operations for making a program adaptive, plus two operations for making changes to the input and adapting the output to these changes. We give a general bound on the time it takes to adapt the output, and based on this, show that an adaptive Quicksort adapts its output in logarithmic time when its input is extended by one key.To show the safety and correctness of the mechanism we give a formal definition of AFL, a call-by-value functional language extended with adaptivity primitives. The modal type system of AFL enforces correct usage of the adaptivity mechanism, which can only be checked at run time in the ML library. Based on the AFL dynamic semantics, we formalize thechange-propagation algorithm and prove its correctness.\n          <\/jats:p>","DOI":"10.1145\/1186632.1186634","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"990-1034","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":70,"title":["Adaptive functional programming"],"prefix":"10.1145","volume":"28","author":[{"given":"Umut A.","family":"Acar","sequence":"first","affiliation":[{"name":"Toyota Technological Institute, Chicago, IL"}]},{"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Robert","family":"Harper","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]}],"member":"320","published-online":{"date-parts":[[2006,11]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"83","volume-title":"Proceedings of the International Conference on Functional Programming","author":"Abadi M.","unstructured":"Abadi , M. , Lampson , B. W. , and Levy , J . -J. 1996. Analysis and caching of dependencies . In Proceedings of the International Conference on Functional Programming , pp. 83 -- 91 .]] 10.1145\/232627.232638 Abadi, M., Lampson, B. W., and Levy, J.-J. 1996. Analysis and caching of dependencies. In Proceedings of the International Conference on Functional Programming, pp. 83--91.]] 10.1145\/232627.232638"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 30th Annual ACM Symposium on Principles of Programming Languages. ACM","author":"Acar U. A.","unstructured":"Acar , U. A. , Blelloch , G. E. , and Harper , R . 2003. Selective memoization . In Proceedings of the 30th Annual ACM Symposium on Principles of Programming Languages. ACM , New York.]] 10.1145\/604131.604133 Acar, U. A., Blelloch, G. E., and Harper, R. 2003. Selective memoization. In Proceedings of the 30th Annual ACM Symposium on Principles of Programming Languages. ACM, New York.]] 10.1145\/604131.604133"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 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 (SODA). 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 (SODA). ACM, New York.]]"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ACM SIGPLAN Workshop on ML. ACM","author":"Acar U. A.","unstructured":"Acar , U. A. , Blelloch , G. E. , Blume , M. , Harper , R. , and Tangwongsan , K . 2005a. A library for self-adjusting computation . In Proceedings of the ACM SIGPLAN Workshop on ML. ACM , New York.]] Acar, U. A., Blelloch, G. E., Blume, M., Harper, R., and Tangwongsan, K. 2005a. A library for self-adjusting computation. In Proceedings of the ACM SIGPLAN Workshop on ML. ACM, New York.]]"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experimentation. ACM","author":"Acar U. A.","unstructured":"Acar , U. A. , Blelloch , G. E. , and Vittes , J. L . 2005b. An experimental analysis of change propagation in dynamic trees . In Proceedings of the Workshop on Algorithm Engineering and Experimentation. ACM , New York.]] Acar, U. A., Blelloch, G. E., and Vittes, J. L. 2005b. An experimental analysis of change propagation in dynamic trees. In Proceedings of the Workshop on Algorithm Engineering and Experimentation. ACM, New York.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0988"},{"key":"e_1_2_1_8_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_9_1","first-page":"26","volume-title":"Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming. ACM","author":"Carlsson M.","year":"2002","unstructured":"Carlsson , M. 2002 . Monads for incremental computing . In Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming. ACM , New York , pp. 26 -- 35 .]] 10.1145\/581478.581482 Carlsson, M. 2002. Monads for incremental computing. In Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming. ACM, New York, pp. 26--35.]] 10.1145\/581478.581482"},{"key":"e_1_2_1_10_1","first-page":"105","volume-title":"Proceedings of the 8th Annual ACM Symposium on Principles of Programming Languages. ACM","author":"Demers A.","unstructured":"Demers , A. , Reps , T. , and Teitelbaum , T . 1981. Incremental evaluation of attribute grammars with application to syntax directed editors . In Proceedings of the 8th Annual ACM Symposium on Principles of Programming Languages. ACM , New York , pp. 105 -- 116 .]] 10.1145\/567532.567544 Demers, A., Reps, T., and Teitelbaum, T. 1981. Incremental evaluation of attribute grammars with application to syntax directed editors. In Proceedings of the 8th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, pp. 105--116.]] 10.1145\/567532.567544"},{"key":"e_1_2_1_11_1","first-page":"365","volume-title":"Proceedings of the 19th ACM Symposium on Theory of Computing. ACM","author":"Dietz P. F.","unstructured":"Dietz , P. F. and Sleator , D. D . 1987. Two algorithms for maintaining order in a list . In Proceedings of the 19th ACM Symposium on Theory of Computing. ACM , New York , pp. 365 -- 372 .]] 10.1145\/28395.28434 Dietz, P. F. and Sleator, D. D. 1987. Two algorithms for maintaining order in a list. In Proceedings of the 19th ACM Symposium on Theory of Computing. ACM, New York, pp. 365--372.]] 10.1145\/28395.28434"},{"key":"e_1_2_1_12_1","first-page":"67","volume-title":"Proceedings of the Workshop on Algorithms and Data Structures. (Aug.) Lecture Notes in Computer Science, Vol 382","author":"Dietz P. F.","year":"1989","unstructured":"Dietz , P. F. 1989 . Fully persistent arrays . In Proceedings of the Workshop on Algorithms and Data Structures. (Aug.) Lecture Notes in Computer Science, Vol 382 . Springer-Verlag, ACM, New York , pp. 67 -- 74 .]] Dietz, P. F. 1989. Fully persistent arrays. In Proceedings of the Workshop on Algorithms and Data Structures. (Aug.) Lecture Notes in Computer Science, Vol 382. Springer-Verlag, ACM, New York, pp. 67--74.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.185791"},{"key":"e_1_2_1_15_1","first-page":"307","volume-title":"Proceedings of the ACM '90 Conference on LISP and Functional Programming. (June). ACM","author":"Field J.","unstructured":"Field , J. and Teitelbaum , T . 1990. Incremental reduction in the lambda calculus . In Proceedings of the ACM '90 Conference on LISP and Functional Programming. (June). ACM , New York , pp. 307 -- 322 .]] 10.1145\/91556.91679 Field, J. and Teitelbaum, T. 1990. Incremental reduction in the lambda calculus. In Proceedings of the ACM '90 Conference on LISP and Functional Programming. (June). ACM, New York, pp. 307--322.]] 10.1145\/91556.91679"},{"key":"e_1_2_1_17_1","unstructured":"Heydon A. Levin R. Mann T. and Yu Y. 1999. The Vesta approach to software configuration management. Rep. 1999-001 Compaq Systems Research Center.]]   Heydon A. Levin R. Mann T. and Yu Y. 1999. The Vesta approach to software configuration management. Rep. 1999-001 Compaq Systems Research Center.]]"},{"key":"e_1_2_1_18_1","first-page":"311","volume-title":"Proceedings of the 2000 ACM SIGPLAN Conference on PLDI. (May). ACM","author":"Heydon A.","unstructured":"Heydon , A. , Levin , R. , and Yu , Y . 2000. Caching function calls using precise dependencies . In Proceedings of the 2000 ACM SIGPLAN Conference on PLDI. (May). ACM , New York , pp. 311 -- 320 .]] 10.1145\/349299.349341 Heydon, A., Levin, R., and Yu, Y. 2000. Caching function calls using precise dependencies. In Proceedings of the 2000 ACM SIGPLAN Conference on PLDI. (May). ACM, New York, pp. 311--320.]] 10.1145\/349299.349341"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/291889.291895"},{"key":"e_1_2_1_21_1","unstructured":"Liu Y. A. 1996. Incremental Computation: A Semantics-Based Systematic Transformational Approach. Ph.D. dissertation. Department of Computer Science Cornell University.]]   Liu Y. A. 1996. Incremental Computation: A Semantics-Based Systematic Transformational Approach. Ph.D. dissertation. Department of Computer Science Cornell University.]]"},{"key":"e_1_2_1_22_1","first-page":"33","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 . The Netherlands , pp. 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. The Netherlands, pp. 33--70.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1038\/218019a0","article-title":"memo\u2019 functions and machine learning","volume":"21","author":"Michie D.","year":"1968","unstructured":"Michie , D. 1968 . \u2018 memo\u2019 functions and machine learning . Nature 21 , 8, 19 -- 22 .]] Michie, D. 1968. \u2018memo\u2019 functions and machine learning. Nature 21, 8, 19--22.]]","journal-title":"Nature"},{"key":"e_1_2_1_24_1","first-page":"487","volume-title":"Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Miller G. L.","unstructured":"Miller , G. L. and Reif , J. H . 1985. Parallel tree contraction and its application . In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA , pp. 487 -- 489 .]] Miller, G. L. and Reif, J. H. 1985. Parallel tree contraction and its application. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, pp. 487--489.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129501003322"},{"key":"e_1_2_1_27_1","first-page":"315","volume-title":"Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages. ACM","author":"Pugh W.","unstructured":"Pugh , W. and Teitelbaum , T . 1989. Incremental computation via function caching . In Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages. ACM , New York , pp. 315 -- 328 .]] 10.1145\/75277.75305 Pugh, W. and Teitelbaum, T. 1989. Incremental computation via function caching. In Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, pp. 315--328.]] 10.1145\/75277.75305"},{"key":"e_1_2_1_28_1","first-page":"502","volume-title":"Conference Record of the 20th Annual ACM Symposium on Principles of Programming Languages. ACM","author":"Ramalingam G.","unstructured":"Ramalingam , G. and Reps , T . 1993. A categorized bibliography on incremental computation . In Conference Record of the 20th Annual ACM Symposium on Principles of Programming Languages. ACM , New York , pp. 502 -- 510 .]] 10.1145\/158511.158710 Ramalingam, G. and Reps, T. 1993. A categorized bibliography on incremental computation. In Conference Record of the 20th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, pp. 502--510.]] 10.1145\/158511.158710"},{"key":"e_1_2_1_29_1","first-page":"169","volume-title":"Proceedings of the 9th Annual Symposium on Principles of Programming Languages. ACM","author":"Reps T.","year":"1982","unstructured":"Reps , T. 1982 . Optimal-time incremental semantic analysis for syntax-directed editors . In Proceedings of the 9th Annual Symposium on Principles of Programming Languages. ACM , New York , pp. 169 -- 176 .]] 10.1145\/582153.582172 Reps, T. 1982. Optimal-time incremental semantic analysis for syntax-directed editors. In Proceedings of the 9th Annual Symposium on Principles of Programming Languages. ACM, New York, pp. 169--176.]] 10.1145\/582153.582172"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_31_1","first-page":"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 , pp. 1 -- 13 .]] 10.1145\/99583.99587 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, pp. 1--13.]] 10.1145\/99583.99587"},{"key":"e_1_2_1_32_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\/1186632.1186634","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1186632.1186634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:51Z","timestamp":1750258071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1186632.1186634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2006,11]]}},"alternative-id":["10.1145\/1186632.1186634"],"URL":"https:\/\/doi.org\/10.1145\/1186632.1186634","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,11]]},"assertion":[{"value":"2006-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}