| |
ISSN 1320-0682 | ||
| Volume 03 | April 1996 | ||
Jon McCormack
Music is one of those areas of activity that, despite its ubiquitous presence in human culture, remains largely immune to a detailed understanding. Nobody knows why something so apparently simple as the succession of changing discrete tones has the power to move the listener emotionally. Of all the arts, music is considered "to be open to the purest expression of order and proportion, unencumbered as it is by material media" [14]. It has been often noted that music bears a close affinity to mathematics, and that notions of mathematical and musical aesthetics may have some similarities [31]. In recent years, many researchers and musicians have turned to the computer as both a compositional and synthesis device for musical expression.
In this paper, we describe a system for computer-assisted music composition and therefore the majority of this introduction will focus on the application of computers for composition. This is not to discount the many other uses of computers in music, such as sound synthesis, acoustic and physical modelling, automated notation, score editing and typography.
A major part of music creation involves the use of certain musical formalisms (systematic ordering), as well as algorithmic and methodic practices. Many of these were well established before the advent of digital computers. In a substantial survey of computer composition, Loy [15] suggests that the application of musical formalisms, based on a priori theories of composition, have been largely developed this century, originating with composers such as Schoenberg and Hindemith. Loy also notes the contribution of music typographers and instructors who have found formal systems attractive to their profession.
Representations for notation and programming of music (and thus computer composition) can be broadly classified into symbolic and iconic [14]. Symbolic representations relate symbols and a sonic event, but have no direct resemblance between them. Iconic representations carry some resemblance (usually visual) to the sound the icon represents. Common music notation combines both forms of representation: time signature, cleffs, bar lines are symbolic; pitch coding, crescendo, diminuendo are iconic. While this system is not completely adequate, particularly for some contemporary forms of music, it is an extremely versatile and capable notation for a diverse range of musical expression.
It has been observed that almost all forms of music involve repetition [12], either of individual sequences of notes or at some higher levels of structural grouping. Often these repetitions appear at a number of different levels simultaneously. Some compositions repeat patters that are slightly changed at each repetition, or revolve around some musical "theme" whereby complex harmonic, timing or key shifts in a basic theme provide a pleasing musical diversity.
It is also commonly known that what allows us to identify an individual piece of music is the change in pitch between notes, not the pitch of the notes themselves. We can change the key of a composition (equivalent to multiplying all frequencies by some fixed amount) and still recognise the melody.
A wide variety of approaches have been taken to the compositional problem. In Loy's survey paper, he details many different methods: stochastic and combinatorial models, grammar-based models, algorithmic models, process models and other models derived from Artificial Intelligence techniques.
The methods used in the system described in this paper are grammar-based. While grammars have been a popular method for algorithmic composition, in most instances, the grammars used are relatively primitive and thus limit the scope of control and diversity of composition that can be generated. The approach used in the system described in this paper, is to take recent developments in grammars used for modelling of biological morphogenesis and herbaceous plants in computer graphics, and apply them to music composition. In addition to being able to represent a variety of both stochastic and deterministic compositional techniques, the system has compositional properties unique to this approach.
The remainder of this paper is organised as follows. The next section briefly looks at the problem of computer based musical creativity and explains the rationale behind computer-assisted composition. The section "Representations for Music Composition" examines algorithmic representations for music composition and introduces the basis of the grammar method. The section "Grammars for Music Composition" details how grammars can be adapted for music composition, with specific emphasis on Lindenmayer Systems (L-Systems) as the basis for the model. The following section discusses implementation details. The final section details possible extensions and further work.
A complete theory of general creativity, or even musical creativity, remains elusive. While many attempts have been made to study and document the creative process - [1], [5], [31], for example - any generality seems difficult to uncover. In many cases, people do not know how or why they make creative decisions, and much of the creative process is difficult to repeat in controlled experiments.
The question of whether creativity is computable is an issue of even greater controversy. Many researchers from Poincaré [25] to Penrose [24] have argued against a computable model of creativity because, simply put, the underlying mental processes are not computable. These arguments depend largely on speculation and the personal opinion of the authors (although Penrose does base his objections on an, as yet, untested theory of the relationship between consciousness and Quantum theory). It is this author's opinion that, while creativity is clearly an ability of the human mind, to a large extent practical creativity is deeply related to an individual's life experience. A life experience includes relationships to the environment, interaction with both living and nonliving things, social and cultural constructions. We all know that these things have a major effect on a person's internal states. Much creativity also depends on serendipitous and chance events in the external world, both conscious and unconscious. The explicit use of random events in composition is a practice many centuries old. It can be found in the works of many artists - from Mozart and Hayden, to Burroughs and Pollack. Creativity is not only influenced by external events, it may also be stimulated by artificially induced internal effects - some artists claim their best creative work is done under the influence of a large variety of chemical substances.
Some day it may be possible to build a computer with processing capabilities similar to that of the human brain [21]. However, computing a simulated life experience would appear to be impossible [22]. It is feasible that a robot that has life-experience in the real world may have the potential to exhibit creative behaviour but again, if life-experience is bound to physicality and matter (as opposed to mechanisms and processes) any creativity exhibited by such a robot may not be recognised as human-like creativity, or even recognised as creativity at all.
Johnson-Laird [9] has argued that music is an excellent testing ground for theories of creativity because, as opposed to other Artificial Intelligence domains such as natural language generation, music avoids the problem of semantics; that is, a musical expression cannot be judged to be true or false. While this statement is literally correct, many musicians would argue that as part of the compositional process, musical expressions do contain semantics. For example, some composers associate emotive, structural or linguistic semantics with individual themes or passages in a composition. Carl Orff described musical composition as the raw expression of human energies and states of being [23]. The musical development of a composition is driven by the associated development of emotions, structure or language. In this sense, such compositions do have "meaning" and there is a semantic association between musical expressions. Such expressions have ordering and denote an emotive symbolic system. According to Langer [11], music as a symbolic system of emotional archetypes conveys a "morphology of feeling" akin to algebraic notation conveying a mathematical expression.
Some composers (Brian Eno, for example) visualise abstract or real environments as mental images, and the visual and emotive feeling of these environments directly influences the composition. Composition is rarely a one-way process from mind to finished composition either. It is an iterative feedback process - hearing the music causes change in the composition. Composers are rarely interested in one aspect of the composition in isolation, such as pitch, timing or timbre; rather these things in total - the "surface" of the music - greatly influence the emotional feeling and thus carry the composition.
In summary, while music may appear to be an easier domain to test theories of creativity, it is difficult to expect a computer program to exhibit a genuine musical creativity which approaches that of human composers. A more achievable approach, one adopted by the system described in this paper, is to use the machine as a synergetic partner to the human composer. The human and computer work in tandem through an interactive feedback process, the computer presenting new musical possibilities by synthesising complexity and variation and the human composer directing the overall creative "quality" of the composition. This human-machine feedback process, known as computational synergetics has been used to significantly enhance both scientific [33] and artistic [19] creativity. The computer, used in heuristic mode can lead the human collaborator to new discoveries that may have been difficult or impossible without the collaboration. In this way, the machine acts as a kind of "creative amplifier" enhancing the creative potential of the composer.
A grammar-based approach to composition makes heavy use of procedural models. One advantage of procedural methods in general, is that they allow a terse representation of a complex model. This is often referred to as database amplification. Such techniques are not the exclusive domain of computing. The representation of a complex organism is effectively encoded in the much simpler (in relative terms) DNA. Likewise, with grammars there is the possibility for the emergence of complexity through the repeated production of simple (and possibly deterministic) rules. One has to be careful with such analogies however, for biological morphogenesis relies also on many factors, such as the laws of physics, special properties of carbon atoms, the self-organisational properties of many molecular and cellular structures and complex environmental interactions. Certainly, these features are not built into our music compositional model, though it is possible that some of these concepts, in an abstract sense, could be incorporated into the model.
A diverse variety of stochastic processes have been applied to music composition [10], [20]. Most involve two stages. Firstly, some existing musical expression or quantity is analysed. Following the analysis, re-synthesis is applied using the selected stochastic technique. Importantly, while we can undertake statistical analysis of many musical patterns, when we attempt to synthesise music based on that analysis, the results rarely seem to have the clarity or intent of human composition. For example, Voss [32] analysed many different types of music and found that several were statistically similar to 1/f noise. However, when one converts 1/f noise to musical notes, the results have little in common musically with any of the compositions from which the statistical analysis was derived. Given the discussion in the first section regarding formalisms, it is clear that a more sophisticated model is required.
Generally in composition, one primary concern is the notion of temporal events and event spaces. We use the general term event to represent some basic building block of composition - in many instances, a note or set of notes, but in other compositional applications, events may refer to sound complexes, individual sound samples or other basic musical elements. An event space is an ordered set of events. The number of events contained in a given event space represents its order.
One popular approach to computer composition is the use of Markov chains, where the probability of a specific event i is context-dependent on the occurrence of a previous event or event space. Most attempts using this form of modelling first require some existing composition to be analysed. For the purposes of explanation, we will restrict this discussion to consider only the pitch of notes. However, there is no reason why the same techniques cannot be applied to other musical qualities such as duration, volume or timbre. We also consider only discrete-valued (as opposed to continuous-valued) data. Markov processes are suited to the analysis of conventional musical pitches. A Markov process is considered stationary if the transition probabilities remain static.
An N-order Markov model can be represented using an N+1 dimensional transition matrix. For example, Figure 1 shows a sequence of note events and the corresponding transition matrix. This is a 1st-order model, where the probability of a given event depends only on the event immediately preceding it. Each element in the transition matrix, Pij represents the probability of event j occurring given that event i has just occurred. Pij is calculated by summing the occurrences of each note j that follows note i in the input melody. Counts in each row are normalised so the combined probabilities for each row sum to 1 - that is:
Figure 1: A set of input notes (from the nursery rhyme Mary had a little lamb), and the corresponding 1st order Markov model, represented as a transition matrix. Each element of the table Pij is the probability of event j given that event i just occurred. Empty elements in the matrix represent a probability of 0.
Jones [10] shows how transition tables can be converted to event-relation diagrams which are essentially finite-state automata. Lyon [16] has used Petri Nets to extend the finite-state model generated by stationary N-order Markov models for real time performance.
The Markov process for composition has several problems:
The grammar-based approach is not new to music composition. Early users of grammar-based techniques include Buxton et al. [2] and Roads [30]. Holtzman's Generative Grammar Definition Language (GGDL) compiler [7], [8] is based on Chomsky grammars of type 0 to 3 (regular, context-sensitive and context-free) [3], [4]. Jones [10] discusses context-free space grammars that can operate across many dimensions, where each dimension represents a different musical attribute. An interesting property of space grammars is that an n-dimensional grammar can generate an n-dimensional geometric shape, which may provide a higher level iconic representation of the music generated by a particular set of rules.
Little use of L-Systems has been made in the area of music composition. Prusinkiewicz [26] has used two-dimensional space-filling curves generated by L-Systems as a basis for music generation, where the spacial position of a vertex in the curve represents a note, and the edge length, the duration.
Much development in music composition and synthesis has been performed in closely related areas such as fractal and stochastic methods, procedure-oriented and recursive composition. Moore [20] gives an overview of some of these methods.
In techniques that use Chomsky grammars, the rewriting is sequential; that is, symbols are replaced one at a time sequentially across the string (corresponding to the serial nature of the process that the grammar represents). In the system described in this paper, we adapt parallel rewriting grammars for composition. Due to constraints discussed in the next section, rewriting is not fully parallel as is the case with L-Systems (upon which the system is based). Rewriting proceeds on parallel sets of elements in the string after the events represented by the string have occurred.
L-Systems are a form of string rewriting grammar, first developed by Lindenmayer in 1968 [13]. The original emphasis was as a mathematical model of cell development and plant topology. Prusinkiewicz [29] applied a turtle interpretation to produce strings that create realistic models of plants for computer graphics purposes. Hannan developed parametric L-Systems that allow symbols in the grammar to have associated numerical parameters [6]. Work by Prusinkiewicz, et al. [28] developed L-Systems further, incorporating more complex models for growth (differential L-Systems) [27], geometric control and interaction with the environment. Hierarchical L-Systems, explained later, allow more complex sequences of rules and give the user greater potential for modelling of interacting event spaces at different levels. L-Systems have been used extensively in computer graphics for the visual modelling of herbaceous (non-woody) plants [28]. They have also been successful for a number of other applications, including the general modelling of natural forms, morphogenesis, legged gaits of animals, image processing and the modelling of human organs for medical analysis.
L-Systems provide a compact way of representing complex patterns that have some degree of repetition, self-similarity or developmental complexity. Because of the abstract nature of the grammar itself, produced symbols have found a diversity of physical and structural representation. In the case of geometric modelling, L-Systems fundamentally provide a way of representing topology. Extensions to the basic grammar allow the interpretation of the topology through complex environmental and structural parameters.
A basic introduction to L-Systems is presented here. For detailed explanations, the reader is referred to [28].
A deterministic, context-free L-grammar (DOL-System) is an ordered triplet:
where:
- alphabet
of the system,
the set of all words over
,
the set of
all non-empty words over
.
P - finite set of productions or rules.
A production
is written
as: 
, where
and
. a
is termed the predecessor and chi the successor of the
production.
alpha - a non-empty word called an axiom,
.
If for any letter in the alphabet
there is no
production, then the identity production
is assumed
(and included by default in the set of productions). Beginning with the axiom,
, we apply
the production in parallel to all letters (symbols) in the word. This iterative
process proceeds for a given number of levels. The resultant string is then
interpreted as musical information.
For example, given the set of productions and an axiom:
p1:
p2:
p3:
( 
is an
empty word or null)
The produced string for the first five iterations becomes:
ITERATION STRING
0 C (axiom)
1 E
2 C G C
3 E E
4 C G C C G C
5 E E E E
Concatenating the strings together gives C E C G C E E C G C C G C E E E E. If each letter is interpreted as a musical note, the string can be played as music:
This simple example has no provision for note-timing, so each note defaults to a quarter-note duration. It is, of course, possible to incorporate symbols in the grammar that control duration.
Stochastic grammars directly map a set of probabilities [ pa1, pa2,...
paN ] with a set of the productions [ Pa1, Pa2, ...PaN
] involving a letter
as the
predecessor. The probability is usually written above the arrow symbol:
This means that a has equal probability of being replaced by b or c. It is assumed that, for all productions with a as the predecessor, that the combined probabilities for that letter sum to 1 - that is:
Stochastic grammars allow the representation of Markov models. For example, the transition matrix shown in Figure 1 is equivalent to the stochastic grammar here:
The choice of axiom is arbitrary. For a correct simulation of the Markov chain, the axiom should select a starting letter based on the frequency a note appears in the set of input notes (this can be incorporated into the grammar as one additional production).
Numerical parameters may be associated with letters in the alphabet [6], [29]. Successor words in a production may involve mathematical expressions in the calculation of parameters. An arbitrary number of real-valued parameters may be associated with any letter. In addition, conditional statements resolve the application of rules based on parameter values:
In the example above, the production is applied while the parameter of A is less than 64. If the parameter in this case is interpreted as note volume, then the above rule plays a crescendo.
The following parametric grammar computes the Fibonacci series:
In a musical application, parameters can be used to control continuous-valued attributes such as note velocity. The MIDI [+] specification allows for a number of continuous-valued controllers. These controllers can be effected through parametric association with the appropriate symbol. (Musical Instrument Digital Interface (MIDI) is a standard method of control in electronic music. It allows the connection of various types of computers, synthesisers and keyboard controllers, provided they obey the MIDI protocol).
As stated, many forms of music involve repeating patterns, often at a number of different levels in a composition. While it is possible to incorporate many levels in a set of productions, a naturally easier way is to impose a hierarchical containment of rules in order to better represent the structure of the music.
Hierarchical grammars have a similar specification as a DOL-System grammar, except that on the successor side of a production, one or more of the successor symbols may be an entire grammar in itself. Development of each set of rules proceeds independently. However, rule sets may pass parameters between sets of grammars. Figure 2 shows an example of grammar and the resulting strings produced from the rules.
Figure 2: A simple hierarchical grammar consisting of two rule
sets, A and B. Below the rules the diagram shows the produced
strings, with iterations over system A running horizontally and
iterations over system B running vertically (the iterations of B
for the third iteration of A is not shown). Each system's development
proceeds independently, but they may communicate via parameters.
Thus far, we have introduced various types of grammars and listed some simple interpretation of the strings they produce for musical purposes. In this section, we discuss the implementation of a composition system based on the grammars described in the previous section.
The system is implemented on a Silicon Graphics workstation connected to a digital synthesiser via MIDI. Once a grammar is parsed, it is capable of generating note sequences (MIDI data) in real time. Very complex grammars (such as those with many levels of hierarchy, or productions that cause exponential growth in the produced string) may cause noticeable delays in the system during processing. In this case, sequences can be saved onto disk for later playback. The goal of the system is real time performance and, in most cases, this is adequately accommodated.
Essentially, the composition system has three major processing stages, outlined in Figure 3. The system builds lists of strings. Productions are applied to these strings and the results interpreted as commands that are output as MIDI data to various synthesisers connected to the system. MIDI data can be converted to standard notation, suitable for interpretation by real musicians (as opposed to machines) if required.
Figure 3: Stages of processing in the system. Square boxes
represent data; rounded boxes represent processes. The lines with arrows show
the directional flow of information. Firstly, a grammar is parsed and the axiom
loaded into the variable currentString. Rule application is iterative.
After rewriting is applied to currentString, the results are
interpreted. The interpretation converts symbols into MIDI data that is then
played, or saved to a file.
The system uses the notion of a virtual player. The player is responsible for the interpretation of instructions given to it, which in the general case means playing notes (sending MIDI messages or writing score information). Players always maintain a current state that consists of:
Control parameters may be used to specify continuous or discrete controllers (for example, pitch bend, filter resonance, etc.).
Symbols in the produced string change the players' state. The string is read sequentially from left to right and each symbol is interpreted by the player, just like a Turing machine reads instructions from a tape. Different symbols cause different components of the player to change state, or perform a task. For example, the dot "." symbol tells the player to play the current note(s), a "+" increments the current note by a semitone, a "-" decreases it by the same amount. Players are capable of playing any number of notes simultaneously. However, in practice this may be limited by output hardware. The square parenthesis symbols "[" and "]" push and pop the current player's state onto a First-In, Last-Out stack.
Multiple players perform a composition. Any number of players may be involved in a composition, however again hardware limitations may fix an upper limit on the total number of notes playable simultaneously. Generally, each player plays a single voice or instrument and each has a different set of rules.
Individual notes can be represented by their name. The "#" symbol represents a sharp, "&" a flat and "@" a natural. Notes in uppercase change the pitch and play the note. Notes in lowercase change the pitch but don't play the note. This means that "C" is equivalent to "c". A comma "," plays a rest for the current duration. Other symbols change duration, timbre, and so on.
Polyphonic playing of notes is achieved by enclosing the notes to be played simultaneously in round parenthesis: "(" and ")". For example, the string C E G plays the specified notes, each for the current duration, in temporal sequence from left to right. The string C E G plays the same three notes, for the current duration simultaneously (a C Major chord). Pitch specification can be relative - thus c ( . + + + . + + + . ) does the same thing (plays a C Major chord).
Context sensitivity relates production application to the predecessor's
context (symbols that appear before the predecessor in an axiom or string). In
the case of music composition, context sensitivity is represented in the
grammar both polyphonically (notes currently being played) and temporally (note(s)
previously played). A vertical bar "
" is used to
signify temporal context: symbols to the left of the bar must precede the
current symbol for the rule to apply. For example:
The use of context in a grammar allows for complex shifting themes to propagate through a composition, both chromatically and temporally. Context is necessary for a grammar to implement Markov models of order 2 or more.
Development of the system is still in early stages, but already it is possible to see potential from the grammar-based approach. The use of stochastic grammars allows the compact representation Markov chains. The parallel rewriting technique of L-grammars has capabilities equal to, or better than, those of previous grammar-based methods. Parametric numerical parameters allow the control of non-discrete processes such as attack velocity or volume. Finally, hierarchical and context-sensitive grammars allow the simultaneous development of complex patterns at different levels within a composition.
In the introduction, it was emphasised that this is a computer-assisted composition system, where composer and machine work in a synergetic tandem. Currently, this tandem is little better than the way a programmer edits and debugs source code. Grammars must be written, compiled (removing syntax errors in the process) before music can be heard. Currently, work is being done to make the system much more interactive from a performance point of view. A composer will author a grammar and, within the grammar, place areas of discrete and continuous control that can be influenced by external processes or systems. One such example would be the recognition of hand gestures (gestures have both continuous and discrete information) in the spirit of the GROOVE system of Mathews and Moore [17]. In this way the composer can act as conductor, instantiating medium-term changes in the performance through gesture (discrete gestures cause rule changes) and also influencing the short term quality of the performance (continuous data from hand positions in space). Development of such a system is currently underway.
It is also possible to apply "genetic" processes to grammars; to interactively evolve better sounding compositions using a novel variation of the genetic algorithm. Evolution of grammars has already been done for computer graphics modelling [18]. Starting with a base grammar, a number of different mutated versions of the grammar can be represented as pictorial icons on the computer screen. By moving the mouse towards an icon, the contribution to the composition is increasingly biased towards the associated grammar. If the mouse is completely on the icon, only that grammar is heard. Once the user finds the best spacial position (and thus the best sounding composition), the selected grammars are "mated" and become the new parent grammar. The process is repeated for as long as the user wants, hopefully evolving the grammar into a better sounding composition.
While this technique sounds appealing, there is a limit to the number of mutations that can be displayed on the screen at any one time and also to the number of generations that can be critically evaluated by a human during any one sitting. We are still a long way from allowing the machine to exhibit creative judgement on its own.
Grammar-Based Music Composition
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html mccorm.
The translation was initiated by Pam Milliken on Tue Jan 21 16:37:36 EST 1997
