Algorithmic Composition: A Gentle Introduction to Music Composition Using Common LISP and Common Music
Skip other details (including permanent urls, DOI, citation information): This work is protected by copyright and may be linked to without seeking permission. Permission must be received for subsequent distribution in print or electronically. Please contact [email protected] for more information.
For more information, read Michigan Publishing's access and usage policy.
Chapter 14: Iteration
14.1 Introduction to Iteration
Iteration is a repeating process. In Common LISP, iteration is accomplished through loops. Loops repeat a process over and over again. A loop should terminate after a specified number of repetitions or when a condition is met. Common LISP has a multitude of iterative forms. Because there are so many, this chapter will use many of the same examples used in Chapter 13 so the reader can easily compare recursive and iterative forms.
14.2 DOTIMES
Perhaps the simplest iterative form in Common LISP is DOTIMES.DOTIMES, as its name suggests, performs a specified task(s) a prescribed number of times.DOTIMES increments a loop-control-variable up to (but not including) an upper-bound. You may optionally specify a return value when the loop is terminated. The body of the loop specifies the task(s) that should be completed during each iteration.
In Example 14.2.1, we use DOTIMES to increment the loop-control-variable COUNTER. As we enter the loop, the variable COUNTER starts counting at 0. We enter the body of the loop and print the value of COUNTER. Because the value of COUNTER is less than the upper-bound, COUNTER increments by 1 and the body of the loop is executed again. The iterative process stops when COUNTER equals the upper-bound.
Notice that Example 14.2.1 returns NIL after concluding the iterative process. The reason DOTIMES returns NIL is because we did not specify an OPTIONAL-RESULT. Example 14.2.2 is the same as Example 14.2.1 except an optional result is specified. We return the symbol DONE. Compare Example 14.2.2 with the recursive function in Example 13.2.4.
Example 14.2.2
In Example 14.2.3, we define a function MAKE-A-CHROMATIC-LICK. The purpose of the function is to create a list that generates a specified number of half steps from a starting keynumber. We begin by entering a LET that initializes the variable THE-LIST to NIL. The notes we generate will be collected into THE-LIST. The body of the LET consists of a DOTIMES. The loop-control variable is INDEX, the upper-bound is the NUMBER-OF-NOTES we need to create, and the result is THE-LIST of notes. In the body of the DOTIMES, we CONS the sum of STARTING-NOTE and the INDEX onto the list. We re-assign the variable THE-LIST using SETF. The list consing process continues until the variable INDEX is equal to the NUMBER-OF-NOTES. The consed list is returned. To help understand the iterative process, a FORMAT statement has been inserted into the body of the dotimes.
Example 14.2.3: make-a-chromatic-lick.lisp
When we call the function, we get the following results:
? (make-a-chromatic-lick 60 6)
Why does the list go from largest to smallest? Because we consed the newly-created element onto the front of the list. If we want a list in ascending order, we should use the Common LISP primitive REVERSE on THE-LIST. Compare Example 14.2.4 with the recursive solution found in Example 13.3.2.
Example 14.2.4
We call the function:
14.3 DOLIST
The Common LISP primitive DOLIST is like DOTIMES, except that it operates on lists. Like DOTIMES, DOLIST has a loop-control-variable, an optional result, and a body. The loop-control-variable serves as an index to the list. The loop-control-variable increments until it is equal to the length of the list.
Example 14.3.1 shows a simple application of DOLIST.
Example 14.3.1:
? (dolist (counter '(60 61 62 63) 'done)
(print counter))
Example 14.3.2 defines a function COUNT-OUTLYERS that counts the number of notes in a list that are outside of the range of the MIDI Specification. We enter a LET and initialize the variable RESULT to 0.RESULT is incremented when a note exceeds the range of the MIDI Specification. We initialize the lower and upper bound of the MIDI Specification to 0 and 127, respectively. The body of the LET is a DOLIST. The DOLIST has a loop-control-variable named ELEMENT that steps through the list. We use WHEN to test the value of each element of the list with the upper and lower bounds. If the element exceeds either the lower bound or the upper bound, we increment the variable RESULT. When the DOLIST completes processing, it returns the value of the variable RESULT. A FORMAT statement is added to the body of the DOLIST to track the values of the variables ELEMENT and RESULT. Compare Example 14.3.2 with the recursive solution found in Example 13.4.4.
Example 14.3.2: count-outlyers.lisp
When we call the function, we get the following results:
14.4 RETURN
RETURN is generally preceded by a condition that forces an early exit from the loop. If a return-value is not specified, the loop returns NIL.
Example 14.4.3 is a modification of Example 14.2.2. Instead of counting the notes that fall outside of the MIDI Specification, the function returns the first occurrence of a note outside of the range. If no notes in the list exceed the range of the MIDI Specification, DOLIST returns NONE-FOUND.
Example 14.4.3: return-first-outlyer.lisp
14.5 DO
Variables may be initialized in DO and their values optionally updated at each iteration. A LOOP-TERMINATION-TEST terminates processing. One or more consequences may be evaluated when the loop terminates. If the condition to terminate processing is false, the body of the DO is evaluated.
Recall Example 14.2.1 when we used DOTIMES to print the changing value of the loop-control-variable. Example 14.5.1 implements the same algorithm using DO.
Example 14.5.1
(print counter))
We enter the DO. We initialize the variable COUNTER to 0. The loop-termination-test (= COUNTER 4) is evaluated. If the evaluation is false, then DO executes its body and prints the value of counter. On the next iteration, DO updates the variable COUNTER by incrementing it by one. The loop-termination-test is evaluated and because it evaluates to false, the body is executed again. This process repeats until the value of COUNTER is equal to 4. The consequent clause on loop termination evaluates the quoted symbol DONE.
Recall Example 14.2.1 when we used DOLIST to PRINT each element in a list. Example 14.5.2 implements the same functionality using DO.
Example 14.5.2
In Example 14.5.3, we modify Example 14.2.2 to use DO. Notice in this example, we provide initialization and update values for the variable ELEMENT. The variable RESULT is initialized but not updated. The reason we do not update RESULT is because we conditionally increment its value in the body of the DO.
Example 14.5.3: count-outlyers-do.lisp
We call the function:
In Example 14.5.5, we modify the function in Example 14.2.3 MAKE-A-CHROMATIC-LICK, to use DO.
Example 14.5.5
We call the function MAKE-A-CHROMATIC-LICK-DO with inputs of 60 and 6. The function returns a list of half steps starting on 60 and going for 6 in descending order.
14.6 DO*
The Common LISP primitive DO* is like DO except that its variable initializations are done sequentially. The difference between DO and DO* is analogous to the difference between LET and LET* .
In Example 14.6.1, we use DO* to implement the same procedure in Example 14.3.3: a function that returns the first note outside of the range of the MIDI Specification. Just as we saw in Example 14.3.3, we use a condition followed by RETURN to force an early exit from the loop. We RETURN the value of the variable ELEMENT that is outside the range.
Example 14.6.1: return-first-outlyer-do*.lisp
We call the function:
Why do we need to use DO* rather than DO for Example 14.6.1? Because the variable ELEMENT is initialized based on the value of the variable INDEX.
14.7 LOOP with WHEN and UNLESS
LOOP is generally followed by a conditional form such as WHEN or UNLESS to prevent an infinite loop.
In Example 14.7.1, we once again make a chromatic lick as we did in Examples 14.2.3 and 14.4.5. This time, we use LOOP.
Example 14.7.1: make-a-chromatic-lick-loop.lisp
(incf index))))
Notice that we enter a LET in the body of the function. We initialize the variable INDEX to 0 and the variable THE-LIST to the empty list. We enter a LOOP in the body of the LET.LOOP is immediately followed by a condition where the value of INDEX is compared to the variable NUMBER-OF-NOTES. If the condition evaluates to NIL, the body of the LOOP is evaluated and we CONS a note onto THE-LIST and re-assign the-list using SETF. We increment the index using SETF. The iterative process continues until the INDEX equals the NUMBER-OF-NOTES. When the INDEX equals the NUMBER-OF-NOTES, the RETURN is evaluated and the LOOP returns the value of the variable THE-LIST.
We call the function:
In Example 14.7.2, once again we search for MIDI note numbers that are outside the range of the MIDI Specification as we did in Examples 14.2.2 and 14.4.3. This time, we use LOOP.
In the body of the function, we enter a LET and initialize the variables INDEX and RESULT to 0. In the body of the LET, we enter a LOOP. The condition that terminates iterative processing uses UNLESS. Recall that UNLESS evaluates its consequent clause only when the condition is false. Because element is 0, and the UNLESS is true, we enter the body of the LOOP. Within the LOOP is a condition that checks to see if the note is in out of bounds. If the note is too high or too low, the variable RESULT is incremented. The body of the LOOP increments the variable ELEMENT. The LOOP terminates when the condition that ELEMENT is less than the length of the MIDI note list is false. The value of the variable RESULT is returned.
Example 14.7.2: count-outlyers-loop.lisp
(incf element))))
We call the function:
14.8 Reading and Writing Records using Iteration
In Chapter 7, we learned how to input data into a program from the computer keyboard using the Common LISP primitive READ. Common LISP provides the macro WITH-OPEN-FILE that allows you to read data from a file. The template for WITH-OPEN-FILE is:
(WITH-OPEN-FILE (VARIABLE "PATH-TO-DATA-FILE"))
VARIABLE is a variable that is associated with the stream of data that is read from the file.
The exact specification of the PATH-TO-DATA-FILE is dependent on your operating system.
The following code assumes you are using the Macintosh Operating System (MacOS) and that the file midi.dat resides on the desktop.
(WITH-OPEN-FILE (MY-DATA "MACINTOSH HD:DESKTOP FOLDER:MIDI.DAT"))
The contents of the ASCII (plain text) file midi.dat looks like this:
WITH-OPEN-FILE accepts the optional keyword :DIRECTION with a keyword value of :INPUT or :OUTPUT. If no keyword and value is specified, WITH-OPEN-FILE assumes the file is opened for input.
In Example 14.8.1, we define a function GET-MIDI-DATA that opens the file midi.dat, reads data from the file, and outputs what it has read to the monitor using FORMAT.
Example 14.8.1: get-midi-data.lisp
We enter a LET while still in the lexical context of the WITH-OPEN-FILE. The LET assigns the variables THE-NOTE, THE-AMPLITUDE, and THE-CHANNEL with data read from the file. The body of the LET uses a FORMAT to print the data read from the file to the monitor.
In Example 14.8.2, we call the function GET-MIDI-DATA.
Example 14.8.2
? (get-midi-data)
As you can see, the function GET-MIDI-DATA only retrieved the first line of data from the file. We need to use an iterative process to retrieve more than one line of data. Example 14.8.3 defines a function READ-MULTIPLE-RECORDS. The function uses a DO loop to repeatedly process data from the file. The DO loop assigns the variables MIDI-NOTE, VELOCITY, and CHANNEL. In this case, both the initialization and update values of the variable in the DO are to READ from the file. The NIL in (READ MY-DATA NIL) tells LISP to return NIL when it encounters the end of the file. The loop terminates using the condition (NOT MIDI-NOTE). Since LISP assigns MIDI-NOTE NIL when it reaches the end of the file, the NOT of NIL is T and the loop terminates. The body of the DO loop is a FORMAT.
Example 14.8.4: read-multiple-records.lisp
(format t "~%The midi note is ~a the velocity is ~a and the channel is ~a" midi-note velocity channel))))
In Example 14.8.5, we call the function READ-MULTIPLE-RECORDS.
Example 14.8.6 opens two files: one for input (midi.dat) and one for output (midi-out.dat). Common LISP assumes that midi-out.dat does not exist. We use a DO loop to iteratively read from the input file. We use FORMAT in the body of the DO loop to write to the output file. Notice that FORMAT does not use T to write to the terminal but instead uses the variable OUT-DATA to direct printing to the output file.
Example 14.8.6: write-multiple-records.lisp
In Example 14.8.7, we call the function WRITE-MULTIPLE-RECORDS.
All of the output from the function has been directed to the file midi-out.dat. When we view the contents of midi-out.data, we see:
14.9 Using Iterative Forms in Common Music
We have used generators, algorithms, and merges in most of the Common Music examples thus far. Merges were used to schedule generators. We found that generators and algorithms have an implicit iterative nature as they step through item streams in the assignment of slots.
The thread container does not have a looping behavior like a generator or an algorithm. We can use iterative forms inside a thread container to accomplish repetitive processing. Example 14.9.1 creates a thread named chromatic-lick-stella that contains a DO loop. The variables initialized in the DO loop are MY-NOTE and MY-RHY that are initialized at 0 and a random floating point value between 1 and 2.9999, respectively. The loop-termination-test is when the variable MY-NOTE is greater than 65. When the loop-termination-test is false, a new midi-note object is created using the Common Music macro object. The note and rhythm slots are assigned the value of the variables MY-NOTE and MY-RHY. The remaining slots are assigned numeric constants.
Iterative forms like DOLIST are very handy in creating chords using a thread. Example 14.9.2 demonstrates the use of DOLIST to step through a list assigning each element to the note slot. Because the rhythm slot retains a value of 0, the notes are generated with the same start time. Playback of the chord may be controlled using the thread initialization parameter start.
Example 14.9.2: c-chord.lisp
Of course, threads may be combined into a merge to control playback of events. Example 14.9.3 is a simple example of how iterative forms may be contained in threads and processed in parallel using a merge.
Example 14.9.3: simple-example.lisp
simple-example.mp3
