Execute a Lindenmayer System

A Lindenmayer System (or L-system) is related to Thue and Post systems, and is used in botanical modeling and fractal generation.

An L-system is described by string-rewriting where a symbol from the symbol-alphabet is mapped to a replacement sequence of symbols. A collection of these mappings constitutes the L-system proper.

The graphical output method as devised by Prusinkiewicz interprets the resulting sequence after the mappings have been applied to an initial sequence for a specified number of iterations, as Turtle-Drawing commands: forward, backward, left, right, that kind of stuff. This may require extra code to control the scale of the drawing as different iteration counts may produce drastically differently-sized images.

Your task is to execute an L-system in the fewest number of characters. Your program must be able to render both the Dragon Curve and the Branching Stems from the Wikipedia page by providing appropriate input (file, command-line, but external to the source, please).

Branching Stems Dragon Curve

This is code golf.

Edit: Here are some examples I've posted around town. answer to SO/rotate-to-north {Where I first discovered the L-system}, answer to SO/how-to-program-a-fractal, answer to SO/recursion-in-postscript, comp.lang.postscript discussion/recital, postscript l-system collection, codegolf.SE/draw-a-sierpinski-triangle {origin of the competition between myself and thomasW}.

  • \$\begingroup\$ BTW, anybody know the origin of the above quote? I've heard William James, and I've heard Faraday. \$\endgroup\$ Commented Dec 31, 2012 at 11:57
  • 1
    \$\begingroup\$ Wikipedia says the origin is in dispute, best guess is Bertrand Russel. \$\endgroup\$
    – ugoren
    Commented Dec 31, 2012 at 13:09
  • \$\begingroup\$ ITYM Bertrand Russell. \$\endgroup\$
    – Paul R
    Commented Dec 31, 2012 at 16:06
  • 1
    \$\begingroup\$ Are there any limits on the size of the alphabet, number of rules, number of rounds or possible (visualization) rules (draw a straight line, push/pop position/angle, turn how many degrees etc.) If we only need to draw those two then we would need pushing & popping, drawing straight lines and being able to turn 45 degrees in both directions, only two rules and an alphabet of size 4. \$\endgroup\$
    – shiona
    Commented Dec 31, 2012 at 16:54
  • \$\begingroup\$ @shiona The hope is that it would draw more than these two. But if you can make simplifying assumptions that hold for these two, that's ok. \$\endgroup\$ Commented Dec 31, 2012 at 17:18

5 Answers 5


Mathematica 200 198 188 171 168

Spaces added for clarity:

f[i_, b_, h_, j_, r_, n_] :=
 (a = h; p = j; s = k = {}; t = Flatten;
      6, s = {a, p, s},
      8, {a, p, s} = s,
      _C, k = {k, Line@{p, p += {Cos@a, Sin@a}}}];
     If[# < 9, a += I^# b ]) & /@ t@Nest[# /. r &, i, n];


i : Initial state;
b : rotation angle
h : initial angle
j : initial position
r : production rules
n : iterations

Production rules grammar:

2 = Turn Left (-);
4 = Turn Right (+);
6 = Push and Turn Left ("[");
8 = Pop and Turn Right ("]");
C[i] = Draw (Any number of symbols)
Any other symbol = Do Nothing, just use it in producing next state (Any number of symbols)

The {2,4,6,8} sequence is there because I'm using I^n (I = imaginary unit) to make turns.


f[{C[1], X}, Pi/2, 0, {0, 0}, {X -> {X, 4, Y, C[1]}, Y -> {C[1], X, 2, Y}}, 10]

Mathematica graphics

f[{C@1}, Pi/2, 0, {0,0}, {C@1->{C@1, 2, C@1, 4, C@1, 4, C@1, 2, C@1}}, 6]

Mathematica graphics

f[{C[1]}, Pi/4, Pi/2, {0, 0}, {C[2] -> {C[2], C[2]}, C[1] -> {C[2], 6, C[1], 8, C[1]}}, 10]

Mathematica graphics

f[{C[1]}, Pi/3, 0, {0, 0}, {C@1 -> {C@2, 4, C@1, 4, C@2}, C@2 -> {C@1, 2, C@2, 2, C@1}}, 10]

Mathematica graphics

f[{X},5/36 Pi, Pi/3, {0,0},{X->{C@1, 4, 6, 6, X, 8, 2, X, 8, 2, C@1, 6, 2, C@1, X, 8, 4, X},
                            C@1->{C@1, C@1}}, 6]

Mathematica graphics

  • \$\begingroup\$ Just modify Graphics@k by Graphics@Flatten@kif you plan to use many iterations. Otherwise a Recursion Limit will bite you and your Mma session will abort. \$\endgroup\$ Commented Jan 2, 2013 at 21:03
  • \$\begingroup\$ My macro-expansion method had a similar issue with higher iterations. The strings just become enormous. But the solution there was not to flatten. :) \$\endgroup\$ Commented Jan 3, 2013 at 11:55
  • 2
    \$\begingroup\$ +1 very nice indeed ;) Could be a cool Demonstration. Do you submit those? \$\endgroup\$ Commented Apr 6, 2013 at 2:32
  • \$\begingroup\$ @VitaliyKaurov Nope, but feel free to use it if you think it's worth the effort \$\endgroup\$ Commented Apr 6, 2013 at 2:36
  • 3
    \$\begingroup\$ @belisarius demonstrations.wolfram.com/GraphicalLSystems \$\endgroup\$ Commented Apr 6, 2013 at 6:38

Python, 369 294

Not a winner but I'll post what I've tried anyway.

from turtle import*
for j in range(8):
    for i in s:S+=eval('{'+I[1]+'}')[i]
for k in s:
    if k=='[':p+=[heading(),pos()];continue
    if k==']':pu();goto(p.pop());seth(p.pop());pd();continue

Not good at golfing Python...... Maybe someone else can do it.


Input is from an external file named "l" (no extension), with the following format:
Line 1: Initial state (Axiom)
Line 2: Comma-separated rules

f and F: Draw forward
+: Turn right 5 degrees
-: Turn left 5 degrees
[: Save position and heading
]: Pop position and heading
Other symbols are ignored by the drawing function.

A rule is in the format "predecessor":"successor(s)"
Note that the quotes are necessary, whether single or double.
predecessor must be a single character.
Also, there are no implicit constants: You must explicitly specify a no-change rule for those.


Branching stems



Note that the source is modified to get this out put ONLY TO SCALE DOWN THE GRAPH TO THE VISIBLE AREA. The console is also used to hide the "turtle".

Dragon curve



Again, the console is used to hide the "turtle".

Sierpinski Triangle



Generations reduced to 5 here.

  • 3
    \$\begingroup\$ You can get a decent saving (I make it 32 chars) by removing the functions f, r, l; adding a dummy parameter to o and c; and then changing the pseudo-switch to {'f':fd,'F':fd,'+':rt,'-':lt,'[':o,']':c}[k](5) \$\endgroup\$ Commented Jan 2, 2013 at 13:13
  • \$\begingroup\$ You can also inline g, and I think o and c are worth eliminating with inline if statements (cheaper than the global declaration) \$\endgroup\$ Commented Jan 2, 2013 at 13:36
  • \$\begingroup\$ @PeterTaylor good work. I had an intuition that some of those functions could be inlined, but didn't know enough Python to suggest it articulately. \$\endgroup\$ Commented Jan 3, 2013 at 11:57
  • 1
    \$\begingroup\$ @luserdroog, I don't know Python either: I just did trial and error to see what worked - i.e. some of the things I tried (e.g. using lambdas for o and c directly in the pseudo-switch) gave syntax errors, but others didn't. \$\endgroup\$ Commented Jan 3, 2013 at 12:24
  • \$\begingroup\$ Hints for further golfing: 1. Change input format: Require braces around the rules and seperate axiom from rules by a space (not a newline). 2. Read from stdin: s,R,*p=input().split(). 3. Generate the final value of s by exec('s="".join(map(eval(R).get,s));'*8). 4. Leave out continue. 5. Indent only 1 space. 6. Save the space after the if by switching the sides fo the test. 7. Put k:int in the dict (first entry) and then you don't need except: try:. (I get 215 characters.) \$\endgroup\$ Commented Oct 29, 2013 at 0:15

Javascript (179 bytes)

Not completely sure this qualifies, as the rules object does all of the actual drawing.

Demo (Dragon, animated):
-- Expanded: http://jsfiddle.net/SVkMR/9/show/light
-- With Code: http://jsfiddle.net/SVkMR/9/


function L(c,r,n){o=(function g(d,s,o,i){for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):a;return o||s;})(n,r.r[r.s]);(function z(i){r[s=o[i]]&&r[s](c)||setTimeout(z,10,i+1)})(0)}


function L(c,r,n){
    o=(function g(d,s,o,i){
        return o||s

    (function p(i){


var sierspinski = {

var koch = {
    r: {'F':'F+F-F-F+F'},
var dragon = {
    r: {'X':'X+YF','Y':'FX-Y'},

var algae = {
    r: {'A':'B[A]A','B':'BB'},
    '[':function(c){c.save();c.rotate(Math.PI/4);},  // save/restore will push/pop current state of context. 

var tree = {


var ctx = document.getElementById('l').getContext('2d'); // grab context
ctx.translate(299.5,199.5); // start drawing from center, fractional pixels because the canvas draws lines centered on the x/y coord specified
L(ctx, dragon, 8); // pass in context, rules object, and recursion cap

Bonus: Golden Spiral http://jsfiddle.net/SVkMR/35/show/light/

var golden = {


  • \$\begingroup\$ I think the animation more than compensates for any liberties with the rules. Good job! +1 \$\endgroup\$ Commented Jan 30, 2013 at 21:49
  • \$\begingroup\$ :) Fun stuff! . \$\endgroup\$
    – Shmiddty
    Commented Jan 30, 2013 at 21:57

Postscript 264 298 295 255

Here's my attempt to do it differently. Rather than the macro-expansion that I usually use, this one checks the size of the execution stack to bound the recursion. If the bound is exceeded, it stops recursively examining the procedure and tries to interpret turtle commands (and discards pop pop otherwise). An advantage of this method is that it does not require enormous amounts of memory. A disadvantage is the recursion control is rather clumsy, as the stack size grows by more than just 1 from one recursion level to the next.

Edit: +34 chars for branching.
Edit: -3 chars. Redesigned to use the operand stack for recursion control. This makes the basic system much simpler. But brackets need an independent stack, so I put the saved position in the dictionary stack, and almost paid back all the savings.

Also, redesigned to use strings and integers instead of arrays and names.

Edit: -40 chars. Added two procedures for calling system names by number (I can't seem to get raw binary tokens to work. But this idiom works for me.)

/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73
B eq{T<0d3e>${<643f>$}<4939>$}{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>><0d6b>$
0 S<a7>$

Semi-commented binary.

/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73 *}def %73=forall
[/T[70{R 0<85>$}48{}49{} %<85>=rlineto
43{A<88>$}45{A<6e88>$} %<88>=rotate <6e>=neg
91{<1e39>$ %<1e>=currentdict <39>=end
    [/.[<286827>$]cvx>> %<28>=currentpoint <68>=matrix <27>=currentmatrix
        <0d0d>$} %<0d>=begin
93{.<9c6b1e39390d>$}>> %<9c>=setmatrix <6b>=moveto
/S{dup B eq{T<0d3e>${<643f>$}<4939>$} %<3e>=exch <64>=load <3f>=exec <49>=forall
{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>>
<0d6b>$ 0 S<a7>$  % 85=ifelse <a7>=stroke


[/T[70{R 0 rlineto}48{}49{}43{A rotate}45{A neg rotate}91{currentdict
end[/.[currentpoint matrix currentmatrix]cvx>>begin begin}93{. setmatrix
moveto currentdict end end begin}>>/S{dup B eq{T begin exch{load exec}forall
end}{exch{load exch 1 add S}forall}ifelse 1 sub }>>begin moveto 0 S stroke

It requires the L-system to be defined in a dictionary on the dictstack, with the initial string and the starting position of the turtle on the operand stack (prepended to the source, eg. gs dragon.sys lsys.ps).

Dragon Curve.

[                     %begin dictionary construction
    % productions are described by integer-key/string-value pairs
    48(0+1F) %0       %ascii code for '0' defined as the string "0+1F"
    49(F0-1) %1       %  "     "   "  '1'   "     "   "    "    "F0-1"
    43(+) %+          %  "     "   "  '+' defined as itself
    45(-) %-          %  "     "   "  '-'   "     "   "
    70(F) %F          %  "     "   "  'F'   "     "   "
    % parameters
    /A 90 %angle
    /R 2  %radius
    /B 10 %maximum recursion-level
>>begin  % L-system dictionary on top of dictstack
(F0)     % initial string on stack
300 400  % starting position on stack

Branching Stems.

    48(F[+0]-0) %0
    49(F0-1) %1
    43(+) %+
    45(-) %-
    70(FF) %F
    91([) %[
    93(]) %]
    /A 45 %angle
    /R 5  %radius
    /B 3 %recursion
(++0)     % initial string
300 400  % starting position

Ungolfed and commented.

[                                 % begin dictionary construction
    /T[                           % /T is the Turtle dictionary containing
                                  % integer-key/procedure-value pairs
                                  % keyed to ascii values
        70{R 0 rlineto}        %F  
        48{}                   %0
        49{}                   %1  
        43{A rotate}           %+  
        45{A neg rotate}       %-  

          % For brackets, create a dictionary containing a single procedure '.' (dot)
          % which holds a saved matrix (orientation+size) and currentpoint.
          % Since this procedure is called while the Turtle dict is on top of the
          % dictstack, the temporary dictionary is placed just under the top.
        91{currentdict end[/.[currentpoint matrix currentmatrix]cvx>>begin begin} %[
          % Right bracket: reset position and orientation,
          % pop the dict just under the top.
        93{. setmatrix moveto currentdict end end begin}    %]  
    /S{ % stack contains: string recursion-level
        dup B eq{ % hit recursion bound, interpret string as turtle commands
            T begin
                exch % level string
                %dup =
                {                      % iterate through string
                    load exec          % execute turtle command by integer code
                } forall % level       % string has been consumed
            %(B)= pstack
        }{ % recurse
            %(A)= pstack
            exch % level string
            { % level char                   iterate through string
                load exch % string level   process production:load string by int code
                1 add S   % string level+1   increase level and call self
            } forall                       % string has been consumed
        1 sub            % return level-1
        %(C)= pstack
moveto 0 S stroke

To run it, these 3 blocks can be saved as 3 files: dragon.ps, stems.ps, lsys.ps (any of the above program blocks will work identically). Then run with gs: gs dragon.ps lsys.ps or gs stems.ps lsys.ps. They can also be concatenated first, if desired: cat dragon.ps lsys.ps | gs - or cat stems.ps lsys.ps | gs -.

dragon curve

No stems picture. It doesn't get any more interesting at higher depths.


Mathematica 290

This bare-bones implementation focuses on the output rather than the processing. It does not use production rules. So it may not be a suitable response to the challenge.

Branching stems adapted from Theo Gray's demonstration.


f@{a_, b_} := {{a, #}, {b, #}} &[a + (b - a)/2 + {{0, 1/2}, {-1/2, 0}}.(b - a)]; w = Flatten;
h[s_, g_] :=Graphics[If[s == 0,Line /@ Nest[w[f /@ #, 1] &, {{{0, 0}, {1, 0}}}, g], 
 MapIndexed[Line@# &, NestList[w[Map[{{#[[2]], #[[2]] + m.(#[[2]] - #[[1]])}, {#[[2]], 
 #[[2]] + ({{1, -1}, {-1,1}} m).(#[[2]] - #[[1]])}} &, #], 1] &, {{{0, -1}, {0, 0}}}, g]]]]


The first parameter determines whether the Dragon Curve or Branch Stems will be displayed. The second term refers to the generation.

h[0, 5]
h[1, 5]

second pic

More Examples

GraphicsGrid@Partition[Flatten[Table[h[j, k], {j, 0, 1}, {k, 10}]], 5]


  • 1
    \$\begingroup\$ Very pretty. But wouldn't it save some bytes to pass the rule in as an argument? \$\endgroup\$ Commented Dec 31, 2012 at 21:38
  • \$\begingroup\$ If this were a general solution, perhaps one could pass a rule rather than parameters. I would have to be more knowledgeable about Lindenmayer Systems than I presently am. \$\endgroup\$
    – DavidC
    Commented Dec 31, 2012 at 21:46
  • \$\begingroup\$ I don't read mathematica. I should go learn some. (add it to the stack :) But you can interpret that to mean "whatever constitutes the description of the image, as distinct from the engine that drives it" can be factored out. If you can then modify the data to control some feature of the image, independently from touching the engine proper; I'd consider that to be "functionally equivalent" to an L-system. [That should give you lots of loopholes to work with ;)]. +1 anyway 'cause it's so pretty. \$\endgroup\$ Commented Jan 1, 2013 at 3:45
  • 1
    \$\begingroup\$ @dude I think it's because the graphics requirements aren't well suited for them \$\endgroup\$ Commented Jan 3, 2013 at 16:37
  • 1
    \$\begingroup\$ Finally figured out the l-system for your tree: A->F[+A][-A] where F is move, + is rotate left 30, - is rotate right 30, and [/] are push/pop \$\endgroup\$
    – Shmiddty
    Commented Jan 31, 2013 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.