# Fun with L-Systems

11 Jan 2015I had the great pleasure to speak at CodeMash this week, and, on my way back, ended up spending a couple of hours at the Atlanta airport waiting for my connecting flight back to the warmer climate of San Francisco – a perfect opportunity for some light-hearted coding fun. A couple of days earlier, I came across this really nice tweet, rendering the results of an L-system:

{start:'FFPF',rules:{F:'PF++F[FF-F+PF+FPP][F]FFPF',P:''},'α':60} pic.twitter.com/JZGDV4ghFy

— LSystemBot 2.0 (@LSystemBot) January 10, 2015

I ended up looking up L-systems on Wikipedia, and thought this would make for some fun coding exercise. In a nutshell, a L-system is a grammar. It starts with an alphabet of symbols, and a set of rules which govern how each symbol can be transformed into another chain of symbols. By applying these rules to a starting state (the initial axiom), one can evolve it into a succession of states, which can be seen as the growth of an organism. And by mapping each symbol to operations in a logo/turtle like language, each generation can then be rendered as a graphic.

So how could we go about coding this in F#? If you are impatient, you can find the final result as a gist here.

First, I started with representing the core elements of an L-System with a couple of types:

```
type Symbol = | Sym of char
type State = Symbol list
type Rules = Map<Symbol,State>
type LSystem =
{ Axiom:State
Rules:Rules }
```

A symbol is a char, wrapped in a single-case discriminated union, and a State is simply a list of Symbols. We define the Rules that govern the transformation of Symbols by a Map, which associates a particular Symbol with a State, and an L-System is then an Axiom (the initial State), with a collection of Rules.

Let’s illustrate this on the second example from the Wikipedia page, the Pythagoras tree. Our grammar contains 4 symbols, 0, 1, [ and ], we start with a 0, and we have 2 rules, (1 → 11), and (0 → 1[0]0). This can be encoded in a straightforward manner in our domain, like this:

```
let lSystem =
{ Axiom = [ Sym('0') ]
Rules = [ Sym('1'), [ Sym('1'); Sym('1') ]
Sym('0'), [ Sym('1'); Sym('['); Sym('0'); Sym(']'); Sym('0') ]]
|> Map.ofList }
```

Growing the organism by applying the rules is fairly straightforward: given a `State`

, we traverse the list of Symbols, look up for each of them if there is a matching rule, and perform a substitution if it is found, leaving it unchanged otherwise:

```
(*
Growing from the original axiom
by applying the rules
*)
let applyRules (rs:Rules) (s:Symbol) =
match (rs.TryFind s) with
| None -> [s]
| Some(x) -> x
let evolve (rs:Rules) (s:State) =
[ for sym in s do yield! (applyRules rs sym) ]
let forward (g:LSystem) =
let init = g.Axiom
let gen = evolve g.Rules
init |> Seq.unfold (fun state -> Some(state, gen state))
// compute nth generation of lSystem
let generation gen lSystem =
lSystem
|> forward
|> Seq.nth gen
|> Seq.toList
```

What does this give us on the Pythagoras Tree?

```
> lSystem |> generation 1;;
val it : Symbol list = [Sym '1'; Sym '['; Sym '0'; Sym ']'; Sym '0']
```

Nice and crisp – that part is done. Next up, rendering. The idea here is that for each `Symbol`

in a `State`

, we will perform a substitution with a sequence of instructions, either a Move, drawing a line of a certain length, or a Turn of a certain Angle. We will also have a Stack, where we can Push or Pop the current position of the Turtle, so that we can for instance store the current position and direction on the stack, perform a couple of moves with a Push, and then return to the previous position by a Pop, which will reset the turtle to the previous position. Again, that lends itself to a very natural model:

```
(*
Modelling the Turtle/Logo instructions
*)
type Length = | Len of float
type Angle = | Deg of float
// override operator later
let add (a1:Angle) (a2:Angle) =
let d1 = match a1 with Deg(x) -> x
let d2 = match a2 with Deg(x) -> x
Deg(d1+d2)
type Inst =
| Move of Length
| Turn of Angle
| Push
| Pop
let Fwd x = Move(Len(x))
let Lft x = Turn(Deg(x))
let Rgt x = Turn(Deg(-x))
```

We can now transform our L-system state into a list of instructions, and convert them into a sequence of Operations, in that case Drawing lines between 2 points:

```
type Pos = { X:float; Y:float; }
type Dir = { L:Length; A:Angle }
type Turtle = { Pos:Pos; Dir:Dir }
type ProgState = { Curr:Turtle; Stack:Turtle list }
let turn angle turtle =
let a = turtle.Dir.A |> add angle
{ turtle with Dir = { turtle.Dir with A = a } }
type Translation = Map<Symbol,Inst list>
type Ops = | Draw of Pos * Pos
let pi = System.Math.PI
let line (pos:Pos) (len:Length) (ang:Angle) =
let l = match len with | Len(l) -> l
let a = match ang with | Deg(a) -> (a * pi / 180.)
{ X = pos.X + l * cos a ; Y = pos.Y + l * sin a }
let execute (inst:Inst) (state:ProgState) =
match inst with
| Push -> None, { state with Stack = state.Curr :: state.Stack }
| Pop ->
let head::tail = state.Stack // assumes more Push than Pop
None, { state with Curr = head; Stack = tail }
| Turn(angle) ->
None, { state with Curr = state.Curr |> turn angle }
| Move(len) ->
let startPoint = state.Curr.Pos
let endPoint = line startPoint len state.Curr.Dir.A
Some(Draw(startPoint,endPoint)), { state with Curr = { state.Curr with Pos = endPoint } }
let toTurtle (T:Translation) (xs:Symbol list) =
let startPos = { X = 400.; Y = 400. }
let startDir = { L = Len(0.); A = Deg(0.) }
let init =
{ Curr = { Pos = startPos; Dir = startDir }
Stack = [] }
xs
|> List.map (fun sym -> T.[sym])
|> List.concat
|> Seq.scan (fun (op,state) inst -> execute inst state) (None,init)
|> Seq.map fst
|> Seq.choose id
```

We simply map each Symbol to a List of instructions, transform the list of symbols into a list of instructions, and maintain at each step the current position and direction, as well as a Stack (represented as a list) of positions and directions. How does it play out on our Pythagoras Tree? First, we define the mapping from Symbols to Instructions:

```
let l = 1.
let T =
[ Sym('0'), [ Fwd l; ]
Sym('1'), [ Fwd l; ]
Sym('['), [ Push; Lft 45.; ]
Sym(']'), [ Pop; Rgt 45.; ] ]
|> Map.ofList
```

… and we simply send that `toTurtle`

, which produces a list of Draw instructions:

```
> lSystem |> generation 1 |> toTurtle T;;
val it : seq<Ops> =
seq
[ Draw ({X = 400.0; Y = 400.0;},{X = 401.0; Y = 400.0;});
Draw ({X = 401.0; Y = 400.0;},{X = 401.7071068; Y = 400.7071068;});
Draw ({X = 401.0; Y = 400.0;},{X = 401.7071068; Y = 399.2928932;})]
```

Last step – some pretty pictures. We’ll simply generate a html document, rendering the image using SVG, by creating one SVG line per Draw instruction:

```
let header = """
<!DOCTYPE html>
<html>
<body>
<svg height="800" width="800">"""
let footer = """
</svg>
</body>
</html>
"""
let toSvg (ops:Ops seq) =
let asString (op:Ops) =
match op with
| Draw(p1,p2) ->
sprintf """<line x1="%f" y1="%f" x2="%f" y2="%f" style="stroke:rgb(0,0,0);stroke-width:1" />""" p1.X p1.Y p2.X p2.Y
[ yield header
for op in ops -> asString op
yield footer ]
|> String.concat "\n"
open System.IO
let path = "C:/users/mathias/desktop/lsystem.html"
let save template = File.WriteAllText(path,template)
```

And we are pretty much done:

```
> lSystem |> generation 8 |> toTurtle T |> toSvg |> save;;
val it : unit = ()
```

… which produces the following graphic:

Pretty neat! Just for fun, I replicated the Sierpinski Triangle example as well:

```
let sierpinski () =
let lSystem =
{ Axiom = [ Sym('A') ]
Rules =
[ Sym('A'), [ Sym('B'); Sym('>'); Sym('A'); Sym('>'); Sym('B') ]
Sym('B'), [ Sym('A'); Sym('<'); Sym('B'); Sym('<'); Sym('A') ]]
|> Map.ofList }
let l = 1.
let T =
[ Sym('A'), [ Fwd l; ]
Sym('B'), [ Fwd l; ]
Sym('>'), [ Lft 60.; ]
Sym('<'), [ Rgt 60.; ] ]
|> Map.ofList
lSystem
|> generation 9
|> toTurtle T
|> toSvg
|> save
```

… which results in the following picture:

That’s it for tonight! I had a lot of fun coding this (it certainly made the flight less boring), and found the idea of converting code to turtle instructions, with a stack, pretty interesting. Hope you enjoyed it, and if you end up playing with this, share your creations on Twitter and ping me!