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 always stimulated interest.1 For centuries, compositional rules are 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.
Constraint programming has proven a particularly successful programming paradigm to realise ruled-based systems. Many compositional tasks have been addressed by constraint programming and are described in the literature. Besides tasks inspired by traditional music theory such as the generation of harmonic progressions or counterpoint, examples include dense Ligeti-like textures, modelling of non-European music, or instrumentation.
The attraction of constraint programming is easy to explain. Constraint programming offers a simple way to model complex problems. 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. At the same time, some melodic rules my restrict the same pitches as well. 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 systems can efficiently solve a CSP — a fact which greatly contributed to the popularity of constraint programming.
When compared with the approach of other general computer aided composition systems (e.g. Common Music, OpenMusic), the constrained-based approach is thus more declarative.
A generic music constraint system predefines concepts shared by many theories (e.g. duration, pitch, note, chord) and that way greatly simplifies the definition of musical CSPs. Strasheela implements such a generic music constraint system.
Compared with existing music constraint systems (e.g. PWConstraints, OMSituation, OMClouds and the combination MusES plus Backtalk), Strasheela is more generic, that is Strasheela allows to define and solve a considerable larger set of musical CSPs or makes their definition clearly more modular and concise. Besides, existing generic music constraint systems are not released under an open source license (e.g. OMSituation and OMClouds are libraries of OpenMusic: OpenMusic itself is open-source but its libraries are not).
Strasheela is more generic than existing music constraint systems primarily because Strasheela is more programmable and more extendable. The Strasheela user controls the information expressed by the music representation, programs how rules are applied to the music, and defines the decision-making conducted by the search process.
Strasheela features an highly expressive symbolic music representation. The representation explicitly stores diverse information such as user-definable score object attributes (e.g. the pitch of a note or the duration of a voice) and a user-defined hierarchic nesting of score objects (e.g. a voice containing a sequence of notes). Any explicit information available in the score is accessible from any score object and can be used to obtain derived information (e.g. the interval between the pitches of two notes). Explicit and implicit score information can be expressed by variables. Such information is unknown in the CSP definition and can be constrained. A rich data abstraction interface allows convenient access to explicitly stored or derived information (e.g. higher-order interface functions allow to collect all objects in the score which fulfill a user-defined condition) and the user can incrementally extend this data abstraction (by class inheritance).
Strasheela proposes a rule formalism which combines convenience and full user control to express which sets of variables in the music representation are constrained by a given rule. A Strasheela rule is a first-class function and a rule application mechanism is a higher-order function implementing an arbitrary traversal across the score to apply the rule to the score.
Strasheela is founded on a constraint programming model based on the notion of computation spaces. This model makes the search process programmable at a high-level. Strasheela customises the space-based constraint model for music constraint programming by preserving its full programmability. The Strasheela user can optimise the search for a particular constraint satisfaction problem by programming the decision making process conducted during search (the distribution strategy) — independent of the problem definition. Special distribution strategies for efficiently solving musical CSPs including complex prolophonic problems are proposed.
The user interface of Strasheela (and its implementation language) is the multi-paradigm programming language Oz.
1. Here, the term `rule' primarily denotes the musical concept of a compositional rule, and does not implicitly refer to any specific programming technique (e.g. the term does not implicitly refer to a Prolog rule or a condition-action rule).