Alexandre Trilla, PhD - Data Scientist | home publications


-- Thoughts on data analysis, software development and innovation management. Comments are welcome

Post 63

L-systems, fractal plants and grammars


One beautiful example of life is vegetation. In fact, since I was little I had always believed that ferns were supposed to be the first form of life on Earth, but now I see that the Wikipedia debunks this fact here. Anyhow, plants do deserve a lot of admiration and respect, they are fascinating to me. I myself grow a vegetable garden (especially for cultivating tomatoes with the seeds that my grandfather carefully selected for over 40 years), I annually visit the St. Boi and Molins expositions of agriculture and farming, and I own two exemplars of John Seymour's books on horticulture. However, since I am also a computer enthusiast, seeing such beauty in the form of an algorithm is a doubly rewarding experience to me. In this regard, I here release my implementation of an L-system (see the CODE section).

L-systems are a mathematical formalism originally aimed at modelling the growth processes of plant development. The basic idea is to define complex objects by successively replacing parts of a simple object using a set of rewriting rules, aka productions. These production rules can be carried out recursively and in parallel (in contrast to Chomsky grammars, which are applied sequentially).

The biological motivation of L-systems is to interpret a character string as a sequence of drawing instructions. Here is where turtle graphics come in handy, otherwise the generated object would be very difficult to describe by standard Euclidean geometry. The Logo programming language is one example of such turtle graphics system. See what can be generated with the fractal plant and tree definitions that L-system provides:


The linguistic motivation of L-systems lies in the grammar that defines them. The former examples were produced with deterministic grammars, which means that there is exactly one production rule for each symbol in the grammar's alphabet. However, this implementation of L-system also allows defining multiple rules per symbol, i.e., a stochastic grammar, and the choice is made according to an uniform distribution among the available choices. If this concept takes a textual form, the pair of sentences:

(where N stands for noun, V for verb and D for determiner)

may be produced with a single L-system with the following definition:

SymbolProduction rule
(where S stands for sentence, NP for noun phrase and VP for verb phrase)

The source code organisation of L-system follows common FLOSS directives (such as src folder, doc, README, HACKING, COPYING, etc.). It only depends externally on the Boost Iostreams Library for tokenising the definition file, and it makes use of the premake build script generation tool. Additionally, a Logo code interpreter is needed to graphically represent the production. I hope you enjoy it.

By the way, Merry Xmas!

All contents © Alexandre Trilla 2008-2024