I'm trying to make a tree that can be used to build nested functions out of smaller functions.
The goal is to have a tree that is filled with functions. Functions should fill the oldest unfulfilled node at the end all of the unfulfilled nodes should become input slots for the meta function.
Currently I have some python code that does this, its a little sloppy in a couple of ways (no error handling, string typing, using None for unfulfilled nodes), but I was wondering before I clean up all the minor problems if the overall structure is any good. I have very little experience with parsing so I am not sure if my general idea is any good. I'm looking to improve the current structure.
My Structure
Currently the tree is stored as a list of lists, each sublist represents a layer. Each layer is comprised of tuples, representing nodes, each node contains a reference to a function and that functions arity.
Adding a node
Each time a node is added to the tree, the program searches through each of the layers looking through them for an unfulfilled node, if it finds a layer that has not been fulfilled it puts the new node in its place, it also adds n new unfulfilled nodes to the end of the next layer, where n is the arity of current node.
Calling the meta function
The first thing that is done when the function is called is it replaces all of the unfulfilled nodes with self.input, the function that fetches our inputs.
Then we perform a recursive call starting at the top of the tree; we run mancall on the top of the tree. mancall looks to the its left in its layer and sums up the arities of all the functions to the left, this is the number of args on the next layer that have already been consumed. Skipping the args that have already been consumed It gets the results of the next n entries on the next layer using mancall and passes them as arguments to the function at the current node. It returns the result of this call.
Code
Here is the python code I currently have that implements this. At the bottom is an example of how this code might be run. It implements the function x,y->add(add(x,y),6) and runs it on 2 and 5.
class parsetree(object): def __init__(self): self.structure = [[None]] self.arguments = [] self.argpointer = 0 def input(self): self.argpointer += 1 return self.arguments[self.argpointer-1] def build(self,function,arity): #Find highest unfilled node for x,layer in enumerate(self.structure): if None in layer: break; else: raise Exception("Parsing Error, all nodes filled") if function == ".": function = self.input layer[layer.index(None)] = (function,arity) if x == len(self.structure)-1: self.structure.append([]) self.structure[-1].extend([None]*arity) def cement(self): self.structure = [[(self.input,0)if branch == None else branch for branch in layer]for layer in self.structure] # Manual call with optional arguments # Intended for internal purposes def mancall(self,layer,branch): arity = self.structure[layer][branch][1] offset = sum(x[1]for x in self.structure[layer][:branch]) args = [self.mancall(layer+1,x) for x in range(offset,offset+arity)] return self.structure[layer][branch][0](*args) def __call__(self,args): self.cement() self.arguments = args self.argpointer = 0 return self.mancall(0,0) def __str__(self): return str(self.structure) if __name__ == "__main__": h=lambda x,y:x+y g=lambda x:x+1 f=lambda:6 a = parsetree() a.build(h,2) a.build(h,2) a.build(f,0) print a([2,3]) 
