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 :

A
_|_
A   B
_|   |
A B   A
_| |   |_
A B A   A B
_| | |_  |_ \
A B A A B A B A

[etc.]

Notes

 Adapted from the University of Hamburg Biology webpages

close

+ 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"
Rules:
X => F-[[X]+X]+F[+FX]-X
F => FF
Axiom: X

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

+ 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)) close

+ 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)) close

+ 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.

close