# Abstract

In this article we will compose a design for expressing a
*deterministic*, *context-free* L-system (\(\textrm{D}0\textrm{L}\)). 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 \(\textrm{D}0\textrm{L}\).

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}\)

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

Applying the first rule from \(P\) yields

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

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 \(\textrm{A} \rightarrow \textrm{B}\) and \(\textrm{B} \rightarrow
\textrm{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

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}

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

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
\(\textrm{D}0\textrm{L}\) 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
```

You
may discern *HC SVNT DRACONES* on the south-east coast of
Asia.^{6}

**But!** A \(\textrm{D}0\textrm{L}\) system is given by a word \(w\) of
the free monoid \(\Sigma∗\) (all strings we can form of the alphabet
\(\Sigma\), \(*\) is the
Kleene operator) together
with a morphism \(\sigma\) prolongable at \(w\).

Formally, the system generates the infinite \(\textrm{D}0\textrm{L}\) word \(\omega = lim_{n \to \infty} \sigma^n(w)\). The “to the power of \(n\)” notation means that the function \(\sigma\) is applied to the argument \(w\) \(n\) times. Informally, L-systems generate infinitely long strings by applying substitution rules ad infinitum.

By extension, all purely morphic words are \(\textrm{D}0\textrm{L}\) 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\): if \(f\) has such a propretry then we say that \(f\) is prolongable at \(a\). The word

is a pure morphic — or pure substitutive — word.

To exemplify using Lindenmayer’s original L-system, we recall that the alphabet \(\Sigma = \{\textrm{A}, \textrm{B}\}\), and that the production rules \(P = \{\textrm{A} \rightarrow \textrm{AB}, \textrm{B} \rightarrow \textrm{A}\}\). Now, we are searching for a symbol \(a\) such that there is a substitution rule such that \(f(a) = as\) for a non-empty string \(s\). The only symbol satisfying this quality is \(\textrm{A}\) as \(f(\textrm{A})\) yiels \(\textrm{AB}\).

It follows from a previous statement that \(f\) is prolongable at \(\textrm{A}\),

Starting with \(\textrm{A}\) we get that

It is this quality we will use to define our \(\textrm{D}0\textrm{L}\) using only monads,

```
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 \(\textrm{D}0\textrm{L}\) 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.”

- A dummy footnote, click here to return \(\rightarrow\) ↩
- 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 ↩ - Each application in the biological sense is the advancement of a generation. ↩
- 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*. ↩ - Here be dragons. Thou art forewarned. ↩
- Slightly below India ↩