CEAL: A C-Based Language for Self-Adjusting Computation

Matthew A. Hammer, Umut A. Acar and Yan Chen


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.

Bibtex Entry

  author = "Matthew A. Hammer and Umut A. Acar and Yan Chen",
  title = "{CEAL}: a {C}-Based Language for Self-Adjusting Computation",
  booktitle = "ACM SIGPLAN Conference on Programming Language Design and Implementation",
  year = 2009

Paper and Slides


Visit the wiki for information on the latest version:
Note: The code provided below is no longer maintained, though we still provide it here for posterity purposes. This code has been subsumed by a new implementation, whose design is different in several ways. We describe this new approach in our OOPSLA 2011 paper, and document it online at https://ceal.mpi-sws.org