Example: Add

As a very simple example, consider a self-adjusting core program that simply adds the values of two modrefs, m1 and m2, and stores the result in a output modref, m3. The meta program initially adds 1 and 2 (by having m1 and m2 contain 1 and 2, respectively), and then changes the input modref m1 and uses change propagation to update the output (which is updated in m3). While this program is really too simple by itself to benefit from self-adjusting computation, it illustrates how simple meta and core programs are written using the CEAL primitives.

#include <stdio.h>

afun add(modref_t* m_a,
         modref_t* m_b,
         modref_t* m_result)
{
  int a = read(m_a);
  int b = read(m_b);  
  write(m_result, (void*) (a + b));
}

int main(int argc, char** argv) {

  slime_t* slime = slime_open();
  
  modref_t* m1 = modref();
  modref_t* m2 = modref();
  modref_t* m3 = modref();
    
  write(m1, (void*) 1);
  write(m2, (void*) 2);  
    
  printf("m1 holds %d, m2 holds %d\n",
         modref_deref(m1),
         modref_deref(m2));
  
  add(m1, m2, m3);

  printf("m3 holds %d\n\n",
         modref_deref(m3));
  
  {
    int i;

    for(i = 2; i < 10; i++) {
      slime_meta_start();
      
      /* Change some input: */
      write(m1, (void*) i);
      printf("now m1 gets %d\n", i);

      /* Change-propagate: */
      printf("propagating ... \n");
      slime_propagate();
      printf("propagating done.\n");

      /* Look at updated output: */
      printf("now m3 holds %d\n\n",
             modref_deref(m3));
    }
  }
  
  slime_close(slime);
  
  return 0;
}

The code works as follows:

• The core program consists of a single function, add. The meta program is contained in main.

• The return-type of core functions is afun. This is a special synonym for void, meaning that core functions have no return value. Instead, their results must be handled in so-called destination-passing style (DPS), where destinations are modrefs. In the example, m3 is the destination for the result of the addition.

• The meta program begins setting up the core computation by using slime_open to get a pointer to an abstract value of type slime_t. This value will represent the core computation and its state.

• Next, the meta program creates and writes input modrefs m1 and m2, and creates a destination for the result, m3. The destination m3 will be written with the output of the core program.

• The meta program performs the initial-run of the core program by simply calling add with the modrefs m1, m2 and m3.

• Then the meta program loops:
  • It writes m1 with a new input value.
  • It uses slime_propagate to automatically update the output in m3.
  • It prints this new output value.

  Before changing the value of m1, however, the meta program uses slime_meta_start to ensure that this change is recorded as an input change that happens before the core computation (as represented in the execution trace). If this step is omitted, the changes to m1 will behave like writes that happen after the core program has finished using m1, and change propagation will perform no work.

We can compile and run this program as follows. Assuming cealc is in your $PATH, and that this program is stored in ex_add.c, do the following:

  cealc ex_add.c -o add
  ./add 

The program will then run and print something like:

m1 holds 1, m2 holds 2
m3 holds 3

now m1 gets 2
propagating ... 
propagating done.
now m3 holds 4

now m1 gets 3
propagating ... 
propagating done.
now m3 holds 5

now m1 gets 4
propagating ... 
propagating done.
now m3 holds 6

now m1 gets 5
propagating ... 
propagating done.
now m3 holds 7

now m1 gets 6
propagating ... 
propagating done.
now m3 holds 8

now m1 gets 7
propagating ... 
propagating done.
now m3 holds 9

now m1 gets 8
propagating ... 
propagating done.
now m3 holds 10

now m1 gets 9
propagating ... 
propagating done.
now m3 holds 11

The next example explores a natural generalization of this core program: Example: Arithmetic Trees