Follow

long and stupid 

(Written while programming today. Ignore this post!)
Programming today:

Writing a node replacement function replace_node_with_new for my python shallow tree library

I find I need to be able to remove each child subtree from the to-be-removed node (or else I might end up with an accidental forest)

So I have to make a subtree remover function remove_subtree. But its probably a better idea to change the existing remove_node function so it has an option to remove child nodes too recursively (thus removing the subtree). Unfortunately, I could use recursion, but some subtrees might be potentially really deep, so I’ll have to make a leaf-first node index generator to iterate a subtree so I can remove it without function recursion. Which is tricky because if the node you yielded is mutated (eg: removed) after the yield, and you try to get properties from that node, then that will fail or result in undefined behavior


Ok, finished with the subtree node generator and test. And with remove_node, and replace_node_with_new. And I’m mostly finished with a replace_node that I also wrote but ran into a bug, so I’ll shelve that function for now. For reference, this all took 2 hours

Ran into some test failures with remove_node, which I solved by collecting all the traversed child subtree nodes and then just nullifying them in the tree (setting them to None nullifies them itc), which is much faster (and evidently less error prone) than calling disconnect_parent, etc on each child. While doing this, I noticed my random tree building and destroying remove_node unit test much more quickly destroys the tree it builds when it picks a random node and removing that node and its subtree, rather than just removing the node itself. This makes sense, but now I’m wondering how many random selections and remove_node calls with subtree removal it takes to destroy a tree on average. I might write a script to test this later


And now that i have replace_node_with_new, I can move on to the completing greater_than_ef which is what SetTL’s draft executor calls when it encounters a > function (or it will, when I finish it), and needed replace_node_with_new to be finishable

Ok, I finished greater_than_ef and it seems to work, but I discovered the executor now is skipping certain parent call nodes for those nodes’ parents, instead of calling the call nodes and continuing to their parents

I found that this problem was because I wasn’t returning True from print_ef, which is an external function that removes itself during its execution, and so it also advances the execution head during its execution. External functions like print_ef can advance to the next executable node on their own, and if they don’t advance the executor will advance after they’re done, but to signal to the executor that an external function has advanced, and the executor shouldn’t advance automatically, the external function should return True, or something else not None. Since I wasn’t returning True, the print_ef function was advancing, and then the executor was advancing automatically as well, so every time I called print_ef while testing greater_than_ef it would skip over one node during execution

Anyway, I fixed that, and after fixing it I discovered that I can cheat a little with simple external functions and made generic_fn_ef which creates a closure that acts like greater_than_ef and a lesser than ef and all other n-ary operations, and all other kinds of functions otherwise that just take arguments and return a result. So I can even replace print_ef, and probably any other function that doesn’t mess around with the stack or have to return non-value nodes, or whatever.

This took around 2 hours


Now since I have some condition to test with (5 < 10): onto testing the implementation I wrote yesterday of if_ef – which is the analog of if, if-else, if-else-if, etc statements

I’m immediately running into the issue that the 3 print statements in the if statement I’m testing are all printing, when only one should print depending which condition in the if arguments is evaluating to true.

..
After about 2 hours of running into multiple small bugs, if_ef apparently works correctly

I tested how long it takes to entirely remove all nodes from a randomly constructed tree such that if you remove a parent node all child nodes below it are also removed, and it seems that on average the removal-count-complexity is O(sqrt(n)) where n is the number of initial nodes in the random tree. If you remove the nodes one by one, with no subtree removal on parent removal, then it takes n steps to remove all the nodes

Note: the O(sqrt(n)) complexity depends on what type of random graph is constructed; I built the random graphs for this test by adding a new child to a uniformly-selected random node in the graph

Now to try and find why this is true, theoretically (I imagine its either really simple or really complex)

Show thread
Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.