Example: Arithmetic Trees: Full Code

Example: Arithmetic Trees gives a high-level explanation of this code

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#define read_num(m)        ((int) read(m))
#define write_num(m, num)  write(m, (void*)(num))

typedef enum {ADD, MUL} binop_t;
typedef struct tree_node_s {
  enum {NUM, BINOP} kind;
  union {
    modref_t* num;
    struct { 
      binop_t binop;
      modref_t* left;
      modref_t* right;
    } binop;
  } u;
} tree_node_t;

void tree_print_rec(FILE* file, tree_node_t* node) {
  const char* binop_syms[] = {"+", "*"};
  if(node->kind == NUM) {
    fprintf(file, "%d", modref_deref(node->u.num));
  }
  else if(node->kind == BINOP) {
    fprintf(file, "(");
    tree_print_rec(file, modref_deref(node->u.binop.left));
    fprintf(file, " %s ", binop_syms[node->u.binop.binop]);
    tree_print_rec(file, modref_deref(node->u.binop.right));
    fprintf(file, ")");
  }
}

void tree_print(FILE* file, tree_node_t* tree) {
  fprintf(file, "tree = ");
  tree_print_rec(file, tree);
  fprintf(file, "\n");
}

/* Recursively evaluates a tree to a result (a number) and stores this
   result in the given modref */
afun tree_eval(tree_node_t* node, modref_t* result) {
  if(node->kind == NUM) {
    write_num(result, read_num(node->u.num));
  }
  else if(node->kind == BINOP) {
    modref_t *result_left = modref();
    tree_eval(read(node->u.binop.left), result_left);

    modref_t *result_right = modref();
    tree_eval(read(node->u.binop.right), result_right);

    if(node->u.binop.binop == ADD) {
      write_num(result, read_num(result_left) + read_num(result_right));
    }
    else if(node->u.binop.binop == MUL) {
      write_num(result, read_num(result_left) * read_num(result_right));
    }
    else {
      abort();
    }
  }
  else {
    abort();
  }
}

/* Initialization for NUM nodes */
ifun node_num_init(tree_node_t* node) {
  node->kind = NUM;
  node->u.num = modref();
}

/* Allocation for NUM nodes */
tree_node_t* Node_Num(int num) {
  tree_node_t* node = alloc(sizeof(tree_node_t), node_num_init);
  write_num(node->u.num, num);
  return node;
}

/* Initialization for BINOP nodes */
ifun node_binop_init(tree_node_t* node, binop_t binop) {
  node->kind = BINOP;
  node->u.binop.binop = binop;
  node->u.binop.left = modref();
  node->u.binop.right = modref();
}

/* Allocation for BINOP nodes */
tree_node_t* Node_Binop(binop_t binop) {
  return alloc(sizeof(tree_node_t), node_binop_init, binop);
}

/* Try to build a tree with a given number of nodes while making it
   "as balanced as possible".  The tree is written to the given
   modref.  Let n be the difference between the number of requested
   nodes and the number of nodes in the built tree.  Either n=0 or
   n=1.  Returns n.  */
int tree_rand(int nodes, modref_t* tree) {
  if(nodes < 3) {
    write(tree, Node_Num(rand() % 10)); /* 10 is arbitrary */
    return nodes - 1;
  }
  else {
    tree_node_t* binop_node = Node_Binop(rand() % 2); /* 2 possible binops */

    int a = (nodes - 1) / 2; /* # of nodes for left subtree */
    int b = (nodes - 1) - a; /* # of nodes for right subtree
                                (not counting leftovers from left subtree) */
    int c = tree_rand(a, binop_node->u.binop.left);
    int d = tree_rand(b + c, binop_node->u.binop.right);
    write(tree, binop_node);
    return d;
  }
}

/* Fill in the array, starting with element nodev[nodec].  Assumes the
   remaining space in the array is large enough to hold every node in
   the (sub-)tree. */
int tree_get_nodes(tree_node_t* node, tree_node_t** nodev, int nodec) {
  nodev[nodec++] = node;  

  if(node->kind == NUM) {
    return nodec;
  }
  else if(node->kind == BINOP) {
    nodec = tree_get_nodes(modref_deref(node->u.binop.left), nodev, nodec);
    nodec = tree_get_nodes(modref_deref(node->u.binop.right), nodev, nodec);
    return nodec;    
  }
  else {
    abort();
    return -1;
  }
}


int main(int argc, char** argv)
{
  int TREE_SIZE = 16;
  slime_t* slime = slime_open();  
  modref_t* input_tree = modref();
  modref_t* result = modref();

  /* We want to build the "random" input tree the same way in each
     run.  Similarly, we want to make the same "random" changes in
     each run.  */
  srand(0);
  
  /* Create a random tree with 16 nodes (that is close to balanced). */
  tree_rand(TREE_SIZE, input_tree);

  /* Print the tree */
  tree_print(stdout, modref_deref(input_tree));

  /* Evaluate the tree (the CORE computation) */
  tree_eval(read(input_tree), result);
  
  /* Print the result of evaluation. */
  fprintf(stdout, "     = %d\n\n", modref_deref(result));

  /* Create an array containing each node in the input tree.  For each
     leaf node (i.e., each node where the kind is NUM), do the
     following: (1) change the number at the leaf, (2) propagate the change, (3)
     restore original number (4) propgate this change.  */  
  {  
    tree_node_t** nodev = malloc(sizeof(tree_node_t*) * TREE_SIZE);
    int nodec = tree_get_nodes(modref_deref(input_tree), nodev, 0);
    int i;

    fprintf(stdout, "changing each number in tree, then changing it back ...\n");
    
    /* Do changes & propagations over tree. */
    for(i = 0; i < nodec; i++) {
      if(nodev[i]->kind == NUM) {
        /* Save the old number at this node and the old result. */
        int old_result = (int) modref_deref(result);
        int old_num    = (int) modref_deref(nodev[i]->u.num);
        int new_num    = rand() % 10;
        
        /* Change the old number to a new, random one and propagate
           this change. */
        slime_meta_start();
        write_num(nodev[i]->u.num, new_num);
        slime_propagate();

        /* Print the result of evaluation. */        
        tree_print(stdout, modref_deref(input_tree));
        fprintf(stdout, "     = %d\n", modref_deref(result));

        /* Write the old value back into the node. */
        slime_meta_start();
        write_num(nodev[i]->u.num, old_num);
        slime_propagate();

        /* Print the result of evaluation. */
        tree_print(stdout, modref_deref(input_tree));
        fprintf(stdout, "     = %d\n\n", modref_deref(result));
        
        /* Since we've restored the old number in the changed node,
           the old result should now be the same as the current
           result: */
        assert((int) modref_deref(result) == old_result);
      }
    }
  }
    
  slime_close(slime);

  return 0;
}