ï~~
AN EXPERT SYSTEM
FOR HARMONIZING FOUR-PART CHORALES'
Kemal Ebcioglu
IBM, Thomas J. Watson Research Center
P.O. Box 218
Yorktown Heights, NY 10598, U.S.A.
Abstract
We describe a rule-based expert system called CHORAL. that attempts to
harmonize four-part chorales in the style of J.S. Bach. The system contains
about 3(1K rules, expressed in first order predicate calculus, and harmonizes
chorales using a generate-and-test method with intelligent backtracking. A
substantial number of heuristics are used for biasing the search toward musical
solutions. Encouraging results have been obtained.
Introduction
In this paper. we will report on a rule-based expert system called CHORAL, for
harmonization and Schenkerian analysis of chorales in the style of Johann
Sebastian Bach. We will first briefly compare our approach with some current
trends in algorithmic composition and music analysis, and we then will describe
the CIORAL system itself.
Overview of current approaches to algorithmic music
Quite a few trends in algorithmic composition today are based on a streamlined
formalism, for example, in the form of random generation of note attributes
using elegant statistical distributions I Xenakis 711. terse and powerful formal
grammars IJones 11. elegant mathematical models IKendall 81. Vaggione 841.
or generalizations of serial composition procedures (Laske 811. The economy
and elegance of the formal representation underlying these musical styles
(which are not in the least less respectable than traditional styles of music), may
often have an aesthetic appeal in and of themselves. On the other hand. traditional music, and most of modern music, which are usually composed without
a computer, do not seem to permit such economical representations. In the
traditional style, the typical basic training the composer has to go through in
harmony, strict counterpoint. fugue, and orchestration, already imposes a certain minimal complexity on the amount of knowledge required to describe such
a style. Also, many will agree that a similar complexity can be observed in the
works of modern "non-computer" composers like Karlheinz Stockhausen.
Pierre Boulez. Gyorgi Ligeti, Jan Rychlik, and Steve Reich (his later compositions). It seems that musical composition is a hard mental task that requires a
substantial amount of knowledge, and any serious attempt to simulate "noncomputer" music composition on the computer would have to face the. task of
constructing a formal model of considerable complexity. In fact. we have found
that even the algorithmic representation of the knowledge underlying the
seemingly simple Bach chorale style is a task that already borders the
intractable.2
As for the music analysis field, the prevailing trends seem to emphasize selective
and unobvious properties of music; for example, a golden section in sone
motels of Dufay ISandreski 8 11. or a surprising log-normal distribution in the
dissonances within some chortles of Bach I Knopoff and Hutchinson 811. Even
the analysis approaches that capture a profound structure in tonal music, such
as reduction techniqucs ISchenker 79, Lcrdahl and Jackendoff 831. are still
based on finding selective properties. These propertics, although interesting in
their own right, do not constitute a satisfactory explanation of the music in
question, in the sense that there exist many "pieces" that have these properties
but that have no relationship with the style. An alternative approach that would
perhaps provide a more satisfactory understanding of the music, is to attempt
to algorithmically generate pieces in the same approximate style. There have
already been some attempts at this analysis by synthesis approach to music in
some simpler traditional styles, such as folk melodies IZaripov 601. or the first
two phrases of Bach chorale melodies [Baroni and Jacoboni 761. But there are
two problems associated with extending this approach to more substantial traditional styles: First, it may be difficult to prevent the designer of such a resynthesis algorithm from introducing traits that would distort the style in an
unscholarly fashion (this uncholarliness may be trivially rcmoved by resynthesizing only thc original pieces of the composer - but we feel that the approach
of synthesizing new pieces is also interesting). The second, and more fundamental problem is that, although there has been good progress in the automated
synthesis of sound (Mathews et al. 69. Roads and Strawn 851. the automated
composition of non-trivial tonal music is to date not sufficiently understood
(and is still rcgarded with some suspicion in the traditional circles). The present
research is an attempt to further our understanding of the mechanical generation of music, by extending the analysis by synthesis approach to a more
complex style. the style of the Bach chorale harmonizations. To cope with the
complexity of the problem. we have developed a rule-based approach inspired
from recent research in artificial intelligence, which we will describe below.
BSL: an efficient logic programming language
Perhaps because of its inherent difficulty, the generation of non-trivial tonal
music appears to require large computational resources. In typical computing
cnvironments. A.I. languages such as Prolog or Lisp tend to be too slow for
implementing our particular approach to the algorithmic gcneration of music.
At the outset of our rcsearch, we decided to represent musical knowledge using
first-order predicate calculus, and we have designed BSL IEbcioglu M6a, 86b,
an efficient logic programming language which is fundamentally different from
Prolog. From the execution viewpoint, BSL is a non-deterministic Algol-class
language where variables cannot be assigned more than once except in controlled contexts. However. BSL has a desirable relationship with first-order
predicate calculus that makes it a new kind of logic programming language.* A
formal and rigorous description of BSL. in a style inspired from (de Bakker 791,
and a proof of BSL's soundness can be found in IEbciotlu 86a(. To implement
BSL on real computers, we wrote a compiler, in Lisp, that translates BSL programs into efficient backtracking programs in C. On the simple integer computations for which it is intended. BSL tends to be about 4-5 times faster than
compiled Lisp on traditional architectures like the IBM 3090 or the VAX
1 /780. assuming that all available optimizations are applied to the Lisp program, such as fixed arithmetic.
A knowledge representation technique for music
To represent substantial amounts of musical knowledge in logic. it appears
necessary to divide op the assertions into groups that observe the music from
multiple viewpoints. The idea of using a small, nonredundant set of primitive
functions and predicates to represent the music, although mathematically appealing. does not seem to be suitable for expressing all the viewpoints in a natural way. For example. a set of primitives that observes each voice as a linear
string of notes, is good for expressing voice leading rules, but is somewhat unnatural for expressing harmonic relationships between voices. Similarly. a large
scale work may require several hierarchical viewpoints that may constitute successively refined plans of the piece. So we opted for a representation that uses
multiple sets of logical primitives to represent the different viewpoints of the
music. The need for using multiple viewpoints of the solution object has arisen
in expert systems in other domains as well: For example, the Hearsay-Il speech
understanding system (Erman et al. 801 observed the input utterance as mutually consistent streams of syllables. words, and word sequences, and the "Constraints" system of ISussman and Steele 801 used equivalent circuits for
This research was supported by NSF grant MCS-5316665. and the major portion of it was done at the Department of Computer Science. S.U.N.Y. at Buffalo. under the direction of
my advisor Prof. John Myhill.
Note that we are not referring to four-part harmonization in the context of an elementary school exercise here. When harmooiations are to encompass style specific idioms such as
hold clashes of simultaneous inessential notes, without which they would he devoid of interest, the underlying knowledge tends to become greatly complicated. Traditional studies on
Iach IMcI lose 47, Koechlin 221 have avoided the complexity of inessential notes by proceeding by examples rather than precise rules.
The setnantics of a (ISL program F is defined via a ternary relation '. such that (F. n, al means program F k'ads to final state n' when started in initial state e. where a state is a
mapping from variable names to elements of a "computer" universe, consisting of integers, arrays, records.... There is a simple mapping that translates a BSL program to a formula
of a first order language, such that if a SLI program terminates in some state a, then the eorresponding first order formula is true ina (where the truth of a formula in a given state o
is evaluated in a fixed "computer" interpretation involving integers, arrays, records, and operations on these. after replacing any free variables a in the formula by (x). Thus, successful ecuetion of a 51. psigram without free variables amounts to a proof of the corresponding first order sentence.
447
ICMC 86 Proceedings
