Proceedings SMC'07, 4th Sound and Music Computing Conference, 11-13 July 2007, Lefkada, Greece

A Grammatical Approach to
Automatic Improvisation
Robert M. Keller, David R. Morrison
Harvey Mudd College
Claremont, California, USA
[email protected], [email protected]

Abstract— We describe an approach to the automatic context-free grammar, as it occurs in computer science
generation of convincing jazz melodies using probabilistic and linguistics. Then we show how a grammar can be used
grammars. Uses of this approach include a software tool for to generate plausible rhythmic and melodic sequences for
assisting a soloist in the creation of a jazz solo over chord
progressions. The method also shows promise as a means of jazz. Playable examples will be presented that show the
automatically improvising complete solos in real-time. Our effectiveness of the approach. Our approach has been
approach has been implemented and demonstrated in a free implemented and has been tested in the past year as
software tool. part of a broader educational software tool, which proved
Keywords— jazz, improvisation, educational software, beneficial in a jazz improvisation course taught by the first
probabilistic context-free grammar, melody generator.
author and has also been used by various third parties.
I. I NTRODUCTION
Our group set out to develop a tool for assisting III. R ELATED W ORK
improvisors in creating jazz solos in the context of given
chord progressions (“changes” in jazz musicians’ parlance The motivation for our use of grammar was based
(JMP)). An initial approach involved creating a large primarily on implementation needs. It was only during
database of existing melodic fragments (“licks” in JMP) writing the final version of this paper that we became
from which the user could choose, to help create melodic aware of the many references that suggested using gram-
lines or fill gaps in these lines. One problem with this ap- mars in one form or another for various aspects of
proach is that there are many different chord progressions, music analysis and synthesis. Early work includes that
even when normalized to a given tonal center, which of Winograd [3], Lindblom and Sundberg [4], Longuet-
would thus require an extremely large database. Moreover, Higgins [5] and Roads [6], to name a few. Rader’s work
the database needed to be manually created, which was [7] used probabilistic grammars to generate traditional
very labor-intensive, albeit instructive to the creator. melodies. Hughes [8] surveyed the use of grammars for
An alternate approach that does not have the above non-western musics, and Bel and Kippen [9] used them
difficulties is to have the software dynamically generate for patterns in Indian drumming. Please see Roads and
novel licks. While this idea has great appeal, it is less Strawn [10], Cope [11], and McCormack [12] for more
than obvious how to make it work so that the results thorough surveys, the latter including use of L-systems
sound like convincing jazz solos. Choices of notes that and Markov chains. Recent work of Assayag and Dubnov
are largely random, even ones drawn entirely from the [13] demonstrate the use of factor oracles to generate
chords, tend not to sound good, especially rhythmically. improvised sequences.
Some additional structuring method is required to make Lerdahl and Jackendoff [14] used a generative gram-
the notes fit together in a manner that will be pleasing to mar theory for music analysis, which is referenced by
the ear. Horowitz [15] as an approach to jazz analysis. Steed-
We have developed an approach based on the idea man [16] described the use of a grammar for analyzing
of a formal grammar, augmented with certain pragmatic jazz chord progressions, but not melodies, and Johnson-
devices, which seems to be largely successful in achieving Laird [17] elaborated on this approach. Earlier work by
our objective of creating good-sounding melodic lines. Johnson-Laird [18] also suggests using regular grammars
The approach has been realized as a feature of a free soft- for explaining rhythmic sequences. Despite this large set
ware tool for assisting improvisors in the creation of better of references, we believe that the particular way in which
solos. The tool is called Impro-Visor (for “Improvisation we employ grammars and the meaning we assign to
Advisor”) and has been available on the world-wide web the terminal symbols has adequate elements of novelty.
since January 2006 [1]. A preliminary paper describing Because we use probabilistic grammars, we mention
our tool was presented in [2]. Temperley’s recent book [19], which describes wide uses
of probabilistic models for music analysis, including both
II. S TRUCTURE OF THE PAPER pitch and rhythm. The work of Ulrich [20] and, although
Having reviewed the background and motivation of it does not use grammars, Grachten [21] seem to share
our project, we will briefly review the concept of a some of the spirit of our own approach.

330
Proceedings SMC'07, 4th Sound and Music Computing Conference, 11-13 July 2007, Lefkada, Greece

manual construction is also a slow process. It would be

much better if we could automate the generation of these
segments, either on-line while the tool is being used, or
off-line, saving the segments in the vocabulary file in
which such segments currently reside.
On-line generation is somewhat risky. Unless one has
a very reliable algorithm for doing it, the results can be
poor and therefore misleading to the student. Of course
the ear can be used as the ultimate selection device, and
it is easy to backtrack to a different sequence, but the
beginner’s ear is often not sufficiently developed, so it
would be better to have every generated segment sound
good.
Historically, we intended to create a training corpus for
Fig. 1. Screen shot of Impro-Visor
machine learning research. We had originally constructed
a “lick triage” device as part of a software improvisation
assistant tool, from which we learned some things about
Work on jazz melody generation includes Biles’ Gen- the problem, as we now describe. The tool allowed one to
Jam [22] and the work of Papadopoulos and Wiggins specify (unordered) sets of preferred tones over two-chord
[23], both of which use genetic algorithms, thus re- sequences, although the idea could easily be extended
quiring a fitness function to perform genetic selection, to more chords. The preferred tones are essentially scale
and Thom’s BoB [24], which used a statistical learning tones and color tones, information that is already available
approach. Band-in-a-Box [25] is a commercial tool that in a vocabulary. Minimum and maximum duration for
will generate choruses without user interaction. Although notes were set by the user. When triggered by the user,
effective for non-interactive solo generation, its methods the tool generated a random sequence of pitches within
are proprietary, and appear to rely mostly on a pre- the realm of the parameter settings. The user could then
constructed database of melodic fragments. accept this sequence, or reject it and try another.
One surprise that resulted was that, when we simply
IV. B RIEF BACKGROUND ON JAZZ S OLOING avoided repeated notes and used a uniform duration
A jazz solo consists of a melody improvised over a of eighth-notes, most of the segments were acceptable
given chord progression. The progression usually consists jazz melodies, at a level above 90 percent. When the
of chords chosen to support the original melody of a song, duration was not uniform, say a mixture of eighth and
and is usually somewhat standardized, although chord quarter notes, the acceptance rate was not as high, but
substitutions and embellishments are often introduced. still encouraging. Some interesting syncopated melodies
Common practice would be for the group to play the were observed, consistent with the intended use for jazz.
original tune (called the “head” in JMP), then each soloist The acceptance rate deteriorated significantly when longer
would improvise some number of “choruses” over the licks were stipulated, and seemed to suggest that rhythmic
changes, then the group would typically play the head aspects are at least as important as pitch aspects when
a final time. characterizing acceptable jazz melodies. Being encour-
The challenge for the soloist is to have sufficient aged by the results from fairly simple technology, we set
creative ideas to be able to play one or more choruses. out to develop a better tool based on grammars, as next
Good preparation for this kind of creation entails knowing describe.
the melody and changes, as well as the harmonic under-
VI. F ORMAL G RAMMARS
pinnings of the changes.
Impro-Visor was designed to assist the soloist, who While a review of grammars might not be necessary
may not yet have a strong theory background, in the for the computer scientist or linguist (who can thus skip
process of creating solos. Our intention is to provide this this section), their use is less common in music, so we
as a practical end-user tool, not simply a research vehicle, briefly present the basic concepts here. There are several
so we have included niceties such as MIDI-playback for categories of grammar, but the type that are perhaps the
usability. Fig. 1 provides a screen-shot of Impro-Visor in most manageable while still serving our purpose are the
action. context-free grammars, so we restrict ourselves to this
family in the current exposition.
V. AUTOMATING M ELODY G ENERATION The purpose of a grammar is to generate sequences of
We would like our tool to provide a very large reper- symbols. In our case, the symbols will be interpreted as
toire of melodic segments. Our initial approach was to rhythmic values and tonal families of notes.
construct these manually or transcribe them from recorded A context-free grammar (CFG) consists of the follow-
sources. Manual construction is enjoyable, and turns ing components:
out to be as educational, if not more educational, than 1) The terminal alphabet is a set of symbols that
using the segments to construct complete solos. However, directly form the objective sequence. In our case,

331
Proceedings SMC'07, 4th Sound and Music Computing Conference, 11-13 July 2007, Lefkada, Greece

these symbols are a step away from being rendered • S → M → HH → hH → hh

as musical notes. • S → M → HH → hH → hqq
2) The auxiliary alphabet (also called non-terminal • S → M → HH → qqH → qqh
alphabet) is a set of symbols that serve to con- • S → M S → HHS → qqHS → qqhS →
struct sequences of terminal symbols, but are not qqhHH → qqhqqH → qqhqqqq
themselves terminal symbols. They are analogous To allow syncopation, we would need to add to the
to scaffolding in building construction. previous set productions that allow a half-note to straddle
3) The start symbol is a symbol in the non-terminal the mid-point of a measure and the bar lines, such as in:
alphabet that is used as the root in generating a
• S → HS
sequence.
• S → qS
4) Productions are rules that create new sequences
by replacing symbols in the old sequence with In this case, a much richer set of possible sequences
sequences of new symbols. is generated. In particular, every sequence of half and
quarter notes is generated by this grammar. Of course, we
Here is a simple example of a CFG outside of a musical
could use terminal symbols that represent rests as well as
context. It generates all strings of matched parentheses
notes.
1) terminal alphabet: { ’(’, ’)’ }, the set of parenthe-
The advantage of a grammar for representing rhythmic
ses.
sequences is that a well-constructed grammar can be
2) auxiliary alphabet: { S, T }, a set of two symbols.
used to avoid awkard rhythms, such as a sixteenth-note
3) start symbol: S
followed by a half-note followed by a sixteenth-note then
4) productions:
an eighth-note.
• S → ()
• S → (T ) VIII. P ROBABILISTIC G RAMMARS
• T →S
So far, a grammar is completely non-deterministic and
• T → TT
void of any sense of distribution of the types of sequences
Below are some sequences generated by the above
generated. By adding a probability to the application of
grammar. At each step, an auxiliary symbol in the pre-
a production, a semblance of style can be introduced. In
vious string that occurs on the left of a production is
other words, the degree to which a sequence is “main-
replaced with the sequence on the right of the same
stream” can be controlled. Specifically, sequences that are
production, leaving the other symbols unchanged. Only
stylistically on the fringe can be produced infrequently.
strings consisting entirely of terminal symbols are consid-
In our model, each production is given a weight, with
ered to be in the set of strings generated by the grammar.
the intention that when an auxiliary symbol is selected
• S → ()
for replacement, the choice of production is among all
• S → (T ) → (S) → (())
productions with that symbol on the left-hand side, with
• S → (T ) → (T T ) → (ST ) → (()T ) → (()S) →
productions having heavier weights being used more fre-
(()(T )) → (()(S)) → (()(())) quently. These weights are like probabilities, except that
they don’t have to sum to 1. For the user’s convenience,
and so on
the program normalizes the weights by dividing each by
VII. G RAMMARS FOR R HYTHMIC S EQUENCES the sum of the given weights for that particular left-
We use a grammar to generate coherent skeletal rhyth- hand side to get an actual probability that is used to
mic sequences, then fill those sequences with appropriate parameterize random selection.
notes. For example, suppose we just want to generate an As an example, if we wished to generate sequences
arbitrary number of measures of half notes and quarter that were only occasionally syncopated, we would desig-
notes, with no syncopation. A suitable grammar might nate lower weights for productions that tend to produce
be: syncopated rhythms.
• S →M
One further augmentation of the basic grammar idea is
• S → MS
used to control the length of the sequence generated: cer-
• M → HH
tain auxiliary symbols are accompanied by an argument
• H →h
giving the length of the sequence to be generated. This
• H → qq
argument may be used arithmetically in recursive rules,
as will be seen in the example shortly.
(In the Impro-Visor tool, the grammar is actually repre-
sented using S-expressions [26]. We present it here in IX. G ENERATING M ELODIC S EQUENCES
the form shown for greater readability.) Here the terminal
alphabet is { h, q }, representing half-notes and quarter- Once we have generated a rhythmic skeleton, we can
notes respectively. The auxiliary alphabet is { S, M, H } provide a tone for each note. In our framework, which
where S represents a sequence of one or more measures, mainly concentrates on jazz at this point in time, we have
M represents a measure, and H represents a half-measure. a classification of tones according to the operative chord:
Some example derivations are: 1) Chord tones: tones of the current chord.

332
Proceedings SMC'07, 4th Sound and Music Computing Conference, 11-13 July 2007, Lefkada, Greece

2) Color tones: complementary tones for the current Other possible constraints will be considered in the
chord. These are tones that are not in the chord, but future.
which are individually sonorous with it. They are
XI. A S AMPLE G RAMMAR
also often called “tensions” in JMP.
3) Approach tones: non-chord tones that make good Here is an example of a grammar that seems to be
transitions to chord-tones or color tones. very workable for contemporary jazz licks. It is the
4) Other: tones that do not fall into one of the cate- current default in our tool. As mentioned earlier, an
gories above. added advantage of using a grammar is that the user
These characterizations are similar to ones used by jazz can change it to suit, for example, to make the generated
players. The corresponding notes, in the context of chords, melodies simpler or more complicated. The terminals in
provide the tension-release aspect common to professional the grammar consist of the note class symbols followed
jazz solos. We use a distinct symbol for each of the first by a duration value. These representations are chosen to
three types of tones, and four additional terminals, as be natural for the musician, who can also use the same
follows: notation in other parts of the software tool, such as in
accompaniment style specifications. The duration values
1) C a chord tone.
are designated as follows:
2) L a color tone.
• 1 a whole-note
3) A an approach tone.
• 2 a half-note
4) H a “helpful” tone, defined to be any of one of the
• 4 a quarter-note
above.
• 4. a dotted quarter-note
5) S a scale tone, a member of a scale designated as
• 8 an eighth-note
being compatible with the chord.
• 16 a sixteenth-note
6) X an arbitrary tone.
• 4/3 a quarter-note triplet
7) R a rest.
• 8/3 an eighth-note triplet
Approach tones currently force the following tone to
• 16/3 a sixteenth-note triplet
be a chord tone, even if its designation is otherwise. The
definitions of chord, color, approach, and scale tones is For example A8/3 designates an approach tone with a
given on a per-chord basis in a separate vocabulary spec- duration of a eighth note triplet. Note that we did not
ification. All vocabulary information is user specifiable include dotted eighth-notes and sixteenth-notes, as they
as a text file of S-expressions [26]. The later provide a don’t occur frequently enough in jazz. A pair of eighth
readable way to communicate structure, in comparison to notes, however, is usually “swung”, that is articulated so
alternatives such as XML or proprietary formats. that the note on the beat is about 2/3 of a beat long,
For example, the grammar might generate a sequence and the following note about 1/3 of a beat long. This
(A8 L8 S8 C8 H4. S8). Based on the current chord, the swing ratio is implied from the ambient style, rather than
symbols would be replaced with actual pitches, to become being shown in the grammar explicitly. Hence the same
a note sequence, such as (f#+8 g+8 e+8 d+8 b4. g8), grammar works well for both swing tunes and for latin
representing the notes shown in the first staff of Fig. 2 tunes, where the eighth notes are more nearly equal. If
(Note: All staves in this paper are treble clef.). Here 8 ordinary dotting is desired, a dot after a terminal symbol
refers to eighth-note duration, 4. means a dotted quarter- denotes lengthening the normal value by 1/2.
The terminal set of the example grammar, where each
note duration, and + means to raise the pitch one octave
item separated by commas counts as a single symbol, is:
from its default position, the octave just above middle
C. Although the second note class in the sequence is X2, X4, X4., X8, X16, X4/3, X8/3,
specified as a color tone, this is actually over-ridden to H2, H4, H4., H8, H16, H4/3, H8/3,
be a chord tone, due to the previous note class being an A4, A8, A16, A8/3, C2, C4, C8,
approach tone. (This is the current operative convention, L4, L8, R4, R8, S4, S8
but it could be changed.) The following section elaborates Auxiliary symbos, such as P below, can be endowed
on the overall process. with parameters, to permit generation of melodies to fit a
certain number of beats. A parameter of N beats on the
X. A DDITIONAL C ONSTRAINTS left-hand side of a production is sub-divided using arith-
We allow the user to apply additional constraints to metic on the right-hand side to enable a coarse skeletal
increase the likelihood that the pitch sequence is melodic. layout, which is further refined with other productions.
Although this information could be provided with an The first group of productions below are parameterized.
extension of the current grammar notation, this is left for With P (N ) as the start symbol, where N is an argument
future exploration. The specific controllable constraints indicating the length of the overall sequence in beats,
are as follows: the productions, with their assigned weights in square
1) Minimum and maximum pitch values. brackets, are (where the Q′ s are auxiliary symbols that
2) Minimum and maximum interval between pitches. expand into a sequence occupying the indicated number
3) A probability of using an interval outside the above of beats):
specification, i.e. for a “leap”. 1) P (0) → empty [ 1 ]

333
Proceedings SMC'07, 4th Sound and Music Computing Conference, 11-13 July 2007, Lefkada, Greece

2) P (1) → Q1 [1]
3) P (2) → Q2 [1]
4) P (3) → Q2 Q1 [ 1 ]
5) P (n) → Q2 P (n − 2) [ .25 ]
6) P (n) → Q4 P (n − 4) [ .75 ]
An example initial derivation sequence might be

P (8) → Q4 P (4) → Q4 Q2 P (2) → Q4 Q2 Q2

This sequence of auxiliary symbols would then be refined,

using productions chosen probabilistically from the fol-
lowing set, where the probabilities have been derived em-
pirically by adjusting them based on generated melodies.
Such adjustments may also be done by the end user Fig. 2. Licks over CM9 in the pattern (A8 L8 S8 C8 H4. S8)
for customization purposes. The remaining productions
follow:
1) Q4 → Q2 V 4 V 4 [ 0.52 ]
2) Q4 → V 8 N 4 N 4 N 4 V 8 [ 0.01 ]
3) Q4 → V 4 Q2 V 4 [ 0.47 ]
4) Q2 → N 2 [ 0.06 ]
5) Q2 → V 4 V 4 [ 0.6 ]
6) Q2 → V 8 N 4 V 8 [ 0.12 ]
7) Q2 → H4. N 8 [ 0.16 ]
8) Q2 → H4/3 H4/3 H4/3 [ 0.06 ]
9) Q1 → C4 [ 1 ]
10) V 4 → N 4 [ 0.22 ]
11) V 4 → V 8 V 8 [ 0.72 ]
12) V 4 → H8/3 H8/3 H8/3 [ 0.05 ]
13) V 4 → H8/3 H8/3 A8/3 [ 0.01 ]
14) V 8 → N 8 [ 0.99 ]
15) V 8 → H16 A16 [ 0.01 ] Fig. 3. Licks over C13b9 in the pattern (R8 S4 C8 S8 S8 L8 R8)
16) N 2 → C2 [ 1 ]
17) N 4 → C4 [ 0.5 ]
18) N 4 → L4 [ 0.2 ] Fig. 2 shows three example generated licks over this
19) N 4 → S4 [ 0.5 ] chord. Our textual chord notation, also used in other
20) N 4 → A4 [ 0.01 ] aspects of our software for ease in user interaction, uses
21) N 4 → R4 [ 0.25 ] M to abbreviate major, m to abbreviate minor, and the
22) N 8 → C8 [ 0.4 ] symbols b and # to represent musical flats and sharps,
23) N 8 → L8 [ 0.2 ] respectively.
24) N 8 → S8 [ 0.4 ] The next example is also over a single dominant chord,
25) N 8 → A8 [ 0.01 ] a C13b9. The generated terminal sequence is:
26) N 8 → R8 [ 0.1 ]
R8 S4 C8 S8 S8 L8 R8
XII. S AMPLE M ELODIC S EQUENCES
In this section, we demonstrate some of the sequences However, the licks generated are quite different from
that are generated by the preceding grammar over selected the previous due to the chord and scale tones being
chords. We show both the terminal sequence of symbols interpreted over different types of chords. Fig. 3 shows
as well as melodic sequences. Note that for a given three generated licks. Here b9 (D flat) is a chord tone, #9
terminal sequence, there will generally be many distinct (D sharp) has been designated as a scale tone, and #11 (F
melodic sequences. The user can explore the latter while sharp) is a color tone. The melodic notation for the third
leaving the terminal sequence intact if desired. lick would be
The first example is over a single major chord, a C
r8 c + 4 db + 8 bb8 e8 f #8 r8
major 9. A terminal sequence generated by the grammar
is:
in our tool. The stave display and play-back can be
A8 L8 S8 C8 H4. S8 generated automatically from this notation.
which designates a sequence of tones as Now let’s try a two-chord sequence typical of modern
jazz: a D minor 9 followed by a Db9#11, the latter rep-
approach, color, scale, helpf ul, scale resenting a “tritone substitution” in JMP. The generated

334
Proceedings SMC'07, 4th Sound and Music Computing Conference, 11-13 July 2007, Lefkada, Greece

Fig. 4. Licks over Dm9 Db9#11 in the pattern (C8 C4 S8 C8 S8 R8)

Fig. 6. Lick Generator Control Panel

chord and scale parameters that are part of the standard

vocabulary specification. The casual user simply presses a
button in the main window to generate melodies, without
necessitating opening this panel. Other buttons in the
panel allow us to assign a grade to licks and save
them. The corpus of saved licks will be used to train a
computational filter, such as a neural network or support
vector machine, so that only licks satisfying subjective
Fig. 5. Licks over CM9 Eb9 AbM9 Db9#11 standards of a user will pass. We intend to incorporate
such filtering into a future version of the tool.
terminal sequence is:
XIV. I MPLEMENTATION
C8 C4 S8 C4 S8 R8
Fig. 4 shows three generated licks corresponding to this Impro-Visor is implemented entirely in Java, version
terminal sequence. 1.5. S-expression input and output for vocabulary el-
To show the capabilities of our approach in connecting ements is handled using the Polya library [27] which
melodies, we present melodies generated for a four- provides Lisp-like functionality [26] in Java. Some of the
chord sequence, the famous “Tadd Dameron turnaround”, musical representation aspects were constructed using a
giving three different generated sequences, with respective modified version of jMusic [28]. GUI development was
melodic possibilities in Fig. 5. done using NetBeans [29].
Finally we show how an entire chorus can be generated
at one time by a single grammatic derivation, in this case XV. E VALUATION
for the chord changes to John Coltrane’s Giant Steps, is
shown in Fig. 7. Solos of this type take about one second Currently evaluation is mostly subjective. As a moon-
to generate. lighting instructor of jazz improvisation, the first au-
thor assesses that the grammar-based approach generates
XIII. L ICK G ENERATOR C ONTROL PANEL melodies that compare favorably with those played by
Fig. 6 shows the lick generator control panel in Impro- college-level jazz students of at least an intermediate
Visor. The terminal string generated by the grammar playing level, if not better. The reader is invited to listen to
appears in the upper left text area. It may be used to examples played automatically on the website [1], which
generate an arbitrary number of melody sequences by include both human-composed and machine-composed
replacing the terminals with notes, or the user can press improvisations, and is encouraged to download Impro-
a button to regenerate the terminal sequence. Although Visor and try it for him/herself. Because the grammar is
it is possible for the user to customize many of the user-modifiable, there is plenty of opportunity to try to
parameters, and even adjust the grammar output to suit, in modify the grammar to generate melodies to individual
typical operation, this panel is set automatically based on taste.

335
Proceedings SMC'07, 4th Sound and Music Computing Conference, 11-13 July 2007, Lefkada, Greece

XVI. F UTURE W ORK R EFERENCES

We plan to explore further other types of terminals in [1] Impro-Visor, http://www.cs.hmc.edu/˜keller/jazz/improvisor.
the grammar, such as one that specify particular forms [2] Robert Keller, Stephen Jones, David Morrison, Belinda Thom, and
Aaron Wolin, “A computational framework enhancing jazz cre-
of scalar sequences, including, but not limited to, chro- ativity”, CDROM Proceedings, Third Workshop on Computational
matic approach sequences and other common jazz idioms. Creativity, ECAI 2006, Riva del Garda, Italy.
In addition to the generation of melodies, Impro-Visor [3] Terry Winograd, “Linguistics and computer analysis of tonal
harmony”, Journal of Music Theory, volume 12, pp. 2-49, 1968.
generates accompaniment in the form of percussion, bass [4] B. Lindblom and J. Sundberg, “Towards a generative theory of
line, and chordal comping. All of these are specified melody”, Swedish Journal of Musicology, volume 52, pp. 77-88,
in a style language similar to the one used to express 1970.
[5] H.C. Longuet-Higgins, “The Grammar of Music”, Interdisci-
melodic sequences. We intend to describe the algorithms plinary Science Reviews, volume 3, no. 2, pp 128-156, 1978
for generating accompaniment from style specifications in (reprinted in Longuet-Higgins, Mental Processes, MIT Press,
a future paper. 1987).
[6] Curtis Roads, “Grammars as Representations for Music”, Com-
Work is also in progress to construct critic filters for puter Music Journal, volume 3, no. 1, 1979, pp. 48-55.
licks based on machine learning. This would be done [7] Gary M. Rader, “A Method for Composing Simple Traditional
by attaching grades to a large number of licks generated Music by Computer”, Comm. ACM, volume 17, no. 11, pp. 631-
638.
by the lick generator, which are then saved as a training [8] David W. Hughes, “Grammars of Non-Western Musics: A Selec-
corpus. Once trained, the filter can be imposed to improve tive Survey”, in Peter Howell, et al., ed., Representing Musical
even further the quality of generated licks, rejecting ones Structure, pp 327-362, Academic Press, 1991.
[9] Bernard Bel and Jim Kippen, “Modelling music with grammars:
that are below a specified level and regenerating in such formal language representation in the Bol Processor”, in Alan
a case. Another possible line of work envisioned is to Marsden and Anthony Pople eds., Computer Representations and
use machine learning to learn grammars from a corpus, Models in Music, pp 207-238, Academic Press, 1992.
[10] Curtis Roads and John Strawn, eds., Foundations of Computer
including possibly separate grammars for different player Music, MIT Press, 1985.
styles. [11] David Cope, Computers and Musical Style”, A-R Editions, Inc.,
Madison, WI, 1991.
XVII. C ONCLUSION [12] Jon McCormack, “Grammar-Based Music Composition”, Com-
plexity International, volume 3, (http://www.complexity.org.au/
We have described the use of probabilistic context- ci/vol03/mccorm/mccorm.html), 1996.
free grammars for generating convincing jazz sequences. [13] Grard Assayag and Shlomo Dubnov, “Using Factor Oracles for
Machine Improvisation”, Soft Computing, volume 8, no. 9, pp 604-
Although the use of grammars has been suggested be 610, 2004.
many others, we believe that the key idea that makes our [14] F. Lerdahl amd R. Jackendof, A Generative Theory of Tonal Music,
approach work well is the interpretation of the terminal MIT Press, Cambridge, Mass., 1983.
[15] Damon Horowitz., “Representing Musical Knowledge in a Jazz
symbols as chord tones, color tones, approach tones, Improvisation System”, In Proceedings of Artificial Intelligence
etc. This provides the linkage between pitch classes and and Music, IJCAI workshop, pp 16-23, August, 1995.
chords without requiring the grammar to be too specific [16] M.J. Steedman,“A generative grammar for jazz chord sequences”,
Music Perception, voume 2, no. 1, pp. 52–77, 1984.
as to pitches. [17] P.N. Johnson-Laird, “How Jazz Musicians Improvise”, Music
The original intended use of this approach is in an Perception, volume 19, no. 3, pp 415-442, 2002.
instructive tool for suggesting melodic ideas to impro- [18] P.N. Johnson-Laird, “Jazz Improvisation: A Theory at the Compu-
tational Level”, in Peter Howell, et al., eds., Representing Musical
visers. An advantage of the grammar approach in this Structure, Academic Press, 1991.
context is that the user of a software tool based on [19] David Temperley, Music and Probability, MIT Press, Cambridge,
grammar can change the grammar to suit. For example, Mass., 2007.
[20] John Wade Ulrich, “The analysis and synthesis of jazz by com-
a simple grammar can be used for beginners while a puter”, Proceedings 5th IJCAI, pp 865-872, 1977.
more sophisticated grammar can be used for advanced [21] Maarten Grachten, “JIG: Jazz Improvisation Generator”, Workshop
players and ones who are more technically accomplished. on Current Research Directions in Computer Music, pp 1-6,
Audiovisual Institute-UPF, 2001.
Although not the original intent, our approach could also [22] J. A. Biles, “GenJam: a genetic algorithm for generating jazz
be the basis of a real-time improvising companion, since solos”, Proceedings of the 1994 International Computer Music
in its current state, our tool will generate entire choruses Conference, Aarhus, Denmark, pp. 131–137.
[23] George Papadopoulos and Geraint Wiggins, “A genetic algorithm
in one second or less, but even with slower processing, for the generation of jazz melodies”, Proceedings of STeP 98,
the processing could, in principle, be overlapped with Jyvskyl, Finland, 1998.
playback in a separate thread. [24] Belinda Thom, “BoB: an interactive improvisational music com-
panion”, Proceedings of the Fourth International Conference on
ACKNOWLEDGMENT Autonomous Agents, ACM Press, Barcelona, Catalonia, Spain, pp.
309–316, 2000.
This work was supported by a Faculty Enhancement [25] PG Music, Band in a Box, http://www.band-in-a-box.com.
grant from the Mellon Foundation and by the National [26] John McCarthy, “Recursive functions of symbolic expressions and
their computation by machine”, Comm, ACM, volume 3, no. 1, pp
Science Foundation REU Program under grant Award 184-195, 1960.
No. 0451293 to Harvey Mudd College. We wish to [27] Robert Keller, Polya Java library, http://www.cs.hmc.edu/
thank Stephen Jones, Martin Hunt, and Steve Gomez for keller/polya/.
[28] Andrew Sorensen and Andrew Brown, jMusic Java library,
contributing to other aspects of our project that have help http://jmusic.ci.qut.edu.au/.
amplify the usefulness of our work. [29] NetBeans, http://www.netbeans.org/.

336
Proceedings SMC'07, 4th Sound and Music Computing Conference, 11-13 July 2007, Lefkada, Greece

Fig. 7. Typical choruses generated on John Coltrane’s Giant Steps

337