Lindenmayer Generator

Now we know a pretty nice fractal expression system. It's pretty simple, so it shouldn't be hard to express in python.

Remember that a Lindenmayer System (L-System) takes a set of variable characters, a set of constant characters, a string of start characters, and a set of rules to go from one iteration to the next.

We'll represent each state as a string, and each symbol as a character. The rules will be mapping from a symbol to a replacement, which we represent as a python dictionary. It turns out we don't need variables, because variables are obviously just everything that's a key in the rules dictionary. We also don't need constants, because any character that shows up that isn't a variable must be a constant.

So we just make a standard python generator that, each iteration, yields the axiom and then updates it. To update the axiom, we just apply each rule in turn, which is a standard fold. Or, as python calls it, a reduce:

1
2
3
4

def lindenmayer(axiom, rules):
    while True:
        yield axiom
        axiom = reduce(apply_rule, rules.items(), axiom)

Now we just have to write apply_rule, which takes the current axiom, and a (key, value) pair from rules:

1
2

def apply_rule(axiom, (symbol, replacement)):
    return axiom.replace(symbol, replacement)

Wow, that was easy. But it's not correct! Astute users will notice the issue. We can see the issue if we try to calculate the second iteration of the dragon curve.

If the X rule is applied first (we have no ordering guarantees in a python dictionary), then apply_rule replaces FX with FX+YF.

Then the Y rule is applied and it's all "hey, look, there's a Y!" so it replaces FX+YF with FX+FX-YF.

This is incorrect. The Y rule is expanding a "Y" that was just put there this iteration. We need some way to tell a rule that it can only expand symbols that were there at the beginning of the iteration. How can we do this?

Simple. We say that all keys in the rules dictionary (i.e. all of the variables) must be uppercase. Then when we're doing a replacement, upper case characters are fair game but lower case characters are off limits. Whenever we do a replace, we replace with replacement.lower() instead of just replacement. Then, when we're done, we just have to remember to make everything uppercase again.¹

1
2
3
4
5
6
7
8
9

def lindenmayer(axiom, rules):
    rules = rules.items()

    def apply_rule(axiom, (symbol, replacement)):
        return axiom.replace(symbol, replacement.lower())

    while True:
        yield axiom
        axiom = reduce(apply_rule, rules, axiom).upper()

And here's some tests:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

>>> dragon = lindenmayer('FX', {
...     'X': 'X+YF',
...     'Y': 'FX-Y',
... })
>>> dragon.next()
'FX'
>>> dragon.next()
'FX+YF'
>>> dragon.next()
'FX+YF+FX-YF'
>>> dragon.next()
'FX+YF+FX-YF+FX+YF-FX-YF'

Looks like it's working! Now on to actually doing something with these L-System strings.