In the post about Koch curves, I talked about how a grammar-rewrite system could be used to describe fractals. There’s a bit more to the grammar idea that I originally suggested. There’s something called an L-system (short for Lindenmayer system, after Aristid Lindenmayer, who invented it for describing the growth patterns of plants), which is a variant of the Thue grammar, which is extremely useful for generating a wide range of interesting fractals for describing plant growth, turbulence patterns, and lots of other things.
The main difference between an L-system and a simple grammar rewrite system is that in a simple rewrite system, in each step, you replace an occurence (or sometimes all occurences) of one symbol – the left-hand side of the grammar rule – with the contents of the right-hand side of the grammar rule. In an L-system, in each step, you replace all instances of all symbols that match any rule as a single atomic step.
Both simple rewrite systems and L-systems take the same inputs – a grammar, but the behave differently. If you think of them as computation systems, L-systems have a kind of parallelism to them. Let’s look at how they’re made up, and then I’ll show you an example of how different their results can be.
The grammar of L-systems and simple rewrite systems consist of:
- A set
of symbols, called non-terminal symbols
- A set
of symbols, called non-terminal symbols
- A set
of rewrite-rules that map from a symbol
to a sequence of symbols from
. Each rule in R says that the non-terminal symbol l can be replaced by the sequence of symbols in rhs.
- A special distinguished symbol in S called the initiator. Every use of the rewrite system will start with a single instance of the initiator.
To demonstrate the difference, let’s look at a simple grammar, and its evolution as an L-system compared to a simple rewrite system. The non-terminal symbols consist of {A,B}; the terminal symbols set will be empty; and the initiator will be “A”.
- A → AB
- B → A
Here’s a sequence of steps from the simple rewrite and the L-system:
| Simple rewrite | L-system |
|---|---|
| AB | AB |
| AA | ABA |
| ABAB | ABAAB |
| AAAA | ABAABABA |
| ABABABAB | ABAABABAABAAB |
The parallelism of the L-system is very useful in defining fractals; it’s part of the key to why some fractals can be described so easily and naturally using L-systems: the self-similarity of the fractal in different positions corresponds to the parallel expansions. For example, here’s a version of Cantor’s dust as an L-system:
- Non-terminals: {B,W}; terminals={}
- Rules: B→BWB, W→WWW
- Initiator: B
A series of steps of this are: “B”, “BWB”, “BWBWWWBWB”, “BWBWWWBWBWWWWWWWWWBWBWWWBWB”. If you think of “B” as “black point”, and “W” as “white point”, then you can easily see that the limit of this L-system is a drawing of the Cantor dust. And you can also see how the parallelism of the L-system makes it work so easily. Without it, you’d need to do something like horizontal passes across the string; and to do that, you would need to add some kind of place-holder into the rules to keep track of which symbols had been modified by a given pass. The L-system makes it much easier.
A neater example of how we can do fractals using L-systems is a tracing of the Sierpinski gasket. This is very typical of how we do fractal curves with L-systems: the grammar generates a set of instructions for a pen or turtle. (There are other tricks for how to use L-systems for higher dimension structures, but for this post, we’ll stick with curves.
To trace the gasket, we’ll use a set of symbols with meanings for turtle drawings:
- “+” is a terminal symbol which means “turn right 60 degrees”.
- “-” is a terminal symbol which means “turn left 60 degrees”.
- “1” and “2” are both non-terminal symbols which mean “go forward”. We use the two different symbols for “forward” because there are two different kinds of expansions, which should
alternate.
- Rules:
- 1 → 2-1-2
- 2 → 1+2+1
- Initiator: 1
Over to the right is the sierpinski tracing after 6 iterations.
One of the more famous self-intersecting fractal curves, the dragon curve, is very natural as an L-system; it involves one more trick beyond what we’ve done so far – the instruction string is going to include no-ops to drive the expansions; all of the instructions are terminal symbols; non-terminals are interspersed, and do the actual work of generating the fractal structure.
- Terminals:
- +: right 90 degrees
- -: left 90 degrees
- Rules:
- 1 → 1+2f+
- 2 → -f1-2
- Initiator: “f1”
Over to the right is the dragon after 8 iterations.
One last one for today – it’s quite hairy for a planar L-system, but it’s a good one! I came across this on Wikipedia; I haven’t seen it elsewhere described via an L-system. It’s a fractal fern – a pattern that comes out looking like a sprig of dill or a frond of fennel. The complexity of it comes from the way it handles the branches in the fronds: in addition to the use of non-terminals as expansion drivers, it also uses a stack. The stack marks a position and direction that the turtle was facing at a particular point in time. There’s a terminal symbol that indicates that the current position/heading should be pushed onto the stack, and a terminal that indicates that the stack should be popped, and the turtle set to the position heading in the popped value.
- Terminals:
- Fwd: move forwards drawing a line.
- Right: rotate right 25 degrees.
- Left: rotate left 25 degrees.
- [: push turtle position/heading.
- ]: pop turtle position/heading.
- Non-terminals:
- X
- Rules:
- X → Fwd,Left[[X]Right,X]Right,Fwd[Right,Fwd,X]Left,X
- Fwd → Fwd,Fwd
And here’s the result of running it for 6 iterations:
Long time fan and lurker MCC, I was wondering if you would grace us with a Good Math/Bad Math look at the Kane Paper that is being discussed over at deltoid and at crooked timber.
Might not be your area of interest, but it seems ripe for a bad math smackdown.
I’m awfully sorry, but it’s not at all clear to me in what sense this fractal stuff can truly be said to “describe” the growth of a plant like a fern. If you look at a real living fern, you see that what is most interesting about it is that it is not in any sense fractal: at the leaf tips, there’s a blurring and a complete lack of differentiation of parts that directly contradicts any claim of fractality. Please go out into your garden and observe.
Fascinating stuff. Thanks!
Oh, and a microscopic nit:
— A set T of symbols, called non-terminal symbols —
Shouldn’t this be terminal symbols?
My fiance is a computer animator, and he plays with this program a lot: http://home.wanadoo.nl/laurens.lapre/lparser.html
It’s called Lparser and it will generate lots of different L-systems based on your stated parameters. Fun 🙂
Jonathan:
Two points about your comment:
(1) Using fractals to describe natural processes is always an approximation. The fractals we use to model things are infinite; real things are finite. So when you’re thinking about a fractal as a model for something real, you’ve got to think of the real thing as corresponding to the state after some finite number of iterations. The fractal says the fern branches forever; that’s obviously not true.
(2) The fern fractal is particularly compelling if you watch
it being drawn. The way that the fractal builds the fern is actually very similar to the way that a real fern grows. The stem starts, branches; as it branches, the initial stem grows longer, and eventually sprouts another branch. In fact, as the fern grows, any stem that reaches a certain length will sprout a new branch. It doesn’t matter whether it’s the initial stem, or the 50th branch; when it gets big enough to support another branch, it will sprout one – which is what we see if we watch a dill-like fern grow. It’s actually a good model – it really does describe something very close to the true growth model of the plant. It’s not perfect, but it’s good.
L-systems were designed specifically to model the growth of plants. They’re certainly not perfect – but they do a remarkably good job.
> in a simple rewrite system, in each step, you replace an occurence (or sometimes all occurences) of one symbol – the left-hand side of the grammar rule – with the contents of the right-hand side of the grammar rule
If there are multiple rules, then do you just iterate through the rules in consecutive steps? It seems like that’s what you’re doing with the A -> AB; B -> A example.
What if you’re applying the rules to one symbol instead of all symbols… How do you proceed in consecutive steps in that case?
WaterBreath:
Simple rewrite systems are in principle non-deterministic – at each step, you can apply any rule which matches anything in the string. Real systems, in practice, typically have some kind of fairness constraint – something along the lines of “The least recently used applicable rule will be the next to be invoked”, or “The rules will be applied in the order in which they’re specified”.
Compared to an L-system, a simple rewrite system is less predictable – you need to add extra structure to it to force it to evaluate things the way you’d like it to to evolve a particular kind of structure. If you want to further restrict it to single-replacement, that just gets worse. In order to do something like what we’ve done with the L-system, you need to add symbols to the grammar to create a system of passes, and force it to cycle through passes to emulate the L-system. With single replacement, you need to add two levels of symbols – one to manage the left-to-write cycling of a single rule through the string, and a second to manage passes.
For the A->AB, B->A example, you could see an sequence like:
A,AB,AAB,AAAB,AAAAB,AAAAAB, AAAAAA, AABAAAA, …
Thank you to speedwell.
I was just wandering through the book “Chaos” by James Gleick which reminded me of Dr. P. (P. Prusinkiewicz) my CS 405 prof. I was just last night wondering how his ‘Plant Fractal Generator’ turned out.
During that class I ported the program from Unix to Mac. It was quite interesting (and painful – the Mac had none of the specialized hardware the Silicon Graphics machine had).
Good to see some of the old names given credit in his publication.
Thanks Mark.
Simple rewrites don’t sound so simple after all that. =)
WaterBreath:
This discussion makes simple rewrite systems look complicated. They aren’t really – it’s just that they’re very poorly suited towards the kinds of grammatical expansions that produce fractals, where you really want to capture the idea of iteration over an expanding sequence.
Take a look into the archives for pathological programming, for my article about the language Thue. There you can see some examples of interesting programs written using simple rewrites.
I’m awfully sorry, but it’s not at all clear to me in what sense this fractal stuff can truly be said to “describe” the growth of a plant like a fern.
…
It’s actually a good model – it really does describe something very close to the true growth model of the plant. It’s not perfect, but it’s good. L-systems were designed specifically to model the growth of plants.
I guess the thing that confuses me here is, what does it mean to “describe” a fern? Is there some meaning for the word “describe” here which applies more rigorously than “the output looks like a fern”?
Like, with the system that approaches the Sierpinski triangle, we have a specific idea ahead of time of what a Sierpinski triangle is as a mathematical object, and we could hypothetically prove that the evolving L-system is approaching it. Ferns aren’t mathematical objects, though, they’re natural ones. And they’re not even natural objects following some nice simple set of equations, they’re the emergent outcome of a messy biological process.
I mean, we do have ways of representing natural systems, even messy emergent ones, mathematically. For example, we have climate models that attempt to approximate the fiendishly complex physical interactions in the atmosphere as big systems of differential equations or whatever. We consider these valid because the differential equations are crafted to fit the behavior of gases in experiment, we test the model’s accuracy and place error bars on the model, etc. On the other hand I’ve also seen people attempt to claim some computational system they’ve set up “models” some natural phenomenon or other just because the two look similar to a human observer; this approach seems to me illegitimate. (Okay, so I’m specifically thinking here of Stephen Wolfram and some of the ways he’s attempted to apply cellular automata.) When I see someone saying a fractal “models” or “approximates” or “describes” a natural process, I sometimes find it difficult to tell which of these two situations is occuring.
So is the idea that we say the fern L-system “describes” actual fern growth, we’re just saying that it’s a mathematical model of the way in which someone observed physical ferns to grow and branch? If so, is there some specific practical application for this L-system, or is the idea just to demonstrate a pedagogical point about plant growth?
Models can have so many purposes. Here one can think of modeling branching growth for artistic or commercial purposes (art, anime, games), or to have something that captures growth with branching to understand that part in a toy model.
Physicists amass a lot of toy models that we know are incomplete or inappropriate in some senses, but can in a simpler setting help generate questions or even answers that a more naturalistic model would need to encapsulate.
Coin:
L-systems were invented for describing how plants grow. The point of them is not so much to draw pretty pictures of plants, but to have some formalism for describing how they develop their shapes. The L-system fern isn’t just something that draws a picture of a fern – but it’s a rather simple
way of describing how it grows.
The point of it is more than just pedagogical. It’s descriptive – you can describe specific growth patterns of plants via L-systems; you can compare similar plants, and see how their growth patterns differ. You can do things like look at related plants, and predict what their common ancestors growth pattern was like. It’s a useful tool.
May I suggest that with each of your blog entries, you provide a couple of books that explain the subject in greater detail.
For example, I am very interested in fractals, L-Systems, various language grammars taught to Comp. Sci. students (regular, context free, etc.) and the relationship among them all.
Thanks
Nothing important, just idly wondering: Is there any specific reason to have a separate set of terminal and non-terminal symbols? Couldn’t you get the same effect by just having a set of symbols and a set of rewrite rules, and saying that if you want to find out which symbols are terminal, just pick the ones that don’t appear in any rewrite rule’s lhs?
I mean, it’s not as if it makes a significant difference, it’s just that I don’t see why you should bother having that distinction unless it’s quite necessary.