CEAL Manual

Quick start

Geting the code: Instructions for checking out the current (development) version of CEAL are available on the CEAL homepage.

Building CEAL

This section describes how to build CEAL applications, starting with the building compiler itself.

Systems where we've successfully built CEAL:

Owner/machine name

uname -a

ocaml -version

gcc -v


Mac 10.6.8


gcc version 4.2.1 (Apple Inc. build 5664)




gcc version 4.3.2 (Debian 4.3.2-1.1)

It seems that there's a problem building under ocaml 3.12. We will fix this soon. In the meantime, please use 3.11 to build CEAL.

If you experience problems building CEAL, please email a report to ceal-devel@mpi-sws.org.

(And in addition to getting bad news, we also like to hear that you successfully built CEAL on your system!)

Building everything

  1. After downloading or checking out the code into a directory named ceal, change to this directory.

    $ cd ceal
  2. Build CIL with CEAL extensions:

    $ pushd cil
    $ ./configure
    $ make
    $ popd
  3. Build the CEAL benchmark applications:
    $ pushd build
    $ ./compile-apps.pl
    $ popd
  4. Run the CEAL applications
    $ ./bin/apps/<some-app-name>/<some-version-name>/<some-app-name>

Each application has a directory (of the same name). From each application, depending on the build script configuration, we build multiple versions. Each version receives a subdirectory within the application directory. The verification binary (the conventional, non-self-adjusting version of the application) is usually put into a sub-directory named verf. For example:

For the application list_copy, the (single-file) source program is:


The self-adjusting binaries are placed here:


The verification binary is placed here:


The example versions above are just examples. Your results may differ depending on the state of the compile scripts:


Currently, these scripts determine which applications are built, and for each applicaiton, which versions are built. Finally, it is also important to note that you'll get a different run-time system configuration depending on the state of its Makefile, located here:


This build system suffices for now, but obviously a better build system would be nice for the future. (Design suggestions are welcome.)

Creating a CEAL program

Currently, the CEAL building and testing process is geared towards benchmark applications. The CEAL Programming How-To gives a quick guide on how to create new benchmarks. However, if you haven't programmed in CEAL before, you may want to first read the overview section below.


Now that you have a working CEAL build, this section will give you an overview of programming in CEAL.

The CEAL language extends a restricted subset of C. So, programming in CEAL is similar to programming in C, but also somewhat different.

CEAL extends C with keywords that:

It is not necessary to understand all of these keywords before beginning to program in CEAL. Indeed, this overview section, we give successive examples that introduce this subset of the above keywords:

In turn, these keywords form the basic syntax needed to write simple-yet-interesting self-adjusting programs.

The behavior of these examples illustrates a general concept: what constitutes a (time-)efficient self-adjusting computation is the stability of this computation across changes. That is, a such a computation is efficient exactly when it has stability across a given class of data changes. When this is the case, the computation can self-adjust quickly to any given change (among those in the class under consideration).

Atop the conceptual framework given in the overview and by the simple examples, further keywords, syntax and semantics are discussed in the language reference.

Basic features: `core` and `propagate`

The keywords core and propagate allow the CEAL programmer to record and repeat a computation, respectively.

The code below is "literate" in the sense that it is interspersed with commentary and explanations. A non-literate (but build-able) version of this example code resides here:

Example code

We begin with a very simple self-adjusting program that computes the square of the maximum value of two longs.

First, we define the core of the computation using ordinary C syntax as follows:

   1 #include <stdlib.h>
   2 void max_of_squares(long* in1, long* in2, long* out) {
   3   long max;
   5   if(labs(*in1) > labs(*in2)) {
   6     max = labs(*in1);
   7   }
   8   else {
   9     max = labs(*in2);
  10   }
  12   *out = (max * max);
  13 }

(Note: stdlib.h provides labs, which returns the absolute value of a long.)

From the programmer's view, the chief features of self-adjusting computation are that

To demonstrate the second point, we write meta-level code that uses the code above as a core-level computation:

   1 int main(int argc, char** argv) {
   3   /* Construct input. */
   4   long x = 2;
   5   long y = -3;
   7   /* Space for output. */
   8   long z;
  10   /* Invoke the core. */
  11   core(max_of_squares)(&x, &y, &z);
  12   print_inout(&x, &y, &z);
  14   /* Mutate the input. */     
  15   x = -4;
  17   /* Invoke change propagation. */
  18   propagate;
  19   print_inout(&x, &y, &z);
  21   /* Mutate the input. */     
  22   y = 3;
  24   /* Invoke change propagation. */
  25   propagate;
  26   print_inout(&x, &y, &z);
  28   return 0;
  29 }

The main function above is just like conventional C code, except that:

The function main above uses print_inout as a subroutine:

   1 void print_inout(long* in1, long* in2, long* out) {
   2   printf("input values: %ld and %ld\n", *in1, *in2);
   3   printf("max of squares: %ld\n", *out);
   4 }

Example output

After building this CEAL application and running the resulting binary, we get the following output on stdout:

input values: 2 and -3
max of squares: 9
input values: -4 and -3
max of squares: 16
input values: -4 and 3
max of squares: 16

Note that this output is consistent with a "conventional" version of main, where the uses of propagate are replaced by re-invocations of max_of_squares.


This simple example illustrates how core- and meta-level computations typically look in CEAL. They usually have the following structure:

This structure can be seen in the example code given above. What this example does not illustrate is why CEAL is helpful in improving the efficiency of algorithms written in C. After all, in this case, re-invoking the core computation (max_of_squares) would not be very costly. Generally, core computations can be complex, and in these cases, the use of the automatic change propagation mechanism is more helpful. Before moving onto such examples, however, we use this simple running example to illustrate other basic features of CEAL.

Introduction to stability

Informally, we say that a CEAL program is stable if, under some assumed class of input changes, its computations "don't change too much".

Though the CEAL programmer does not explicitly specify how to adjust computations to input changes, they do specify this behavior implicitly. To get the desired performance and efficiency from their code, it is helpful for the CEAL programmer to understand the basics of how change propagation works within a self-adjusting computation, and in particular, how to tell when and why their code is stable.

From the CEAL programmer's view, there are two facets to change-propagation that are relevant when writing their code to be stable. First, the CEAL programmer begins with a core program and a particular class of input changes. Then they ask themselves the following:

Where and when re-evaluation begins

Informally, the question of where is asking for a line number. For instance, on what lines does the program access memory that may be directly changed by the meta-level? Those are (some of) the places in the code where re-evaluation will begin.

Informally, the question of when is asking for something more dynamic than just a line number. The answer to this question consists of ideas like "on the ith iteration", or "when the recursive call reaches pointer p".

In other words, the question of when is asking for a particular point during the execution, not just a particular point in the code. If you were stepping through the execution with a debugger, you may "name" points in the execution based on the values of local variables; this is a useful way to understand the question of when.

A related concept is that of the execution timeline. On this line, the first end represents the beginning of the core program. Each intermediate point on this line corresponds to a step of execution, as one might view it within a debugger, by walking step-by-step. The other end of the line represents the end of the core program. Asking "when and where" re-evaluation will begin is answered by choosing a point on this line.

Once re-evaluation begins, the code may update memory in a different manner than in the previous execution. Later in the execution timeline, when and if this newly-changed data is accessed, re-evaluation will occur again.

To summarize, re-evaluation begins at each of the following points along the execution timeline:

  1. when the original execution directly accesses changed input data, and if this results in other memory changes, then additionally

  2. when the original execution accesses memory that is changed during re-evaluation.

Where and when re-evaluation ceases

As above, we can understand where to be asking for something like a line number. And again, we can understand when to be asking for information about the local state of the computation, or equivalently, for a point on the execution timeline.

In particular, the local state at each point consists of the values of local variables which are in active use. These variables are often referred to as live variables, because unlike dead variables, their values will be used later in the execution ("in the future"). The notion of liveness of data is important exactly because it concerns the future of the execution, which in general is hard or impossible to predict.

Live variable analysis is a (conservative) compile-time algorithm that tries to determine, for each point in the program text, what variables hold values that may be live. Like almost all interesting program properties, knowing exact liveness information is generally undecidable.

Because of the undecidability of live variable analysis, CEAL uses a stopping criteria that is conservative, but sound (i.e., correct in general): it allows re-evaluation to cease, locally, when (a conservative estimate of) the live variables have the same values as a comparable point in the previous execution.

Checking the stopping criteria at every point during re-evaluation would be quite costly. Moreover, as CEAL programmers, we often know good times to check for this condition. We (implicitly) specify that it should be checked by using special program structure and/or specific CEAL keywords.

In particular, the stopping criteria is checked at each of the following points:

  1. when re-evaluation reaches the end of a function body that it begins within, and

  2. when re-evaluation reaches the end of a cut block that it begins within, and

  3. when re-evaluation reaches a memo point.

The memo point and cut block constructs are CEAL extensions to C. We explain them in detail with examples below.

Example code

In the previous example, we defined a function that computes the maximum square of two numbers. What is the stability of this program, as written? That is, exactly what happens during change propagation after one of these numbers is changed?

We can begin this investigation by placing printf calls in the code. For instance, say we insert such a call on line 11:

   1 #include <stdlib.h>
   2 void max_of_squares(long* in1, long* in2, long* out) {
   3   long max;
   5   if(labs(*in1) > labs(*in2)) {
   6     max = labs(*in1);
   7   }
   8   else {
   9     max = labs(*in2);
  10   }
  11   printf("max is %ld, computing its square..\n", max);
  12   *out = (max * max);
  13 }

Now, after we find the maximum of the two inputs, but before we compute the square of this number, we will get some feedback on stdout.

In CEAL, calls to printf are executed both during the initial run (within a use of core) as well as during change propagation (within a use of propagate). For a stable CEAL program, the re-evaluated printf calls indicate which execution steps are affected by data changes. For other programs, however, there may be some printf calls that are re-evaluated needlessly. The current example gives a specific instance of this kind of situation, as we see below.

Example output

To make the output more readable, suppose that we also insert printf calls before invoking the core, and before invoking change propagation. Our output now looks like the following:

running core program..
max is 3, computing its square..
input values are 2 and -3
max of squares is 9

running change propagation..
max is 4, computing its square..
input values are -4 and -3
max of squares is 16

running change propagation..
max is 4, computing its square..
input values are -4 and 3
max of squares is 16

The first few lines correspond to running the core program. The next few correspond to the first change propagation invocation, after the first input value is changed from 2 to -4. Finally, the last few correspond to the second change propagation invocation, after the second input value is changed from -3 to 3.

How do we interpret this output? First, we notice that in all three cases, the max (of absolute value of) the two inputs is printed. This either means that this value has been affected by an input change, or is part of some larger computation that was.

After the first input value is changed, the value of max changes from 3 to 4; hence, this printf was affected. However, after the second input it changed, the value of max does not: it is still 4. In this case, the printf is not itself affected, but is contained within a larger computation that is, namely, the portion of the execution corresponding to the if statement on line 5. The condition of this if statement accesses both input values, the second of which has changed.


Informally, we say that a CEAL program is stable if only a few steps of execution require re-evaluation. Sometimes, due to the CEAL system's conservativeness, the number of steps that require re-evaluation is different from the number of steps that are actually re-evaluated.

For instance, in our example output above, we see that in one case, some steps of execution were re-evaluated needlessly.

We will consider the code fixed when, instead of the output given above, we get the following output on the final change:

running change propagation..
input values are -4 and 3
max of squares is 16

Unlike our current output, this output indicates that the printf we inserted was not re-evaluated. This is the desired, stable behavior: since the maximum (4) has not changed, this step of the execution is unaffected by the input change (of -3 to 3). Further, based on this output we conclude that, as desired, the square of the maximum (16) is not needlessly recomputed.

CEAL programmers can control where re-evaluation begins and ends by choosing where to access data that changes, and by structuring their code with care. The sections that follow, we consider many alternative ways of fixing the unstable behavior illustrated here.

Delimiting re-evaluation

As described above, reevaluation can potentially cease in three places:

Below, we give examples of how to adapt the example code above to avoid needlessly recomputing the final multiplication (which squares the value of max).

Function outlining

Function outlining is the inverse operation of function inlining: it moves code out from a large function into a smaller function; in its place, we insert a call to the smaller function.

Usually, function outlining is used as a part of "low-level" optimization, e.g., those passes that exist in the back end of a C or Fortran compiler. It is applied to isolate "cold" code, and separate it from "hot" code.

In self-adjusting computation, function outlining serves a different purpose: it isolates frequently re-executed code into smaller functions. These functions provide a well-defined boundary for data and control-flow. Without loss of generality, we assume that they have precisely one return point, which defines the local state (live variables) at the conclusion of re-evaluation. Then, we need only check that these return values are the same as in the prior evaluation to determine if re-evaluation should continue or cease.

Here's how we isolate the computation of max via function outlining:

   1 long max_of_labs(long* in1, long* in2) {
   2   return labs(*in1) > labs(*in2) 
   3    ? labs(*in1) 
   4    : labs(*in2) ;
   5 }
   7 void max_of_squares(long* in1, long* in2, long* out) {
   8   long max = max_of_labs(in1, in2);
   9   print("max is %ld, computing its square..", max);
  10   *out = (max * max);
  11 }

`cut` blocks

It is tedious to perform function outlining by hand. The programmer must:

This makes it harder to read since the code local data and state is obscured by function call/return boundaries. For the same reasons, it makes the code harder to maintain.

CEAL provides a simple shorthand that programmers can use to outline code in a more implicit fashion. Rather than move the code, they leave it in place and wrap it in a cut block. This has exactly the effect of outlining the code by hand, except that the source code remains readable.

For instance, the following is equivalent to the outlining in the example above:

   1 void max_of_squares(long* in1, long* in2, long* out) {
   2   long max;
   4   cut {
   5     if(labs(*in1) > labs(*in2)) {
   6       max = labs(*in1);
   7     }
   8     else {
   9       max = labs(*in2);
  10     }
  11   }
  13   print("max is %ld, computing its square..", max);
  14   *out = (max * max);
  15 }

`cut` expressions

In the previous examples, we avoided recomputing the square of max by moving the entire computation of max to another function---either manually or by the use of a cut block. This consisted of either moving several statements, or wrapping several statements in a cut block.

However, in this example, we can actually isolate less code and achieve (nearly) the same effect. If we only isolate the comparison in the condition of the if statement, then in (nearly) all cases, we will avoid needlessly recomputing the square. We can either outline this comparison manually, or use a cut expression to achieve the same effect.

Munz: How does the live variable analysis work? For the following example to work it needs to know the part of the if-statement that is going to get executed to exclude the var of the other part from the set of live vars. So it evaluates the return value of the outlined function?

   1 void max_of_squares(long* in1, long* in2, long* out) {
   2   long max;
   4   /* The cast to long is needed by CEAL for obscure reasons.
   5      (See also: the 'minimum-modref-size' restriction). */
   6   if( cut( (long)(labs(*in1) > labs(*in2)) ) ) {
   7     max = labs(*in1);
   8   }
   9   else {
  10     max = labs(*in2);
  11   }
  13   printf("max is %ld, computing its square..\n", max);
  14   *out = (max * max);
  15 }

Munz: How does cut handle the following code example?

   1 void max_of_squares(long* in1, long* in2, long* out) {
   2   long max;
   3   long labsin1;
   4   long labsin2;
   6   if( cut( (long)(labsin1=labs(*in1) > labsin2=labs(*in2)) ) ) {
   7     max = labsin1;
   8   }
   9   else {
  10     max = labsin2;
  11   }
  13   printf("max is %ld, computing its square..\n", max);
  14   *out = (max * max);
  15 }

Munz: Does it update the variables correctly? If so how? Does it hand over the memory destinations of these local variables to the outlined function?

And how do I use the source code environment inside the note environment here in the wiki?

A subtle point: It is interesting to note that on nearly all input changes, this code avoids the needless reevaluation of squaring max. However, even so, there are still many cases where it doesn't: whenever the max of the two inputs changes sign, from positive to negative (or vice versa), the second pointer dereference of that input value is affected. Suppose, for instance, that the input values are 1 and 2, and then the second value is changed from 2 to -2. Then read in the statement max = labs(*in2) is affected and will be reevaluated.

A fix:One way to fix these sign-flipping corner cases is with two additional cut expressions:

   1   if( cut( (long)(labs(*in1) > labs(*in2)) ) ) {
   2     max = cut(labs(*in1));
   3   }
   4   else {
   5     max = cut(labs(*in2));
   6   }

This works, but is not advisable: each cut introduces some overhead associated with recording the return value and its dynamic dependencies within the execution timeline. For this reason, the cut block solution given above is preferred.

`memo` statements

   1 void max_of_squares(long* in1, long* in2, long* out) {
   2   long max;
   4   if(labs(*in1) > labs(*in2)) {
   5     max = labs(*in1);
   6   }
   7   else {
   8     max = labs(*in2);
   9   }
  11   memo;
  12   print("max is %ld, computing its square..", max);
  13   *out = (max * max);
  14 }

Simple recursive patterns

This section is currently in a draft form, as apart of CEAL course.

Language reference

We assume the reader is familiar with C. To understand CEAL, we begin by assuming C. Then, we:

Restrictions (and other known issues) imposed CEAL are discussed in their own section.

In this section, we discuss first commonly-used features of C, and how they appear in CEAL. Many are similar, if not identical. Others require some different syntax, or are subject to some restrictions.

Then, we discuss extra features added by CEAL. A subset of these features are introduced in overview section. We assume the reader has this level of familiarity, but no more.

Dynamic allocation

Use the CEAL keyword alloc to dynamically allocate a (constant-sized block) of memory, of a given type:

   1 typdef struct point_s {
   2  double x;
   3  double y;
   4 } point_t;
   6 double distance(point_t* p) {
   7   double x = p->x; /* reads the x field */
   8   double y = p->y; /* reads the y field */
   9   return x * x + y * y;
  10 }
  12 void foo() {
  13   point_t* p = alloc(point_t);
  14   p->x = 1; /* writes the x field */
  15   p->y = 2; /* writes the y field */
  16   int d = distance(p);
  17 }

Global variables

   1 /* Top-level, global scope. */
   2 long x;     /* Allocates space for x. */
   3 long y = 0; /* Allocates space for and writes y. */
   5 void foo() {
   6   x = y + 1; /* Reads y, writes x */
   7 }


Arrays are declared in CEAL just as they are in C. The syntax and semantics for accessing and updating arrays works just as in C. When allocated implicitly, the syntax and semantics is the same as in C. When allocated explicitly, there is a slightly different syntax.

As in C, programmers can declare CEAL arrays in the usual way, using either bracket [ ] or pointer notation. All the usual conversions between array types and pointer types occur in CEAL. For instance, consider the code below.

   1 size_t size;
   3 /* Implicit allocation of global array. */
   4 long Global[100];
   6 /* This pointer aliases the Global array */
   7 long* Global_alias = Global;
   9 void foo() {
  10   /* The usual C array syntax works in CEAL. */
  11   Global[1] = Global_alias[0] = 1234;
  13   long A[10]; /* Implicit allocation of 10 elements */
  14   long* B = alloc(long[size]); /* Explicit allocation of `size` elements, */
  16   A[0] = B[0] = 1234; /* A and B have different declaration styles, 
  17                          but array access/update has the same syntax, as in C. */
  19   struct s { /* as in C, arrays can be mixed with other structure's declarations. */
  20    long arr1[10]; /* implicit allocation of 10 elements whenever s is allocated. */
  21    long* arr2; /* explicit allocation is needed. */
  22   } foo; /* implicit allocation of struct s */
  24   foo.arr2 = alloc(long[size]);
  25   foo.arr1[0] = foo.arr2[0] = 1234;
  26 }

Using concrete syntax, this code illustrates various points. All these points are consistent with C:

The above program text is nearly supported in the current CEAL implementation (see the note below).

There is currently an issue is with the dynamic allocation syntax alloc(long[size]). Unlike fixed-sized types such as structs, arrays often have dynamic sizes that are not generally known at compile time. For instance, consider the size of long[size] where size is a variable.

Due to current technical issues, dynamically-allocated arrays must be allocated in manner different from that shown above. See the CEAL manual for further details. This fact is regrettable, but fortunately, it will be fixed soon.

Dynamically-sized arrays

For now, dynamically-sized arrays must be allocated in a special (ugly) way:

   1 int* myarray = malloc(sizeof(int) * n);
   2 memset(myarray, 0, sizeof(int) * n);

In particular: you must use malloc to get the memory, not alloc. And, you must be sure to zero-out this memory with memset.

Then, initialize each entry separately:

   1 for(int i = 0; i < n; i++) {
   2   myarray[i] = 0;
   3 }

This seems redundant, but it's not: the memset used above is part of the allocation, not part of the initialization.

Counter-intuitively, the call to memset does not initialize the array to hold all zeros. In CEAL, you must initialize each entry of the array manually. A common idiom for this is a for-loop.

Obviously, you can initialize in a more arbitrary way (without setting each entry to zero):

   1 for(int i = 0; i < n; i++) {
   2   myarray[i] = initialize_myarray_entry(&myarray[i]);
   3 }

After initialization, you can access and update the array in the usual way:

   1 int foo = myarray[1]; /* read from index 1. */
   2 myarray[0] = 3; /* write to index 0. */

Return values

Return values are the values that flow from a caller to a callee. In the absence of side-effects to global state, or to callee memory given to the caller via arguments, return values are the only way to communicate data from a function body back to its calling context.

In self-adjusting computation, return values have been a problematic language feature, at least historically. For instance, early versions of self-adjusting computation did not support them at all.

In the current version of CEAL, return values are supported via a special compiler transformation that puts the code into so-called destination-passing style.

Hence, a call to function foo may start by looking like this:

   1 int r = foo(1,2,3);

But after destination passing style, it behaves like the following:

   1 int* d = alloc(int);
   2 foo_dps(1,2,3,r);
   3 int r = *d;

In turn, foo_dps behaves like this:

   1 int* foo_dps(int a, int b, int c, int* d) {
   2   *d = foo(a, b, c);
   3   return d;
   4 }

We note that foo_dps takes d as an argument, and also returns d as a result. This seems unnecessary. If the caller knows the value of d, why does foo_dps return it? This is an excellent question, with an interesting answer. We return to this point later on.

In CEAL, it is often useful to use "return values" in the middle of a function. For instance, consider the "unstable" example code given in the manual. Of the two proposed fixes, one consists of outlining a small piece of code into a separate file. The other consists of using the CEAL keyword cut to achieve the same behavior.

Hence, cut blocks (and expressions) also introduce return values. As with explicit function returns, the local values that flow out of the cut block (or expression) are DPS-converted, just as in the example above.

Restrictions and known Issues

Permitted accesses patterns

We say that a address has permissible effects if it observes the restrictions below.

Minimum size. Every read and write that may access (read or write) changeable memory, must be at of size least sizeof(void*).

Here's an example that violates this restriction:

   1 /* Global variable */
   2 char global = 0;

Since sizeof(char) is 8, and sizeof(void*) is either 32 (on a 32-bit machine), or 64 (on a 64-bit machine), all accesses of global variable violate the restriction.

Similarly, consider this code (assuming that x points at changeable memory):

   1 /* Suppose we are on a 64-bit machine. */
   2 if ( cut (*x != 0) ) { /* Do something. */ }
   3 else { /* Do something else. */ }

Since boolean operators (such as !=) evaluate to type int, and since generally sizeof(int) < sizeof(void*) (on a 64-bit machine), and since the return value of the cut expression is changeable, this code also violates the restriction.

Consistent alignment & size. To be properly aligned and sized, every read/write must occur at an address that is either:

That is, if we read a word at address &(p[0]), then the next non-overlapping memory entry begins at &(p[1]), and not earlier. To violate this restriction means that we read or write at (word_t*)(((char*)p)+k) using some byte offset of k < sizeof(word_t).

To support this kind of overlapping unaligned access, we should first decompose it into two accesses that are each properly aligned (according to the definition above). Theoretically, this decomposition could be done by the compiler. Currently, it must be done manually by the programmer (or better yet, avoided altogether).

Consistent qualification. To be properly qualified, the qualification of the access must be consistent with prior accesses. This is a straightforward rephrasing of the consistent alignment and size restriction above: accesses that coincide on the same address all occur with the same qualification.

Foreign C exclusively uses foreign_c. In the case of the foreign_c qualifier, we require that accesses occur in

Put differently,

Other restrictions and known issues

Here's a list of other restrictions and known issues in the current version of CEAL:

  1. Array allocation is broken. See Arrays section for reference and workaround.

  2. Foreign C code can call meta functions, but only calls into the core using the core keyword.

  3. The CEAL stack is simple:
    1. CEAL functions must take scalar arguments and produce scalar results.
    2. CEAL functions must not be vararg (but calls to vararg functions in foreign C code is okay).

    3. Using setjmp/longjmp will break fundamental assumptions in the compiler and run-time system.


CEAL_manual (last edited 2011-12-11 01:09:14 by munz)