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


Matthew Hammer


In this talk I'll describe the design and implementation of CEAL: a C-based language for self-adjusting computation. The language extends C with a small number of primitives to enable writing self-adjusting programs in a style similar to conventional C programs. I'll 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. 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 reasonably small constant. Compared to previous work, we measure significant space and time improvements.