L-Systems

Introduction

Lindenmayer [Lin1968] proposed a model of development based on rewriting rules or productions. This model, known as L-systems, originally provided a formal description of the development of simple multicellular organisms and was later extended to higher plants [Prusinkiewicz, 89]. For this, the structure of the systems is represented as a string of modules, i.e. a label and some parameters, representing the different components and their states. The rewriting rules operate on components of a plant; for example an apex, an internode, or a leaf and describe their evolution in time.

A rule consists of two components, a predecessor and a successor. During a derivation step, the predecessor is replaced by the successor. Even very simple L-systems can produce plant-like structures. The difference between L-systems and other rewritting system such as Chomsky grammars lies in the method of applying productions. In Chomsky grammars productions are applied sequentially, whereas in L-systems they are applied in parallel and simultaneously replace all letters in a given string.

String Representation

Lindenmayer developed a string notation that makes it easy to specify productions and carry out simulations. Each components of the system is represented as a module. A module is characterized by a by a label, for instance A, and possibly a set of parameters. For instance, an apex of age 10 can thus be represented by the module A(10), an internode of length 20 and radius 3 by I(20,3). To represent a linear structure, a string can be created as a serie of modules. For branched structure such as tree, special module [ and ] are used to represent begin and end of branches. After each module in the string, its lateral successors enclosed in square brackets are first given followed by its axial successor. For instance in the structure A[B]C, A carries a lateral module B and is followed by module C.

Geometric representation of the string

To graphically represent the string, it is possible to use a LOGO like turtle that will parse sequentially the string and interpret some of the modules as geometric commands [Prusinkiewicz, 86]. The commands will be additioned to create the geometry. For instance, module F makes the turtle draw a cylinder and move forward, + and - to rotate on the right or left. You can read section [Predefined Symbols] to have the list of interpretable modules.

Rules

Production rules are composed of a predecessor which represents the pattern of modules to match and replace, and successor which is expressed as python code containing production statements.

# simple rule
predecessor --> successor
# equivalent to
predecessor : produce successor
# more complex rule
predecessor :
  if condition:
     produce successor
  else:
     produce successor2

As an example,

I(l) --> I(l+dl)
A(t):
  if t < APEX_DURATION:
    produce I(INITIAL_LENGTH)
  else:
    produce  # empty production

The pattern given in the successor is expressed as a set of modules represented by their labels and variables for the parameters. A pattern is matched to a module or a set of modules of a string only if labels and numbers of parameters are the same. If matched, the variables are assigned to the actual values in the string of the parameters and the code of the successor is called.

As one can see on the example the production of the successor can be conditional. The successor can produce empty string (produce or produce *) meaning that the successor is replace by nothing. The production can also produce nothing. In this case the application will supposed to have failed and other rules can be tested. If no rule match a module of the string, then identity rule will be applied and the module will be replace by himself.

The replacement of a successor can depend on the neighbours of the modules to replace. In this case, the rule is called context sensitive and the successor, now called strict successor is augmented with pattern for neighbour modules (i.e. the contexts). Lpy supports 4 types of contexts.

  • left and right contexts, i.e. neighbour modules on the left and on the right.
left_context < strict_predecessor > right_context  --> successor

For instance, A < B > C –> D or I < A –> IA

  • new left and right contexts, i.e. futur neighbour modules in the new string on the left and on the right.
new_left_context << strict_predecessor --> successor
                    strict_predecessor >> new_right_context   --> successor

Of course, the new_left_context is only available if the rule are applied from left to right on the string and new_right_context from right to left.

These contexts can then be combined.