Design II: Index/Supply

Introduction

In the index/supply design, the active component generates intermediate index values in the discrete range from 0 to N-1. The passive component uses the intermediate index to look up a target value in the supply containing N elements. When I use the word "selection" here, its about dereferencing a supply element using a generated index. A supply might be implemented as a simple array or as a list (an indexed collection).

My own experience with the index/supply design comes from a program named Compose, which I developed during my two-semester teaching career. (The first semester happened at the New England Conservatory and the second semester happened at the State University of New York at Buffalo.) Like Koenig's Project2, which was very much in mind, Compose was created to give non-programmers an opportunity to mix and match compositional algorithms. Compose was programmed for the Macintosh Plus and Macintosh II and as such represented a generational upgrade of Project2 to a windowing environment. Compose projects were built up from procedural units, each unit being presented as a modeless dialog. Some units implemented selection principles like Koenig's SEQUENCE and SERIES. Other units collated time, duration, timbre, dynamic, and pitch to create elemental subscores (single notes and/or chords). Still other units assembled smaller subscores into larger ones. The fully assembled score could then be performed using MIDI. The semester at SUNY/Buffalo ended with a concert of music by graduate composition students, with 11 of the 12 pieces being produced using Compose. I gave everybody A's, even the guy who didn't use my program.

Compose was subsequently documented in Interface: Journal of New Music Research¹. It organized all its data (integers, reals, degrees, pitches, and subscores) as trees. Trees could be single elements (effectively a single-member list), lists of elements, or lists of subtrees. A lot of what went on in a Compose project involved assembling smaller trees into larger trees and/or selecting subtrees from a tree's top-level list. Thus a phrase-generating unit could append subscores acquired from a note-generating unit, and the note-generating unit could in turn acquire pitches from a sequence-iterating unit. The sequence-iterating unit would have for its supply a tree of pitches (each element being a pitch or a chord). The sequence-iterating unit would also be responsible for notifying the phrase-generating unit when its supply had been exhausted.

The index generators (indexers for short) described on this site were all originally features of Compose. They are:

• IndexSequence (there's also a DriverSequence) draws indices sequentially from a stored collection of integers.
• Feedback draws from the discrete range from 0 to N-1 using a quasi-deterministic algorithm favoring indices which have so-far received less than their fair share of usage.
• MarkovMatrix conditions each target selection upon its source — that is, the selection that came before.
• ChomskyGrammar conditions each selection both on the choice that came before and the choice that is coming up.

Couplings which process continuous Driver output from zero to unity through bounded-range Transform.Discrete units can also serve the Indexer role.

In the unpublished textbook I wrote on composing programs (reproduced on this site here) the Index/Supply pattern contributed to the pedagogical organization, as did Jakob Bernolli's urn model and Noam Chomky's phrase-structure grammars:

• Chapter 3, "Literal Selection" dealt with deterministic process of the type represented by IndexSequence in UsageMode.SAMPLES_DIRECT.
• Chapter 4, "Direct Randomness" addressed what Bernolli called "selection with replacement", that is random choices conforming loosely (through the Law of Large Numbers) to statistical distributions. This chapter emphasized the Driver/Transform model of note-attribute selection. Chomsky's phrase-structure grammars characterize this selection model as "context-free".
• Chapter 5, "Statistical Frames" addressed what what Bernolli called "selection without replacement". These were process of the type represented by IndexSequence in UsageMode.DIRECT_SHUFFLED. This is a rudimentary kind of context sensitivity, governed by a rule against repeating any supply element until the entire supply had been presented.
• Chapter 6, "Markov Chains" explored the notion of conditional selection, that is, predicating a current choice upon the choice or choices leading up to it. This is the basis of the present MarkovMatrix indexer. In the phrase-structure world Markov chains reflect sensitivity to what came before, which limitation was criticized by Chomsky for having no sensitivity to what was to come.
• Chapter 7 introduced statistical feedback as a quasi-deterministic and "frame-free" way of conforming to statistical distributions over the short term. The algorithms explored in this chapter were less-functional predecessors to the algorithm implemented by the Feedback indexer.
• Chapter 8, "Evolutions" introduced the practice of using line-segment graphs to shape how a piece evolves over time. Classes supporting this practice are explored in "Design III: Contours".
• Chapter 11, "Grammars" worked out examples of how recursive productions could be used to elaborate a simple overall outline of a piece into fleshed-out content. The ChomskyGrammar indexer was a feature of Compose intended to give non-programmers the opportunity to design such productions. No students actually used it.

Later chapters of my textbook (14 chapters in all) veered away from sequence generation, turning rather to the constrained decision-making algorithms which I favor in my own composing programs.

Detachment Issues

Isolating the supply from the selection principle detaches the supply element from the index used to select it. This detachment creates no issues for indexers which are neutral; that is, where indices have equal statistical weight and where the only context is the element's position in the supply. Such is the case with IndexSequence. However the remaining indexers are less neutral. Index-weights are normally unequal for applications employing Feedback. This situation leaves it to the user to make sure index weights align properly with supply elements. Context issues become even more intense with MarkovMatrix and ChomskyGrammar.

The Index Domain

Within the Index/Supply design, looking up a value in an array or list establishes a mathematical function mapping values from a source set, the domain, to a target set, which in my day was called the range. I have adopted the term index domain for the source set, since this set describes values produced generally by Indexer.next().

Mathematically, index domain values are whole numbers. Whole numbers are "discrete" in the sense that each given number has just one immediate successor; the number half-way between is not also a whole number. This means that whole numbers can be represented in binary form without digits to the right of the binary point. Whole numbers are thus distinguished from real numbers which are continuous and which have digits right of the binary point. Whole numbers are implemented on this site using Java's int type.

Each supply defines its own index domain. That particular domain runs from 0 to N-1, where N is the number of supply elements. The supply size N is the number returned by Indexer.getLimit().

/**
 * The {@link Indexer} interface prescribes common methods for objects
 * that generate sequences of non-negative integers.
 * @author Charles Ames
 */
public interface Indexer extends Iterator<Integer> {
   /**
    * Test that the indicated index value ranges from zero (inclusive)
    * to limit (exclusive).
    * @param index The indicated index value.
    * @param limit The exclusive maximum index.
    * @return True if the value is in the index range; false otherwise.
    */
   public static boolean valueInRange(int index, int limit) {
      return (0 <= index && limit > index);
   }
   /**
    * Check that the indicated index value is non-negative.
    * @param index The indicated index value.
    * @param limit The exclusive maximum index.
    * @throws IllegalArgumentException when the index falls outside
    * the index range.
    */
   public static void checkIndexValue(int index, int limit) {
      if (!valueInRange(index, limit))
         throw new IllegalArgumentException(
            "Index value [" + index +
            "] ouside range from zero (inclusive) to "
            + limit + " (exclusive)");
   }
   /**
    * Get the excluded upper index bound, which should correspond
    * to the supply size.
    * @return The excluded maximum index.
    */
   public int getLimit();
   /**
    * Query if this driver/indexer class supports the {@link #reset()} operation.
    * @return true if {@link #reset()} is supported; false otherwise.
    */
   public boolean hasReset();
   /**
    * Reset iteration through to starting state.
    */
   public void reset();
   /**
    * Calculate a practical lower bound for graphing output from this
    * generator.
    * @return A practical lower bound for graphing output from this
    * generator.
    */
   public abstract double minGraphValue();
   /**
    * Calculate a practical upper bound for graphing output from this
    * generator.
    * @return A practical upper bound for graphing output from this
    * generator.
    */
   public abstract double maxGraphValue();
}

Comments

1. Charles Ames, "Introduction to Compose: An editor and interpreter for automated score generation and score processing", Interface: Journal of New Music Research Vol. 20, No. 3-4 (1991) pp. 181-196.