```// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// This module implements an algorithm for evaluation of expression trees that//
// runs in time O(log(N)) for expression trees with O(N) leaf nodes. The      //
// algorithm is based on tree contraction that is based on the SHUNT operation//
// as described in [KaRa88,Meta97]. Expressions may consist of constants and  //
// addition and multiplication operations of a ring.                          //
// Expressions are stored as arrays of tuples having the following components://
// (opc,parent,sibling,val,isLeft,a,b,bsy) with the following meaning:        //
//  * opc indicates either the root node, a constant value CST or an operation//
//  * parent is the index of the parent node                                  //
//  * sibling is the index of the sibling node                                //
//  * val is the value of a leaf which must have opcode opc=CST               //
//  * isLeft: if opc=CST holds, then this indicates whether its a left leaf   //
//  * a,b are integers that specify the meaning of the expression so that if  //
//    the expression is recursively evaluated to a value v, the the value is  //
//    a*v+b                                                                   //
// In addition to the expression tree, the algorithm requires also an array   //
// that contains the indices of the leaf nodes from left to right.            //
// ************************************************************************** //

// the following are components of a node in the expression tree:
macro opc     = 0;  // indicates the operation associated with this node
macro parent  = 1;  // index of the parent node in the expression array
macro sibling = 2;  // index of the sibling in the expression array
macro val     = 3;  // value of a constant (if opc indicates a constant)
macro isLeft  = 4;  // if opc=CST holds, then this indicates whether its a left leaf
macro a       = 5;  // value a of a pair (a,b) labeling a partially evaluated edge
macro b       = 6;  // value b of a pair (a,b) labeling a partially evaluated edge
macro bsy     = 7;  // boolean value bsy indicating whether node is in use

// the following are possible op-codes
macro OpNo = 4;     // number of different operations
macro ROOT = 0;     // tag indicating the root node
macro CST  = 1;     // tag indicating constants
macro MUL  = 3;     // tag indicating multiplication

macro N = 20;       // number of possible expression nodes
macro L =  8;       // number of possible leaves of the expression

module EvalRingExpr([N](nat{OpNo} * nat{N} * nat{N} * int * bool * int * int * bool) ?e,
[L]nat{N} ?lf,
int !y,event !rdy) {
[N](nat{OpNo} * nat{N} * nat{N} * int * bool * int * int * bool) expr;
[L]nat{N} leaf;  // list of leafs

// copy the inputs to local variables that can be read and written
for(i=0..N-1) expr[i] = e[i];
for(i=0..L-1) leaf[i] = lf[i];

// the following loops perform the evaluation in time O(log(L))
for(i=0..log(L)-1) {
// the two iterations of the next loop eliminate the leafs with even index
// that are left/right operands of their parent node
for(shuntLeft=0..1) {
// the next loop enumerates all leafs with even index and eliminates
// those that are left/right operands depending on shuntLeft
for(j=0..(L-1)/exp(2,i+1)) {
let(lj = leaf[2*j])
let(l = expr[lj])
// Eliminate (shunt) leaf nodes with even indices in alternating rounds where
// in one round either left or right operand leafs are eliminated
// thus, the number of leafs is divided by two after two rounds
if(lj!=0 & l.bsy & ((shuntLeft==0) <-> l.isLeft)) {
let(a1 = l.a)
let(b1 = l.b)
let(a2 = expr[l.sibling].a)
let(b2 = expr[l.sibling].b)
let(a3 = expr[l.parent].a)
let(b3 = expr[l.parent].b)
let(x  = l.val) {
next(l.bsy) = false;               // delete leaf l
next(expr[l.parent].bsy) = false;  // delete parent of leaf l
next(expr[l.sibling].parent)  = expr[l.parent].parent;
next(expr[l.sibling].sibling) = expr[l.parent].sibling;
next(expr[l.sibling].isLeft)  = !expr[expr[l.parent].sibling].isLeft;
next(expr[expr[l.parent].sibling].sibling) = l.sibling;
next(expr[l.sibling].a) = a2 * a3;
next(expr[l.sibling].b) = b3 + a3 * (a1 * x + b1 + b2);
} else {
next(expr[l.sibling].a) = a2 * a3 * (a1 * x + b1);
next(expr[l.sibling].b) = b3 + a3 * b2 * (a1 * x + b1);
}
}
}
}
// if all leafs with even indices have been eliminated, we relabel the remaining
// leafs on the odd indices so that leafs are again enumerated from 0..L/exp(2,i)
if(shuntLeft==1)
for(j=0..(L/exp(2,i+1))-1)
next(leaf[j]) = leaf[2*j+1];
pause;
}
}
// finally, one leaf is left
let(root = expr[leaf[0]])
y = root.val * root.a + root.b;
emit(rdy);
}
drivenby LeftSpine {
int va,vb,vc,vd,ve,vf,vg,vh;
// The assignments below encode the following expression tree:
//
//      [1]  [3]  [5]  [7]  [9]  [11] [13]
//    <- * <- + <- * <- + <- * <- + <- * <- 8 [15] <7>
//       ^    ^    ^    ^    ^    ^    ^
//       |    |    |    |    |    |    |
//       1    2    3    4    5    6    7
//      [2]  [4]  [6]  [8] [10] [12] [14]
//      <0>  <1>  <2>  <3> <4>  <5>  <6>
//
// where all edges are labelled with (a,b)=(1,0) and where the numbers
// in square brackets are the indices in the expr array and the numbers
// in brackets <> denote the indices in the leaf array. The first round
// of SHUNT operations should reduce this tree to the following one:
//
//     (1,0) [3] (3,0) [7] (5,0) [11] (7,0)
//    <------ + <------ + <------ + <------- 8 [15] <3>
//            ^         ^         ^
//            |(1,0)    |(1,0)    |(1,0)
//            2         4         6
//           [4]       [8]       [12]
//           <0>       <1>       <2>
//
// next, we obtain:
//
//     (3,2) [7]  (35,30)
//    <------ + <-------- 8 [15] <1>
//            ^
//            |(1,0)
//            4
//           [8]
//           <0>
//
// and finally:
//
//     (105,104)
//    <--------- 8 [15] <0>

va = 1;
vb = 2;
vc = 3;
vd = 4;
ve = 5;
vf = 6;
vg = 7;
vh = 8;
// syntax tree of 1*(2+3*(4+5*(6+7*8)))
e[0] = (ROOT, 0, 0,00,false,1,0,true);
e[1] = (MUL, 0, 0,00,false,1,0,true);
e[2] = (CST, 1, 3,va,true, 1,0,true);
e[4] = (CST, 3, 5,vb,true, 1,0,true);
e[5] = (MUL, 3, 4,00,false,1,0,true);
e[6] = (CST, 5, 7,vc,true, 1,0,true);
e[8] = (CST, 7, 9,vd,true, 1,0,true);
e[9] = (MUL, 7, 8,00,false,1,0,true);
e[10] = (CST, 9,11,ve,true, 1,0,true);
e[12] = (CST,11,13,vf,true, 1,0,true);
e[13] = (MUL,11,12,00,false,1,0,true);
e[14] = (CST,13,15,vg,true, 1,0,true);
e[15] = (CST,13,14,vh,false,1,0,true);
// operand leafs
lf[0] = 2;
lf[1] = 4;
lf[2] = 6;
lf[3] = 8;
lf[4] = 10;
lf[5] = 12;
lf[6] = 14;
lf[7] = 15;
await(rdy);
assert(y==944);
}
drivenby RightSpine {
int va,vb,vc,vd,ve,vf,vg,vh;
// The assignments below encode the following expression tree:
//
//      <7>  <6>  <5>  <4> <3>  <2>  <1>
//      [2]  [4]  [6]  [8] [10] [12] [14]
//       1    2    3    4    5    6    7
//       |    |    |    |    |    |    |
//       v    v    v    v    v    v    v
//    <- * <- + <- * <- + <- * <- + <- * <- 8 [15] <0>
//      [1]  [3]  [5]  [7]  [9]  [11] [13]
//
// where all edges are labelled with (a,b)=(1,0) and where the numbers
// in square brackets are the indices in the expr array and the numbers
// in brackets <> denote the indices in the leaf array. The reduction
// is as follows:
//
//      <7>  <6>  <5>  <4> <3>  <2>
//      [2]  [4]  [6]  [8] [10] [12]
//       1    2    3    4    5    6
//       |    |    |    |    |    |
//       v    v    v    v    v    v  (8,0)
//    <- * <- + <- * <- + <- * <- + <------ 7 [14] <1>
//      [1]  [3]  [5]  [7]  [9]  [11]
//
//
//      <3>       <2>       <1>
//      [2]       [6]       [10]
//       1         3         5
//       |         |         |
//       v  (1,2)  v  (5,6)  v  (8,6)
//    <- * <------ * <------ * <------ 7 [14] <0>
//      [1]       [5]       [9]
//
//
//      <3>       <2>
//      [2]       [6]
//       1         3
//       |         |
//       v  (1,2)  v  (62,4)
//    <- * <------ * <------ 5 [10] <1>
//      [1]       [5]
//
//
//      <1>
//      [2]
//       1
//       |
//       v  (186,14)
//    <- * <--------- 5 [10] <0>
//      [1]
//
//
//      (944,0)
//    <--------- 1 [2] <1>
//
va = 1;
vb = 2;
vc = 3;
vd = 4;
ve = 5;
vf = 6;
vg = 7;
vh = 8;
// syntax tree of (((7*8+6)*5+4)*3)+2
e[0] = (ROOT,0, 0,00,false,1,0,true);
e[1] = (MUL, 0, 0,00,false,1,0,true);
e[2] = (CST, 1, 3,va,false,1,0,true);
e[4] = (CST, 3, 5,vb,false,1,0,true);
e[5] = (MUL, 3, 4,00,false,1,0,true);
e[6] = (CST, 5, 7,vc,false,1,0,true);
e[8] = (CST, 7, 9,vd,false,1,0,true);
e[9] = (MUL, 7, 8,00,false,1,0,true);
e[10] = (CST, 9,11,ve,false,1,0,true);
e[12] = (CST,11,13,vf,false,1,0,true);
e[13] = (MUL,11,12,00,false,1,0,true);
e[14] = (CST,13,15,vg,false,1,0,true);
e[15] = (CST,13,14,vh,true, 1,0,true);
// operand leafs
lf[0] = 15;
lf[1] = 14;
lf[2] = 12;
lf[3] = 10;
lf[4] = 8;
lf[5] = 6;
lf[6] = 4;
lf[7] = 2;
await(rdy);
assert(y==944);
}
drivenby TreeExpr {
int va,vb,vc,vd,ve,vf,vg,vh;
va = 2;
vb = 3;
vc = 4;
vd = 5;
ve = 6;
vf = 7;
vg = 8;
vh = 9;
// syntax tree of (2+3*4)*(5*6+7*(8+9))
e[0] = (ROOT,0, 0,00,false,1,0,true);
e[1] = (MUL, 0, 0,00,false,1,0,true);
e[3] = (CST, 2, 4,va,true, 1,0,true);
e[4] = (MUL, 2, 3,00,false,1,0,true);
e[5] = (CST, 4, 6,vb,true, 1,0,true);
e[6] = (CST, 4, 5,vc,false,1,0,true);
e[8] = (MUL, 7,11,00,false,1,0,true);
e[9] = (CST, 8,10,vd,true, 1,0,true);
e[10] = (CST, 8, 9,ve,false,1,0,true);
e[11] = (MUL, 7, 8,00,false,1,0,true);
e[12] = (CST,11,13,vf,true, 1,0,true);
e[14] = (CST,13,15,vg,true, 1,0,true);
e[15] = (CST,13,14,vh,false,1,0,true);
// operand leafs
lf[0] = 3;
lf[1] = 5;
lf[2] = 6;
lf[3] = 9;
lf[4] = 10;
lf[5] = 12;
lf[6] = 14;
lf[7] = 15;
await(rdy);
assert(y==2086);
}

```