Adaptive functional programming Export

@inproceedings{citeulike:6060704, abstract = {An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in their scope of applicability. We propose a general mechanism for adaptive computing that enables one to make any purely-functional program adaptive.We show that the mechanism is 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 the change-propagation algorithm and prove its correctness.}, address = {New York, NY, USA}, author = {Acar, Umut A. and Blelloch, Guy E. and Harper, Robert}, booktitle = {POPL 2002}, citeulike-article-id = {6060704}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=503272.503296}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/503272.503296}, citeulike-linkout-2 = {http://www.cs.cmu.edu/~sangria/publications/popl02.pdf}, doi = {10.1145/503272.503296}, isbn = {1-58113-450-9}, keywords = {adaptive, algorithms, functional-programming, incremental, ml, submit-incremental}, location = {Portland, Oregon}, pages = {247--259}, posted-at = {2009-11-03 16:47:43}, priority = {2}, publisher = {ACM}, title = {Adaptive functional programming}, url = {http://dx.doi.org/10.1145/503272.503296}, year = {2002} }

TY - CONF ID - citeulike:6060704 L3 - citeulike-article-id:6060704 N2 - An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in their scope of applicability. We propose a general mechanism for adaptive computing that enables one to make any purely-functional program adaptive.We show that the mechanism is 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 the change-propagation algorithm and prove its correctness. CY - Portland, Oregon SN - 1-58113-450-9 AD - New York, NY, USA EP - 259 TI - Adaptive functional programming PB - ACM T2 - POPL 2002 SP - 247 KW - adaptive KW - algorithms KW - functional-programming KW - incremental KW - ml KW - submit-incremental AU - Acar, Umut AU - Blelloch, Guy AU - Harper, Robert PY - 2002/// UR - http://dx.doi.org/10.1145/503272.503296 ER -