I thought I’d jump on the Rust blogging bandwagon. Specifically, I’ve been toying with a new library to define and iterate over L-systems in a unique and Rust-inspired fashion. It’s been very rewarding to fool around with a type system so foreign to my roots in duck- and weakly-typed languages.

If you haven’t heard of L-systems before, they’re mostly used to make pretty pictures. I was able to create a little animation of the first seven iterations of an L-system that draws Penrose tiles (below).

L-systems have put them to a variety of different uses, including modelling plants and trees, buildings and cities, and all manner of interesting geometric constructions. They hold their fascination in part because of the way in which a very small number of basic components and rules can evolve in startling ways over time. In other words, L-systems put emergence on display.

## Leveraging Rust’s Syntax for Implementation

Formally, an L-system consists of three things:

- An alphabet of symbols,
- An intial starting point (called an
*axiom*) composed of letters of this alphabet; and - A set of rules (called
*productions*) for transforming sets of letters into one another.

I thought it might be neat to see what it looked like if one were to use a
`type`

as the alphabet, and pattern matching (inside of a closure) to express
the productions. It turns out that Rust’s syntax makes this is a nice way to
build up not only the kinds of L-systems I defined above, but also more
advanced parametric and stochastic L-systems as well.

As an L-system evolves over time, each successive *iteration* uses the
productions to replace the symbols in the axiom with new symbols, and the
result then becomes the new axiom for the next iteration. The concept of
iteration in L-systems also suggests a natural expression in Rust: an iterator
type, which responds to calls to `next()`

by internally mutating a vector
according to a production function.

This is the basic outline of the implementation: start with a vector of some arbitrary type, use pattern matching to express productions, and then allow iteration over the vector to produce successive axioms.

## Lindenmayer’s Algae

The original application that inspired the invention of L-systems is modelling
the growth of algae cells. According to Lindenmayer, these cells are in one of
two distinct states, reproduction (usually denoted “A”) or growth (usually
denoted “B”). In Rust, we can represent these states with a type, specifically
an `enum`

:

```
#[deriving(Clone, Show, Eq, PartialEq)]
enum Algae {
/** Reproduction State */ A,
/** Growth State */ B
}
```

In order to capture how a group of algae cells grows and changes over time,
Lindenmayer proposed that algae cells that are in the growth state transition
to being in the reproductive state after a set period. In this same period, a
cell in the reproductive state will birth a new cell, which starts in the
growth state. These two processes can be represented using a simple function
that makes use of Rust’s `match`

construct:

```
fn algae_rule(input: Algae) -> Vec<Algae> {
match input {
Algae::A => vec!(Algae::A, Algae::B),
Algae::B => vec!(Algae::A)
}
}
```

If we take the `Algae`

type as representing the L-system’s alphabet, these two
pieces are all that we need to define an L-system:

```
use lsystem::LSystem;
let algae = LSystem::new(vec!(Algae::B), |input| match input {
Algae::A => vec!(Algae::A, Algae::B),
Algae::B => vec!(Algae::A)
});
```

Although this time I’ve used a closure instead of referencing the `algae_rule`

function directly. In the current version of the library, the `LSystem`

type
itself is an `Iterator`

, which means we can capture the notion of iteration as
it pertains to L-systems in a very idiomatic way. For instance, to check that
the `n = 4`

case matches Lindenmayer’s “ABAAB” string:

```
let algae_n4 = algae.nth(4).unwrap();
// Confirm that it matches Lindenmayer's fifth iteration.
assert_eq!(algae_n4,
vec!(Algae::A, Algae::B, Algae::A, Algae::A, Algae::B));
```

Of course, you could also use some form of `for n in algae { ... }`

, but keep
in mind that this is an infinite loop when dealing with `LSystem`

, so you’d
have to `break`

out of it somehow.

## An Implementation

It actually took me quite a while to hammer out an exact implementation for
these ideas — all of the backpedalling in
the commit history is a
testament to this. But it ended up being quite simple now that Rust has the
`FnMut`

trait:

```
pub struct LSystem<T, F: FnMut(T) -> Vec<T>> {
axiom: Vec<T>,
rules: F
}
impl<T, F> LSystem<T, F> where F: FnMut(T) -> Vec<T> {
/// Creates a new representation of an L-system with the given axiom and
/// production rules.
pub fn new(axiom: Vec<T>, rules: F) -> LSystem<T, F> {
LSystem { axiom: axiom, rules: rules }
}
}
```

The closure (or `fn`

) is actually called during iteration. I experimented with
a number of ways to turn an `LSystem`

into a iterator, including a top-level
function and an `LSystemIterator`

that was created with a call to an `iter()`

method. In the end, I decided just to implement the `Iterator`

trait for the
key struct directly:

```
impl<T, F> Iterator for LSystem<T, F> where T: Clone, F: FnMut(T) -> Vec<T> {
type Item = Vec<T>;
/// Yield the next iteration of the L-system by rewriting the current
/// axiom's contents using the productions.
fn next(&mut self) -> Option<Vec<T>> {
// To handle the "n = 0" case, we return the current state of the
// iterator by value, and then rewrite the internal vector in
// preparation of the next state.
let result = self.axiom.clone();
// Apply the production rules to the axiom to produce a new axiom for
// the iteration level.
let mut new_axiom = Vec::new();
for element in self.axiom.drain(..) {
new_axiom.extend((self.rules)(element).into_iter());
}
self.axiom = new_axiom;
Some(result)
}
}
```

*Update: Thanks to u/matthiem for some
nice improvements over the original implementation.*

## The “Turtle” Interpretation of L-systems

You might be asking yourself “what do I *do* with an L-system?” at this point.
That is, what does the vector of symbols that each interation produces actually
mean? In Lindenmayer’s algae model, we could look at the vector of symbols and
see it as a culture of cells, but that doesn’t hold for other examples.

If you followed any of the links above, you might have noticed that L-systems
are often associated with
turtle graphics. The essential
idea is that a string of symbols can be sequentially “interpreted” as a series
of drawing commands^{1}.

Once again, this has a very nice representation in Rust:

```
pub mod turtle {
// Note that this is only a small subset of more complete Turtle graphics
// implementations.
pub enum Turtle {
Forward(u32), Left(u32), Right(u32), Push, Pop
}
pub trait TurtleInterpretation {
fn to_turtle(&self) -> Turtle;
}
}
```

That is, the `Turtle`

algebraic type represents turtle graphics commands, and
any type can have a “turtle interpretation” by implementing a simple `trait`

.

For example, we can create a version of the Sierpinski triangle with the following:

```
extern crate lsystem;
use lsystem::LSystem;
use lsystem::turtle::{Turtle, TurtleInterpretation};
fn draw<T: TurtleInterpretation>(v: Vec<T>) { /* see below */ }
#[derive(Clone)]
enum Sierpinski {
A, B, Plus, Minus
}
impl TurtleInterpretation for Sierpinski {
fn to_turtle(&self) -> Turtle {
match *self {
Sierpinski::A => Turtle::Forward(10),
Sierpinski::B => Turtle::Forward(10),
Sierpinski::Plus => Turtle::Left(60),
Sierpinski::Minus => Turtle::Right(60)
}
}
}
fn main() {
let mut s = LSystem::new(vec!(Sierpinski::A), |x| match x {
// A -> B-A-B
Sierpinski::A => vec!(Sierpinski::B, Sierpinski::Minus, Sierpinski::A,
Sierpinski::Minus, Sierpinski::B),
// B -> A+B+A
Sierpinski::B => vec!(Sierpinski::A, Sierpinski::Plus, Sierpinski::B,
Sierpinski::Plus, Sierpinski::A),
// + and - are constants.
c => vec!(c)
});
draw(s.nth(3).unwrap());
}
```

The last piece of code we need is a function that will take a `Vec<T: Turtle>`

and `draw()`

it to the screen. I didn’t really want to write any graphics code,
so here’s a way to cheat:

```
fn draw<T: TurtleInterpretation>(v: Vec<T>) {
println!("import turtle\n\nturtle.speed(0)\n");
for command in v.iter() {
match command.to_turtle() {
Turtle::Forward(val) => println!("turtle.forward({})", val),
Turtle::Left(val) => println!("turtle.left({})", val),
Turtle::Right(val) => println!("turtle.right({})", val),
_ => ()
}
}
println!("\nturtle.exitonclick()\n");
}
```

It turns out that there’s a turtle graphics implementation distributed with
Python — so this little `draw()`

function will write a complete Python
program to draw your L-system to `stdin`

(which you can pipe to `python`

). I
usually just run something like the following in my shell to test them:

`$ ./sierpinski | python -`

Sneaky, eh? There’s a much, much more complete version of such a `draw()`

function included in the script I used to create the Penrose tiles above, which
can be found in the
examples directory of the project.
All of the heavy lifting for creating the `.gif`

itself is done by
ImageMagick’s `convert`

utility, because I don’t think there’s a Rust image
library that will handle Postscript files at the moment.

A possible improvement to the library in the future might be output to the new turtle graphics implementation in Rust, which was posted to Reddit a few days ago.

Comments on the implementation details are very welcome! There were also some good comments on the Reddit thread.

L-systems are often expressed

*only*in this form. This is a bit of a mistake, as the algae example illustrates.^{[return]}