Tree Representation in Python
6 apps of L- Tree
We have been excited about the concept of indirect encodings applied to natural systems. Specifically we found a formal grammer called the L-System that can encode some very emergent natural properties of self similiarity and fractal structure. We thought s(ASP) would be the perfect language to generate instances of this system.
What it does
It generates formal grammar sequences that can be interpreted however we chose (and chose to represent biological trees visually in Python). Once sequences are generated we can efficiently discover sub-sequences based on an inverse L-system algorithm. This function could be useful for finding gene sequences in large genome sets, which coincidentally are a great universe to be modelled by L-Systems.
How we built it
This is implemented in s(ASP). We created rules to travese up and down the L-System tree one level at a time. We then recusively called the travse down method in order to check if a given system can be reduced to a given seed. Using the travese up method we recursively made a function to generate all the possible tree level given a seed. After generating large trees we passed those tree level's into python to create a visualization of the tree.
Challenges we ran into
We found out quickly that using any recursive algorithm quickly increases the processing time exponentially .Getting to run the program in a reasonable amount of time and memory was challenging because of the algorithm time complexity and stack space limitation we had to deal with.
Accomplishments that we're proud of
We solved the time complexity issue by making the algorithm left recursive and re-wrote a lot of fundamental algorithm to fit our case.
What we learned
Recursive languages may increase simplicity, but if implemented poorly will fill up the stack unnecessarily. To avoid events like this tail recusion is a must and every recursive call and recursive method must be carefully thought and the implementation considered.
What's next for L-Gen
We want to integrate L-Gen into gene-sequencing for neuro-evolution. s(ASP) will allow us to harness the speed and flexibilty simply. L-Gen has great potential into the realm of data compression, if rules could be made to reduce the length of a binary string and then used again to obatain the orginal string.