I've ported Screamer to Corman Lisp 2.01. You can download the Corman specific distribution (~400KB). The original distribution for other Common Lisp implementations available from the Screamer website.
Screamer is a library for Common Lisp that provides support for non-deterministic programming. This includes backtracking, undoable side effects and constraint programming.
Recently I've had the need to do some constraint programming and I've been looking at other languages that have this support built in. Mozart/Oz and Alice were the two I was looking at. Alice in particular is nice, being a superset of SML with concurrency, laziness and constraint based programming.
Being more of a Common Lisp programmer though I'd prefer to use my favourite tool, and the libraries I needed to use were written in Lisp so I wasn't in a hurry to port things over. I remembered a post on c.l.l by someone recommending to extend existing Lisp implementations rather than always using other languages so I went on the hunt for contraint systems for Common Lisp.
I'd heard of Screamer but had always thought it to be a very difficult product which would be hard to port. In fact, it was almost trivial. It's all done with macros. Basically it walks the code you write using macros looking for non-deterministic function calls. When these are found it converts that code to continuation-passing-style and uses these continuations to implement backtracking, etc. It's very clever but you don't need to know anything about the implementation to use it.
As an experiment with Screamer I ported the Alice simple constraints example. The problem goes like this:
Find the distinct digits for the letters S, E, N, D, M, O, R, Y such that S and M are different from zero and the equation SEND + MORE = MONEY is satisfied. Here's the Screamer implementation that returns the values of S, E, N, D, M, O, R and Y as a list: (defun money ()
(let* ((s (an-integer-betweenv 1 9))
(e (an-integer-betweenv 0 9))
(n (an-integer-betweenv 0 9))
(d (an-integer-betweenv 0 9))
(m (an-integer-betweenv 1 9))
(o (an-integer-betweenv 0 9))
(r (an-integer-betweenv 0 9))
(y (an-integer-betweenv 0 9)))
(assert! (/=v s e n d m o r y))
(assert!
(=v
(+v (*v 1000 s) (*v 100 e) (*v 10 n) d
(*v 1000 m) (*v 100 o) (*v 10 r) e)
(+v (*v 10000 m) (*v 1000 o) (*v 100 n) (*v 10 e) y)))
(one-value
(solution (list s e n d m o r y) (static-ordering #'linear-force)))))
Basically I create a set of logic variables constrained to be integers valued between 0 and 9 (or 1 and 9 for S and M). I then add the constraint that each digit may not be equal to the other digits and finally that the addition of SEND + MORE = MONEY should be true. I search for the single solution. I could use ALL-VALUES to find all solutions but in this case there is only one.
Screamer is great to use for interactive programming too. Using it you can watch how adding your constraints affect the variables in use: ?(setq x (make-variable))
=> [899]
Now we assert that X is an integer: ?(assert! (integerpv x))
?x
=> [899 integer]
Add the constraint that it must be >= 0 and <= 10: ?(assert! (andv (>=v x 0) (<=v x 10)))
?x
=> [899 integer 0:10 enumerated-domain:(0 1 2 3 4 5 6 7 8 9 10)]
Unfortunately it not all constraints have an immediate effect though: ?(assert! (notv (=v x 2)))
?x
=> [899 integer 0:10 enumerated-domain:(0 1 2 3 4 5 6 7 8 9 10)]
Here you don't see the effect of not allowing X to be equal to two, but if we solve it you do see the effect: ?(all-values (solution x (static-ordering #'linear-force)))
=>(0 1 3 4 5 6 7 8 9 10)
In this regard Alice is a bit better as it always shows the effect of interactive constraints.
You can have 'notifiers' set up that watch values and automatically change based on them. Here's a really quick example: ?(setq x (make-variable))
=> [907]
Now we ask if X is an integer. But since X is not yet 'bound' (ie. has a single value) then there is no correct answer. So the result of the check is a Boolean watcher: ?(setq y (integerpv x))
=> [908 Boolean]
Later we find out that X is in fact an integer: ?(assert! (integerpv x))
?x
=> [907 integer]
Lets look at Y: ?y
=>T
It has magically changed to T for us because X is indeed an integer.
There's lots more to Screamer. Here's some pointers to more information:
1:13:46 AM 
|
