Botany with Bytes

by Lito Nicolai

The video "Botany with Bytes" presented by Lito Nicolai at RubyConf 2015 explores the intersection of botany and computer science, effectively illustrating how plants can be viewed as computational entities. Through the utilization of the Ruby 'graphics' gem, which facilitates easy visualization, the talk delves into the applications of L-systems and grammars in modeling plant growth and understanding botanical structures. Key points include:

Introduction to L-systems: L-systems, formulated by botanist Aristid Lindenmayer, simulate the processes of plant growth through a defined set of rules, and are akin to the Fibonacci sequence in terms of cell division.
Connection to Computer Science: L-systems are related to rewriting systems in computer science, showcasing how structures and sequences can be represented through rules and mathematical grammar.
Parsing and Grammars: The talk discusses the hierarchy of grammars, including regular and context-sensitive grammars, emphasizing Ruby's potential positioning between these classifications.
Plant Simulation: Nicolai demonstrates an L-system for plant sprouts, using turtle graphics to visualize growth patterns, with rules for leaves budding off from stems. This method allows for the creation of intricate designs that reflect the natural branching of plants.
Turing’s Contributions: The speaker mentions Alan Turing’s work on phyllotaxis, particularly the mathematical principles governing leaf arrangements that prompt growth and structure.
3D Visualization: The discussion extends to the visualization of cells as they geometrically compress, drawing parallels to biological structures like jellyfish, which reflect the elegance of natural design.

In conclusion, the presentation encapsulates the simplicity and efficiency of plant growth and its underlying mathematical principles, reinforcing the notion that while plants operate through instinctive growth, they can also be interpreted through computational modeling. By understanding these principles through programming and simulations, viewers gain a unique perspective on the beauty of botany interwoven with computer science. Audience engagement through questions highlights further applications and insights into the theory of formal parsing and biological modeling, encouraging an interdisciplinary appreciation for these subjects.

00:00:14.410 Thank you all for coming to Botany with Bytes. I realize this is one of the more obscure topics on the Ruby Conference schedule, so I feel like you're absolutely the most adventurous crowd at RubyConf. Welcome! This is Botany with Bytes. I'm Lito Nicolai.

00:00:32.660 This talk is very simulation and graphics focused. It uses the 'graphics' gem, which is a very new gem still in beta, authored by Ryan Davis. He wrote this to be a very simple yet powerful graphics library. Unlike a game library where everything is drawn upside down and there are many optimizations for gaming purposes, this is a visualizations library. Even though it runs very fast, it conforms to usual mathematical conventions, such as having the up axis as up. If you're interested in how I created any of these simulations, all of the code is done using this library. You can install it by running 'gem install --pre graphics' for the beta version, and all my code is on GitHub under the name LitoNico.

00:01:00.140 Now, imagine you are algae. Let’s call you Alga 4. Your job is to do what algae do: produce more algae through a process called mitosis, which is simply cell division. Once you're done, you'll be the proud parent of a baby alga, which we'll call Baby 4. This process will continue endlessly; you'll keep splitting off your little babies, who will grow up, and so on. Incidentally, this process forms the Fibonacci sequence in terms of the number of individuals per generation, similar to the rapid breeding of rabbits. This was first described by Aristid Lindenmayer, a botanist, who developed these generative systems called L-systems.

00:02:31.020 L-systems are composed of a start, like a single alga, and a set of rules, such as 'one alga becomes a baby alga' and 'a baby grows up into a full-sized alga.' Now, let's talk about computers for a moment. In day-to-day computer science, we encounter something known as rewriting systems. For instance, in the game of life, each cell is rewritten based on its neighbors, or in the famous Koch snowflake fractal, each line segment is replaced with a smaller triangle. This indicates that these are grammars. A grammar essentially describes the structures or sequences you can create with certain rules, whether they are geometric or based on our L-systems.

00:04:22.990 As programmers, we might ask what strings can be matched with these rules. For example, we can use regular expressions to determine what strings they match. When we discuss grammars, it helps to know where L-systems fit in a broader context, especially as we use computers to organize our grammars. We understand regular expressions well, and to implement them, all we need is a deterministic finite automaton, which is simply a series of states and transitions. This means you don't need extra memory like a stack or heap, but only the states and the transitions.

00:05:03.930 With this structure, you can represent every regular expression ever and all of the strings that can be matched with one. This is known as regular grammars. However, we know that some grammars exist outside of this scope. For example, if you try to parse HTML with a regular expression, it will fail because HTML contains nested structures that require a more complex system. Finite grammars, which we will ignore for now, are a subset of regular grammars.

00:06:01.130 To parse HTML, you need to keep track of which tags you're inside of, necessitating random access memory to remember how far down you've gone in the hierarchy. This complexity is described by the Chomsky hierarchy, as proposed by linguist Noam Chomsky. Beyond context-free grammars like those used for HTML, there are context-sensitive grammars such as C++, where the interpretation of code depends on its broader context. To parse such structures effectively, you also require random access memory.

00:06:45.320 Among other complexities, recursively enumerable grammars necessitate potentially infinite memory for parsing, tapping into the concept of a full Turing machine. Ruby exists at this intersection between context-sensitive and recursively enumerable grammars. While I suspect Ruby is context-sensitive, I don't have proof. For example, parsing Perl can be notoriously difficult or even impossible, highlighting the limits of certain grammars. L-systems are an intriguing blend of various grammar types, encompassing some finite grammars, regular grammars, context-free, and potentially some context-sensitive grammars.

00:07:28.300 Let's consider the example of matching nested balanced parentheses. We can use a context-free parser, much like HTML, keeping track of how deep we are, but an L-system can only match this structure if there's a token in the middle. For instance, we can create a rule where 'token X' maps to 'X with parentheses' around it and iterate on that process to get nested balanced parentheses. However, if there's no token in the middle, the L-system cannot configure that structure. Regular expressions similarly struggle with an arbitrary number of balanced parentheses.

00:08:55.050 Here's an implementation of an L-system in Ruby. You’ll notice it's quite simple, mainly bookkeeping, such as tracking the state we've passed and the rules. The core logic of L-systems is condensed into a simple process: we take the state, like an alga and a baby, split that into a list of algas and then apply the mapping rules to this list before joining them back together. This concludes the implementation of L-systems. You can easily insert it into a console and see it work, resulting in a sequence of algas and their babies.

00:09:52.860 For this talk, my goal is to move into more dimensions. Since we are discussing plants, let's visualize a sprout. Through an L-system, we can describe a sprout with just two rules: each leaf buds off into a stem that has a left-facing leaf and a right-facing leaf, with each stem growing longer with each generation. In a traditional representation, we're drawing this as a string. When it comes to demonstrating it in two dimensions, we'll introduce turtle graphics. Have you played around with turtle graphics? It's an implementation from the Logo programming language where you control a turtle that draws as it moves.

00:11:06.110 For instance, you can instruct the turtle to move forward, turn, and save its position. As the turtle evaluates a string, which includes symbols indicating actions, it follows the rules: moving forward for 'S', turning left for 'L', etc. In discussing the sprout, we will reduce the structure so the turtle can understand it. I want to emphasize that the turtle is simply an arbitrary drawing framework; in a more graphics programming context, you could achieve this through mathematical transformations.

00:12:30.850 At the end of a stem, after drawing a leaf, we save the position, turn left to draw a left-facing leaf, restore the state to draw the right-facing leaf, and continue this cyclical process. In our L-system for the sprout, we have rules that write in a terse manner the relationships between a stem and its leaves. Once again, we create a turtle that functions based on our L-system and map each symbol to corresponding actions. The first generation produces just a single leaf, the second generation replicates the same, but as we progress, we see more intricate patterns emerge.

00:13:46.660 It’s worth noting that trees don’t necessarily look like simple sprouts. Some plants, like the Drosophila resarova, demonstrate exact branching structures, which can be approximated through our simulation. We can also model more complex structures like a juniper branch. Though it looks complicated, the L-system simply translates the imagery into a long string that effectively models the actual branching of the tree. The animation of the turtle executing these actions will produce a representation similar to an actual juniper branch.

00:15:05.860 While we might find that the representation holds well with a turtle, remember that each twig on a juniper can vary in length. Despite this, it remains an excellent approximation of reality, especially when drawing with just a turtle graphics setup. We’ve discussed how L-systems relate to grammars and inherently connect with computing because the plant essentially operates like a computational machine while it grows.

00:15:54.000 You can create non-organic simulations using L-systems, such as producing patterns akin to the Sierpinski triangle. Now let’s shift our perspective on the plant’s growth, examining the stem from a top-down view where leaves emerge from the meristem, a growth area filled with hormones and nutrients. As the leaf develops, it absorbs surrounding resources, prompting other leaves to branch outward in search of more nutrients.

00:17:38.780 As we model this growth, one might expect it to be computationally complex, but it can be simplified. The earliest model of plant growth was proposed in the 1950s and revolved around charged particles, demonstrating how they repel each other and form spirals due to electromagnetic forces. Implementing this through graphics, we can visualize particles spreading out and mimicking the patterns seen in plant growth.

00:19:04.160 Alan Turing notably contributed to this understanding, proposing the hypothesis of general phyllotaxis, which addresses the growth patterns leaves display. He provided a closed-form solution, ultimately demonstrating that each leaf exits the previous one at a specific angle—around 137.5 degrees—known as the golden angle. Understanding this allows us to construct our L-system, detailing how a stem rotates to produce leaves, reinforcing the connections between math, programming, and biology.

00:20:25.410 Returning to L-systems, this time we envision many algae in a line again undergoing cell division downward on a plane. Some may even divide multiple times, leading to an intricate structure representing all cells. To simplify our visualization, we represent these cells as dots with faces inside them and track their boundaries, ultimately revealing a minimalistic graph connecting the centers of the cells for computational efficiency.

00:22:50.020 As we simulate the squatting together of cells, they will start compressing tighter. The resulting shape resembles a jellyfish structure when transformed into three dimensions. This softness gives way to patterns we can observe easily in plants like the Oregon grape or holly, which exhibit similar wavy structures along their leaves, a direct reflection of biological principles at play.

00:24:22.150 In conclusion, we must recognize the simplicity with which plants operate; while we analyze them through mathematical structures, plants themselves are not concerned with these classifications. They grow based on instinct and environmental feedback. We can verify this by stepping outside to observe the naturally occurring structures and spirals in flora. Thank you very much for your attention.

00:26:00.620 Now, we have some time for questions. Yes, in the back?

00:27:52.390 The question is whether I can suggest any applications for hyperbolic structures since we draw a lot of inspiration from nature. A significant reason hyperbolic structures appear in nature is that they maximize surface area, which could serve specific purposes in various designs in nature. Though I can't definitively say hyperbolic structures have been fully utilized, they are often produced because nature selects for their effectiveness.

00:28:12.680 This is how I began my programming journey; as an illustrator, I struggled to accurately create a jellyfish, which led me to realize I could use programming to model those shapes. If you want to understand formal parsing better, I recommend checking out earlier talks, especially those discussing formal parsing theory.

00:28:33.320 As for a formal background in this field, Turing's papers are a great starting place as they delve into various topics, including life patterns and leaf growth. His last few years contained insightful discussions around the mathematical base of biological modeling.

00:28:51.900 Thank you all very much!