L-systems in PostScript

Although PostScript can be used for programming crazy things, such as computing prime numbers, it can also be used for graphics. The nice thing about PostScript, is that it's not just a way to describe images, but to actually build images, as it has the full power of a programming language. So, it allows you to write small programs that make the printer compute an image (and, incidentally, print it).

I've always been fascinated with the Dragon Curve. One of the first program I ever wrote was a Pascal program that drew it. The Dragon Curve, like all fractals, is highly recursive. Interestingly enough, my Pascal program was not, as I understood nothing about recursion at that time. (It seemed to be just a complicated way to program simple things like factorials or GCDs.) I wish I could dig up that program today. It must have been a remarkable piece of junk.

While in California, I found on the web a PostScript program that draws the Dragon Curve. It intrigued me enough to actually make me learn PostScript just to understand the program. But that didn't help me understand the algorithm. Although by then I had a better understanding of recursion (the Towers of Hanoi had enlightened me years before, way more successfully than factorials or GCDs), I was still unable to understand how this program, which relied on two mutually recursive functions and rotations of 45 degrees (all angles in a Dragon Curve are right angles), could draw a Dragon Curve.

Three years later, as my was doing some Spring cleaning on my account, getting rid of old files, I stumbled across this Dragon Curve program and decided to have another look at it. I was now teaching recursive programming in ML, and started to write my own recursive code to draw the Dragon. But what I obtained wasn't even close to this mysterious code I had. If you clean it up (the original code used global variables between recursive calls instead of relying on the stack, which is a crime), you end up with two mutually recursive functions X and Y, and a nonrecursive function F that does the drawing:

                   X -> -FX++FY-
                   Y -> +FX--FY+
                   F ->

I found that set of equations remarkable, certainly too good to have been invented by a guy who uses global variables between mutually recursive functions. So, I looked for Dragon Curve programs on the web, and eventually found somewhere that exact set of equations. It was part of a list of L-systems that drew everything from classic fractals (Hilbert, Koch) to various plant-like pictures.

Here is what I learned that day about L-systems. L-system is short for Lindenmayer System, after Aristid Lindenmayer who, interestingly enough, was a biologist from Sweden. He used these systems to model the growth of plants, and published papers both in biology and computer science journals. Those systems have been extended to 3D and widely used in plant biology and computer graphics. The reference book seems to be The Algorithmic Beauty of Plants, by Przemyslaw Prusinkiewicz and Aristid Lindenmayer. Although all the equations that are used in this page were found on the web, I strongly suspect they originated from this book. (All I can say is that they are definitely not mine.)

Using the set of equations above (starting from X), and applying their rules iteratively, here is what you get (read a curve from left to right, starting horizontally):

1	-F++F-
2	--F++F-+++F--F+-
3	---F++F-+++F--F+-+++-F++F---+F--F++-
4	----F++F-+++F--F+-+++-F++F---+F--F++-+++--F++F-+++F--F+---+- F++F---+F--F+++-
5	-----F++F-+++F--F+-+++-F++F---+F--F++-+++--F++F-+++F--F+---+ -F++F---+F--F+++-+++---F++F-+++F--F+-+++-F++F---+F--F++---+- -F++F-+++F--F+---+-F++F---+F--F++++-
6	------F++F-+++F--F+-+++-F++F---+F--F++-+++--F++F-+++F--F+--- +-F++F---+F--F+++-+++---F++F-+++F--F+-+++-F++F---+F--F++---+ --F++F-+++F--F+---+-F++F---+F--F++++-+++----F++F-+++F--F+-++ +-F++F---+F--F++-+++--F++F-+++F--F+---+-F++F---+F--F+++---+- --F++F-+++F--F+-+++-F++F---+F--F++---+--F++F-+++F--F+---+-F+ +F---+F--F+++++-
7	-------F++F-+++F--F+-+++-F++F---+F--F++-+++--F++F-+++F--F+-- -+-F++F---+F--F+++-+++---F++F-+++F--F+-+++-F++F---+F--F++--- +--F++F-+++F--F+---+-F++F---+F--F++++-+++----F++F-+++F--F+-+ ++-F++F---+F--F++-+++--F++F-+++F--F+---+-F++F---+F--F+++---+ ---F++F-+++F--F+-+++-F++F---+F--F++---+--F++F-+++F--F+---+-F ++F---+F--F+++++-+++-----F++F-+++F--F+-+++-F++F---+F--F++-++ +--F++F-+++F--F+---+-F++F---+F--F+++-+++---F++F-+++F--F+-+++ -F++F---+F--F++---+--F++F-+++F--F+---+-F++F---+F--F++++---+- ---F++F-+++F--F+-+++-F++F---+F--F++-+++--F++F-+++F--F+---+-F ++F---+F--F+++---+---F++F-+++F--F+-+++-F++F---+F--F++---+--F ++F-+++F--F+---+-F++F---+F--F++++++-

If you "round the corners", you better see how the curve is drawn. Here it is, at order 7:

Now, here's the PostScript program that does the job.

First, tell the printer it's a PostScript file:

          %!PS

          /order 7 def

          /START { X } def
          /X {
            dup 0 ne
            {1 sub 4 {dup} repeat - F X + + F Y -}
            if pop
          } def
          
          /Y {
            dup 0 ne
            {1 sub 4 {dup} repeat + F X - - F Y +}
            if pop
          } def

          /F {
            0 eq { 10 0 rlineto } if 
          } bind def

          /- { -45 rotate } bind def
          /+ { 45 rotate } bind def

          1 setlinejoin
          1 setlinecap

          newpath
          220 180 moveto
          50 order { 2 sqrt div } repeat dup scale

          90 rotate
          order START

          stroke
          showpage

On my way to understand the mysteries of this Dragon Curve program that I had, I've encountered a number of L-system equations. Some of them are classic fractals, like Hilbert's curve:

angle 90 START -> X X -> -YF+XFX+FY- Y -> +XF-YFY-FX+

or Koch's snowflake:

angle 60 START -> +F--F--F F -> F+F--F+F

But the ones I liked best were plant-like pictures, like those on this page. What I find interesting about them is how different they are from each other while based on similar sets of equations. My two favorites are below:

angle 22.5 START -> F F -> FF-[-F+F+F]+[+F-F-F]
angle 22.5 START -> X X -> F-[[X]+X]+F[+FX]-X F -> FF

I have not mentioned [ and ] which are used for branching. Basically, ] brings you back in the drawing at the point where the corresponding [ was issued. They are easily implemented in PostScript using gsave and grestore which pushes and pops the graphics context on and off the stack.

Here is the PostScript code for the first of these two. Code for the other one (as well as all other plants on this page) is identical except for the equation. This code looks a little more complicated than the Dragon Curve before, but it's mostly because of colors and because it's made generic to work with many different equations and coloring schemes.

PostScript is a lot of fun. Recursive functions are a lot of fun. But the two together can be an amazing waste of precious time...

Michel Charpentier <>