Algorithmic Composition: A Gentle Introduction to Music Composition Using Common LISP and Common Music

15.1 Introduction to Probability

Chapter 4 introduced the random item stream pattern type. Using the random item stream pattern type, we were able to control the probability that a certain event would be selected.

Probability is the study of outcomes that produce a given event to the total number of possible outcomes. A probability is the likelihood that a particular event will occur. A probability is expressed as a ratio- the likelihood that a given event will occur in relation to the total number of possible outcomes. For example, consider a six-sided die where each side is uniquely identified 1,2,3,4,5 and 6. The probability that a 1 will be rolled is 1:6. The ratio 1:6 may also be expressed as a floating point value or .16666 (16.666%). Considering the example of the six-sided die, the sum of all possible outcomes is 6/6 or 1.0 (100%).

15.2 Random Item Stream

The random item stream pattern type uses the optional keyword :weight to alter the probability of an event being selected in relation to the other events in the item stream.

In Example 15.2.1, the note c4 is 1/2 as likely to be selected as d4 and e4. Given that there are 3 notes and the sum of their probabilities must equal 1 (of 100%), and c4 is 1/2 as likely to be selected as d4 and e4, Table 15.2.1 shows the probabilities of the note events.

Table 15.2.1

Note Probability Table

If a weight is not specified, the random pattern type calculates the probabilities of each event as being equal. When all events have an equal probability of being selected, white noise results. White noise has a flat spectrum meaning that its energy is dispersed evenly throughout a specified range. White noise is also referred to as 1/f ⁰ noise because of its flat spectrum. In Example 15.2.2, the range of events are the rhythms for a quarter, sixteenth, and eighth note.

Example 15.2.2

(setf rhythm (item (rhythms q s e in random)))

Table 15.2.2 shows that the selection of rhythms based on equal probability.

Table 15.2.2

Rhythm Probability Table

The random item stream pattern type also implements the options :min and :max. The option :min determines how many direct repetitions are allowed before a new element must be selected. The option :max sets a maximum value an element may be repeated before a new element must be selected.

Example 15.2.3

(setf amplitude (item (items (.1 :max 1) (.2 :max 1) (.3 :min 2) (.4 :min 2)in random)))

Example 15.2.3 indicates that .1 and .2 can repeat at most one time before a new event must be selected. .3 and .4 must repeat at least 2 times before a new event is selected.

The random item stream constructor has no recollection of past events. Each time an item is assigned to a slot, Common Music evaluates the probability and selects an item. The keyword options :min and :max force Common Music to take previous events into consideration before a slot is assigned. Because of the evaluation of the probability at every pass of an item stream, and the memory for past slots as specified by :min and :max, it is possible that mixing a container will yield results very different from the specified weights. When evaluating Examples 15.2.4, Common Music returns 3 C4s, 4 E4s, and 5 D4 and 2 quarter notes, 5 eighth notes and 5 sixteenth notes. Notice the amplitude slot is not successively assigned .1 or .2. Also notice that when .3 and .4 is selected, its value is assigned twice in succession.

Example 15.2.4: random.lisp

15.3 Graph Item Stream

The graph item stream pattern type creates an item stream of user-specified rules for traversing a series of nodes called a graph.

The graph in Figure 15.3.1 has three nodes- C4, E4, and DS4. Each node represents a symbolic note name. The arrows connecting the nodes specify the direction in which the graph may be traversed. For example, from node E4, we can go to C4 or DS4. From node C4, we can only go to E4.

Figure 15.3.1

In Common Music, the relationship between nodes is specified as (start to destination) where destination may be an item stream. For example,

(e4 to (items c4 ds4 in cycle))

states that node E4 may traverse to C4 and DS4 in cycle. When the graph arrives at node E4, it will alternate its destination to either C4 or DS4.

The graph in Figure 15.3.1 may be represented in Common Music as

In Example 15.3.1, we create a graph item stream comprised of notes and assign it to the variable X. We may read the item stream using the Common Music function read-items as seen in Example 15.3.2.

 graph.mp3

Carefully compare the graph in Figure 15.3.1 with the output of the read-items in Example 15.3.2. Notice that the succession of notes follows the specified rules and item stream pattern types. E4 goes to C4 and DS4 in cycle. DS4 goes to C4 and E4 in palindrome. The nodes C4, E4, and DS4 are in graph.

Example 15.3.3 incorporates the graph item stream pattern in Example 15.3.1 in a generator.

15.4 Markov Item Stream

A markov process is a probability system where the likelihood that an event will be selected is based on one or more past events. A matrix referred to as a transition table is used to show the probability that a certain event will be selected based on one or more past events. The order of the transition table is dependent on the number of past events considered in the selection of the next event. A first-order transition table describes the probability that an event will be selected given one past event and a second-order transition table describes the probability that an event will be selected given two past events. The succession from one event to the other is called a markov chain .

Table 15.4.1: A first-order transition table

Table 15.4.1 is an example of a first-order transition table. The current events are listed in the zeroth column and the possible next events are listed in the zeroth row. We interpret the first row of the transition table as "if the current event is a C4, there is a 10% chance that another C4 will be selected, a 75% chance that D4 will be selected, and a 15% chance that E4 will be selected."

Two frequent errors in constructing transition tables are loops and dead ends. The transition table in Table 15.4.2 will quickly fall into a loop that generates a chain of alternating D4s and E4s.

Table 15.4.2: A first-order transition table that loops

A dead end occurs in a transition table when an event is specified and there is no way to select another event from that event. The transition table in 15.4.3 states that "if the current note is a C4, there is a 50% chance that D4 will be selected, a 25% chance that E4 will be selected, and a 25% chance that F4 is selected." If F4 is selected, it had no available outputs since there is no row in the transition table that considers F4 as a current event. The markov chain reaches a dead end.

Table 15.4.3: A first-order transition table that dead-ends

The Common Music macro markov may be used to generate an item stream that constructs a markov chain. The markov macro template is:

(markov (past-event -> (outcome-1 weight-1) (outcome-2 weight-2) . . . (outcome-n weight-n)))

Example 15.4.1 uses markov to assign the note slot using the first-order transition table described in Table 15.4.1.

Example 15.4.1: markov1.lisp

When markov1.lisp is evaluated, the following note series is generated:

Figure 15.4.1: Output from markov1.lisp

Quite often, markov processes are used to generate music based on a previous composition or set of compositions. A transition table may be constructed by analyzing the likelihood that a certain event will be followed by another event. Consider the folk melody Aunt Rhody as notated in Figure 15.4.2.

Figure 15.4.2: Aunt Rhody

There is one occurrence of the note F5 and it always goes to E5. To describe this relationship in a first-order transition table, we would say given F5, there is 100% change that E5 will be selected.

(F5 -> (E5 1.0))

means that C4 is 1/2 as likely to be selected as D4 and E4 or the probability that given a C4, another C4 will be selected is 20%. The likelihood that D4 or E4 will be selected is 40%.

The Common Music function markov-analyze analyzes a list and returns both a transition table and the Common Music code to implement the transition table.markov-analyze may be accompanied by keywords :order and :sort to specify the order of the transition table Common Music should return from the analysis and the sequence of events in the table. Example 15.4.2 demonstrates the use of markov-analyze by passing markov-analyze the note list from Aunt Rhody. We specify that Common Music return a first-order transition table and the table be arranged according to the list (c5 d5 e5 f5 g5).

Evaluating the code in 15.4.2 returns the following:

Example 15.4.3 Output from Example 15.4.2

markov-analyze returns a first-order transition table. The transition table is followed by the Common Music code that implements the transition table.

Next, we analyze the rhythm of Aunt Rhody using markov-analyze. We specify a second-order transition table.

Evaluating the code in 15.4.3 returns the following:

Example 15.4.4 Output from Example 15.4.3

The second-order transition table is more complex to read than a first order transition table. Consider the third row of the transition table in Example 15.4.4.

(Q E -> (Q 1.0))

The row is interpreted as, "if the current rhythm is an eighth note and it was preceded by a quarter note, return a quarter note."

Given a first-order transition table for the selection of note events and a second-order transition table for the selection of rhythmic values, we can generate a melody that has the comparable note and rhythm probabilities as Aunt Rhody.

Figure 15.4.3: Output from Example 15.4.5

Sometimes, markov-analyze generates transition tables that dead end. These dead ends generate the error message, "No outputs for past choices." The error message can be avoided by reducing the order of the transition table or extending the transition table to include possible choices not returned by markov-analyze.

If you have a large MIDI file you'd like to analyze using markov-analyze, it is easiest to import the MIDI file into Common Music. Example 15.4.6 assumes a MIDI file named test.midi resides on the desktop of a Macintosh computer.

We use the newly-imported file that has been named From-Test. We change our current focus object to From-Test.

Example 15.4.7

Stella [Top-Level]: go 1

In Example 15.4.8, we use the map command to collect all of the note data into a list. We then use the collected list of note data as input to the markov-analyze function.

15.5 1/f ² Noise or Brownian Motion

Brownian motion is the observed movement of small particles randomly bombarded by the molecules of the surrounding medium. The phenomenon was first observed by the biologist Robert Brown and was eventually explained by Albert Einstein. Brownian motion is also referred to as 1/f ² noise.

That number series may be mapped to a number line to describe one-dimensional motion along the number line. Our number line is as follows:

Example 15.1.1 implements this algorithm for one-dimensional Brownian motion resulting in a note list given a starting position and prescribed number of elements. The Common LISP function BROWNIAN-MOTION accepts two inputs: the starting position and how many steps it should simulate. We enter a DO* and initialize the variable COUNTER to 0, incrementing the variable at each pass of the loop.COUNTER is a loop-control-variable that terminates iteration when its value is equal to the NUMBER-OF-NOTES. A one-dimensional array named THE-ARRAY is created and initialized to have seven locations with the values of -3, -2, -1, 0, 1, 2, and 3. We CONS the variable start onto the variable THE-LIST at the first iteration. For subsequent iterations, we CONS the newly-calculated note value onto THE-LIST.

Example 15.5.1: brownian-motion.lisp

((= counter (- number-of-notes 1)) (reverse the-list))))

In Example 15.5.2, we call the Common LISP function BROWNIAN-MOTION inside the generator brownian-music.BROWNIAN-MOTION returns a note list that is converted to an item stream and assigned to the variable brown-item-stream using the Common Music declaration vars. We assign one item from the brown-item-stream to the note slot.

 brownian-music.mp3

Example 15.5.2: brownian-music.lisp

The output of the generator is as follows:

2. #<MIDI-NOTE | 58| 0.400| 0.500| 0.700| 0|>

10. #<MIDI-NOTE | 55| 0.400| 0.500| 0.700| 0|>

15.6 1/f Noise

A special class of noise called 1/f Noise has been discovered in many natural phenomenon including rainfall patterns and sunspot activity. Oddly enough, the 1/f relationship has been found by analyzing recordings of non-random music in various styles [Voss, 1978]. Number series generated using a 1/f formula correlate logarithmically with past values [Dodge, 1986]. Because of this property, 1/f noise seems to have a memory for past values, conceptually similar to what we've seen with markov processes. This property can be used to realize music that has highly-correlated attributes.

Richard F. Voss developed a simple algorithm to simulate 1/f noise [Gardner, 1986]. His algorithm uses three six-sided dice: one red, one green, and one blue. The sum of the three dice range in value from 3 to 18 returning 16 possible values. These 16 values may be mapped to any 16 adjacent notes or any sixteen musical parameters.

Voss uses a table similar to that found in Table 15.6.1 to create 1/f music. The numbers 0 through 7, base 10, are located in the left-most column. The three-digit binary equivalent of the decimal value is found in the right-most three columns. Each binary position is associated with a die color noted in the column heading.

The algorithm commences by rolling all three dice returning a value between 3 and 18. This initial action corresponds to Row 0 in the table. When comparing Row 0 to Row 1, we note that only the red value changes (from 0 to 1). Our corresponding action is to pick up the red die and throw it calculating a new sum for the three dice. The new sum is used to select the next note of the composition. We are ready to generate a new note, so we compare Row 1 with Row 2 and find that both the green and red values change. Our corresponding action is to pick up the red and green dice and throw them. The dice are summed and the new sum corresponds to another new note. This process is repeated until the prescribed number of notes is generated.

Table 15.6.1

Example 15.6.1 is a Common LISP implementation of a slightly modified version of the algorithm by Richard F. Voss. The principle modification is that Example 15.6.1 simulates three five-sided dice. Each die returns the values 0, 1, 2, 3, or 4. The sum of the three dice ranges from 0 to 12 that easily maps to an octave.

The Common LISP function 1-OVER-F accepts as input a NUMBER representing the number of events it should generate. A DO* begins the iterative process by simulating the initial throw of the three dice represented by the variables BLUE, GREEN, and RED. The sum of the random process is assigned to the variable TOTAL that is CONS ed onto THE-LIST. Upon subsequent iterations of the loop, we simulate the toss of die only if the variable COUNTER has certain values that correspond to the entries in Table 15.6.1. For example, we toss the BLUE die only if the COUNTER equals four simulating the change in state from 3 ₁₀ to 4 ₁₀ in Table 15.6.1.

Example 15.6.1: 1-over-f.lisp

 1-over-f.mp3

We can easily integrate our function to generate a list of notes based on the 1/f algorithm into Common Music. Example 15.6.2 creates an item stream by calling the Common LISP function 1-OVER-F inside the generator 1-over-f-music. A LET randomly selects the value of OCTAVE in the range 4 to 5. The value of OCTAVE is multiplied by the value of an item returned from the 1-over-f-item-stream.

Example 15.6.2: 1-over-f-music.lisp

15.7 Suggested Listening

Gloriette for John Cage for mechanical organ was composed by Heinrich Taube in 1993. The piece is a tribute to the composer John Cage who died in 1992. As Heinrich Taube states, "In keeping with the late composer's interest in chance music, this work was composed using an algorithmic chance process in which the likelihood of the musical notes C-A-G-E being played gradually increases over the course of the work, the composer's name slowly emerges out of the harmonic background of G dorian." [Taube, 1993]

Entropy for computer-controlled piano by Christopher Dobrian [Dobrian, 1991] explores the perception of randomness and order (entropy and negentropy) in musical structure, and demonstrates the use of stochasticism not only as a model for the distribution of sounds in time, but also as a method for variation of a harmonic "order." The composing algorithm takes as its input a description of some beginning and ending characteristics of a musical phrase, and outputs the note information necessary to realize a continuous transformation from the beginning to the ending state. The algorithm composes melodic phrases of any length by calculating arrays of instantaneous probabilities, and incrementing toward the ending point and repeating the process.