Write down a word. Replace every letter in it at once, using a short list of rules. Do it again. Then hand the result to a turtle that reads F as "step forward" and + as "turn left". Out come ferns, weeds, snowflakes and space-filling curves. And if you fold a strip of paper in half a dozen times and open it out, you get a dragon.
Common mix-up: an L-system is not a drawing program. It is a grammar that produces a string of letters; the drawing is a separate step, an interpretation of that string by a turtle. The same string can be drawn with a different angle or step and look entirely different, and some L-systems, like Lindenmayer's algae, were never meant to be drawn at all.
Aristid Lindenmayer was a Hungarian-born biologist working at Utrecht who studied how simple multicellular organisms grow, in particular filaments of algae: chains of cells where each cell, depending on its state, either divides or matures. In 1968 he published a way to describe that growth with symbols. Each kind of cell is a letter. Each rule says what a cell of that kind becomes one time step later. Apply all the rules to all the cells at once, and you get the next stage of the filament.
The textbook version has two letters. A is a mature cell, ready to divide; B is a young cell that needs one step to mature. The rules are A → AB (a mature cell divides into a mature cell and a young one) and B → A (a young cell matures). Start from a single A, called the axiom, and rewrite:
That Fibonacci pattern isn't a coincidence you have to take on trust. Each word is the word before it with the word before that tacked on the end: ABAAB is ABA followed by AB. So the lengths obey the Fibonacci rule, and the ratio of the number of A's to B's approaches the golden ratio, about 1.618.
What made Lindenmayer's systems different from the grammars linguists were already using is the phrase "all at once". Noam Chomsky's grammars of the 1950s rewrite one symbol at a time, which is a good model of building a sentence. Cells in a living organism don't wait their turn; they all divide in the same hour. This parallel rewriting is the defining feature of an L-system (L for Lindenmayer), and it is what makes the strings grow so explosively: every letter can turn into several letters in a single step.
The simplest L-systems, the kind used in most of this chapter, are called D0L systems: deterministic (each letter has exactly one rule) and context-free, or "0-sided" (a letter's rule ignores its neighbors). The algae system is D0L.
Lindenmayer's 1968 paper also considered rules that look at a cell's neighbors, so that a signal can travel along the filament from one cell to the next. These are context-sensitive, or IL, systems. Later work added parameters (a letter carries numbers, such as its length or age, and rules can test them) and stochastic rules, which this chapter meets below. Przemysław Prusinkiewicz and Lindenmayer's book The Algorithmic Beauty of Plants (1990) covers the whole family, with the plant pictures that made L-systems famous.
Because each letter in a D0L system rewrites independently, you can count how a string grows without building it. Keep a count of each letter; one step multiplies that vector of counts by a fixed matrix. The string's length grows, in the long run, like the largest eigenvalue of that matrix raised to the generation. For the algae, that eigenvalue is the golden ratio.
A string of letters is not a picture. To get a picture you need an interpretation, and the one everybody uses comes from Logo, the programming language Seymour Papert and colleagues designed for children in the late 1960s. Logo had a "turtle": a cursor with a position and a heading that you steer with commands like FORWARD 10 and LEFT 90, leaving a line behind it. In the 1980s Prusinkiewicz connected the two ideas: read an L-system's string one letter at a time, and treat each letter as a turtle command.
| Symbol | The turtle… |
|---|---|
| F | steps forward one unit, drawing a line. (Other letters can be told to draw too; G, A and B often do.) |
| f | steps forward one unit without drawing. |
| + | turns left by the angle δ. |
| − | turns right by δ. |
| | | turns around, 180°. |
| [ | remembers its position and heading, pushing them on a stack. |
| ] | jumps back to the last remembered position and heading, popping the stack. |
| X, Y, … | does nothing. These letters exist only to steer the rewriting. |
Take the Koch curve from Chapter 3. Its construction says: replace every straight segment by four segments a third as long, with a bump in the middle. In turtle language, one segment is F, and the bump is F+F−−F+F with δ = 60°: forward, turn left 60°, forward, turn right 120°, forward, turn left 60°, forward. So the whole construction is one rule, F → F+F−−F+F. Start from F++F++F, a triangle, and you get the snowflake. Each generation multiplies the number of F's by four. To keep the drawing the same size you shrink the step by three each time, which is exactly the Koch curve's dimension, log 4 / log 3 ≈ 1.2619, written in the rule.
The non-drawing letters are a quiet but powerful trick. In the Hilbert curve, A and B never draw anything; they mark the places where the curve will be refined next generation, and which way round. The rewriting is done by the invisible letters, and the turtle only ever draws the F's they leave behind.
The turtle always takes unit steps, so a higher generation draws a bigger picture: the Koch snowflake gets three times wider per generation. Programs, including the editor below, rescale the finished drawing to fit the screen, which is the same as shrinking the step. If a rule multiplies the number of drawn segments by N each generation while the picture grows by a factor r in width, the limit has dimension log N / log r. For Koch, N = 4 and r = 3. For the Hilbert curve N is (almost exactly) 4 and r is 2, so the dimension is 2: the curve fills the square.
The square brackets are what make L-systems botanical. A turtle that meets [ remembers where it is; when it reaches the matching ], it teleports back. Everything in between is a side branch. The rule F → F[+F]F[−F]F says: a stem segment becomes a stem with a branch to the left partway up and a branch to the right further up. Apply it five times with δ = 25.7° and you get a convincing weed, because every segment, including every branch, has sprouted branches of its own.
Two refinements make plants look much more alive. The first is an apex letter like X that doesn't draw but marks a growing tip: X → F[+X]F[−X]+X, F → FF. Here the tips do the branching, while old stem segments simply double in length each generation, F → FF, the way a real stem elongates. The second is choosing the angle carefully. Many of the classic examples use angles like 22.5°, 25.7° and 20°, chosen by eye to look like real plants, not derived from botany.
| Plant | Axiom | Rules | δ | Gens |
|---|---|---|---|---|
| Weed | F | F → F[+F]F[−F]F | 25.7° | 5 |
| Bush | F | F → FF−[−F+F+F]+[+F−F−F] | 22.5° | 4 |
| Twig | X | X → F[+X]F[−X]+X, F → FF | 20° | 7 |
| Sprig | X | X → F[+X][−X]FX, F → FF | 25.7° | 7 |
| Fern-like | X | X → F−[[X]+X]+F[+FX]−X, F → FF | 22.5° | 5 |
All five come from Figure 1.24 of Prusinkiewicz and Lindenmayer, The Algorithmic Beauty of Plants. Each is a preset in the editor below.
Real plants are modular. A shoot grows by repeating the same unit, a stem segment with a leaf and a bud, again and again, and buds grow into shoots that repeat the same unit. Botanists describe plants in exactly these terms, and an L-system with brackets is a direct transcription: a letter for the unit, brackets for the bud that becomes a side shoot. The self-similarity is real biology, just cut off after a handful of levels.
What the simple systems leave out is the environment. Real branches compete for light, die back when shaded, and bend under their own weight. Later L-system research added "environmentally sensitive" and "open" L-systems, in which the string can query the world (is this bud in shade?) and the answer changes which rule fires.
Pick a preset or write your own. Rules go one per line as X=… (an arrow works too). Several rules for the same letter, each starting with a probability in brackets like F=(0.33)F[+F]F, make a stochastic system; press "Re-roll" for a different plant from the same rules. The editor really rewrites the string, shows how long it gets, and draws it, progressively for big strings. It stops before a string passes three million letters.
Every deterministic L-system draws the same picture every time, and a field of identical weeds looks wrong at once. The fix is to give a letter several possible rules, each with a probability, and let chance choose one every time that letter is rewritten. With F → F[+F]F[−F]F, F[+F]F and F[−F]F at roughly a third each, some segments branch both ways, some only left, some only right. The overall character, the angle, the density and the way it tapers, stays the same, while every individual plant is different.
The randomness has to be applied per letter, not per generation. If you flipped one coin per generation and applied the winning rule to every F, all the branches at that level would make the same choice and the plant would still be perfectly symmetric in its own way. Choosing independently for each F, every time, is what breaks up the regularity.
In practice, the dice are a seeded pseudorandom number generator, so a given seed reproduces the same plant exactly. That is how a forest in a film can be both varied and repeatable: store each tree's seed, not its geometry. The editor's "Re-roll" button changes the seed.
There is a family resemblance to Chapter 4. There, a deterministic set of maps had a fixed attractor and the dice only chose the order of visits. Here the dice change the shape itself, because each choice is baked into the string and never revisited. A stochastic L-system describes a probability distribution over plants, and each run draws one sample from it.
Almost every curve in Chapter 3 can be written as a two-line L-system, and seeing them side by side shows how much they share. Each rule replaces a segment by several smaller segments arranged by turns; the dimension comes from how many segments replace one, and how much smaller they are.
| Curve | Axiom | Rules | δ | Segments ×, size ÷ | Dimension |
|---|---|---|---|---|---|
| Koch snowflake | F++F++F | F → F−F++F−F | 60° | 4, 3 | 1.2619 |
| Sierpinski arrowhead | A | A → B−A−B, B → A+B+A | 60° | 3, 2 | 1.585 |
| Sierpinski triangle | F−G−G | F → F−G+F+G−F, G → GG | 120° | 3 triangles, 2 | 1.585 |
| Hilbert curve | A | A → +BF−AFA−FB+, B → −AF+BFB+FA− | 90° | 4, 2 | 2 |
| Heighway dragon | FX | X → X+YF+, Y → −FX−Y | 90° | 2, √2 | 2 (boundary 1.5236) |
| Lévy C curve | F | F → +F−−F+ | 45° | 2, √2 | 2 |
| Gosper curve | A | A → A−B−−B+A++AA+B−, B → +A−BB−−B−A++A+B | 60° | 7, √7 | 2 (boundary ≈ 1.129) |
Several of these have names attached. David Hilbert described his curve in 1891, a year after Giuseppe Peano showed that a continuous curve can pass through every point of a square. Paul Lévy studied the C curve in 1938. The Gosper curve, also called the flowsnake, is due to Bill Gosper in the 1970s and was popularized by Martin Gardner in 1976; seven copies of the region it fills fit together into a larger copy of the same shape.
The arrowhead version of the Sierpinski triangle is worth a look in the editor. It draws one continuous path, never lifting the pen, that traces out the triangle with all its holes. The "triangle" version instead draws the outlines of the small triangles, with G as a second drawing letter that only ever doubles.
The Hilbert curve visits the four quarters of a square in order, but in each quarter it must be rotated or reflected so that its exit lines up with the next quarter's entrance. A single letter can't remember which way round it is. A and B are the two mirror-image orientations, and the rules say how each orientation's four sub-curves are oriented: A becomes B, A, A, B with turns between, and B becomes A, B, B, A. That bookkeeping is the whole difficulty of the Hilbert curve, and the L-system states it in two lines.
Take a long strip of paper and fold it in half, always folding the same way, say right end over onto the left. Fold the doubled strip in half again, the same way. Do it a few more times. Now unfold it, opening every crease to exactly a right angle, and look at the strip edge-on. It traces a jagged, curling path that never crosses itself. With more folds it starts to look like a dragon, with a curled tail, a spiny back and a head.
The curve was found in the 1960s by three NASA physicists, John Heighway, Bruce Banks and William Harter, and is called the Heighway dragon (or Harter–Heighway dragon). Martin Gardner wrote about it in his Scientific American column in 1967, and Michael Crichton's novel Jurassic Park used successive stages of it to head its sections.
Why does folding make a fractal? Look at what each fold does. Folding the strip in half and unfolding gives two segments at a right angle. Fold twice and unfold: the strip is the one-fold curve, followed by a copy of the one-fold curve rotated by 90° about its end. Every extra fold does the same thing: the new curve is the old curve plus a copy of itself, swung around the end point by a right angle. That is the unfolding the instrument below animates, and it means the dragon after n folds has 2ⁿ segments.
The sequence explains itself if you look at it the right way. Every other crease (the odd ones) was made by the last fold, and they alternate R, L, R, L, because the strip was doubled and alternate layers face opposite ways. Remove those, and the remaining creases are the sequence for one fewer fold. So the paperfolding sequence contains itself, a fractal in a line of letters.
The dragon is also an L-system, X → X+YF+ and Y → −FX−Y with δ = 90°, starting from FX, and also an iterated function system with two maps, the scaled rotations z → (1 + i) z / 2 and z → 1 − (1 − i) z / 2. The IFS editor in Chapter 4 has it as a preset. Three different machines, one dragon.
J's JellyDazzle app has a dragon-curve fold among its fractal patterns, and this section is the folding behind the name.
Not many. Each fold doubles the thickness and, for a strip folded in one direction, roughly halves the length available, so the paper runs out fast. Seven or eight folds is the usual limit for an ordinary sheet. In 2002 the high-school student Britney Gallivan worked out the length a strip needs for a given number of folds and then folded a very long strip of paper in half twelve times. The instrument goes to sixteen because pixels are thinner than paper.
Choose how many times to fold the strip, then press "Unfold". The animation opens the creases in the reverse of the order they were made: the last fold opens first, swinging half the strip round the end by 90°, then the next fold, and so on, until every crease sits at a right angle. Color runs along the strip from one end to the other. "Twindragon" and "Four dragons" add rotated copies around the starting point to show how dragons tile.
The first creases of the unfolded strip, read from the starting end (R = right turn, L = left):
The dragon never crosses itself. Segments meet at corners, but no stretch of strip is ever drawn twice. As the folds increase and the segments shrink, the curve fills a region of the plane solidly. In the limit it has positive area and dimension 2, like the Hilbert curve. All the fractal roughness moves to the edge of that region, the dragon's boundary, and that boundary has dimension about 1.5236.
Place two dragons back to back, joined at their starting points with one turned through 180°, and their regions fit together without overlapping into a shape called the twindragon. Copies of the twindragon tile the whole plane, and so do copies of the dragon itself: four dragons rotated by 90° about a shared starting point fit together around it without overlap. Chandler Davis and Donald Knuth worked out these tilings in their 1970 paper "Number Representations and Dragon Curves".
That paper's title points at a lovely fact. Write numbers in base −1 + i, a complex number, using only the digits 0 and 1. The numbers whose expansion has only digits after the point, the "fractions" of this strange base, fill exactly a twindragon. Knuth uses it as an illustration of complex-base number systems in The Art of Computer Programming. A shape you get by folding paper is also the shape of the fractional parts of a number system.
In ordinary base 10, the numbers 0.d₁d₂d₃… fill the interval from 0 to 1, and the interval is made of ten copies of itself scaled by a tenth: 0.0…, 0.1…, up to 0.9…. Shifting by whole numbers tiles the line with copies of the interval.
Base −1 + i has |−1 + i| = √2, so dividing by it shrinks by √2 and rotates by 135°. With digits 0 and 1, the "fractional part" set T satisfies T = (T ∪ (T + 1)) / (−1 + i): two copies of itself, each scaled by 1/√2 and rotated. That is a two-map IFS, and its attractor is the twindragon. Every Gaussian integer a + bi can be written in this base with digits 0 and 1, which is what makes the shifted copies T + (a + bi) cover the plane without overlap, the same way the shifted unit intervals tile the line.