{"id":237,"date":"2016-05-17T12:10:51","date_gmt":"2016-05-17T12:10:51","guid":{"rendered":"http:\/\/www.rangakrish.com\/?p=237"},"modified":"2016-05-17T12:17:49","modified_gmt":"2016-05-17T12:17:49","slug":"constraint-programming-using-screamer","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2016\/05\/17\/constraint-programming-using-screamer\/","title":{"rendered":"Constraint Programming Using Screamer"},"content":{"rendered":"

A few years I ago I had briefly experimented with the\u00a0Screamer<\/a>\u00a0library in the context of automatic test case generation from specification. I felt it was a useful utility for doing simple constraint programming tasks.<\/p>\n

Recently while going through some of the past articles in the\u00a0Opusmodus<\/a>\u00a0forum, 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.<\/p>\n

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.<\/p>\n

You can load Screamer via Quicklisp. In the Listener type the following:<\/p>\n

(ql:quickload \u201cscreamer\u201d)<\/strong><\/p>\n

(If you are going to use the library regularly, then you can load it up as part of OM startup.)<\/p>\n

Screamer functions are in\u00a0:screamer<\/strong>\u00a0package, so you must include this at the beginning of your source file:<\/p>\n

(use-package ‘(:screamer))<\/strong><\/p>\n

In my case, this threw up many shadowing errors, so I included the conflicting symbols in\u00a0shadowing-import<\/strong><\/em>\u00a0declaration.<\/p>\n

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:<\/p>\n

(defun an-element-from-list (alist)<\/strong><\/p>\n

\u00a0 (if (null alist)<\/strong><\/p>\n

\u00a0 \u00a0 (fail)<\/strong><\/p>\n

\u00a0 \u00a0 (either (first alist) (an-element-from-list (cdr alist)))))<\/strong><\/p>\n

The pre-defined function\u00a0either<\/em><\/strong>\u00a0allows you to specify multiple values of a computation and the function\u00a0fail<\/strong><\/em>\u00a0forces the system to backtrack when necessary. These contribute to non-deterministic behaviour. One simple way of using the function we have written is:<\/p>\n

(one-value (an-element-from-list ‘(a b c)))\u00a0<\/strong><\/p>\n

=> a<\/strong><\/p>\n

If you want to get all possible values, then you can do this:<\/p>\n

(all-values (an-element-from-list ‘(a b c)))\u00a0<\/strong><\/p>\n

=> (a b c)<\/strong><\/p>\n

It is important to note that\u00a0non-deterministic<\/strong><\/em>\u00a0does not mean\u00a0random<\/strong><\/em>. In the above case, elements are returned in the supplied order.<\/p>\n

Let us expand our understanding by writing a function to compute\u00a0all combinations<\/em>\u00a0of elements from two lists:<\/p>\n

(defun 2list-combinations (list1 list2)<\/strong><\/p>\n

\u00a0 (all-values (list (an-element-from-list list1) (an-element-from-list list2))))<\/strong><\/p>\n

Let us check it:<\/p>\n

(2list-combinations ‘(1 2 3) ‘(7 8 9))\u00a0<\/strong><\/p>\n

=> ((1 7) (1 8) (1 9) (2 7) (2 8) (2 9) (3 7) (3 8) (3 9))<\/strong><\/p>\n

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<\/a>.<\/p>\n

OK, all this is fine, but how can we apply Screamer to constraint programming, in particular, to music synthesis?<\/p>\n

Let us consider this problem:<\/p>\n

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:<\/strong><\/em><\/p>\n

n1 and n2 are ascending, n3 and n4 are descending<\/strong><\/em><\/p>\n

(OR)<\/strong><\/em><\/p>\n

n1 and n2 are descending, n3 and n4 are ascending\u00a0<\/strong><\/em><\/p>\n

Every time we call the above function, we wish to get a different set of results, if possible.<\/p>\n

So first we write a function to return an element from a list, similar to the earlier one we wrote, but introduce randomness:<\/p>\n

(defun a-note-from-midi-list (midi-list)<\/strong><\/p>\n

\u00a0 (a-member-of (rnd-order midi-list)))<\/strong><\/p>\n

Here we are using the pre-defined Screamer function\u00a0a-member-of<\/strong><\/em>. Also, for simplicity, we will assume that the argument is a list of MIDI values of pitches. Here is the main function:<\/p>\n

(defun notes-for-bar-midi (midi-list)<\/strong><\/p>\n

\u00a0 (one-value<\/strong><\/p>\n

\u00a0\u00a0 (let ((n1 (a-note-from-midi-list midi-list))<\/strong><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 \u00a0 (n2 (a-note-from-midi-list midi-list))<\/strong><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 \u00a0 (n3 (a-note-from-midi-list midi-list))<\/strong><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 \u00a0 (n4 (a-note-from-midi-list midi-list)))<\/strong><\/p>\n

\u00a0\u00a0 \u00a0 (assert! (orv (andv (<v n1 n2) (<v n4 n3)) (andv (>v n1 n2) (>v n4 n3))))<\/strong><\/p>\n

\u00a0\u00a0 \u00a0 (solution (list n1 n2 n3 n4) (static-ordering #’linear-force)))))<\/strong><\/p>\n

The\u00a0assert!<\/strong><\/em>\u00a0function establishes the constraint for our problem. In a more complex scenario, it is common to find multiple\u00a0assert!<\/strong><\/em>\u00a0calls. The\u00a0solution<\/strong><\/em>\u00a0function drives the computation. Because we are using\u00a0one-value<\/strong><\/em>, each time we call this function it will return a\u00a0single<\/em>\u00a0list of 4 notes.<\/p>\n

\"Constraint<\/a>
Constraint Programming in Screamer<\/figcaption><\/figure>\n

Quite interesting, don\u2019t 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<\/a>.<\/p>\n

I hope to spend more time with Screamer to understand how it can be used for music generation.<\/p>\n

Have a great\u00a0day!<\/p>\n","protected":false},"excerpt":{"rendered":"

A few years I ago I had briefly experimented with the\u00a0Screamer\u00a0library 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\u00a0Opusmodus\u00a0forum, I was pleasantly surprised to find references to constraint programming […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[18,5,17],"tags":[59,58],"class_list":["post-237","post","type-post","status-publish","format-standard","hentry","category-lisp","category-music","category-programming","tag-constraint-programming","tag-screamer"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-3P","jetpack-related-posts":[{"id":245,"url":"https:\/\/www.rangakrish.com\/index.php\/2016\/05\/26\/constraint-propagation-in-picat\/","url_meta":{"origin":237,"position":0},"title":"Constraint Programming in Picat","author":"admin","date":"May 26, 2016","format":false,"excerpt":"In my last post\u00a0I briefly described how we can use the Screamer Lisp library for constraint programming in music. Another language I have been hearing a lot about, in the context of constraint programming, is Picat, a Prolog-derived language. Although I am familiar with Prolog and have been a user\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Picat Program","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2016\/05\/Picat-Program.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2922,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/10\/06\/why-learn-prolog\/","url_meta":{"origin":237,"position":1},"title":"Why Learn Prolog?","author":"admin","date":"October 6, 2022","format":false,"excerpt":"There are several programming languages in use today and a simple google search will throw up interesting recommendations of a subset of these languages to learn, usually based on popularity ranking. As is expected, the popularity of a programming language varies over time and hence a language that was in\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2540,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/09\/19\/c-20-concepts\/","url_meta":{"origin":237,"position":2},"title":"C++ 20: Concepts","author":"admin","date":"September 19, 2021","format":false,"excerpt":"Concepts, introduced in C++20, are predicates that act as contraints on template parameters. As you would expect, the nice thing is that the constraint checking happens as part of template instantiation at compile time and not at run time! Since templates can have type as well as non-type parameters, Concepts\u2026","rel":"","context":"In "C++"","block_context":{"text":"C++","link":"https:\/\/www.rangakrish.com\/index.php\/category\/c\/"},"img":{"alt_text":"Constraint on Type","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/09\/Example1-300x213.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":3589,"url":"https:\/\/www.rangakrish.com\/index.php\/2025\/01\/04\/word-transformation-puzzle-part-2-implementation-in-common-lisp\/","url_meta":{"origin":237,"position":3},"title":"Word Transformation Puzzle – Part 2: Implementation in Common Lisp","author":"admin","date":"January 4, 2025","format":false,"excerpt":"In the last article\u00a0I discussed an interesting word puzzle and showed how to solve it using Prolog. Here is the problem statement: \u201cYou are given two words of the same length. You have to transform the first word into the second word, by changing only one letter at a time.\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Getting Word Neighbors","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2025\/01\/code1-300x127.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2025\/01\/code1-300x127.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2025\/01\/code1-300x127.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":3573,"url":"https:\/\/www.rangakrish.com\/index.php\/2024\/12\/17\/using-prolog-to-solve-the-word-transformation-puzzle\/","url_meta":{"origin":237,"position":4},"title":"Using Prolog to Solve the Word Transformation Puzzle","author":"admin","date":"December 17, 2024","format":false,"excerpt":"In today\u2019s article, I want to share an interesting word puzzle, and then show how to solve it in Prolog. Here is the puzzle: You are given two words of the same length. You have to transform the first word into the second word, by changing only one letter at\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"Our Dictionary","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2024\/12\/prolog1-300x280.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":140,"url":"https:\/\/www.rangakrish.com\/index.php\/2016\/02\/06\/organum-in-music\/","url_meta":{"origin":237,"position":5},"title":"Organum in Music","author":"admin","date":"February 6, 2016","format":false,"excerpt":"When two or more voices in a song follow the same rhythm and move by the same interval, thus causing a parallel motion of the voices, it is referred to as Organum. Depending on the intervals between the voices, this can give rise to a rich and interesting effect. For\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Single voice","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2016\/02\/Single-voice.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2016\/02\/Single-voice.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2016\/02\/Single-voice.png?resize=525%2C300 1.5x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/237","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=237"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/237\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=237"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=237"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=237"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}