I 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 (@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 at @brandewinder!

## Comments

- Create an Excel 2007 VSTO add-in: adding a WPF control (14)
- Management, the Gordon Ramsay way (4)
- How dense is the product of Sparse Matrices? (5)
- Testing and mocking your C# code with F# (5)

Comment RSSHealthy Weight Loss Tips After Pregnancy wrote: This could possibly be enough to help you fit comf... [More]

maximum shred reviews wrote: You really make it seem so easy with your presenta... [More]

How To Reverse Aging wrote: Hello, I enjoy reading all of your article. I want... [More]

thetaoofbadassus.tumblr.com wrote: I have read so many articles about the blogger lov... [More]