screamer
Screamer is a language extension that adds support for nondeterministic programming, including backtracking and undoable side-effects, and includes a constraint programming language.

Screamer was originally written by Jeffrey Mark Siskind and David Allen McAllester, and released under an non-DFSG-free "old school" license in 1991. It has since then been released with permission under at least GPL and MIT-licenses.

Probably the most alive version of Screamer is an MIT-licensed copy on Github, which should run on any ANSI Common Lisp and can be installed using Quicklisp.


The following Screamer code finds a 3x3 matrix of the integers between 1 and 9, such that the sums of the verticals, horizontals, and diagonals are equal.

(defun 3X3 () (let ((a (an-integer-betweenv 1 9)) (b (an-integer-betweenv 1 9)) (c (an-integer-betweenv 1 9)) (d (an-integer-betweenv 1 9)) (e (an-integer-betweenv 1 9)) (f (an-integer-betweenv 1 9)) (g (an-integer-betweenv 1 9)) (h (an-integer-betweenv 1 9)) (i (an-integer-betweenv 1 9))) ;; make sure they all different (assert! (/=v a b c d e f g h i)) ;; make sure the various directions add up (assert! (=v (+v a b c) (+v d e f) (+v g h i) (+v a d g) (+v b e h) (+v c f i) (+v a e i) (+v c e g))) (apply #'format (append (list t "Solution: ~%~d ~d ~d~%~d ~d ~d~%~d ~d ~d") (one-value (solution (list a b c d e f g h i) (static-ordering #'linear-force)))))))

SCREAMER-USER 4 > (3X3)
Solution: 
2 7 6
9 5 1
4 3 8
NIL

There is also an extension to Screamer, called Screamer+, described in the paper Constraint Handling in Common LISP. A copy of the source code that "may be used cost-free for non-commercial use" can be found here (Broken link, as of 11/2010, mirror here.)


Notes

Install

Buried at the bottom of screamer/README, it says you need a certain "preamble" at the top of a file in which you use it. Something like:

(IN-PACKAGE :CL-USER) (SCREAMER:DEFINE-SCREAMER-PACKAGE :MY-PACKAGE ;; ...optional defpackage arguments... ) (IN-PACKAGE :MY-PACKAGE)

Trace weirdness

I could be somehow mistaken, but it seems that TRACEing a nondeterministic function (Screamer seems to replace normal DEFUN with its own) may not be completely reliable. Here's something from my code where I don't expect SOLVE-ONCE's trace to show that it returns different things:

(in-package :cl-user) (screamer:define-screamer-package :blah (:export :solve-once :with-indices :eltv :mid)) (in-package :blah) ;;; Utilities (defun solve-once (&rest things) (one-value (solution things (static-ordering #'linear-force)))) (defmacro with-indices (indices &body body) `(let* ,(loop with last-index = (1- (length indices)) for i in indices collect `(,i (an-integer-betweenv 0 ,last-index))) (assert! (/=v ,@indices)) ,@body)) (defun eltv (&rest rest) (applyv #'elt rest)) ;;; Example (defun mid (n1 n2 n3) (let ((numbers (vector n1 n2 n3))) (with-indices (min mid max) (assert! (<=v (eltv numbers min) (eltv numbers mid) (eltv numbers max))) (elt numbers (first (solve-once mid min max)))))) (trace solve-once) (mid 0 1 2) ;; Trace: ;; 0: (SOLVE-ONCE [1168 integer 0:2 enumerated-domain: (0 1 2)] ;; [1165 integer 0:2 enumerated-domain: (0 1 2)] ;; [1171 integer 0:2 enumerated-domain: (0 1 2)]) ;; 0: SOLVE-ONCE returned (1 0 2) (mid 1 2 0) ;; Trace: ;; 0: (SOLVE-ONCE [1180 integer 0:2 enumerated-domain: (0 1 2)] ;; [1177 integer 0:2 enumerated-domain: (0 1 2)] ;; [1183 integer 0:2 enumerated-domain: (0 1 2)]) ;; 0: SOLVE-ONCE returned (0 2 1)


Topics: pattern matching