Friday, 27 February 2015

Review 1.1: Understanding program trees

Understanding program trees

A program tree represents a program or a application in a tree structure. As we can see in the picture, it show a simple programming logic, which means if x is larger than 5 , then y will add 3, otherwise, y will minus 2. In this program tree, it will choose the middle child node to be executed when the left child node is evaluted be to true or else it will execute the right child node.

The following code shows a method of how to represent a program tree:
trait N {
    def evaluate(params:List[Int]) : Int
}

case class Node( val func:List[Int]=>Int, val children:List[N] ) extends N {
    def evaluate(params:List[Int]) = {
        val results = children.map(_.evaluate(params))
        func(results)
    }
}

case class ParamNode( val parampos:Int ) extends N {
    def evaluate(params:List[Int]) = {
        params(parampos)
    }
} 

case class ConstNode( val v:Int ) extends N {
    def evaluate(params:List[Int]) = {
        v
    }
}

def iff(l:List[Int]) = {
    if(l(0)>0) l(1)
    else l(2)
}

def gt(l:List[Int]) = {
    if(l(0) > l(1)) 1 else 0
}

def add(l:List[Int]) = {
    l(0) + l(1)
}

def minus(l:List[Int]) = {
    l(0) - l(1)
}

val n = new Node(iff,
        List(Node(gt,List(ParamNode(0),ConstNode(5))),
            Node(add,List(ParamNode(1),ConstNode(3))),
            Node(minus,List(ParamNode(1),ConstNode(2)))))
      
println(n.evaluate(List(2,3)))

From the code, we know that every Node has a function to be called and a list of child nodes to be evaluated. Before its function is called, it firstly need to have the evaluated result from its children. So the evaluated method in class Node adopts a recursive way.
val results = children.map(_.evaluate(params))
func(results)
After all children have been evaluted, the parent Node will take all the result as parameters and call the method of its own. In the above example, the parent evaluates its children and gets result [(0>5),(3+3),(3-2)] => [0(false),6,1]. Because of geting a 0( means false) from the first child, the iff function takes the right child's result. Hence, the final result displayed is 1.
Why are we using program trees? Why not just write something like this:
func(x,y){
   if( x>5) y+3; else y-2;
}
The reason is that sometimes we need to make our program mutable,e.g. genetic programming. This requires us to use a systemtic way which is like program tree to represent a program.

No comments:

Post a Comment