OMBacktrack Tutorial

by Charlotte Truchet


 

OMBacktrack is a visual integration of a CLOS constraints solver, Screamer, by Jeffrey Mark Siskind and David Mac Allester. The Backtrack package gives functions to declare Screamer variables, and apply constraints on these variables. Only the backtracking part of Screamer is given here (Screamer also has a solver by propagation). Please keep in mind that it allows mere backtracking, which is a extremely slow algorithm when the number of variables becomes big. Remember that when choosing the domains and writing the constraints.

Tutorial 1

The an-integer-between function allows to create a variable. This function is non-deterministic, that means that you can get many values (instead of one value for the deterministic functions).

In "File", "Preferences", choose "Listener" as your Screamer valuation, then evaluate the function to see the non-deterministic results.

And so on... Each time you choose Yes, Screamer performs a backtrack and gives you another value. When you choose Non, Screamer passes the last value of the Non deterministic Listener to the classical OM Listener.

Remark : the Non deterministic Listener allows to choose the solution, but the function still gives a single value in the real OM listener.

Tutorial 2

Since the previous patch contains a non-deterministic function (and nothing else to go back to determinism), it is itself non-deterministic. This is shown by the rose question mark, ?

Try and evaluate the patch with all the "Screamer valuation" possibilities : one-value, all-values, and Listener.

One-value gives the answer directly to the OM-Listener, the backtracking is hidden and you can use the output like any output of an OM patch.

All-values gives all the answers (may take a long time) to the OM-Listener, the backtracking is hidden and the output is the list of all answers.

Listener allows to choose if you want to keep the current value, or try to go on backtracking. It goes back to the OM Listener only after you answer no.

Tutorial 3

First, open the red non-deterministic patch to see how it works.

There are two kinds of basic non-deterministic functions in the Screamer library. an-integer-between enumerates all the integers between the first and second inputs. a-member-of enumerates all the members of the list given in input.

Then, evaluate the note with all Screamer valuations.

Evaluate this patch in several points, you can see that your are asked twice for the choice of the solution, one for each variable.

Tutorial 4

First, open the red ¿patch?

The first constraint

apply-cont applies the constraint (red patch) to the variables.

Open the red patch : it states the constraint, here that the value must be > 6300. Note that the second input of apply-cont doesn't have to be the variable(s) itself, here the constraint applies directly on the midicent value.

Evaluate the note : you'll see that you are asked twice for the choice of the variable (once for each non-deterministic variable).

Then, evaluate the output. You'll be asked for the choice only once. The reason is that the non-determinism is now entirely hidden in the red patch, non-deterministic itself. With the Non deterministic Listener, you'll get something like a real OM note editor (same for each predefined OM class), with the musical notation and the Palette if you want to listen.. This is why it can be usefull to put a classe factory before the output of a red ?patch.

 

Tutorial 5

 

Here are two other variable declarations. They allow to define a list of Screamer variables.

They work exactly the same as an-integer-between and a member-of, they are indeterministic as well.

 

Tutorial 6

 

On the left, the good way to use constraints. apply-cont is in the same non-deterministic patch than the variables.

On the right, the bad way. list-of-integers-between is a non-deterministic function (like all the ?patches), and the backtracking always take place inside the function (or the ?patches), so that the output becomes deterministic.

Here, apply-cont is evaluated after the ?, which is too late. The output is deterministic and there is no backtracking possible. Evaluate : first you'll be asked for other solutions, this is the evaluation just after the "list-of-integers-between, then you'll get an error because Screamer cannot backtrack (Can't throw to tag screamer::fail).

 

Tutorial 7

 

Open the red ?patch.

a-chord-in is a slightly more complicated function for variable declaration.

It works like list-of-members-of (the output is a list of Screamer variables), except that it includes two predefined constraints.

These constraints are hidden in the function itself, and they state that the values of the list must be all different, and that the list must be sorted.

This is usefull to define a chord for instance. The alldifferent constraints avoids you to get answers like (6000 6000 6000) and the sort constraints avoids (6000 6200 6400) and then (6200 6000 6400), which you may consider the same if you want to define chord midicents.

You could do the same by using apply-cont with list-of-members-of, but a-chord-in answers much faster since the backtracking happens earlier.

You can also add constraints after a-chord-in, here the constraint states that the chord must contain an interval of 400.

Of course, you can use a-chord-in with any domain values, not only midicents (provided they can be sorted with the < predicate), as the name doesn't suggest.

 

Tutorial 8

 

Open the red ?patch

A chord-seq where all chords contain an interval of either 400 midic, or 700 midic.

The global constraint state that the bass must be growing.

list-of-chords-in defines a list of "a-chords-in", as its name say.

The third input is optional and can be used to state constraint on each chord. This input can deal with a single constraint (patch in lambda-mode) or a list of constraints (list of patches in lambda-mode)

Remark : in the "growing bass" patch, you'll find the "growing?" predicate. There is another Screamer predefind predicate, "alldiff?". Both do what their name suggest they do.

Try to evaluate the patch woth different values for the chords' length : you'll see the main trouble with backtracking, the calculation time increases really fast when the number of variables increases. With (3 4 3), the first answer arrives after 0,2 secondes, but with (3 4 3 4), the first solution arrives after 20 minutes !