Constraint Programming Using Screamer

Written by on May 17, 2016 in LISP, Music, Programming with 0 Comments

A few years I ago I had briefly experimented with the Screamer library in the context of automatic test case generation from specification. I felt it was a useful utility for doing simple constraint programming tasks.

Recently while going through some of the past articles in the Opusmodus forum, I was pleasantly surprised to find references to constraint programming in music. Since I have not explored this area much, I felt it was a good idea to give it a try.

Obviously, this is a vast topic, and google search throws up many papers and books. I hope to invest in some good books in the near future. However, the purpose of this post is to show how to install and get started with Screamer, and along the way, show an example of simple constraint programming in Opusmodus.

You can load Screamer via Quicklisp. In the Listener type the following:

(ql:quickload “screamer”)

(If you are going to use the library regularly, then you can load it up as part of OM startup.)

Screamer functions are in :screamer package, so you must include this at the beginning of your source file:

(use-package ‘(:screamer))

In my case, this threw up many shadowing errors, so I included the conflicting symbols in shadowing-import declaration.

One of the fundamental ideas in Screamer is non-determinism and hence backtracking. Let us write a simple function to non-deterministically return the elements of a list:

(defun an-element-from-list (alist)

  (if (null alist)

    (fail)

    (either (first alist) (an-element-from-list (cdr alist)))))

The pre-defined function either allows you to specify multiple values of a computation and the function fail forces the system to backtrack when necessary. These contribute to non-deterministic behaviour. One simple way of using the function we have written is:

(one-value (an-element-from-list ‘(a b c))) 

=> a

If you want to get all possible values, then you can do this:

(all-values (an-element-from-list ‘(a b c))) 

=> (a b c)

It is important to note that non-deterministic does not mean random. In the above case, elements are returned in the supplied order.

Let us expand our understanding by writing a function to compute all combinations of elements from two lists:

(defun 2list-combinations (list1 list2)

  (all-values (list (an-element-from-list list1) (an-element-from-list list2))))

Let us check it:

(2list-combinations ‘(1 2 3) ‘(7 8 9)) 

=> ((1 7) (1 8) (1 9) (2 7) (2 8) (2 9) (3 7) (3 8) (3 9))

I encourage you to try and extend this functionality to multiple lists. I thought it was straightforward, but I was wrong! You can see my solution in the source code.

OK, all this is fine, but how can we apply Screamer to constraint programming, in particular, to music synthesis?

Let us consider this problem:

Given a set of pitches, we have to write a function to select 4 out of them, say n1, n2, n3, and n4, such that:

n1 and n2 are ascending, n3 and n4 are descending

(OR)

n1 and n2 are descending, n3 and n4 are ascending 

Every time we call the above function, we wish to get a different set of results, if possible.

So first we write a function to return an element from a list, similar to the earlier one we wrote, but introduce randomness:

(defun a-note-from-midi-list (midi-list)

  (a-member-of (rnd-order midi-list)))

Here we are using the pre-defined Screamer function a-member-of. Also, for simplicity, we will assume that the argument is a list of MIDI values of pitches. Here is the main function:

(defun notes-for-bar-midi (midi-list)

  (one-value

   (let ((n1 (a-note-from-midi-list midi-list))

         (n2 (a-note-from-midi-list midi-list))

         (n3 (a-note-from-midi-list midi-list))

         (n4 (a-note-from-midi-list midi-list)))

     (assert! (orv (andv (<v n1 n2) (<v n4 n3)) (andv (>v n1 n2) (>v n4 n3))))

     (solution (list n1 n2 n3 n4) (static-ordering #’linear-force)))))

The assert! function establishes the constraint for our problem. In a more complex scenario, it is common to find multiple assert! calls. The solution function drives the computation. Because we are using one-value, each time we call this function it will return a single list of 4 notes.

Constraint Programming in Screamer

Constraint Programming in Screamer

Quite interesting, don’t you think? In my source, I have extended this function to generate chord as well as non-chord tones. Take a look at it. Here is the source code.

I hope to spend more time with Screamer to understand how it can be used for music generation.

Have a great day!

Tags: ,

Subscribe

If you enjoyed this article, subscribe now to receive more just like it.

Subscribe via RSS Feed

Leave a Reply

Your email address will not be published. Required fields are marked *

Top