Example: Arithmetic Trees

The previous section (Example: Add) described a very simple core program that adds two numbers. Now we generalize this program to the case where each core input is a binary tree such that each leaf node contains an integer, and each internal node contains a binary operation (e.g., addition and multiplication) as well as links to its left and right subtrees.

Abstractly, we might evaluate such a tree as a core program with the following psuedocode:

  tree_eval(t):
    if t is a leaf:
      let a = integer at node
      return a      
    otherwise, t is an internal node:
      let binop = binary operation at the node
      let a = tree_eval(left(t))
      let b = tree_eval(right(t))
      return binop(a,b)              

To realize this psuedocode, let's start by making the tree's representation concrete:

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;

The nodes of the tree are represented by the type tree_node_t. Each tree node contains a kind which is either NUM or BINOP. If the kind is NUM, the node holds a number in a modref. If the kind is BINOP, the node contains the type of operation, binop (of type binop_t), and two modrefs, left and right, which contain pointers to the node's subtrees.

Given this concrete representation, we can write a core program to evaluate a given tree as follows:

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();
  }
}

This code realizes the psuedocode we wrote earlier. It uses two simple macros, read_num and write_num, which hide the casting between void* and int for read and write operations, respectively:

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

Example: Arithmetic Trees: Full Code contains the full code for this example, including a meta program that changes each leaf node and runs change propagation.