Abstract

In this article we will compose a design for expressing a deterministic, context-free L-system (D0L). In particular our design will allow us to output successive generations of an L-system on a per-line basis, i.e. one generation per line.

For the remainder of this text, when referring to an L-system, we are specifically referring to a D0L.

Initially, we identify an approach to represent a particular L-system, and apply the same line of reasoning to represent other such systems.

Thereafter we will abstract away representing a specific L-system to afford ourselves a framework for representing any valid L-system.

Introduction

Lindenmayer systems — or L-systems — are a type of formal grammar which was created by Aristid Lindenmeyer in 1968.

The systems was conceived as a mathematical theory for plant development and Lindenmayer used L-systems to describe the behaviour of plant cells and to model the growth processes of plant development.


Remark: Mathematical theory will not be entirely omitted from this article,, but do not let that discourage you. It is not entirely at the heart of the thing itself, although the implementation is. Additionally you are bound to encounter some footnotes that look like this “1” that will transport you to the end of the page, there is a clickable arrow at the end of each footnote returning you to where you originally clicked it.


In particular, Lindenmeyer (a biologist) worked with yeast and filamentous fungi and studied the growth patterns of various types of algae. Originally the L-systems were devised to provide a formal description of the development of such simple multicellular organisms, and to illustrate the neighbourhood relationships between plant cells.

In honour of this our initial L-system therefore one that models the growth of algae.

An L-system consists of an alphabet of symbols \(\Sigma\), an initial axiom \(\omega\) (also referred to as the starting state, or starting string), and a set of production rules \(P\) that expand symbols in \(\Sigma\) into a combination of symbols and constants, where each symbol \(s\) in the produced string satisfies \(s \in \Sigma\). A production consists of two strings, the predecessor and the successor.

For any symbol \(s \in \Sigma\) which does not appear on the left-hand side of a production in \(P\), the identity production \(s \rightarrow s\) is assumed; these symbols are called constants or terminals.

A deterministic L-system is one where there is only one production rule for each letter in the alphabet. A context-free L-system is one where the production rule looks only at the given letter, not at any of its neighbours.

Formally we define a deterministic and context-free L-system as a tuple, see Eq. \(\eqref{definition:l-system}\)

\begin{equation} L = (\Sigma, \omega, P) \label{definition:l-system} \end{equation}

Lindenmayer’s original L-system for modelling the growth of algae is built from the alphabet \(\Sigma = \{A, B\}\), the production rules \(P = \{A \rightarrow AB, B \rightarrow A\}\) and the initial string \(\omega = A\).

The central concept of L-systems is that of rewriting. Rewriting is a technique for defining complex objects by successively replacing parts of a simple initial object using a set of rewriting rules or productions, i.e. the production rules \(P\).

For \(L\) the initial simple object is \(\omega\), the initial axiom. By repeatedly applying the production rules from \(P\) theorems are produced.2

To showcase how this works let us start with the initial axiom \(\omega\) and call the \(n\)-th produced string \(S_n\) starting with \(S_0 = \omega\),

\begin{equation*} S_0 = \omega = A \end{equation*}

Applying the first rule from \(P\) yields

\begin{equation*} A \rightarrow AB \implies S_1 = AB. \end{equation*}

Subsequent applications in succession is shown in Eq. \(\eqref{eq:substitution}\).

\begin{equation} A \rightarrow AB, B \rightarrow A \implies S_2 = ABA. \label{eq:substitution} \end{equation}

Note in Eq. \(\eqref{eq:substitution}\) that when substituting symbols for another symbol, or set of symbols, the continued application of the production rules only apply to the symbols part of originally supplied string. Which is to say \(A \rightarrow B\) and \(B \rightarrow A\) is applied “simultaneously”.3

Implementation

Let us begin modestly by correctly applying the production rules and establishing a vocabulary for the types we will use.

Using successive function applications on specific L-systems

In this subsection our alphabet \(\Sigma\) will be described, as will a single function algae which represents all rules in \(P\).

We will encode \(\Sigma\) in Haskell in the following manner,

data Algae = A | B deriving (Show, Eq)

Then, the type signature for the function, algae, became as follows:4

algae :: [Algae] -> [Algae]

The function expects a list as its input, and the system does not require us to distinguish between the head and the tail of the list (can you see why?) there is no need to explicitly state the name of the input since no pattern-matching is required whatsoever.

Appropriately then, the definition may be written in point-free form. By applying a simple concatMap operation to the list, substituting the letters in \(\Sigma\) as specified by the production rules in \(P\) we procure the following definition:

Using pattern-matching we can define algae in the following manner,

algae :: [Algae] -> [Algae]
algae = concatMap f
  where f A = [A, B]
        f B = [A]

You may use the function by successively calling algae as follows,

Prelude> algae $ algae [A]
[A, B, A]

Running the main function affords us the output,

➜  L-system git:(master) ✗ ghci algae1.hs
GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( algae1.hs, interpreted )
Ok, modules loaded: Main.
*Main> :main
First generation:
[A,B]
Second generation:
[A,B,A]
Third generation:
[A,B,A,A,B]

Using the same schema for other L-systems

Starting with an initial axiom and applying the substitution rules successively work for other L-systems as well, e.g. Pythagoras tree.

The Pythagorean tree L-system is defined as

\begin{equation} L_p = (\{0, 1, [, ]\}, 0, \{1 \rightarrow 11, 0 \rightarrow 1[0]0\}) \label{eq:l-system} \end{equation}

Note that “[” and “]” are constants as they have no production rules which are applied to them so we assume the identity rule.

In Haskell we can represent this as,

which executes as,

➜  L-system git:(master) ✗ ghci pythagoras.hs        
GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( pythagoras.hs, interpreted )
Ok, modules loaded: Main.
*Main> :main
First generation:
[One,LB,Zero,RB,Zero]
Second generation:
[One,One,LB,One,LB,Zero,RB,Zero,RB,One,LB,Zero,RB,Zero]

Utilizing the monadic word to represent arbitrary D0Ls

WARNING: Hic sunt dracones.5

FOOMP

No seriously, monads are not scary. Carry on. Recall from Eq. \(\eqref{definition:l-system}\) that a deterministic and context-freeL-system is defined as a tuple,

\begin{equation*} L = (\Sigma, \omega, P) \end{equation*}

If there is exactly one production for each symbol, or the identity production \(s \rightarrow s,\ s \in \Sigma\) is assumed, then the L-system is said to be deterministic.

The production rules have been context-free as all of them looks only at the given letter, not at any of its neighbours. A deterministic and context-free L-system is popularly called a “D0L” system.

One way to encapsulate this general definition would be,

type Symbol = Char

data D0L = D0L { axiom :: Symbol
               , rules :: Symbol -> [Symbol]
               } deriving Show

but this fails to adequately express rules as a set so we could use another definition,

type Symbol = Char
data ProductionRule = Symbol -> Maybe [Symbol]

data D0L = D0L {alphabet :: [Symbol]
               , axiom :: Symbol
               , rules :: [ProductionRule]
               } deriving Show

Seemingly, the only map containing the phrase "Here be
dragons" You may discern HC SVNT DRACONES on the south-east coast of Asia.6

But! A D0L system is given by a word \(w\) of the free monoid \(\Sigma∗\) on an alphabet \(\Sigma\) together with a morphism \(\sigma\) prolongable at \(w\).

The system generates the infinite D0L word \(\omega = lim_{n \to \infty} \sigma^n(w)\). Hence, all purely morphic words are D0L words.

Let \(f\) be an endomorphism of the free monoid \(\Sigma*\) on an alphabet \(\Sigma\) with the property that there is such a symbol \(a\) such that \(f(a) = as\) for a non-empty string \(s\): we say that \(f\) is prolongable at \(a\). The word

\begin{equation} asf(s)f(f(s)) \cdots f^n(s) \cdots \label{eq:morphic-word} \end{equation}

is a pure morphic word.

Which is why we will define a D0L like earlier, only using monads this time.

data D0L m a = D0L { axiom :: m a
                   , rules :: a -> m a
                   }

In the word shown in Eq. \eqref{eq:morphic-word} rules represent our \(f\). Note that the alphabet parameter is now inferred from the rules function as opposed to a set to sanity check against.

Let us then refine algae so that is a D0L and not only a function from Symbol to [Symbol].

algae :: D0L
algae = D0L [] Char

While not part of any common parlance, we will call this application of production rules an evaluation of the system, and call that function eval.

appliedTo :: Monad m => (a -> m b) -> m a -> m b
appliedTo = flip (>>=)

eval :: Monad m => D0L m a -> D0L m a
eval (D0L axiom rules) = D0L (rules `appliedTo` axiom) rules

If the arguments were flipped, i.e. rules and axiom then one may readily see that the operator would be the bind operation, >>=.

I would rather visualize the rules being applied to the axiom moreso than having the arguments (all the constituents of the axiom) being passed as a parameter to the rules function. Hence the appliedTo function,

appliedTo :: (a -> m a) -> m a -> m b
appliedTo = flip (>>=)

We can now represent both our systems using the same terminology,

and output them in very much the same way (this time getting a much more readable version of Pythagoras tree)

➜  L-system git:(master) ✗ ghci l-system.hs 
GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( l-system.hs, interpreted )
Ok, modules loaded: Main.
*Main> :main
6 generations of algae
A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB

4 generations of Pythagoras tree
0
1[0]0
11[1[0]0]1[0]0
1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0

Limitations

This approach has some limitations, for one we cannot apply our set of production rules exactly once without a cumbersome call sequence, nor can our code assume the identity production rule for letters in the alphabet as the rules themselves define the alphabet.


Within the grove the mist thickened to a warm and bitter-tasting fog; from somewhere up ahead came the sound of bubbling water. The trees parted, and Djishin found himself in a clearing where four nuns in white robes sat contemplating a monolith of glistening black basalt. On its face were inscriptions such as the monk had never seen:

(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a

“What is this stone, great ladies?” asked Djishin.

“We call it the Monad,” said the first nun.

“Why do you venerate it so?” asked Djishin.

“Through it, we may touch the impure without being corrupted,” said the second nun. “We can fell a Maybe-tree with a Maybe-ax and always hear a Maybe-sound when it crashes down—even if the sound is Nothing at all, when the ax isn’t real or there’s no tree to fall.”

Source: The Codeless Code

  1. A dummy footnote, click here to return \(\rightarrow\)
  2. In a formal system, such as L-systems, those strings that are producible by the rules of the system (starting with the axiom, or a string produced by applying rules to another such string) are called theorems. Gödel, Escher, Bach
  3. Each application in the biological sense is the advancement of a generation.
  4. Maybe you will note the similarity between Algae and Char and subsequently [Algae] and [Char] and by extension that in Haskell String is a type synonym for [Char]. As previously stated, this is about string substitution.
  5. Here be dragons. Thou art forewarned.
  6. Slightly below India