CEAL: a C-based language for self-adjusting computation

ABSTRACT

Self-adjusting computation offers a language-centric approach to writing programs that can automatically respond to modifications to their data (e.g., inputs). Except for several domain-specific implementations, however, all previous implementations of self-adjusting computation assume mostly functional, higher-order languages such as Standard ML. Prior to this work, it was not known if self-adjusting computation can be made to work with low-level, imperative languages such as C without placing undue burden on the programmer.

We describe the design and implementation of CEAL: a C-based language for self-adjusting computation. The language is fully general and extends C with a small number of primitives to enable writing self-adjusting programs in a style similar to conventional C programs. We present efficient compilation techniques for translating CEAL programs into C that can be compiled with existing C compilers using primitives supplied by a run-time library for self-adjusting computation. We implement the proposed compiler and evaluate its effectiveness. Our experiments show that CEAL is effective in practice: compiled self-adjusting programs respond to small modifications to their data by orders of magnitude faster than recomputing from scratch while slowing down a from-scratch run by a moderate constant factor. Compared to previous work, we measure significant space and time improvements.

REFERENCES

• 1: MLton. http://mlton.org/.
• 2: Martín Abadi , Butler Lampson , Jean-Jacques Lévy, Analysis and caching of dependencies, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.83-91, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 3: Umut A. Acar, Self-adjusting computation: (an overview), Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation, p.1-6, January 19-20, 2009, Savannah, GA, USA [doi>10.1145/1480945.1480946]
• 4: Umut A. Acar , Amal Ahmed , Matthias Blume, Imperative self-adjusting computation, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 5: Umut A. Acar , Guy E. Blelloch , Kanat Tangwongsan , Duru Türkoğlu, Robust Kinetic Convex Hulls in 3D, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_3]
• 6: 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, 2005.
• 7: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 8: Andrew W. Appel, SSA is functional programming, ACM SIGPLAN Notices, v.33 n.4, p.17-20, April 1998 [doi>10.1145/278283.278285]
• 9: Henry G. Baker, CONS should not CONS its arguments, part II: Cheney on the M.T.A., ACM SIGPLAN Notices, v.30 n.9, p.17-20, Sept. 1995 [doi>10.1145/214448.214454]
• 10: J. A. Bergstra , T. B. Dinesh , J. Field , J. Heering, Toward a complete transformational toolkit for compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.5, p.639-684, Sept. 1997 [doi>10.1145/265943.265944]
• 11: Gerth Stølting Brodal , Riko Jacob, Dynamic Planar Convex Hull, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.617-626, November 16-19, 2002
• 12: Magnus Carlsson, Monads for incremental computing, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.26-35, October 04-06, 2002, Pittsburgh, PA, USA
• 13: Y.-J. Chiang and R. Tamassia. Dynamic algorithms in computational geometry. Proceedings of the IEEE, 80(9):1412--1434, 1992.
• 14: Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy. A simple, fast dominance algorithm.
• 15: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 16: Alan Demers , Thomas Reps , Tim Teitelbaum, Incremental evaluation for attribute grammars with application to syntax-directed editors, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-116, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567544]
• 17: David Eppstein, Zvi Galil, and Giuseppe F. Italiano. Dynamic graph algorithms. In Mikhail J. Atallah, editor, Algorithms and Theory of Handbook, chapter 8. CRC Press, 1999.
• 18: Matthew Fluet , Stephen Weeks, Contification using dominators, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 19: Loukas Georgiadis , Robert E. Tarjan, Finding dominators revisited: extended abstract, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 20: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 21: Matthew A. Hammer , Umut A. Acar, Memory management for self-adjusting computation, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375642]
• 22: Matthew A. Hammer, Umut A. Acar, and Yan Chen. CEAL: A C-based language for self-adjusting computation. Technical Report TTIC-TR-2009-2, Toyota Technological Institute, 2009.
• 23: Simon L Peyton Jones. Implementing lazy functional languages on stock hardware: The spineless tagless g-machine. Journal of Functional Programming, 2:127--202, 1992.
• 24: Simon L. Peyton Jones , Thomas Nordin , Dino Oliva, C-: A Portable Assembly Language, Selected Papers from the 9th International Workshop on Implementation of Functional Languages, p.1-19, September 10-12, 1997
• 25: Richard A. Kelsey, A correspondence between continuation passing style and static single assignment form, Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.13-22, January 22-22, 1995, San Francisco, California, United States
• 26: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 27: Ruy Ley-Wild , Matthew Fluet , Umut A. Acar, Compiling self-adjusting programs with continuations, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, September 20-28, 2008, Victoria, BC, Canada
• 28: Gary L. Miller and John H. Reif. Parallel tree contraction, part I: Fundamentals Advances in Computing Research, 5:47--72, 1989.
• 29: Gary L. Miller , John H. Reif, Parallel tree contraction part 2: further applications, SIAM Journal on Computing, v.20 n.6, p.1128-1147, Dec. 1991 [doi>10.1137/0220070]
• 30: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 31: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 32: Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23: 166--204, 1981.
• 33: W. Pugh , T. Teitelbaum, Incremental computation via function caching, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.315-328, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75305]
• 34: G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158710]
• 35: Ajeet Shankar , Rastislav Bodík, DITTO: automatic incrementalization of data structure invariant checks (in Java), Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 36: David Tarditi , Peter Lee , Anurag Acharya, No assembly required: compiling standard ML to C, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.161-177, June 1992 [doi>10.1145/151333.151343]
• 37: Andrew Tolmach , Dino P. Oliva, From ML to Ada: Strongly-typed language interoperability via source translation, Journal of Functional Programming, v.8 n.4, p.367-412, July 1998 [doi>10.1017/S0956796898003086]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Algorithms, Languages, Performance

Keywords:
compilation, control and data flow, dominators, performance, self-adjusting computation, tail calls, trampolines