Self-adjusting stack machines

ABSTRACT

Self-adjusting computation offers a language-based approach to writing programs that automatically respond to dynamically changing data. Recent work made significant progress in developing sound semantics and associated implementations of self-adjusting computation for high-level, functional languages. These techniques, however, do not address issues that arise for low-level languages, i.e., stack-based imperative languages that lack strong type systems and automatic memory management. In this paper, we describe techniques for self-adjusting computation which are suitable for low-level languages. Necessarily, we take a different approach than previous work: instead of starting with a high-level language with additional primitives to support self-adjusting computation, we start with a low-level intermediate language, whose semantics is given by a stack-based abstract machine. We prove that this semantics is sound: it always updates computations in a way that is consistent with full reevaluation. We give a compiler and runtime system for the intermediate language used by our abstract machine. We present an empirical evaluation that shows that our approach is efficient in practice, and performs favorably compared to prior proposals.

References

1. M. Abadi, B. W. Lampson, and J.-J. Lévy. Analysis and caching of dependencies. In International Conference on Functional Programming, pages 83--91, 1996.
2. M. Abbott, T. Altenkirch, C. McBride, and N. Ghani. D for data: Differentiating data structures. Fundam. Inf., 65 (1--2): 1--28, 2004.
3. U. A. Acar. Self-adjusting computation (an overview). In Proceedings of ACM Symposium on Partial Evaluation and Semantics-Based Program Manipulation, 2009.
4. U. A. Acar, A. Ihler, R. Mettu, and O. Sümer. Adaptive Bayesian inference. In Neural Information Processing Systems (NIPS), 2007.
5. Acar, Ahmed, and Blume}AcarAhBl08U. A. Acar, A. Ahmed, and M. Blume. Imperative self-adjusting computation. In Proceedings of the 25th Annual ACM Symposium on Principles of Programming Languages, 2008.
6. u. A. Acar, G. E. Blelloch, K. Tangwongsan, and D. Türkouglu. Robust kinetic convex hulls in 3D. In Proceedings of the 16th Annual European Symposium on Algorithms, September 2008.
7. U. A. Acar, G. E. Blelloch, M. Blume, R. Harper, and K. Tangwongsan. An experimental analysis of self-adjusting computation. ACM Trans. Prog. Lang. Sys., 32 (1): 3:1--3:53, 2009.
8. U. A. Acar, A. Cotter, B. Hudson, and D. Türkouglu. Dynamic well-spaced point sets. In Symposium on Computational Geometry, 2010.
9. U. A. Acar, A. Cotter, B. Hudson, and D. Türkouglu. Parallelism in dynamic well-spaced point sets. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures, 2011. Symposium on Parallelism in Algorithms and Architectures.
10. P. K. Agarwal, L. J. Guibas, H. Edelsbrunner, J. Erickson, M. Isard, S. Har-Peled, J. Hershberger, C. Jensen, L. Kavraki, P. Koehl, M. Lin, D. Manocha, D. Metaxas, B. Mirtich, D. Mount, S. Muthukrishnan, D. Pai, E. Sacks, J. Snoeyink, S. Suri, and O. Wolefson. Algorithmic issues in modeling motion. ACM Comput. Surv., 34 (4): 550--572, 2002.
11. A. W. Appel. SSA is functional programming. SIGPLAN Notices, 33 (4): 17--20, 1998.
12. R. Bellman. Dynamic Programming. Princeton Univ. Press, 1957.
13. P. Bhatotia, A. Wieder, R. Rodrigues, U. A. Acar, and R. Pasquini. Incoop: Mapreduce for incremental computations. In ACM Symposium on Cloud Computing, 2011.
14. M. Carlsson. Monads for incremental computing. In International Conference on Functional Programming, pages 26--35, 2002.
15. Y.-J. Chiang and R. Tamassia. Dynamic algorithms in computational geometry. Proceedings of the IEEE, 80 (9): 1412--1434, 1992.
16. A. Demers, T. Reps, and T. Teitelbaum. Incremental evaluation of attribute grammars with application to syntax-directed editors. In Principles of Programming Languages, pages 105--116, 1981.
17. P. F. Dietz and D. D. Sleator. Two algorithms for maintaining order in a list. In Proceedings of the 19th ACM Symposium on Theory of Computing, pages 365--372, 1987.
18. D. Eppstein, Z. Galil, and G. F. Italiano. Dynamic graph algorithms. In M. J. Atallah, editor, Algorithms and Theory of Computation Handbook, chapter 8. CRC Press, 1999.
19. J. Field and T. Teitelbaum. Incremental reduction in the lambda calculus. In ACM Conf. LISP and Functional Programming, pages 307--322, 1990.
20. C. Flanagan, A. Sabry, B. Duba, and M. Felleisen. The essence of compiling with continuations. In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, pages 237--247, 1993.
21. M. Hammer and U. A. Acar. Memory management for self-adjusting computation. In International Symposium on Memory Management, pages 51--60, 2008.
22. M. Hammer, U. A. Acar, M. Rajagopalan, and A. Ghuloum. A proposal for parallel self-adjusting computation. In DAMP '07: Proceedings of the first workshop on Declarative Aspects of Multicore Programming, 2007.
23. M. A. Hammer, U. A. Acar, and Y. Chen. CEAL: a C-based language for self-adjusting computation. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2009.
24. A. Heydon, R. Levin, and Y. Yu. Caching function calls using precise dependencies. In Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 311--320, 2000.
25. R. Hoover. Incremental Graph Evaluation. PhD thesis, Department of Computer Science, Cornell University, May 1987.
26. G. Huet. The zipper. Journal of Functional Programming, 7 (5): 549--554, 1997.
27. R. Ley-Wild, M. Fluet, and U. A. Acar. Compiling self-adjusting programs with continuations. In Proceedings of the International Conference on Functional Programming, 2008.
28. J. 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.
29. D. Michie. "Memo" functions and machine learning. Nature, 218: 19--22, 1968.
30. S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1997.
31. G. C. Necula, S. McPeak, S. P. Rahul, and W. Weimer. CIL: Intermediate language and tools for analysis and transformation of C programs. In In International Conference on Compiler Construction, pages 213--228, 2002.
32. W. Pugh and T. Teitelbaum. Incremental computation via function caching. In Principles of Programming Languages, pages 315--328, 1989.
33. G. Ramalingam and T. Reps. A categorized bibliography on incremental computation. In Principles of Programming Languages, pages 502--510, 1993.
34. A. Shankar and R. Bodik. DITTO: Automatic incrementalization of data structure invariant checks (in Java). In Programming Language Design and Implementation, 2007.
35. O. Sumer, U. A. Acar, A. Ihler, and R. Mettu. Fast parallel and adaptive updates for dual-decomposition solvers. In Conference on Artificial Intelligence (AAAI), 2011.
36. R. S. Sundaresh and P. Hudak. Incremental compilation via partial evaluation. In Conference Record of the 18th Annual ACM Symposium on Principles of Programming Languages, pages 1--13, 1991.
37. D. M. Yellin and R. E. Strom. INC: a language for incremental computations. ACM Transactions on Programming Languages and Systems, 13 (2): 211--236, Apr. 1991.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software development techniques