I thought I’d jump on the Rust blogging bandwagon. Specifically, I’ve been toying with a new library to define and iterate over Lsystems in a unique and Rustinspired fashion. It’s been very rewarding to fool around with a type system so foreign to my roots in duck and weaklytyped languages.
If you haven’t heard of Lsystems before, they’re mostly used to make pretty pictures. I was able to create a little animation of the first seven iterations of an Lsystem that draws Penrose tiles (below).
Lsystems 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, Lsystems put emergence on display.
Leveraging Rust’s Syntax for Implementation
Formally, an Lsystem 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 Lsystems I defined above, but also more
advanced parametric and stochastic Lsystems as well.
As an Lsystem 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 Lsystems 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 Lsystems 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 Lsystem’s alphabet, these two
pieces are all that we need to define an Lsystem:
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 Lsystems 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 Lsystem 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 toplevel
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 Lsystem 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 Lsystems
You might be asking yourself “what do I do with an Lsystem?” 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 Lsystems 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 > BAB
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 Lsystem 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.

Lsystems are often expressed only in this form. This is a bit of a mistake, as the algae example illustrates. ↩︎