The present research proposes to make music constraint systems more generic by making them more progammable. This proposal is exemplified in the design of the generic music constraint system Strasheela.4 When comparing Strasheela with previous systems, three important aspects in particular are made (more) programmable: the music representation, the rule application to the score, and the search strategy.
Strasheela's music representation aims to conveniently provide any information required to express musical CSPs. To this end, the representation is highly extendable. Representation building blocks required for many CSPs are ready-made, but Strasheela additionally predefines building blocks which assist the user to extend the representation according needs.
Strasheela defines a novel music representation in the spirit of CHARM [Harris et al., 1991]. Two principles have been adopted from CHARM. Like CHARM, Strasheela's representation is based on the notion of data abstraction [Abelson et al., 1985] and it allows for user-controlled hierarchic nesting of score objects.
Strasheela's representation complements these principles by other principles learned from the music representation literature, for example, selectable score parameter (music magnitude) representations [Pope, 1992] (e.g. a pitch can be represented by a keynumber, cent or frequency value), bidirectional links between score objects to facilitate free traversing in the score hierarchy [Laurson, 1996], temporal containers which organise their elements sequentially or simultaneously in time [Dannenberg, 1989], organisation of musical data types in an user-extendable class hierarchy [Desain and Honing, 1997; Pope, 1991], and a highly generic data abstraction interface realised by higher-order functions [Desain, 1990].
It is essential for a generic music constraint system that the user freely controls which variables in the music representation are constrained by which compositional rule. Unlike many previous systems, Strasheela fully decouples the definition and application of a rule to make the rule application freely programmable.
Strasheela proposes to encapsulate compositional rules in functions (actually proceduces) as first-class values [Abelson et al., 1985]. This approach allows to define rule application mechanisms as higher-order functions expecting rules (i.e. functions) as arguments. A number of rule application functions suited for many CSPs have been defined, which either reproduce rule application mechanisms of existing systems or constitute convenient novel application mechanisms. The user can easily define further such rule application functions according needs.
Finally, a constraint system must be reasonable efficient to be useful in praxis. It makes a big difference whether a CSP takes seconds or hours to solve. Strasheela is founded on a constraint programming model based on the notion of computation spaces [Schulte, 2002]. This model makes the search process itself programmable at a high-level. The programmable constraint model allows the user, for example, to optimise the search process for CSPs with a particular structure (e.g. harmonic CSPs or polyphonic CSPs) by defining what decisions are made during search (the distribution strategy, the branching heuristics). For instance, the user can control in which order variables are visited in the search process - depending on the information available at the time of the decision (dynamic variable ordering). These decisions have immense influence on the size of the search space, but previous systems did not allow the user to customise them. These optimisations are independent of the actual problem definition, which allows to easily test a CSP with different search strategies or to reuse proven strategies.
A number of novel score distribution strategies have been defined for Strasheela which are suitable for a large range of musical CSPs. In particular, Strasheela provides a score distribution strategy which allows to efficiently solve polyphonic CSPs in which both the rhythmical structure as well as other parameters (e.g. pitches) are unknown and constrained in the problem definition [Anders, 2002]. Previous systems discouraged or even disabled the definition of such problems for efficiency reasons.