A quick ruby DSL for creating L-Systems

L-Systems are pretty awesome. With only a bare few rules, you can turn something like this:

LSystem.new("Barnsley Fern") do
    start "+++X"

    rule "X", "F+[[X]-X]-F[-FX]+X" 
    rule "F", "FF"

    terminal "F" do forward end
    terminal "[" do push end
    terminal "]" do pop end
    terminal "-" do rotate -25 end
    terminal "+" do rotate +25 end
end

Into this:

I’ll be the first to admit, this is not a particularly complicated bit of code. Mostly, I’m using it to continue to wrap my head around Ruby’s instance_eval and using that to make DSLs. So here’s what we have:

require 'set'

SLOW_MODE = true

class LSystem
    def initialize(name, &block)
        @name = name
        @start = nil
        @alphabet = Set[]
        @terminals = Set[]
        @rules = {}
        @terminals = {}

        self.instance_eval(&block)
    end

    def start(key)
        @start = key
    end

    def rule(key, value)
        raise "duplicate key #{key}" if @rules.include? key

        @rules[key] = value
        @alphabet.add key
        value.chars.each { |k| @alphabet.add k }
    end

    def terminal(key, &block)
        raise "duplicate terminal #{key}" if @terminals.include? key
        
        @terminals[key] = block
    end

    def to_s
        return "LSystem
  Name: #{@name}
  Start: #{@start}
  Alphabet: #{@alphabet.to_a.join(" ") }
  Terminals: #{@terminals.keys.join(" ") }
  Rules:
#{@rules.map { |k, v| "    #{k}#{v}" }.join("\n")}
"
    end

    def forward(distance=1.0)
        emit "<!-- forward(#{distance}) -->" if @debug
        emit "<!-- x = #{@x}, y = #{@y}, r = #{@r} -->" if @debug

        # Intentionally reversed to rotate
        x1, y1 = @x, @y
        x2 = (x1 - 100.0 * distance * Math.sin(@r)).round(2)
        y2 = (y1 - 100.0 * distance * Math.cos(@r)).round(2)

        emit "<line x1=\"#{x1}\" y1=\"#{y1}\" x2=\"#{x2}\" y2=\"#{y2}\" />"

        @x, @y = x2, y2
        update_bounds
    end

    def push
        emit "<!-- push(#{[@x, @y, @r]}) on to #{@stack} -->" if @debug
        @stack.push([@x, @y, @r])
    end

    def pop
        emit "<!-- pop from #{@stack} -->" if @debug
        @x, @y, @r = @stack.pop
    end

    def rotate(angle, radians=false)
        emit "<!-- rotate(#{angle}, #{radians}) -->" if @debug

        angle = Math::PI * angle / 180.0 unless radians
        @r += angle
    end

    def to_svg(n, debug = false)
        @bounds = [0, 0, 0, 0]
        @x = 0
        @y = 0
        @r = 0
        @stack = []
        @output = []
        @debug = debug

        # Slow mode (calculate first)
        if SLOW_MODE
            # Expansion step
            state = @start
            n.times do
                state = state.chars.map { |c| @rules[c] or c }.join
            end

            # Evaluation step
            state.chars.each { |c| self.instance_eval(&@terminals[c]) if @terminals.include?(c) }

        # Fast mode (calculate as we go)
        else
            def recur(c, depth)
                if depth == 0
                    self.instance_eval(&@terminals[c]) if @terminals.include?(c)
                else
                    (@rules[c] or c).chars.each do
                        |c| recur(c, depth - 1)
                    end
                end
            end
            recur(@start, n)
        end


        viewport = "#{@bounds[0]} #{@bounds[1]} #{@bounds[2]-@bounds[0]} #{@bounds[3]-@bounds[1]}"
        return %{<?xml version="1.0" standalone="no"?>
<svg viewBox="#{viewport}" version="1.1" xmlns="http://www.w3.org/2000/svg">
\t<g stroke="black" fill="transparent" stroke-width="5">
\t\t#{@output.join("\n\t\t")}
\t</g>
</svg>
}
    end

private
    def emit(svg)
        @output.append svg
    end

    def update_bounds
        @bounds = [
            [@bounds[0], @x].min,
            [@bounds[1], @y].min,
            [@bounds[2], @x].max,
            [@bounds[3], @y].max,
        ]
    end
end

In particular, this is the entirety of the parsing code:

def initialize(name, &block)
    @name = name
    @start = nil
    @alphabet = Set[]
    @terminals = Set[]
    @rules = {}
    @terminals = {}

    self.instance_eval(&block)
end

def start(key)
    @start = key
end

def rule(key, value)
    raise "duplicate key #{key}" if @rules.include? key

    @rules[key] = value
    @alphabet.add key
    value.chars.each { |k| @alphabet.add k }
end

def terminal(key, &block)
    raise "duplicate terminal #{key}" if @terminals.include? key
    
    @terminals[key] = block
end

Where it gets rather more interesting is in the to_svg function that actually turns an L-System into something we can look at:

def to_svg(n, debug = false)
    @bounds = [0, 0, 0, 0]
    @x = 0
    @y = 0
    @r = 0
    @stack = []
    @output = []
    @debug = debug

    # Slow mode (calculate first)
    if SLOW_MODE
        # Expansion step
        state = @start
        n.times do
            state = state.chars.map { |c| @rules[c] or c }.join
        end

        # Evaluation step
        state.chars.each { |c| self.instance_eval(&@terminals[c]) if @terminals.include?(c) }

    # Fast mode (calculate as we go)
    else
        def recur(c, depth)
            if depth == 0
                self.instance_eval(&@terminals[c]) if @terminals.include?(c)
            else
                (@rules[c] or c).chars.each do
                    |c| recur(c, depth - 1)
                end
            end
        end
        recur(@start, n)
    end


    viewport = "#{@bounds[0]} #{@bounds[1]} #{@bounds[2]-@bounds[0]} #{@bounds[3]-@bounds[1]}"
    return %{<?xml version="1.0" standalone="no"?>
<svg viewBox="#{viewport}" version="1.1" xmlns="http://www.w3.org/2000/svg">
<!--
#{self} 
#{n} iterations: #{state}
-->
\t<g stroke="black" fill="transparent" stroke-width="5">
\t\t#{@output.join("\n\t\t")}
\t</g>
</svg>
}
end

We’re going to have a number of helper functions (do those next), but essentially, we’re going to stake the single @start character (although it can totally be a starting string) and expand it a number of times:

# Expansion step
state = @start
n.times do
    state = state.chars.map { |c| @rules[c] or c }.join
end

# Evaluation step
state.chars.each { |c| self.instance_eval(&@terminals[c]) if @terminals.include?(c) }

The problem with doing it this way though is that it can be rather memory intensive as it has to keep the entire string in memory–and some of these systems get very very large very quickly. So I made a quicker version that solves it recursively:

def recur(c, depth)
    if depth == 0
        self.instance_eval(&@terminals[c]) if @terminals.include?(c)
    else
        (@rules[c] or c).chars.each do
            |c| recur(c, depth - 1)
        end
    end
end
recur(@start, n)

It’s fairly similar, but this one uses the stack to track only the parts of the string we’re working on, rather than the whole thing. This wouldn’t work nearly as well for doing contextual translations (a TODO for next time) where you need to have the surrounding characters as well, but I think it could still be made to work. We’ll see!

And then finally, we have to add a handful more helpers that can actually be used to generate the systems:

def forward(distance=1.0)
    emit "<!-- forward(#{distance}) -->" if @debug
    emit "<!-- x = #{@x}, y = #{@y}, r = #{@r} -->" if @debug

    # Intentionally reversed to rotate
    x1, y1 = @x, @y
    x2 = (x1 - 100.0 * distance * Math.sin(@r)).round(2)
    y2 = (y1 - 100.0 * distance * Math.cos(@r)).round(2)

    emit "<line x1=\"#{x1}\" y1=\"#{y1}\" x2=\"#{x2}\" y2=\"#{y2}\" />"

    @x, @y = x2, y2
    update_bounds
end

def push
    emit "<!-- push(#{[@x, @y, @r]}) on to #{@stack} -->" if @debug
    @stack.push([@x, @y, @r])
end

def pop
    emit "<!-- pop from #{@stack} -->" if @debug
    @x, @y, @r = @stack.pop
end

def rotate(angle, radians=false)
    emit "<!-- rotate(#{angle}, #{radians}) -->" if @debug

    angle = Math::PI * angle / 180.0 unless radians
    @r += angle
end

def emit(svg)
    @output.append svg
end

def update_bounds
    @bounds = [
        [@bounds[0], @x].min,
        [@bounds[1], @y].min,
        [@bounds[2], @x].max,
        [@bounds[3], @y].max,
    ]
end

It’s kind of funny that I made emit a function, since we’re not actually emitting SVG (only debug) other than in the forward function, but that could change if we do other sorts of things (circles or arcs or whatever). It’s half a remnant of an earlier structure (where I was using g elements with transform attributes for everything) and half future proofing. We could easily add those as functions though!

And that’s about it!

Here are a few of the examples from the Wikipedia page:

$ begin
      ruby examples/barnsley-fern.rb 5 > output/barnsley-fern.svg
      ruby examples/binary-tree.rb 8 > output/binary-tree.svg
      ruby examples/dragon-curve.rb 8 > output/dragon-curve.svg
      ruby examples/sierpinski-arrowhead.rb 8 > output/sierpinski-arrowhead.svg
  end
require './lsystem.rb'

ls = LSystem.new("Barnsley Fern") do
    start "+++X"

    rule "X", "F+[[X]-X]-F[-FX]+X" 
    rule "F", "FF"

    terminal "F" do forward end
    terminal "[" do push end
    terminal "]" do pop end
    terminal "-" do rotate -25 end
    terminal "+" do rotate +25 end
end

iterations = ARGV.length > 0 ? ARGV[0].to_i : 4
puts ls.to_svg(iterations)
require './lsystem.rb'

ls = LSystem.new("Binary tree") do
    start "0"

    rule "1", "11"
    rule "0", "1[0]0"

    terminal "0" do forward end
    terminal "1" do forward end
    terminal "[" do
        push
        rotate -45, degrees = true
    end
    terminal "]" do
        pop
        rotate 45, degrees = true
    end
end

iterations = ARGV.length > 0 ? ARGV[0].to_i : 4
puts ls.to_svg(iterations)
require './lsystem.rb'

ls = LSystem.new("Dragon Curve") do
    start "F"

    rule "F", "F+G"
    rule "G", "F-G"

    terminal "F" do forward end
    terminal "G" do forward end
    terminal "+" do rotate -90 end
    terminal "-" do rotate 90 end
end

iterations = ARGV.length > 0 ? ARGV[0].to_i : 4
puts ls.to_svg(iterations)
require './lsystem.rb'

ls = LSystem.new("Sierpinski arrowhead curve") do
    start "A"

    rule "A", "B-A-B"
    rule "B", "A+B+A"

    terminal "A" do forward end
    terminal "B" do forward end
    terminal "+" do rotate -60 end
    terminal "-" do rotate 60 end
end

iterations = ARGV.length > 0 ? ARGV[0].to_i : 4
puts ls.to_svg(iterations)

There are a pile of things more I could do with this, including probabalistic rules (choose one of many randomly based on pre-set chances) and contextual rules (see what’s around a character before expanding it). We’ll have to see how it goes!