Computational models of composition have long attracted musicians and computer scientists alike. Composers like to explore new compositional approaches in order to develop a distinct personal musical language. Music theorists can evaluate an hypothesis by means of a computational model. For computer scientists, modelling music is challenging because the complexity inherent in music calls for the most advanced computer science concepts.
Notably rule-based approaches have alway stimulated interest.1 For centuries, compositional rules were an established device for expressing compositional knowledge (for example in music education). Many musicians thus feel comfortable with a computational model based on the notion of rules. For example, rule-based approaches attracted much attention among composers, because by defining rules composers can formalise virtually any explicitly available compositional knowledge as a task which the computer can solve automatically.
Constraint programming has proven a particularly successful programming paradigm to realise ruled-based systems. Many compositional tasks have been addressed by constraint programming. Besides tasks inspired by traditional music theory such as the generation of harmonic progressions [Pachet and Roy, 2001] or counterpoint [Laurson, 1996; Schottstaedt, 1989], examples include purely rhythmical tasks [Sandred, 2003], Ligeti-like textures [Laurson and Kuuskankare, 2001], the modelling of non-European music [Chemillier and Truchet, 2001], or instrumentation [Laurson and Kuuskankare, 2001].
The attraction of constraint programming is easily explained. Constraint programming allows to model complex problems a simple way. A problem is stated by a set of variables (unknowns) and constraints (relations) between these variables. For example, a compositional task is stated by (i) a music representation in which some musical aspects are unknown - and therefore represented by variables - and (ii) compositional rules which impose constraints on these variables. For instance, a chord can be expressed by an event list and the chord pitches can be variables. Some harmonic rules may specify how the chord pitches are related to each other. In the terminology of constraint programming, the modelled problem or task is referred to as a constraint satisfaction problem (CSP).
In a solution to a CSP, every variable has a value which is consistent with all its constraints. For example, the solution of a musical CSP is a fully determined music representation consistent with all constraints expressed by the rules. Existing constraint programming systems (abridged: constraint systems) can efficiently solve a CSP - a fact which greatly contributed to the popularity of constraint programming.
A musical CSP can always be defined `from scratch' in a general constraint system. For instance, such a CSP can be defined in a regular programming language with support for constraint programming such as the Prolog based systems ECLiPSe [Cheadle et al., 2003] or SICTus Prolog [SICStus:Site]. However, subject-specific CSPs share a considerable amount of subject-specific knowledge: all musical CSPs require modelling of musical knowledge. For instance, concepts such as note, pitch, or voice are required in a large number of musical CSPs. Whenever a musical CSP is defined `from scratch', all this knowledge must be modelled anew. What's more, any subject-specific optimisation of the search process must also be carried out again (if the chosen constraint system supports such optimisations at all).
Therefore, a number of generic music constraint systems have been proposed. A generic music constraint system predefines general musical knowledge and building-blocks shared by many musical CSPs and that way highly simplifies the definition of such problems. For example, such a system may provide a specific music representation, templates to simplify the definition of compositional rules, or mechanisms to conveniently control how a rule is applied to the score. Particular important systems are PWConstraints [Laurson, 1996], and Situation [Bonnet and Rueda, 1999; Rueda et al., 1998]. A pioneering system is Carla [Courtot, 1990]. Further examples include the aggregation of the music representation MusES with the constraint constraint system BackTalk [Pachet and Roy, 1995], OMRC [Sandred, 2003,2000]2, Arno [Anders, 2000], OMBacktrack [Truchet, ], and OMClouds [Truchet et al., 2001,2003]. Already the number of existing systems demonstrates the high interest in music constraint programming.
The availability of generic music constraint systems makes music constraint programming accessible for a much larger user community. Often, these systems are explicitly tailored for users without any technical background who want to focus on formalising and solving the specific musical tasks they are interested in. A composer can apply such a system as an assistant in the composition process, a music theorist can use it as a testbed to evaluate a music theory, and a teacher can demonstrate the effect of different compositional rules to students.
The constraint programming paradigm is well suited to the needs of computer aided composition. Composers often prefer a way of working which is situated somewhere in the middle between composing `by hand' and formalising the composition process such that it can be delegated to the computer. Constraint programming supports this way of working very well. For example, the composer can determine some aspects of the music (e.g. certain pitches) by hand and constrain other aspects by rules. Alternatively, the composer may specify the high-level structure (e.g. the formal structure) manually and let the computer fill in the details. Furthermore, composers usually do not first fully formalise certain aspects of the composition process before they start actually composing. Instead, the formalisation is often an integral aspect of the composition process itself. A compositional task defined by means of constraint programming can be shaped in a highly flexible way during the composition process by the adding, removing and changing of individual rules.
A number of well-established composers already made extensive use of constraint programming. These include Antoine Bonnet (e.g. for Épitaphe for 8 brass instruments, 2 pianos, orchestra and electro-acoustics, 1992-1994, using Situation [Bresson et al., 2005]), Magnus Lindberg (Engine for chamber orchestra, 1996, using PWConstraints [Rueda et al., 1998]), Georges Bloch (Palm Sax for seven saxophones, using Situation [Rueda et al., 1998]), Örjan Sandred (Kalejdoskop for clarinet, viola and piano, 1999, using OMRC, [Sandred, 2003]), Jacopo Baboni Schilingi (Concubia nocte, in memoria di Luciano Berio for soprano and live computer, 2003, using OMCS)3, and Johannes Kretz (second horizon for piano and orchestra, 2002, using both OMRC and OMCS [Kretz, 2003]).