Expressing L-systems in Rust

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:

1. An alphabet of symbols,
2. An intial starting point (called an axiom) composed of letters of this alphabet; and
3. 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¹.

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.