A curious way to evaluate a binary tree using Go language channels

A bizarre idea occured to me, and surely I am not the first, in fact I may have absorbed it from somewhere else. But I cannot recall where, or when, or if. And yet, here is the idea.

Imagine a binary tree, an imaginary computer construct of data, in which the chief object is a ‘node’. Nodes are connected to other nodes by lines. Leaf nodes only have one connection, root node only has 2, and middle nodes have three.


This tree has 5 nodes. A,B,D the leaves, 
E the root, and C in between.

              A       B       
                \   /
                  C        D
                     \    / 
                       E  

Quite often in computer science, the Node is given as a a collection of four objects… a “value” to hold some information, such as an Integer, then three ‘links’ to the neighboring nodes. . . two ‘descendents’ and one ‘parent’… the parent of course being closer to the ‘root’ of the tree, and the descendents being closer to the ‘leaves’ of the tree.

There are other ways, of course to think of a binary tree… any way, in fact, in which you have nodes connected to each other.

Here is a rather funny way of doing it…. imagine the tree is calculating something. As though it is a parse tree. Take for example this:


( 4 + 5 ) +  3 as a tree:


              4       5       
                \   /
                  +        3
                     \    / 
                       +  

Those nodes are connected by lines. What do the lines represent? In the typical binary tree, they would be some kind of memory address to the other nodes. Each node would have variables associated with it to store the address of the nodes it touched, something like ‘parent’, ‘left-child’, ‘right-child’, etc. Also each node might store a ‘value’, perhaps a number or the symbol ‘+’

Now ask a question. What if….. instead of the nodes being connected directly by links… they are connected by the Go Language object called a “Channel”? Each Node simply has three communication channels.

The entire ‘programming’ of the tree consists of connecting the channels together, The input channels on the leaf nodes, for example, are given integers. then the output channels of those leaf nodes are connected to Input channels of nodes further down the tree towards the Root.

The “blocking” nature of channels means that they pause while we build the tree structure, and only begin to feed data through the tree when they are ready. Somehow, this means
the tree evaluates in the proper order without missing a number here or there. In theory.

The Root’s output channel gets read by the main program, printing the final value “calculated” by the tree.

package main

import "fmt"

type Node struct {
	In1 chan int
	In2 chan int
	Out chan int
}

func NewNode() *Node {
	n := new( Node )
	n.In1 = make(chan int)
	n.In2 = make(chan int)
	n.Out = make(chan int)
	go func() {
		sum1 := <- n.In1
		sum2 := <- n.In2
		n.Out <- sum1 + sum2
	}()
	return n
}

func main() {
	n := NewNode()
	n2 := NewNode()
	n3 := NewNode()
	n4 := NewNode()
	go func() { n.In1 <- 5 }()
	go func() { n4.In2 <- 1 }()
	go func() { n2.In1 <- <- n.Out }()
	go func() { n3.In2 <- 7 }()
	go func() { n2.In2 <- <- n4.Out }()
	go func() { n4.In1 <- 1 }()
	go func() { n3.In1 <- <- n2.Out }()
	go func() { n.In2 <- 4 }()
	fmt.Println( <- n3.Out )

        // what does it represent? Basically this:
        x := "(((5+4)+(1+1))+7)"

        // broken down:
	// ((Node(5,4)+(1+1))+7)
	// ((Node(5,4)+Node(1,1))+7)
	// ((Node( Node(5,4) + Node(1,1) ) + 7 ) 
	// Node( Node( Node(5,4), Node(1,1) ) , 7 )

        // broken down as a tree, n3 = root:
        /*
             5 4     1  1
              n       n4
                \    /
                  n2        7
                     \    /
                       n3  

        */

        // broken down a different way:
	// Node ((5+4)+(1+1), 7)
	// Node ( Node( (5+4), (1+1) ), 7 )
	// (Node( Node( Node(5,4), Node(1,1) ) , 7 )

	fmt.Println( x )
	
}

This seems really weird, but it also seems to work. I am not sure what this is called, but I’d love to know more about it. It would appear at first glance as if it is horribly inefficient.

In fact if some of the data is missing, it is not unusual to get Go-language ‘data race’ errors upon trying to run the program. Ditto for removing ‘go’ concurrency statements.

But on the other hand…. in theory this could be parallelizable by setting Go’s Max Proc Threads variable. Then at least some of the go-routines would run in parallel, not just concurrently in the go-language sense. At least maybe. Just a theory.

Advertisements

About donbright

https://patreon.com/donbright https://github.com/donbright http://dwitter.net/u/donbright
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s