Modeling L-systems in ECMAScript 5.1

L-systems were introduced by Aristid Lindenmayer in a 1968 paper Mathematical models for cellular interactions in development. II. Simple and branching filaments with two-sided inputs. They are particularly useful for the modeling of evolution of self-similar (fractal) systems, such as growth of plants, or successive approximations of space-filling curves. [Algorithmic Beauty, L-system]

A given L-system is defined by an alphabet, a set of production rules over that alphabet, and an axiom – a non-empty sequence of elements from the alphabet that gives the initial state of the system. On every iteration of the system, all the matching rules are applied to the current state in parallel to produce the next state.

One of the simplest (but non-trivial) systems like that is the one described in the Algae section below.

While simpler systems can be explored with pencil and paper, more complex ones require a computer program to perform successive iterations. Examples of such programs are described below.

This system is defined by two production rules: A → AB, B → A. The axiom can be either A or B. The alphabet is consequently {A, B}.

In the example below, we define:

lsy_once

a function that produces the next state of the L-system given its current state and production rules;

rules

a variable that holds an ECMAScript object with properties corresponding to the production rules: the property "A" has value "AB" and the property "B" has value "A".

We then do 5 iterations using a for loop, starting with "A" and 1 as the values of the state variable s and the loop control variable i, respectively; and stopping once i, incremented after each iteration, exceeds 5.

This example is intended to conform to the ECMAScript 5.1 standard, extended for our needs with a print function that converts its arguments to strings and adds those strings, separated with blanks, to the result <textarea /> element of this document. Incidentally, a similar function exists in Duktape, so the example can be run there instead. [Duktape, ECMA-262]

In the rest of this document, rather than defining lsy_once anew for every example, we’ll be creating a StoLsystem object and using its .once method, defined in the library code we use here. The code to do that for the L-system currently considered is commented-out in an if (0) block below. Feel free to uncomment it by editing the statement to read if (1) instead. Note that it will result in two identical outputs from two different implementations of the L-system.

Use the eval button to run the code and see the resulting states of the system. Note that when experimenting with the examples here, you can always reset them to their original state by reloading this document. By the same virtue, be sure to store anything interesting you find separately, as this document nevers stores anything anywhere.

This is the L-system that gives us the classic Koch curve. In addition to a variable, F, this system features two constants (the elements of the alphabet that are not changed by the production rules; also known as terminals): + and -.

In this example, we want not only to produce a sequence of states, but also to interpret the latest state geometrically. Namely, we’ll use turtle graphics [Turtle graphics] (as provided by a TBGIE.Lsy object and the svg_visualize function) and we’re going to interpret our state as a sequence of commands to an imaginary turtle as follows:

F

move forward by one unit of length, while drawing a trailing line;

+

turn left by ⅓ π;

-

turn right by ⅓ π.

The conversion from the symbols above to actual turtle commands is part of the TBGIE.Lsy code. Note that we use −⅓ π as the angle to turn by, to account for the fact that in computer graphics, the y axis points down, not up, like in conventional geometry.

Alternatively, with F--F--F used as the axiom in place of F (try it!), the code will produce a Koch snowflake instead. [Koch snowflake] As that results in a closed path, gi.stop (1) should be used in place of gi.stop (); you can spot the difference if you do only one or two iterations here (or just interpret the initial state straight away.)

This L-system produces a Sierpiński arrowhead curve – a curve that approximates the Sierpiński triangle. Its alphabet has two variables, F and G, and two constants, + and -. As in the previous example, + and - correspond to turning left and right, while both F and G correspond to drawing a unit-length segment of the curve in the chosen direction. [Sierpiński curve]

This is again a fairly simple system, defined by production rules 1 → 11, 0 → 1[0]0. The axiom is 0, and the constants are [ and ].

The complexity of the example code below comes from the fact that we’ll use a slightly different interpretation of the symbols than the TBGIE.Lsy default; namely:

0 and 1

move forward by a unit of length, while drawing a trailing line;

[

create a new turtle for use, then turn it left (or right: our figure is symmetric) by ¼ π;

]

stop using this turtle and switch back to a previous one, then turn right (left) by ¼ π.

Now we’re going to specify two possible production rules for 0: 0 → 0 (i. e. no change) and 0 → 1[0]0. Our implementation is coded in such a way that when presented with several choices, it will on every application select one of them at random, with equal probabilities. In effect, our binary tree will now grow a fork (in each of the eligible positions) only half the time, which surely will affect how it looks.

Note that every run of the code will likely produce a different result. The end effect is as if branching happens at different rates for different parts of the tree.

In order to make the probabilities differ, we can provide a list of right hand sides that has duplicate elements in it, such as [ "0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0", "1[0]0" ], which will result in the 0 being constant with only 10% probability. Alternatively, the right hand side of the production can be given as a function. For instance, you can use if (1) in place of if (0) in the code below to hot-patch the rules so that the 0 → 0 rule will be applied in 10% (or any other probability – as given in the function’s code) of applications.

To simplify the code, we’re going to cheat a bit and use StoLsystem.Examples.BinTree.prototype.g_i as our geometry engine, which is provided by the code library we use here.

This system is defined by production rules X → F+[[X]-X]-F[-FX]+X, F → FF (note the similarity to the rule 1 → 11 in the binary tree definition above.) The axiom is X, and the constants are +, -, [ and ], whose geometric interpretation is similar to the binary tree case, save for two differences: the angle is π ∕ 7.2, and [ and ] do not alter the newly created and restored turtles’ direction. X is ignored by the turtle and is only there to control the evolution of the fractal. [Barnsley fern, L-system]

The following code should execute the test suite for the code libraries used in this document and present the result as a TAP document. [TAP-14]

Algorithmic Beauty

Algorithmic Beauty of Plants / Przemyslaw Prusinkiewicz, Aristid Lindenmayer et al. — (archived) URI: https://web.archive.org/web/20240424190550/http://algorithmicbotany.org/papers/#abop

Barnsley fern

Barnsley fern // Wikipedia. — URI: http://en.wikipedia.org/wiki/Barnsley_fern

Duktape

Duktape. — URI: http://duktape.org/

ECMA-262

ECMAScript Language Specification: ECMA-262 Edition 5.1. — URI: http://262.ecma-international.org/5.1/

Edbrowse.deb

edbrowse package details // Debian Bookworm. — URI: http://packages.debian.org/bookworm/edbrowse

Koch snowflake

Koch snowflake // Wikipedia. — URI: http://en.wikipedia.org/wiki/Koch_snowflake

L-system

L-system // Wikipedia. — URI: http://en.wikipedia.org/wiki/L-system

Microformats2

Microformats2 // Microformats Wiki. — URI: http://microformats.org/wiki/microformats2

Sierpiński curve

Sierpiński curve // Wikipedia. — URI: http://en.wikipedia.org/wiki/Sierpiński_curve

TAP-14

TAP 14 specification // Test anything protocol. — (archived) URI: http://web.archive.org/web/20240106151003/https://testanything.org/tap-version-14-specification.html

Turtle graphics

Turtle graphics // Wikipedia. — URI: http://en.wikipedia.org/wiki/Turtle_graphics

Wget, GNU

Recursive retrieval options: -p // GNU Wget 1.24.5 Manual. — URI: http://gnu.org/s/wget/manual/html_node/Recursive-Retrieval-Options.html#index-page-requisites