Demonstration 11
Constrained Search

Introduction

Demonstration 10 provides the practical component for Chapter 14: “Constrained Search” of my unpublished textbook on composing programs. It illustrates the use of constrained searches in a full-fledged composing program which applies the principle of bottom-up design. The composition produced by this program is a study in what Robert Erickson (1975) terms “perceptual channeling”, that is, the mechanism by which listeners perceive disjoint musical events as components of an ongoing process, or “channel”. In Demonstration 11, the major factor contributing to channeling is register, although the fact that each pitch constantly associates with a fixed group of partners also plays in important role.

Compositional Directives

The compositional process divides into four stages of production:

• Stage I: Material — composing the eight ‘cells’ depicted in Figure 1.
• Stage II: Form — selecting material for each segment in order to determine the compositional profile depicted in Figure 2.
• Stage III: Rhythm — composing rhythm and selecting cells for each note.
• Stage IV: Pitch — selecting inflections for each note.

As happened in Demonstration 10, the present Stage II induces the form of Demonstration 11 from the ‘bottom up’ on the basis of qualities inherent in material composed during Stage I. Information from Stage II enables Stage III to describe all of the notes in the piece to the extent of rhythms and cell numbers. Stage IV completes the process by filling in inflections.

Material

Stage I generates the material of the piece, which consists of eight melodic cells. Figure 1 depicts the products of this stage. Each cell consists of three ‘inflections’ of a register: low, middle, and high. These ‘inflections’ are realized by chromatic pitches spaced no farther apart than a whole tone. The material has the following properties:

1. Each cell consists of two melodic steps, where a step may be either a semitone or a whole tone. This constraint establishes the cells as melodic clusters.
2. Of the four intervallic structure possible given the preceding constraint, each structure appears exactly twice. This constraint seeks to differentiate the cells intervallically.
3. No two cells overlap. This constraint seeks to differentiate the cells registrally.
4. No degree of the chromatic scale appears more than twice in all the material. This constraint seeks to maximize chromatic richness for the eight cells taken in total.
5. No two cells share more than one common chromatic degree. This constraint seeks to differentiate cells chromatically.

Curved brackets in Figure 1 indicate semitones; square brackets indicate whole tones.

Form

The piece consists of 18 segments. Stage II of the composing program assigns cells to segments. Eight segments draw material from one cell only; five segments draw material from two cells simultaneously; three segments draw material from three cells; and the remaining two segments draw material from four cells at once. Since the effect is of implied counterpoint, it will be appropriate to use the word ‘part’ to distinguish between cells simultaneously exploited in a segment. It will also be appropriate to refer to the various segments as ‘solos’, ‘duets’, ‘trios’, and ‘quartets’, depending upon the number of parts involved.

The constraints governing selection of cells for segments are:

1. No two solos, duets, trios, or quartets may share an identical configuration of cells; neither may two quartets share more than two cells. This constraint enforces a diversity of segments.
2. Two cells in adjacent registers may not occur in the same segment if their closest inflections lie within a minor third. This constraint inhibits cross channeling between registrally adjacent cells.
3. A solo may not exploit any cell appearing in the immediately preceding segment; duets, trios, and quartets must share at least one cell with their immediate predecessor if the number of parts remains the same or increases. These constraints enforce a dovetailing effect between consecutive segments.

Rhythm

Stage III selects period between consecutive attacks by direct random selection using John Myhill's variation on exponential distribution, fixing the ratio of maximum to minimum durations to 8.0. The upper graph in Figure 2 details the average period between attacks for each segment. Notice that this average decreases (equivalently, the density of notes increases) as the amount of available material rises.

The program selects cells using cumulative feedback leavened by randomness. This procedure allows unpredictable short-term choices while balancing cell-usage out over the longer term.

Articulation is sensitive to whether or not a note's successor shares the same cell:

• If two consecutive notes share the same cell, then the program acknowledges this relationship by indicating either that the pair should be slurred or that the successor should be tongued with no intervening rest. This decision is conducted by Bernoulli trial; the more parts occurring in a segment, the greater the likelihood that the pair will be slurred.
• If two consecutive notes exploit different cells, then the program acknowledges this difference by insisting that the successor always be tongued. A Bernoulli trial with 50% probability of success decides whether or not the program inserts an intervening sixteenth rest.

Pitch

Stage IV of the the composing process selects for each note which of the three registral inflections available to the cell specified in Stage III will provide the pitch. The program attempts to keep these inflections in balance by employing cumulative feedback to favor the least-used inflection of any cell. It also forbids any cell from repeating an inflection without in the meantime stating at least one of the cell's two alternative inflections.

Since the type of harmonic connections suggested by inter-cell consonances would contradict the central motivations of the piece, the pitches in Demonstration 11 adhere to a dissonant style. As a minimum precaution against cross-channeling, the pitch-selecting program avoids virtual octaves; that is, when one cell plays a chromatic degree shared by a second cell, at least one of the two cells must play a different degree before the second cell may use the shared degree. In addition, consecutive notes must obey the stylistic matrix illustrated in Figure 3. Unlike stylistic constraints employed for previous Demonstrations, the present program skips over chromatic identities in order to apply this matrix to the first two distinct degrees immediately preceding the current note.

Columns in Figure 3 indicate current chromatic intervals given the most recent interval indicated by the row. Non-blank entries show acceptable intervallic sequences.

The end-product of stages I-IV is shown in Figure 4.

Implementation

The following explanations seek to illustrate constrained searches in play. The explanations are peppered with line numbers, but you are are by no means expected to chase down every line of code. Rather, you should follow through with line numbers only when you have a specific question that the narrative is not answering.

Program DEMO11 proper appears as Listing 1; the BLOCK DATA routine used to initialize COMMON memory variables appears as Listing 2. The program which assigned pitches to cells (Stage I) will not be documented, but it too employed the constrained search strategy. After some initialization work, the body of program DEMO11 simply calls out to two subroutines, each of which implements a stage of production. The call to subroutine FORM in line 17 executes Stage II, which assigns cells to segments. The call to subroutine RHYTHM in line 18 executes Stage III, which composes all of the notes in the piece to the extent of describing periods, cells, and articulations. RHYTHM stores its intermediate results to the file named “DEMO11.RHY” for later processing. An independent run by program RHYTHM picks up data from file “DEMO11.RHY” then executes Stage IV, which selects cell-inflections (pitches) for notes and writes out a human-readable listing of the completed product.

Listing 1: Program DEMO7.		Listing 2: BLOCK DATA routine for DEMO7.

Form

The source code for subroutine FORM appears in Listing 3 (a) and Listing 3 (b). This subroutine implements a constrained search which selects from one to four cells for each segment. The initial data resides in two arrays: array element NUMSEG(ISEG) holds the number of parts in segment ISEG while array element DURSEG(ISEG) holds the segment's duration in sixteenths. These two arrays are populated in lines 6-8 of the BLOCK DATA routine.

Listing 3 (a): Subroutine FORM, lines 1-85.		Listing 3 (b): Subroutine FORM, lines 86-170.

FORM stores and accesses cells for each part in each segment by employing arrays CELPRT and LIMSEG along with the following indexing scheme: Cells selected for the Ith segment reside in elements LIMSEG(I-1)+1 through LIMSEG(I) of CELPRT. Lines 10-16 of program DEMO11 proper initialize the relative positions stored in LIMSEG from the cell counts stored in NUMSEG.

The variable IPRT serves as the recursive index and as a pointer to the part and segment currently under consideration. Notice that FORM does not reset IPRT to 1 when it advances to a new segment; referring to Figure 2 for examples, IPRT=2 for segment 2, part 1; IPRT=7 for segment 5, part 2; and so on.

Since a cell may appear no more than once within any segment, FORM derives one schedule of cells for the whole segment. It then proceeds to allot cells to parts by sampling this schedule without replacement. Array element CELIDX(J,I) holds the cell scheduled Jth in line for the Ith segment; array element IDXCEL(K) indicates which position in the schedule is currently being considered for the segment and part accessed by index K; therefore, the actual cell number resides in array element CELIDX(IDXCEL(J),I). Sampling without replacement is enforced by maintaining IDXCEL(LIMSEG(I-1)+1) through IDXCEL(LIMSEG(I)) in strictly increasing order (due to line 137 of FORM).

Prior to the search, program DEMO11 proper computes for each segment the portion of the segment's duration which the program expects to devote to the individual parts (line 15 of the loop spanning lines 10-16), storing this value in the real array INCSEG. Array CUMCEL maintains statistics of cumulative usage for each of the eight cells. Each time it selects a cell, FORM increments the appropriate element of array CUMCEL by INCSEG(ISEG). Calls to the library subroutine FUZZY effect random scheduling with a strong bias — the offset of 1.0 falls far short of the smallest value stored in INCSEG — toward the least-used cells (lies 38 and 134 of FORM).

The bulk of subroutine FORM imposes the constraints upon the search.

• The test for segments with identical material (lines 50-75) compare the current segment to every preceding segment, counting up the number of common cells in each case.
• The test for too-close cells (lines 77-85) steps through cells already selected for the current segment and consults the logical array LGLCEL initialized in lines 11-18) in order to determine whether or not the cell currently under consideration is compatible with this earlier commitment.
• Requirements for dovetailing (lines 88-116) are enforced by first counting up the number of cells shared with the most recent segment, then considering special cases.

Each time FORM encounters a configuration which proves nonviable in the light of choices made for an earlier segment, it updates the backtracking variable BAKSEG(ISEG). FORM scrupulously considers every possible configuration of cells for the current segment until either it discovers a workable arrangement or it runs out of combinations. In the latter case, BAKSEG provides the most recent segment responsible for any conflict.

Rhythm

Subroutine RHYTHM is listed in Listing 4. This subroutine implements Stage III of compositional processing, which selects periods between consecutive attacks, which selects cells for notes, and which selects articulations.

The main body of subroutine RHYTHM consists of an outer loop (lines 32-94) iterating once for each of the 18 segments and an inner loop (lines 38-86) iterating once for each note in a segment.

RHYTHM selects periods between consecutive attacks (lines 40-42) via the library function RANX. Average periods are drawn from array AVGNUM (initialized in line 8) and depend upon the number of parts in the current segment, NUMSEG(ISEG).

The subprogram selects cells (lines 44-65) using the methods of the library subroutine DECIDE. At the end of each segment, RHYTHM steps through the active cells, subtracting each cell's ‘expected’ cumulative statistic SUM*INCCEL(ICEL) from the actual value CUMCEL(ICEL) (lines 86-91). This procedure insures that if a cell has received its fair share of note durations within a segment, it starts out fresh in the next segment; however, when cells have been either slighted or overindulged, RHYTHM retains awareness of such imbalances and acts to compensate for them in later segments.

Articulations (lines 67-72) must be selected one step behind in the process since how a note connects to its successor depends on whether the successor exploits the same cell or a different cell. RHYTHM selects articulations by asking the library function SUCCES to conduct Bernoulli trials; array ARTIC (initialized in line 8) controls likelihoods that two consecutive notes sharing identical cell numbers will be slurred; this likelihood depends on the number of parts in the current segment.

Pitch

Program PITCH is listed in Listing 5 (a). This routine runs independently of program DEMO11. It implements Stage IV of compositional processing, which selects cell inflections (pitches) for each note in the piece.

Listing 5 (a): Subroutine PITCH, lines 1-82.		Listing 5 (b): Subroutine PITCH, lines 83-154.

PITCH organizes data pertaining to individual notes in several parallel queues. Each queue is distinguished by the root abbreviation QUE; the following abbreviated prefixes signify information read by subroutine RNOTE (see Listing 8) from the intermediate file “DEMO11.RHY”:

• TIM — Starting time in sixteenths.
• PER — Period to next attack in sixteenths.
• DUR — Duration of note in sixteenths.
• CEL — Melodic cell (1-8).
• SEG — Segment (1-18).

Listing 8: Subroutine RNOTE.		Listing 9: Subroutine WNOTE.

Subroutine RNOTE creates three additional items of data per note. Two items, a backward link OLDQUE and forward link NEWQUE enable PITCH to access notes quickly when it needs information pertinent to specific cells. Figure 5 illustrates the linked structure derived by RNOTE for an actual sequence of notes read in from “DEMO11.RHY”. Pointers to the head of the backward list for each cell reside in the auxiliary array OLDCEL. The third item supplied by RNOTE, a decision count CNTQUE, indicates a note's position in the absolute sequence of decisions; this information assists the backtracking mechanism.

Each row of numbers in Figure 5 signifies a note; the left network of arrows shows backward links while the right network shows forward links. The information depicted in Figure 5 describes the portion of Figure 4 beginning with the second quarter of measure 14 and ending after the fifth sixteenth of measure 28.

Listing 6: Function IADV.		Listing 7: Function IRET.

The head and tail of the queue are indicated by the integer variables HEAD and TAIL respectively. The variable IQUE serves as the recursive index and also locates the note currently under consideration. The integer functions IADV (Listing 6) and IRET (Listing 7) handle the wrap-around arithmetic necessary to keep this and related indices between 1 and the queue-size MQUE. Array element NFLQUE(IDXNFL(IQUEU),IQUE) holds the inflection under scrutiny; PITCH also dereferences this value into the holding variable INFL. Array DEGNFL (populated in lines 25-26) supplies the chromatic degrees illustrated in Figure 1 for each inflection in each cell; PITCH dereferences the current note's degree from array element DEGNFL(INFL,ELQUE(IQUE)) to the holding variable IDEG. Both INFL and IDEG are also stored in queues of their own for easy future reference: NFLQUE and DEGQUE.

Each time PITCH selects an inflection for a note, the subprogram increments the appropriate element of array CUMNFL by the duration of the note. Calls to the library subroutine SHUFLE in line 49 and line 120 suppress scheduling bias through random shuffling. Calls to the library subroutine ISORT in line 50 and line 121 sort the schedule of inflections so that the least-used inflections are favored.

The constraints controlling how degrees of the chromatic scale may recur are greatly facilitated by the linked structure illustrated in Figure 5:

• PITCH initiates its test for inflections repeated immediately within the same cell (lines 65-69) by locating the most recent note exploiting the same cell through array OLDCEL. The test then reduces to simply comparing inflection numbers.
• The test for virtual octaves (lines 71-82) steps through each cell other than the current note's cell, using OLDCEL to locate the other cell's most recent note. If both notes share the same chromatic degree and if the current cell has no intervening note, then the program rejects the current inflection.
• BY contrast to the tests just described, the test (lines 84-105) for conformity to the stylistic matrix illustrated in Figure 3 is unconcerned with cell numbers. The first step is to locate the two most recent notes in the queue whose pitches are chromatically distinct both from the inflection currently being considered and from each other. The program then feeds the resulting chromatic intervals into the logical array LGLTVL (populated in the DATA statement spanning lines 14-24). in order to determine if the intervallic sequence is suitable.

The backtracking mechanism for program PITCH first consults array BAKQUE in order to determine the source of an immediate conflict. Sometimes the subprogram approves all of the inflections considered for a note, only to propagate impasses at later notes in each instance. PITCH was unable to supply information for dependency-directed backtracking in such cases, so the subprogram was forced to grope back note-by-note in order to pinpoint the source of conflict empirically.