A simple implementation of Lindenmayer systems (also called L-systems, substitution systems) is provided. In basic form, a Lindenmayer system consists of a starting string of symbols from an alphabet, and has repeated transitions applied to it, specified by a list of transition search-and-replace rules.
In addition to the standard formulation, two alternative implementations are included: sequential systems, in which at most one rule is applied; and tag systems, in which the transition only takes place at the beginning and end of the string.
Despite being implemented entirely in Python, for reasonable rules on a modern machine the system is capable of running thousands of generations per second. Lindenmayer systems are found in artificial intelligence and artificial life and can be used to generate fractal patterns (usually via mapping symbols from the alphabet to turtle commands), organic looking patterns that can simulate plants or other living things, or even music.
Getting the software
The software is available in a tarball here: "http://www.alcyone.com/pyos/lsystem/lsystem-latest.tar.gz", http://www.alcyone.com/pyos/lsystem/lsystem-latest.tar.gz.
Lindenmayer systems consist of strings of symbols from an "alphabet"; in this case, the alphabet is all 8-bit characters. The starting string is called the axiom (and is simply a string). Each generation, zero or more transitions are applied to the string, based on a list of rules. Each rule consists of an "input" and an "output"; the input is the search substring and the output is the substring it is to be replaced with. The ordering of the rules is significant. Null strings are legal as both input and output; if at the input, they will match at every location, and if at the output, the search-and-replace will amount to a delete.
In the basic implementation (the 'LSystem' class), these transitions are done in order. The system scans through the string, checking the substring starting with the current position against each rule's input in order. If that rule's input matches, that substring is substituted with the output string for that rule; thus, the ordering of rules is significant. If no rule matches, that character is left alone and scanning continues.
The first alternative, the 'SequentialLSystem' class, alters this by first scanning rule by rule for any matches, and then only substituting the leftmost. In this way, at most one transition takes place per generation.
The second alternative, the 'TagLSystem' class, also involves only allowing at most one transition per generation, but does it differently: The rules are iterated through in sequence, and the inputs are compared against the beginning of the string; if matched, the output is substituted at the end of the string. In effect the string acts as a read-write head, with the reads at the beginning and the writes at the end.
The 'LSystem' class (and its subclass) implement the following members and functions instance:
**.axiom** -- The initial string that the system is initialized to at generation zero.
**.rules** -- A list of tuples of strings, which represent the
transition rules. The order of the elements is significant; each tuple consists of an (input, output) pair.
**.string** -- The current string for this implementation.
**.generation** -- The current generation number. When newly created, the generation starts with zero.
**.done** -- A Boolean variable which indicates whether the system has reached a stable situation, i.e., no more changes will occur.
**.reset()** -- Resets the string back to the axiom.
**.step()** -- Advance one generation through the system.
An 'LSystem' instance, when converted to a string via 'str', evaluates to its L-system string. Subject objects also act as sequences and can be iterated over, e.g., 'for char in system: ...'.
- Python strings (namely their '.find' and '.startswith' methods) are used in the implementation as the implementation for the strings; with Unicode strings, this allows a very large alphabet of characters.
- Sample implementations of fractal patterns is an obvious enhancement.
- Conversion of evolved strings to "file formats," such as turtle commands (via Logo) and other formats would also be in order.
- Variances of rules over generations is a possibility.
- The Algorithmic Beauty of Plants, Prusinkiewicz, Lindenmayer.
- A New Kind of Science, Wolfram.
- 1.0; 2002 Jul 29. Initial release.
This module was written by "Erik Max Francis", http://www.alcyone.com/max/.
Version 1.0 $Date: 2002/07/29 $ $Author: max $