6
\$\begingroup\$

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])
\$\endgroup\$
  • \$\begingroup\$ @GarethRees This project came into reality because I had a dream where I was programming in a Haskell like language where functions were evaluated in this way. At the time I thought it might also have some practical applications for a project I am working on, but after a little more thought I realized it would not be very helpful. This is "just for fun", because I thought an idea I had in a dream was fun, I wanted to fulfill it so I could play around with the idea some more. I thought it might be good to get a code-review because I had never written something like this before. \$\endgroup\$ – Sriotchilism O'Zaic Jul 6 '17 at 11:38
  • 2
    \$\begingroup\$ Can't argue with "it came to me in a dream". \$\endgroup\$ – Gareth Rees Jul 13 '17 at 6:56
3
\$\begingroup\$

speed

It looks like you could use x to avoid the expense of layer.index(None). Alternatively, you might have relied on index instead of enumerate.

style

PEP8 asks you to name your class ParseTree, and to use spaces around an operator: self.argpointer - 1 or def build(self, function, arity):. Run $ flake8 parsetree.py and it will give you guidance.

Consider marking this private: def _input(self):. Also, your "Intended for internal purposes" comment suggests _mancall.

Break cement's single statement into multiple lines:

self.structure = [[(self.input, 0) if branch == None else branch
                   for branch in layer]
                  for layer in self.structure]

I wouldn't mind seeing a comment (a docstring) for cement.

naming

In the offset summation using for x in self.structure ..., you could choose a much more informative name than x.

In the args loop, it appears that you wrote x when you really meant branch.

Yes, modeling nodes with tuples, as you have, makes perfect sense.

Interesting dream!

\$\endgroup\$
  • \$\begingroup\$ Ah thanks! I did not know that private member functions even existed in python. I will be sure to be using many more of these in the future. \$\endgroup\$ – Sriotchilism O'Zaic Sep 4 '17 at 2:48
  • \$\begingroup\$ Umm, it's just a convention, folks can go mess with _foo if they really want to, but they know they shouldn't be. OTOH, a nested helper def within a def really is local. \$\endgroup\$ – J_H Sep 4 '17 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.