Index
Strasheela
Init
GUtils
LUtils
MUtils
Score
SMapping
SDistro
Out
Strasheela
FD_edited
Midi
This functor defines solvers and distribution strategies for a score search. The search process in Strasheela is highly customisable and the present functor makes such customisations concise and convenient. Score distribution strategies are discussed in my thesis "Composing Music by Composing Rules", chapter 7. For information on constraint solvers and distribution strategies in general see the Oz documentation (e.g., the "Finite Domain Constraint Programming" tutorial, http://www.mozart-oz.org/documentation/fdt/index.html), and for detailed background information C. Schulte's book "Programming Constraint Services".

The solvers exported by this function are solvers customised for musical CSPs. Such score solvers (e.g., SearchOne or ExploreOne) expect a musical CSP (a script returning a solution score as its only argument), and optional arguments which define the distribution strategy. Note that this approach differs from the common solvers in Oz. Remember that in Oz the distribution strategy is part of the script, not an argument to the solver. Strasheela's approach separates script and distribution strategy, which is more convenient for complex distributions and in particular for scripts which contain of subscripts (CSP where subdefinitions, e.g., musical sections or the bare harmonic progression without the actual notes, can be solved on their own).

The distribution strategy arguments of all score solvers are documented with the function MakeSearchScript (this function also helps you defining new solvers, see the solver definitions in the source). Particularly important aspects of a distribution strategy are its variable and value ordering (the optional arguments 'order' and 'value').

Several orderings (and other distribution args) are predefined and easily specified with an atom as distribution argument (e.g., by setting the distribution argument 'order' to 'size' or 'leftToRight', see the MakeSearchScript documentation for details). More complex variable orderings can be defined conveniently with the variable ordering constructors and plain variable orderings provided (e.g., a variable ordering which first visits time parameters but breaks ties -- where both its arguments are (are not) time parameters -- by visiting the parameter with the largest domain size first, such a variable ordering is concisely defined as follows: {MakeTimeParams Dom}.



Functor

Import

Export

Define

fun{SearchOne ScoreScript Args}
Calls Search.base.one with a script created by MakeSearchScript. The meaning of the arguments ScoreScript and Args are the same as for MakeSearchScript.
fun{SearchAll ScoreScript Args}
Calls Search.base.all with a script created by MakeSearchScript. The meaning of the arguments ScoreScript and Args are the same as for MakeSearchScript.
fun{SearchBest ScoreScript OrderP Args}
Calls Search.base.best with a script created by MakeSearchScript. The meaning of the arguments ScoreScript and Args are the same as for MakeSearchScript. Best solution is performed with respect to OrderP (a binary procedure).


fun{SearchBest_Timeout ScoreScript OrderP MaxTime Args}
Similar to SearchBest, but after MaxTime milliseconds have passed SearchBestWithTimeout returns the best solution found so far.
fun{SearchOneDepth ScoreScript RcdI Args KillP}
Calls Search.one.depth with a script created by MakeSearchScript. The meaning of the arguments ScoreScript and Args are the same as for MakeSearchScript.
RcdI (an int) is the recomputation distance, and KillP (a nullary procedure) kills the search engine, for details see http://www.mozart-oz.org/documentation/system/node11.html.


proc{ExploreOne ScoreScript Args}
Calls Explorer.one with a script created by MakeSearchScript. The meaning of the arguments are the same as for MakeSearchScript.
proc{ExploreAll ScoreScript Args}
Calls Explorer.all with a script created by MakeSearchScript. The meaning of the arguments are the same as for MakeSearchScript.
proc{ExploreBest ScoreScript OrderP Args}
Calls Explorer.best with a script created by MakeSearchScript. The meaning of the arguments ScoreScript and Args are the same as for MakeSearchScript. Best solution is performed with respect to OrderP (a binary procedure).


fun{Naive _ _}
[variable ordering (a score distribution strategy 'order' procedure)] naive variable ordering: visit first parameter first.
fun{Dom X Y}
[variable ordering] 'dom' score variable ordering: first visits score parameters with smallest domain size. In case of a tie (i.e. both domain sizes are equal), X is preferred.
fun{Width X Y}
[variable ordering] 'width' score variable ordering: first visits score parameters with smallest domain width (the smallest difference between the domain bounds). In case of a tie, X is preferred.
fun{Deg X Y}
[variable ordering] 'deg' score variable ordering: first visits score parameters with most constraints applied (i.e. most threads suspending on its variable). In case of a tie, X is preferred.
fun{DomDivDeg X Y}
[variable ordering] 'dom/deg' score variable ordering: first visits score parameters with the smallest quotient of domain size and number of constraints applied. In case of a tie, X is preferred.
fun{MakeDom P}
[variable ordering constructor] Returns a 'dom' score variable ordering (a binary function expecting two parameter objects and returning a boolean value, a score distribution strategy 'order' procedure), i.e. an ordering which first visits score parameters with smallest domain size. It breaks ties (i.e. both domain sizes are equal) with the score variable ordering P.
fun{MakeDeg P}
[variable ordering constructor] Returns a 'deg' score variable ordering (a binary function expecting two parameter objects and returning a boolean value), i.e. an ordering which first visits score parameters with the most constraints applied (i.e. most threads suspending on its variable). It breaks ties with the score variable ordering P.
fun{MakeLeftToRight P}
[variable ordering constructor] Returns a left-to-right score variable ordering (a binary function expecting two parameter objects and returning a boolean value), i.e. an ordering which visits score parameters in the order of the start time of their associated score object. If only one start time is bound, then prefer the corresponding param (if none is bound prefer Y). In case of equal start times, temporal parameters are visited first. It breaks ties (equal start times and both X and Y are/are not time parameters) with the score variable ordering P.

NB: it is important for this variable ordering that time parameters are determined early so that other start times are determined. So, typically P is defined by {MakeTimeParams Q}, where Q is your actual tie-breaking ordering. The default leftToRight ordering is {MakeLeftToRight TimeParams}.

NB: P is only called if both start times are determined and equal. So, the overhead added should not be too high.

NOTE: MakeLeftToRight cannot handled undetermined offset times correctly. Left-most items with undetermined offset time are not recognised (because MakeLeftToRight depends on determined start times).
fun{MakeLeftToRight2 P}
Generalised version of MakeLeftToRight, which allows for undetermined offset times by not looking at the start time of items but instead at the end time of their predecessors. Because the value of offset time is not taken into account items in a sim (or at first position in other containers nested in a sim) could be processed in any order, even if their later offset times differ.

NOTE: computationally more expensive than MakeLeftToRight (but seemingly not too much).
fun{MakeRightToLeft P}
Generalised version of MakeLeftToRight, which returns a left-to-right score variable ordering (a binary function expecting two parameter objects and returning a boolean value): If the start time of the item of either parameter object are undetermined, then the score variable ordering P1 is used to decide which one to distribute. If both items have the same start time then the score variable ordering P2 is used. Otherwise the parameter that belongs to the "earlier" item is preferred.

This distribution strategy is useful, e.g., when searching for motifs (e.g., pattern motifs), which determine the temporal structure. The motifs would be addressed in P1 and other parameters in P2.

NOTE: distro first visits all params matching P1 and then does left-to-right -- is that actually useful?? Could I get the same result instead (and better comprehensible code) by nesting a MakeLeftToRight call within a MakeSetPreferredOrder call.
*/
fun {MakeLeftToRight2 P1 P2}
fun {$ X Y}
S1 = {{X getItem($)} getStartTime($)}
S2 = {{Y getItem($)} getStartTime($)}
IsS1Bound = ({FD.reflect.size S1}==1)
IsS2Bound = ({FD.reflect.size S2}==1)
in
if start time of both elements are bound
if IsS1Bound andthen ({FD.reflect.size S2}==1)
then
S1 < S2 orelse
if start times are equal, break ties with P2, otherwise false (prefer Y, because S2 < S1)
(S1 == S2 andthen {P2 X Y})
same meaning, but always needs two computation steps:
if S1==S2
then {P X Y}
else S1 =< S2
end
else {P1 X Y}

elseif {GUtils.xOr IsS1Bound IsS2Bound}
one start time is bound -- prefer that one
then IsS1Bound
else {P1 X Y}
end
end
end

/** %% [variable ordering constructor] Returns a right-to-left score variable ordering, i.e. an ordering which visits score parameters in the decreasing order of the end time of their associated score object. If only one end time is bound, then prefer the corresponding param (if none is bound prefer Y). In case of equal end times, temporal parameters are visited first. It breaks ties (equal start times and both X and Y are/are not time parameters) with the score variable ordering P.

NB: this variable ordering only works if the last end time (and thus usually the full score duration) is determined in the problem definition! It can be hard to reliably find a value (total duration) which works? Nevertheless, for some CSPs it is beneficial to work backwards (e.g., the final cadence may pose special problems).

NB: it is important for this variable ordering that time parameters are determined early so that other end times are determined. So, typically P is defined by {MakeTimeParams Q}, where Q is your actual tie-breaking ordering.

NB: P is only called if both end times are determined and equal. So, the overhead added should not be too high.
fun{TimeParams X _}
[variable ordering] first visits time parameters. In case of a tie, Y is preferred.
fun{MakeTimeParams P}
[variable ordering constructor] Returns a score variable ordering (a binary function expecting two parameter objects and returning a boolean value) which first visits time parameters. It breaks ties with the score variable ordering P.
fun{ReflectMin X Y}
[variable ordering] first visits score parameters with minimal lower domain boundary. In case of a tie, X is preferred.
fun{ReflectMax X Y}
[variable ordering] first visits score parameters with maximal upper domain boundary. In case of a tie, X is preferred.
fun{MakeSetPreferredOrder Tests P}
[variable ordering constructor] More general variant of MakeSetPreferredOrder2. Returns a variable ordering which visits parameters in an order specified by test functions. Tests is a list of unary boolean funcs which expect a parameter. Implicitly, a last Boolean function is added which always returns true (so parameters not matching any test are always rated lower). The variable ordering first visits the parameter for which a test with smaller index in Tests returns true. MakeSetPreferredOrder breaks ties with the score variable ordering P.
fun{MakeSetPreferredOrder2 Tests}
[variable ordering constructor] Returns a variable ordering which visits parameters in an order specified by test functions. Tests is a list of unary Boolean funcs which expect a parameter. Implicitly, a last Boolean function is added which always returns true (so parameters not matching any test are always rated lower). The variable ordering first visits the parameter for which a test with smaller index in Tests returns true. In case of a tie (two parameters with equal 'test index'), the first argument of the variable ordering is preferred (naive tie breaking).
fun{MakeMarkNextParam Clauses}
[variable ordering and selection constructor] Allows to mark one or more parameter objects which should be visited directly after specific parameters. For example, after a note's pitch class parameter one may want to visit directly afterwards its octave parameter.
Clauses is a list of pairs in the form [Test1#ItemAccessors1 ...]. TestI is a Boolean function or method expecting a parameter object. If a test function returns true then that means that specific parameters somehow related to the present parameter object are visited directly afterwards. These parameters are accessed with ItemAccessorsI, which is a list of unary functions or methods returning a parameter object to be visited next. Each function/method of ItemAccessorsI expects the item of the present parameter for convenience (so {X getItem($)} must not be called every time). Note that multiple params can be marked with multiple ItemAccessorsI, but the order in which these are visited is not specified.

MakeMarkNextParam returns a unary function for the distribution strategy argument 'select'.
Note: use MarkNextParam always together with MakeVisitMarkedParamsFirst.
fun{MakeVisitMarkedParamsFirst P}
[variable ordering constructor]: Returns a variable ordering which visits parameters marked by MakeMarkNextParam first. MakeVisitMarkedParamsFirst returns a binary function for the distribution strategy argument 'order'. MakeVisitMarkedParamsFirst should be the outmost variable ordering constructor (i.e. it should not be used as argument to another variable ordering constructor).
If neither variable is marked, use the score variable ordering P.

Note: use MakeVisitMarkedParamsFirst always together with MakeMarkNextParam.
fun{MakeRandomDistributionValue RandGen}
Returns randomised value ordering, that is, a binary function for the argument 'value' of FD.distribute. The argument RandGen is a nullary function. If RandGen is created by GUtils.makeRandomGenerator, then the value ordering is randomised but still deterministic: re-executing the distribution will allways yield the same results. Consequently, such a randomised value ordering can be used for recomputation.
NOTE: this value ordering is conveniently applied by setting the distribution argument 'value' of any solver to 'random'.
fun{MakeHeuristicValueOrder RandGen}
Returns a value ordering, i.e. a binary function that will be given to distribution arg 'value'. This value ordering takes heuristic constraints applied with Score.apply_H into account. In addition, it randomises the decision making. RandGen is a nullary function created by GUtils.makeRandomGenerator.

Naturally, any value ordering heuristics is only effective for parameters that are actually distributed. For example, if the pitch classes and octaves of notes are distributed and the note pitches are determined by propagation, then any heuristic constraint applied to the pitches has no effect.

NOTE: this value ordering is conveniently applied by setting the distribution argument 'value' of any solver to 'heuristic'.
fun{MakeSearchScript ScoreScript Args}
Returns a search script (a unary procedure) whose solution is a score. ScoreScript is a unary proc expressing a whole search problem involving a score as its solution, however without specifying any distribution strategy. Args is a record specifying the score distribution strategy with the same features as expected by FD.distribute for a distribution strategy (filter, order, select, value, and procedure) and the additional feature test. The distribution strategy features have mostly the same meaning and usage as in FD.distribute, for example, all these arguments support procedures as values (for details, see http://www.mozart-oz.org/documentation/system/node26.html). However, the distribution defined by MakeSearchScript always distributes score parameter objects, not plain variables. For example, the predefined select-procedure 'value' is defined as follows

fun {$ X} {X getValue($)} end



MakeSearchScript extends the set of predefined values for filter, order, select, value, and procedure already defined by FD.distribute. The following values are supported.

filter:
undet: Considers only parameter objects with undetermined value.
unary Boolean function P: Considers only the parameter objects X, for which {P X} yields true.

order:
'naive': Selects the first parameter object.
'size' or 'dom': Selects the first parameter, whose value domain has the smallest size.
'width': Select the first parameter with the smallest difference between the domain bounds of its value.
'nbSusps' or 'deg+dom': Selects a parameter with the largest number of suspensions on its value, i.e., with the larges number of constraint propagators applied to it. In in case of ties (i.e. this is equal for several parameters), then take the first parameter with the smallest value domain.
'dom+deg': Selects the first parameter, whose value domain has the smallest size. In case of ties take the first parameter with the larges number of constraints applied to it.
'dom/deg': Selects the first parameter for which the quotient of domain size and number of suspended propagators is maximum.
'min': Selects the first parameter, whose value's lower bound is minimal.
'max': Selects the first parameter, whose value's lower bound is maximal.
'timeParams': Selects the first temporal parameter object.
'timeParamsAndSize': Selects the first parameter, whose value domain has the smallest size, but always selects temporal parameter objects first.
'startTime' or 'leftToRight': Left-to-right distribution: Selects a parameter object whose associated temporal item has the smallest start time. Temporal parameters are preferred over other parameters. Note: the outmost temporal container msut have a determined startTime.
binary Boolean function P: Selects the first parameter objects which is minimal with respect to the order relation P.

select:
value: selects the parameter value (a variable).
unary function P: accesses a variable from the parameter object selected by order and filter.

value:
min: Selects the lower bound of the domain.
max: Selects the upper bound of the domain.
mid: Selects the value, which is closest to the middle of the domain (the arithmetical means between the lower and upper bound of the domain). In case of ties, the smaller element is selected.
splitMin: Selects the interval from the lower bound to the middle of the domain (see mid).
splitMax: Selects the interval from the element following the middle to the upper bound of the domain (see mid).
random: Selects a domain value at random. This value ordering is deterministic, i.e., recomputation is supported.
ternary procedure {P X SelectFn ?Dom}: where X is the parameter object selected by order and filter, SelectFn is the function given to the select argument, and Dom is the resulting domain specification. Dom serves as the restriction on the parameter value to be used in a binary distribution step (Dom in one branch, compl(Dom) in the other).
NB: the interface of this function is changed compared to FD.distribute.

Note that each distribution step is always traced at STDOUT (the *Oz Emulator* buffer).

The feature test expects a unary boolean function: all score parameters fulfilling the test are distributed.

The following are the defaults for Args. Note the argument test, which specifies that by default container parameters are ignored by the distribution.
unit(filter: undet
order: size
select: value
value: min
test:fun {Test X}
{Not {{X getItem($)} isContainer($)}}
end)

All distribution steps are traced at STDOUT (*Oz Emulator* buffer).
fun{MakeFDDistribution Spec}
[obsolete function] Function returns a specification of a distribution strategy (i.e. an argument for FD.distribute) for parameter score objects. The result of MakeFDDistribution is a FD distribution strategy specification as expected by FD.distribute (see http://www.mozart-oz.org/documentation/system/node26.html). However, the distribution defined by MakeFDDistribution always distributes score parameter objects, not plain variables.

NOTE: Using MakeFDDistribution is discouraged, better use MakeSearchScript.


End