## L-systems

### + Associated example files

NB: An exercise relating to the material covered in this tutorial can be found on the Exercises page.

L-systems, or *Lindenmayer Systems*, are recursive formulas
used to model self-similar objects or processes. They were developed in
1968 by Hungarian botanist Aristid Lindenmayer (1925–1989) to
model growth processes in plants, but have since been used in many
other fields, including in the generation of fractal images.

*slippery chicken* has a class and methods available for using
L-systems to generate self-similar lists, which can in turn be used to
govern any of the musical data which a `slippery-chicken`

object may contain. For an example of the use of L-systems in
a *slippery chicken* composition, see the tutorial
on *Tempus Perfectum*.

### + L-system basics

L-systems consist of three basic components: a list of individual
symbols that will be used to make strings; a list of rules for how to
expand each symbol into a longer string of symbols; and an initial
state, or *axiom*, with which the process is to begin.

A loop is then used to apply the rules to each symbol of the new, longer strings at each pass, returning an even longer string each time.

#### A simple example

As a common first example, the following L-system uses the
symbols `A` and `B`. Its rules state that at each pass,
every `A` in the current string is to be converted
to `AB`, and every `B` is to be converted
to `A`. The whole process will start with an initial axiom
of `A`.

Symbols: A, B Rules: A => AB, B => A Axiom: A Produces: pass 0 : A pass 1 : AB pass 2 : ABA pass 3 : ABAAB pass 4 : ABAABABA pass 5 : ABAABABAABAAB pass 6 : ABAABABAABAABABAABABA pass 7 : ABAABABAABAABABAABABAABAABABAABAAB

Or, to break the above example down into its
routes^{ [1]}:

A _|_ A B _| | A B A _| | |_ A B A A B _| | |_ |_ \ A B A A B A B A [etc.]

#### Notes

[1] Adapted from the University of Hamburg Biology webpages

### + L-systems in graphics and fractals

#### Turtle Graphics

The use of L-systems to produce fractal graphics is often combined
with an approach to automated drawing called *Turtle
Graphics*, which were originally a feature of the
Logo
programming language (a dialect of Lisp).

Using Turtle Graphics, the symbols of an L-system's resulting string
are converted into drawing instructions, the most basic of which are
"draw a line forward", or "draw nothing". In conjunction with
L-systems, Turtle Graphics also provide for the specification
of *constant* symbols, which don't change the string at all,
but tell the program, for example, to "change the direction of the
line by an angle of *n* degrees", or to "begin a branch",
etc.

#### Sierpinski Triangle

A simple example of using an L-system to control Turtle Graphics can
be seen in a brief set of symbols and rules that produce a
"Sierpinski Triangle". The L-system uses the symbols `A`
and `B`. Both of these are translated into instructions to
"draw a line forward". The system also includes the
constants `+` and `-`, which don't result in anything
being drawn, but instead instruct the graphics program to turn left
or right by the specified angle before drawing the next line. The
rules are that every `A` becomes `B-A-B`, and
every `B` becomes `A+B+A`. The axiom
is `A`.

Symbols: A, B both mean "draw forward" Constants: +, - + means "turn left by angle" - means "turn right by angle" Rules: A => B-A-B B => A+B+A Axiom: A

An angle of 60 degrees produces the following image after 6 iterations:

#### Fractal plant

A second example of L-systems and graphics produces an image that
resembles a plant. It uses the symbols `F` and `X`,
which translate into the instructions to "draw a line forward" in the
one case and to "draw nothing" in the other. As constants, it again
uses the `+` and `-` symbols to change the angle, and
additionally includes the symbols `[` and `]`, which
mean to "create a node and begin a branch", and "end the branch and
return to the most recent node". Its rules are that every `X`
becomes `F-[[X]+X]+F[+FX]-X`, and every `F`
becomes `FF`. It starts with an axiom of `X`.

Symbols: F, X F means "draw forward" X means "draw nothing" Constants: -, +, [, ] - means "turn left by angle" + means "turn right by angle" [ means "create node and begin branch" ] means "end branch and return to most recent node" Rules: X => F-[[X]+X]+F[+FX]-X F => FF Axiom: X

An angle of 25 degrees produces the following image after 6 iterations:

### +
L-systems in *slippery chicken*

In *slippery chicken*, L-systems can be used to generate
self-similar lists based on a collection of items, rules, and an
axiom. The *slippery chicken* implementation of L-systems
does not include constants (i.e. no branching).

*slippery chicken's* L-system class and methods generate a
sequence of key references from a set of specified rules and use
these to retrieve data from a list of key-data pairs
(`assoc-list`

object). Extensions to the algorithm allow the user to implement
Fibonacci-based transitions between the data items, or to generate
linear lists from the data without using L-system rules.

#### The l-for-lookup object

At the core of *slippery chicken's* L-system implementation
is the `l-for-lookup`

object. This object takes an ID, a
list of key-data pairs (each element of the data list must also be a
list), and a list of rules created from the keys of the list of
elements. Both the keys and the data of the rules must consist of the
keys from the list of elements.

For example, the following creates an `l-for-lookup`

object based on the rules `A=>B` and `B=>A`:

(make-l-for-lookup 'l-sys '((1 ((a))) ; elements (2 ((b)))) '((1 (1 2)) ; rules (2 (1))))

A number of methods are then available to create lists based on the
elements and rules specified in the `l-for-lookup`

object.

#### get-l-sequence

The `get-l-sequence`

method operates by collecting a list
of keys, without using those keys as look-up references and therefore
not converting the list of keys into a list of corresponding data
elements. It takes as its arguments the `l-for-lookup`

object, an axiom (the starting key), and an integer that indicates
the length of the resulting list.

(let* ((lfl (make-l-for-lookup 'l-sys '((1 ((a))) (2 ((b)))) '((1 (1 2)) (2 (1)))))) (get-l-sequence lfl 1 29)) => (1 2 1 1 2 1 2 1 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 1 2 1 2 1)

The `l-for-lookup`

object to be accessed by this method
can thus be made without specifying a list of elements (by
using `NIL`

instead).

(let* ((lfl (make-l-for-lookup 'l-sys nil '((1 (1 2)) (2 (1)))))) (get-l-sequence lfl 1 29)) => (1 2 1 1 2 1 2 1 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 1 2 1 2 1)

A musical implementation of this object and method may look like the following:

(let* ((num-seqs 29) (lfl (make-l-for-lookup 'l-sys nil '((1 (1 2)) (2 (1))))) (rs-map (get-l-sequence lfl 1 num-seqs)) (mini (make-slippery-chicken '+mini+ :ensemble '(((vn (violin :midi-channel 1)))) :set-palette '((1 ((c4 e4 g4)))) :set-map `((1 ,(loop repeat num-seqs collect 1))) :rthm-seq-palette '((1 ((((2 4) q q)) :pitch-seq-palette ((1 2)))) (2 ((((2 4) - s s (s) s - - s (32) 32 32 32 - (s))) :pitch-seq-palette ((1 2 3 1 3 2 1))))) :rthm-seq-map `((1 ((vn ,rs-map))))))) (midi-play mini) (cmn-display mini) (write-lp-data-for-all mini))

#### do-simple-lookup

The `do-simple-lookup`

method takes as its arguments
an `l-for-lookup`

object, an axiom (which must be one of
the keys from the list of elements), and an integer to specify the
length of the list to be returned.

The method then performs L-system iterations based on the rules of
the specified `l-for-lookup`

object, collecting the keys
specified in the rules until it returns a list whose length is equal
to or greater than the length specified. (If the list is longer, it
is truncated.) It then uses the list of keys to look up the
associated data, essentially converting the list of keys into a list
of the corresponding data elements.

(let* ((lfl (make-l-for-lookup 'l-sys '((1 ((a))) (2 ((b)))) '((1 (1 2)) (2 (1)))))) (do-simple-lookup lfl 1 29)) => ((A) (B) (A) (A) (B) (A) (B) (A) (A) (B) (A) (A) (B) (A) (B) (A) (A) (B) (A) (B) (A) (A) (B) (A) (A) (B) (A) (B) (A))

A very handy utility function in *slippery chicken* is
the `flatten`

function, which makes a "flat" list out of
any list of sub-lists. Using that function with the above example,
the method returns a list of just the data:

(let* ((lfl (make-l-for-lookup 'l-sys '((1 ((a))) (2 ((b)))) '((1 (1 2)) (2 (1)))))) (flatten (do-simple-lookup lfl 1 29))) => (A B A A B A B A A B A A B A B A A B A B A A B A A B A B A)

A possible musical implementation of this method may look like the following:

(let* ((num-seqs 29) (lfl (make-l-for-lookup 'l-sys '((1 ((a))) (2 ((b)))) '((1 (1 2)) (2 (1))))) (rs-map (flatten (do-simple-lookup lfl 1 29))) (mini (make-slippery-chicken '+mini+ :ensemble '(((vn (violin :midi-channel 1)))) :set-palette '((1 ((c4 e4 g4)))) :set-map `((1 ,(loop repeat num-seqs collect 1))) :rthm-seq-palette '((a ((((2 4) q q)) :pitch-seq-palette ((1 2)))) (b ((((2 4) - s s (s) s - - s (32) 32 32 32 - (s))) :pitch-seq-palette ((1 2 3 1 3 2 1))))) :rthm-seq-map `((1 ((vn ,rs-map))))))) (midi-play mini) (cmn-display mini) (write-lp-data-for-all mini))

### + Combining L-systems and Fibonacci-based transitions

*slippery chicken* provides an extension to the L-system
approach through a combination of L-system look-ups with
Fibonacci-based transitions (see the manual page
on Fibonacci functions for more
detail). This is done using the `do-lookup`

method.

In order for the Fibonacci transitions of the `do-lookup`

method to be evident in the resulting list, the data of at least one
of the key-data pairs must contain at least two sub-lists. In the
final list returned by the method, the instances of the keys for
elements with more than one sub-list will be replaced by gradual
transitions through each of the sub-lists.

For example, the item with key `1`

in the list of
elements from the following `l-for-lookup`

object has the
sub-lists `(a)`

and `(c)`

. In the list produced
by `do-lookup`

, the first sub-list at key `1`

(`a`

) will gradually be replaced by the second,
(`c`

).

(let* ((lfl (make-l-for-lookup 'l-sys-a '((1 ((a) (c))) (2 ((b)))) '((1 (1 2)) (2 (1)))))) (do-lookup lfl 1 73)) => (A B A A B A B A A B A C B A B A A B A B C A B A A B A B C A B A C B A B A C B A B C A B C C B A B C A B C B A C B C A B C B C A B C C B C B C C B)

This is an example with multiple lists in each element, each of which in turn contains multiple items to transition over:

(let* ((lfl (make-l-for-lookup 'l-sys-a '((1 ((a b c) (1 2 3) (ant bird cat) (10 20 30))) (2 ((two) (999)))) '((1 (1 2)) (2 (1)))))) (do-lookup lfl 1 73)) => (A TWO B 1 TWO C TWO 2 A TWO 3 B 999 1 TWO C 2 TWO A 999 3 1 TWO 2 3 TWO 1 999 ANT 2 TWO BIRD 3 999 CAT TWO 1 ANT 999 2 TWO BIRD 3 999 CAT ANT TWO BIRD 999 CAT ANT TWO 10 999 BIRD 20 999 CAT 30 TWO ANT 999 10 BIRD 999 20 CAT 999 30 999 10 20 999)

A musical usage of this method may look as follows:

(let* ((num-seqs 73) (lfl (make-l-for-lookup 'l-sys-a '((1 ((a b c) (d e) (f g h))) (2 ((i)))) '((1 (1 2)) (2 (1))))) (rs-map (do-lookup lfl 1 num-seqs)) (mini (make-slippery-chicken '+mini+ :ensemble '(((vn (violin :midi-channel 1)))) :set-palette '((1 ((c4 e4 g4)))) :set-map `((1 ,(loop repeat num-seqs collect 1))) :rthm-seq-palette '((a ((((2 4) - s s (s) s - - s (32) 32 32 32 - (s))) :pitch-seq-palette ((1 2 3 1 3 2 1)))) (b ((((2 4) - s (s) s s - (32) - 32 32 32 (s) s -)) :pitch-seq-palette ((1 2 3 1 3 2 1)))) (c ((((2 4) (s) - s s (32) 32 - - 32 32 (s) s s -)) :pitch-seq-palette ((1 2 3 1 3 2 1)))) (d ((((2 4) - s s (32) 32 32 32 - (s) - s s - (s))) :pitch-seq-palette ((1 2 3 1 3 2 1)))) (e ((((2 4) - s (32) 32 32 32 - (s) - s s (s) s -)) :pitch-seq-palette ((1 2 3 1 3 2 1)))) (f ((((2 4) (32) - 32 32 32 (s) s - - s (s) s s -)) :pitch-seq-palette ((1 2 3 1 3 2 1)))) (g ((((2 4) - 32 32 32 (32) s s - (s) - s s - (s))) :pitch-seq-palette ((1 2 3 1 3 2 1)))) (h ((((2 4) - 32 32 (s) s s - (s) - s s (32) 32 -)) :pitch-seq-palette ((1 2 3 1 3 2 1)))) (i ((((2 4) h)) :pitch-seq-palette ((1))))) :rthm-seq-map `((1 ((vn ,rs-map))))))) (midi-play mini) (cmn-display mini) (write-lp-data-for-all mini))

### + Non-L-system use of L-system object data

*slippery chicken* also provides an option for using the rules
of an `l-for-lookup`

object without using L-system
data. If this option is chosen, the
corresponding `l-for-lookup`

object can be made without
any data, by substituting the data with `NIL`

.

The `get-linear-sequence`

method creates a list from the
rules of an `l-for-lookup`

object's key-data pairs. It does
so by collecting the *next* element from the given key-data
pair each time that pair is accessed. When the last element of that
pair has been retrieved, the method returns to the head of that
pair's data list.

The method then uses the element collected as the key for the next collection. All of the elements must therefore consist of only the keys from the list of key-data pairs.

(let* ((lfl (make-l-for-lookup 'lfl-test nil '((1 (2 3)) (2 (3 1 2)) (3 (1)))))) (get-linear-sequence lfl 1 23)) => (1 2 3 1 3 1 2 1 3 1 2 2 3 1 3 1 2 1 3 1 2 2 3)

This method can be very useful for algorithmically generating chord sequences within a composition, as the following example demonstrates:

(let* ((num-seqs 23) (lfl (make-l-for-lookup 'lfl-test nil '((1 (2 3)) (2 (3 1 2)) (3 (1))))) (s-map (get-linear-sequence lfl 1 num-seqs)) (mini (make-slippery-chicken '+mini+ :ensemble '(((vn (violin :midi-channel 1)))) :set-palette '((1 ((c4 e4 g4))) (2 ((c4 f4 a4))) (3 ((d4 g4 b4)))) :set-map `((1 ,s-map)) :rthm-seq-palette '((1 ((((2 4) q e (s) s)) :pitch-seq-palette ((1 2 3))))) :rthm-seq-map `((1 ((vn ,(loop repeat num-seqs collect 1)))))))) (midi-play mini) (cmn-display mini) (write-lp-data-for-all mini))

Another example of such use of the `l-for-lookup`

class
can be found in the manual page Tonal composition
with slippery chicken.