Towards a Practical Tool for Music Composition: Using Constraint Programming to Model Chord Progressions and Modulations

1 Introduction

Constraint Programming (CP) is a popular technique for generation [Pachet and Roy, 2011; Papadopoulos et al., 2015; Bonlarron and R´egin, 2024]. Music generation with CP is popular as well, in particular for harmonisation. It is sometimes added to some form of learning [Lattner et al., 2018; Giuliani et al., 2023] to provide more user control as well as a better global structure. However, learning is limited by the training data. An alternative approach is to formalise music theory and rely solely on CP [Huang and Chew, 2005;

Anders, 2008; Anders and Miranda, 2009; Carpentier et al., 2010; Davismoon and Eccles, 2010]. This alternative has multiple advantages. First, there is no limitation based on training data. Second, it ensures that the rules are satisfied in every generated solution. Third, it makes the solutions easier to tweak, giving more control to composers. However, there are two disadvantages. First, it requires a substantial set of rules to make the generated solutions usable, and second, finding solutions often requires significant computation at runtime. Previous work using CP to create composer tools falls into two categories: Tools formalising one specific aspect of music theory [Ebcio˘glu, 1990; Truchet et al., 2003; Herremans and S¨orensen, 2013], that lack generality, and tools that can model large amounts of music theory [Anders et al., 2005; Laurson and Kuuskankare, 2005; Sandred, 2010] but require programming to be used, therefore limiting their usability for composers. In contrast, we propose an approach that completely models a musical style without requiring programming skills to be usable. Aside from CP and ML, two other approaches are generative grammars [Rohrmeier, 2011] and conceptual blending [Eppe et al., 2015]. Chordblending generates new progressions from existing ones, and it could potentially be combined with our approach to obtain more complex modulations. Generative grammars are used to understand the recursive structure of tonal harmony. Compared to these two approaches, constraint programming allows composers to add arbitrary musical ideas to a musical theory such as tonal harmony, and find coherent solutions (see Section 4.2 for a concrete example).

1.1 Harmoniser Project

The Harmoniser project aims to build a practical tool to aid composers based on CP that addresses both the issues of rule definition and computation time. The rules are inferred from treatises on music theory (see Section 3). Because the solver enforces rules, this relieves the composer of much tedious work so they can focus on adding musical ideas to shape solutions into a desired result. To reduce computational complexity, we follow the decomposition of the composition process that was introduced in [Sprockeels and Van Roy, 2024], following [Pachet and Roy, 2001] which concludes that proper structuring is necessary to make constrained musical composition feasible. It decomposes the process of musical composition in four layers, resulting in smaller problems that can be solved independently (see Section 2). The first layer is global harmonic structure, the second is chord progressions and modulations, the third is chord voicing, and the fourth adds ornaments. The present paper focuses on the second layer. The third layer was published in [Sprockeels and Van Roy, 2024] and defines the Diatony model.

1.2 Contributions

The present paper has two main contributions. First, a formal model of the second layer of the composition process, namely chord progressions in a tonality and modulations to neighbouring tonalities. This model gives freedom to express musical ideas while guaranteeing that tonal music rules are respected. Second, a constraint implementation in the Gecode constraint solver [Gecode Team, 2019]. The generated output can be given to Diatony to generate a voicing for the solutions. The solution space contains all possible tonal chord progressions with the given parameters, and composers express musical ideas by giving desired tonalities and modulations as well as adding constraints. This prunes the search space and eventually gives a desired musical solution.

1.3 Structure of the Paper

Section 2 gives the four-layer framework for music composition, which refines the framework of [Sprockeels and Van Roy, 2024]. Section 3 defines the formal model of tonal progressions and modulations. Section 4 evaluates the model showing its intended use by a composer. Section 5 concludes this paper and outlines future work.

2 Harmoniser Project

There are probably as many ways to compose music as there are composers. In a practical tool, it is nonetheless important to give a predefined structure to guide composers. In [Sprockeels and Van Roy, 2024], an iterative process with four layers that are general enough to be relevant for a significant portion of composers was identified, and is refined in this paper. Figure 1 illustrates this structure. This paper focuses on the second layer, namely chord progressions and modulations. To put this in context, we explain all the layers.

Global structure. The first layer decomposes the piece into progressions, each in a single tonality, connected by modulations. It can happen that there is only one tonality for the whole piece, and hence no modulations, but in the general case, there are multiple tonalities with one modulation between every two successive progressions. The same tonality can be present more than once in the whole piece.

Progressions and modulations. The second layer realises the harmonic development within each progression. It defines a sequence of chord degrees for each of the progressions, as well as modulations to transition from one progression to the next. Chord degrees can be diatonic (belonging to the tonality) or chromatic (not belonging to the tonality). Section 3 gives the main aspects of the formal model for this layer.

Voicing. The third layer defines the voicing, i.e., the actual notes on the musical staff for each chord. The typical way to represent chord voicing is to use four voices. There are two aspects to take into account: "vertical" harmony, i.e. the interaction between notes in a given chord, and "horizontal" harmony, the interaction between notes in a voice over time. Some voicing rules have an influence on chord states, in which case they are also handled in layer 2 and thus in the model of this paper. They are presented in Section 3. Layer 3 is presented in Diatony [Sprockeels and Van Roy, 2024].

Ornaments. The fourth and final layer is melodic ornaments. Given a voicing for a chord progression, ornaments such as passing notes or appoggiaturas are added as details to enrich the musical piece. This adds essential complexity to the harmony.

3 Formal Model of Tonal Chord Progressions

We now define the formal model of tonal chord progressions and modulations, which is the second layer of the Harmoniser project and the main focus of this paper. Here, a progression is a sequence of chord degrees in a given tonality and a modulation is a transition between two successive progressions of different tonalities. The model defines the possible chords (degree, quality and state) and transitions between them following the theory of Western tonal music, which is based on the concept of tonality 1 . All the concepts used in the model are standard concepts of tonal music theory, for which many references exist 2 .

The rules implemented in the model are taken from [Duha, 2016] and [Gauldin, 2004], ensuring consistency with Diatony [Sprockeels and Van Roy, 2024] that uses the same references. We use Duha's chapter on modulations as well as Gauldin's chapters 4 (triads and seventh chords), 6 (partwriting), 8-11 (diatonic harmony), 13 (dominant chords), 14 (predominant chords), 16 (6-4 chord), 17 (third and sixth degree), 19 (leading tone seventh chord), 21 (secondary dominant chords), 29 (Neapolitan chord), and 30 (augmented sixth chord). This model was established in collaboration with two composers to ensure its correctness and utility for composers.

3.1 Basic Concepts of the Model

The formalisation builds on the concepts of chord and chord transition:

• A chord is a set of three or more notes, uniquely identified by a triple (r, q, s) where r is the root note (one of the twelve notes of Western music), q is the quality (which defines the intervals between the chord notes), and s is the state (defined by the chord note that is at the

1 A tonality is defined as a pair of a key (one of the twelve notes C, C#, D, up to B) and a mode (major or minor).

2 Some links: tonality, chords and functions, secondary dominants and augmented sixth chords, amongst many others.

lowest voice). Within a given tonality, each note has a degree d that defines its function within the tonality as well as the possible qualities and states that are available to build chords on that note as a root.

• A chord transition is a pair of two chords. In Western tonal music, chord transitions are defined by degree transitions in a tonality.

Our formal model is built on top of these two concepts. The constant transition matrix T defines possible chord transitions between two chord degrees in a tonality, while three other constant matrices M, P, and L define the relationships between a chord degree and the possible chord qualities, states, and root notes respectively. These matrices compactly encode a large amount of tonal music theory, which to our knowledge has not been done by any previous composer tool. Aside from these matrices, constraints are enforced to model more specific aspects of tonal music theory that are not captured by the matrices. Additional constraints are also enforced to allow for modulations between tonalities, which is a key aspect of Western tonal music.

3.2 Composer Input and Solver Output

For chord progressions to be generated, the model requires a series of parameters. These can come from the first layer of the Harmoniser project or from the composer. First, the total number of chords of the musical piece (n) and the number of progressions (l) must be specified. The progressions' beginning (bi) and end (ei) are deduced from the modulations, except for the start of the first progression and the end of the last one, and are known from the start. This is developed in Section 3.4.

The tonality of each progression (ti), in the form of a tuple (key, mode), must also be provided.

where k ∈ {C, C♯, D, ..., B} and m ∈ {major, minor}. Different progressions can have the same tonality, but not successively. Additionally, modulation types 3 (typem), starts (sm) and ends (fm) must also be specified. Together, they will determine the length of each progression.

where m represents a modulation, and is linked to the progression from which it modulates (modulation m goes from progression m to progression m + 1).

Provided these parameters, the model gives the chords of the piece. In tonal music, chords are referred to by their degree, i.e. their role in the tonality. However, degrees are tonality specific, and the different progressions must be able to communicate because in the case of modulations, some chords must be constrained by two progressions. This is done using the triplet (root note, quality, state) that uniquely identifies a chord. The model therefore defines three variable arrays for the whole piece R, Q and S that represent each chord's root note, quality and state, as well as an array for the chord degrees in each progression Di. Additionally, each progression has a subset of the whole piece variable arrays (Ri,Qi, Si) that correspond to their part in the piece. These arrays are defined below.

3 Modulation types are detailed in Section 3.4.

Chord roots. The root of a chord is the note on which the chord is built. It is one of the twelve notes (and their enharmonics) of Western music:

where c denotes each chord of the progression.

Chord qualities. Chord qualities define the intervals of the chord notes with the root of the chord:

Chord states. Chord states define the note of the chord that is at the bass, i.e. the lowest note of the chord:

Chord degrees. The supported chord degrees consist of the seven diatonic chord degrees, as well as some common chromatic chords.

3.3 Progression Constraints

In this section and the next we present the most important constraints of the model. We distinguish two categories of constraints: constraints that apply to progressions, i.e. constraints in a given tonality, and constraints that apply to modulations, i.e. between two tonalities. The progression constraints ensure that chord progressions in a tonality follow the rules of tonal harmony, while modulation constraints ensure a smooth transition between the progressions. Due to space limitations, the matrices M, P and L are presented in the technical appendix 4 . In the following definitions, musical notations have been used to present the model more intuitively. In practice, numerical values are used.

4 http://hdl.handle.net/2078.1/301819

Chord transitions. The most important constraint describes the possible transitions for chord degrees in a tonality. This is enforced through the T matrix and shown in table 1. It is read as: chord row can be followed by chord column if the value in the matrix is equal to 1. For example, the III chord can be followed by the VI and V/VI, but not any other degree. The T matrix encodes generally accepted rules for tonal harmony, taken from [Duha, 2016] and [Gauldin, 2004]. Each block of the matrix constrains a specific aspect of tonal chord progressions:

• Block A (orange) defines possible chord succession between diatonic chords 5 .
• Block B (dark blue) defines what secondary dominant 6 chords can follow diatonic chords.
• Block C (yellow) defines what chromatic chords, amongst the ones supported, can follow diatonic chords.
• Blocks D (green) and E (cyan) define what diatonic chords and other secondary dominants can follow secondary dominants, respectively. Secondary dominants must move to a chord that is based on the note that is a perfect fifth below their root note. They can either resolve to their corresponding diatonic chord (e.g. II for V/II), or move to another dominant chord based on that same note (e.g. V/V for V/II).
• Block F (grey) enforces the rules for chromatic chords following secondary dominant chords. It is not allowed, so this part of the matrix is empty.
• Blocks G (violet) and H (magenta) enforce the rules for chromatic chords. The lowered second degree (♭II) and the augmented sixth (6△) must go to V, but they can go to the fifth degree appoggiatura (Vda) before that.
• Block I (red) enforces rules for the succession of chromatic chords. It is not allowed, thus this part of the matrix is empty.

T can be seen as an adjacency matrix, thus T k counts possible chord progressions of k chords in a tonality, which are valid walks through the equivalent graph. Table 2 shows the graph corresponding to the adjacency matrix, separated into the diatonic part (2a) and the chromatic part (2b) for readability. Bold arrows mean that a transition is the preferred choice, regular arrows mean a possible alternative, and dotted arrows mean that a transition is possible but rarely used. Possible transitions through chromatic chords in the diatonic part are annotated on the transition arrow to make the diagram more readable. Since these are nodes, they can be used to hop to the chromatic part and back. The constraint enforced is:

5 The fifth degree double appoggiatura (Vda) is treated separately because its musical function is completely different.

6 A secondary dominant is the dominant of a diatonic degree.

where i represents each progression and c′i represents each chord of the progression except the last one, and T is the matrix in Figure 1. This is not implemented with the regular constraint [Pesant, 2004] because using a matrix makes it easy for composers to modify the possible transitions without requiring to recompute the whole underlying DFA of a regular constraint. As explained in Section 4, this does not cause efficiency problems but can be done in the future if it becomes necessary.

Though voicing is handled by Diatony, the third layer of the Harmoniser project, a few constraints must be enforced to ensure that the progressions generated by this model are compatible with the strict voicing rules of tonal music, namely tritone resolution and the preparation of diatonic seventh chords. Voicing rules are also necessary for modulations.

Tritone resolution. When one of the tritone notes is at the bass, its resolution affects the state of the next chord. This is the case for dominant chords (primary or secondary) in first or third inversion. For chords in first inversion, the bass note should move up by step. For chords in third inversion, it should move down by step.

Where D is true for a dominant chord, and false otherwise, and Bi is the array containing the degree of the note at the bass for each chord, which is derived from Di and Si and defined in the technical appendix. The " mod 7 " is due to the fact that there are seven diatonic degrees in a tonality.

Preparation of diatonic seventh chords. Except for the fifth degree (V) chord, when a diatonic chord has a seventh, that note must be present in the chord that is played before, at the same voice. In our model, we can only enforce that the seventh is in the previous chord. Diatony will impose that they are in the same voice.

• (b) Chromatic part of the graph described by the adjacency matrix in Figure 1.

(d) Chromatic modulation

Figure 3: Representation of the different modulation types.

Where Hi[ci] is true when chord ci in progression i has a seventh, and false otherwise; Roi, Tii, Fii and Sei are the degree corresponding to the root, third, fifth and seventh of each chord respectively. They are derived from Di and defined in the technical appendix.

3.4 Modulation Constraints

There are two main types of modulation from one tonality to another: modulations to neighbouring tonalities (at least one chord in common), and modulations to distant tonalities. In this paper, we focus on modulations to neighbouring tonalities. We distinguish four types of modulations to neighbouring tonalities. Their representation is given in Figure 3, and their definitions and formalisation are given below.

Perfect cadence modulation. This can be considered as one tonality ending and another beginning. The current tonality ends on a perfect cadence and the next tonality starts on the next chord (see Figure 3a). The only constraint to enforce is that the last two chords of the first tonality are V and I, both in fundamental state.

We link the first and the second progression to the modulation.

Pivot chord modulation. A pivot chord modulation uses a chord that is in both tonalities as a pivot to transition from one tonality to the other. It can be followed by multiple chords that are in both tonalities, and eventually a perfect cadence in the new tonality, which ends the modulation. To model this transition period where chords are in both tonalities, there is an overlap between the two corresponding progressions (see Figure 3b). The global variables from position sm up to position fm-2 are constrained by both tonalities, so the chords at these positions must be available in both tonalities. The pivot chord cannot be VII.

We link the first and the second progression to the modulation.

Alteration modulation. An alteration modulation introduces a note from the second tonality that is not present in the original tonality to start the modulation. This chord has to be followed by the V of the new tonality, affirming it (see Figure 3c). If the chord used to introduce the alteration cannot be followed by V, it has to be the next chord. The last chord of the first progression must be diatonic, cannot be VII and cannot have a seventh. The first chord of the new progression must be diatonic, and cannot be V or VII.

Where Hm[cm] is true when chord cm has a seventh.

We must also ensure that the first chord of the new progression contains a note that is not in the first tonality. We define a function ft(n) that takes as argument a note in [C,B], and returns the quality of the diatonic chord built on that note if it is in t. The function is not defined if the note is not in t.

This is equivalent to a 12-value array, containing for each note the quality of the chord based on this note in t if it exists, and nothing otherwise. We then impose the constraint:

which means that the quality of the chord based on note Rm+1[0] cannot be the same in both tonalities. If this note is not in tm, this is trivially satisfied. This ensures that there is at least one note in the first chord in the new progression that is not in the previous tonality. We still have to enforce that this altered chord is followed by V. Depending on which degree it corresponds to, it might not be possible for V to follow directly. In that case, it should be the next chord.

Chromatic modulation. This kind of modulation occurs when one chord in the first tonality is followed by the V of the new tonality, with a chromatic movement in the voice that plays the leading tone of the new tonality in the dominant chord (see Figure 3d). The voice leading aspect of this modulation needs to be handled in the third (voicing) layer of the Harmoniser project. Similarly to the preparation of diatonic seventh chords, constraints still need to be enforced in this model to make sure that this chromatic movement is possible. In particular, we must enforce that the first chord of the new progression is V, and there must be a one chord overlap between the progressions to ensure that the transition is smooth. The chord in this overlap is thus a secondary dominant in the first tonality, and the dominant in the new one. We must also ensure that the note in the first tonality corresponding to the leading tone in the new tonality is present in the chord just before the dominant of the new tonality (i.e., when modulating from C major to A major, there must be a G in the first chord that can move to a G♯ in the second chord). To enforce that, we must compute the interval in semitones between the keys of the two tonalities, and transform that into a degree difference. This is shown in Table 2.

Where s is the degree that the seventh of the new tonality corresponds to in the first tonality.

3.5 Branching

The goal of our model is to define a search space that is as permissive as possible, only enforcing mandatory rules of tonal harmony to allow for composers' creativity to shape the solutions instead of the constraints. As a result, the number of solutions is very large and the branching strategies are defined for the relevancy of solutions rather than for efficiency.

With that in mind, the branching is first performed on chord degrees, as this is the most important variable array, selecting the variable with the smallest domain size and the value at random. The preferences in Figure 2 are not followed to avoid staying in the "preferred" transitions that would be repetitive. This could of course be improved in the future by considering composer preferences when assigning new values to variables. Branching is then performed on states, also on the smallest domain variable, favouring fundamental state and first inversion as these are the most common states in tonal music. Finally, branching is performed on chord qualities, favouring triads over seventh chords.

4 Evaluation and Example Use Case

Complete source code of our model is available on GitHub 7 , along with its integration with Diatony.

4.1 Efficiency and Number of Solutions

Since the model is designed to give as much freedom as possible to composers, the number of possible solutions for a given problem is enormous if no composer preferences are given. The only constraints enforced by default are the ones that are necessary to ensure that the generated chord progressions follow the rules of tonal harmony. We expect the composer to add musical ideas to guide the solver, formulated as constraints. This will in the future be done through a GUI.

As a result of this approach, solutions are found extremely quickly for problems of significant size and efficiency is hence not the main focus of this section. For example, the musical piece shown in Section 4.2 was generated in 3ms on an M1 MacBook Pro. Another longer piece, consisting of 60 chords with five modulations, was generated in 20ms. This is because this layer of the Harmoniser project on its own lacks global rules, that will be enforced through the first layer in future work. We expect the computation to be more intensive with the addition of composer-subjective constraints, that will transform the problem from a satisfaction problem (finding a valid solution) to an optimisation problem (finding the best solution), where the criteria for what makes a solution better are provided by the composer, and with complex links between the progressions.

4.2 Example of Composer Use

We now put ourselves in the mindset of a composer, to show how our tool can be used to generate a harmonic progression.

7 https://github.com/sprockeelsd/Progressions-and-Modulations/ tree/IJCAI2025

We explain the example in terms of constraints, but in a practical tool, these constraints would be given through a GUI. For our example, we want to write a chord progression that starts in C minor, modulates to its relative tonality E♭ major and then comes back to the tonality of C minor, that is 28 chords long. We want a perfect cadence modulation on chord 12, and a pivot chord modulation from chord 18 to 23.

In addition to these necessary instructions, we add the following constraints to express our musical intentions. (1) The first chord must be I. (2) No chord can be III or VII, except during the pivot chord modulation. (3) Only dominant chords can have a seventh. (4) There is a half cadence on chord seven. (5) There is a chromatic chord just before that (position six). (6) The II chord should only be used in first inversion. (7) There is a perfect cadence at the end of the piece. The input is illustrated in Figure 4.

If we run the solver with these input and constraints, it produces the following output. For the first progression in C minor, the chords suggested by the solver are I-II-Vda-VVI-IV-♭II-V-I-V-I-IV-V-I. This is interesting, but based on personal taste, we make a few modifications: I-II-Vda-V-I-IV6△-V-I-V-I-Vda-V-I. This is also an accepted solution for the solver. For the E♭ major to C minor progression, the output is I-VI-II-V-VI|I-V/VI|V-VI|I-VII|II-V-I-VI-II-V-I, where VI|I is the pivot chord starting the modulation (sixth degree in E♭ major and first degree in C minor) and the following chords are in both tonalities up until the perfect cadence in C minor. For this part, we only make one small modification: we modify the perfect cadence that ends the modulation to be an interrupted cadence. This is due to personal taste. The final chords for this part are thus I-VI-II-V-VI|I-V/VI|V-VI|I-VII|IIV-VI-I-II-V-I. Chord states have been omitted in the listing of the output to keep it readable, but they are as shown in Figure 5. Diatony can then be used to generate a four-voice texture representing our piece. Figure 5 shows one possible four-voice texture of this piece. It can be listened to here 8 . A harmonic rhythm has been given to the chords, as well as some ornamental notes, by the composer.

5 Conclusion

This paper defines a formal model of tonal chord progressions and modulations to neighbouring tonalities. We give a constraint-based implementation of this model in the Gecode constraint solver. Combined with the Diatony model [Sprockeels and Van Roy, 2024], this implementation generates tonal chord progressions with modulations in a four-voice texture.

8 https://youtu.be/97wBAwcZC8E?si=o dvYZyOGCegtrHN

The present model can be used as the foundation for many useful extensions. It can be enriched by allowing for more chromatic and borrowed chords, as well as modulations to distant tonalities, and by adding larger harmonic structures like harmonic sequences. The matrices encoding large amounts of musical knowledge, such as T and others defined in the technical appendix, are currently encoded in Gecode by element constraints, and could be extended to give a weight to each value, allowing composers to value some choices more than others. Extensional constraints could also be used instead of constant values, to dynamically change values during the search. Global constraints such as the regular or costregular constraints could also be used to further improve the efficiency of the model.

In the case where the composer wants suggestions from the solver, it would be interesting to generate successive solutions that differ significantly. This could be done using a branch and bound approach to post additional constraints when a solution is found, or using other approaches such as those proposed in [Pesant et al., 2022] and [Ingmar et al., 2020]. This is left for future work.

This work is part of the ongoing Harmoniser project aiming to assist composers in their creation process with constraint programming. In this project, a four-layer decomposition of the composition process was identified. So far, models have been defined and implemented for layer 2 (this paper) and layer 3 ([Sprockeels and Van Roy, 2024]). Models for the remaining layers are ongoing work with the goal of providing a complete set of models for the whole composition process, allowing to generate full musical pieces with the help of constraint programming. We are also working on a graphical user interface for this tool as well as an implementation as a plugin for a Digital Audio Workstation.

Acknowledgements

The authors wish to thank the Conservatoire Royal de Bruxelles for allowing us to take courses on music theory, and more specifically we thank Prof. Adrien Tsilogiannis for his insight on this paper, as well as Dr. Karim Haddad from IRCAM for his insight on the musical aspect of the paper. We also thank Juliette Vanderhaeghen and Lucile Dierckx for their support and feedback during the redaction. We thank all the anonymous reviewers of this paper who helped us to greatly improve the quality of the paper.