Lambda the Ultimate

inactiveTopic Screamer: a Common Lisp library for non-determinism
started 3/18/2003; 11:10:35 AM - last post 5/29/2003; 6:37:37 PM
Ehud Lamm - Screamer: a Common Lisp library for non-determinism  blueArrow
3/18/2003; 11:10:35 AM (reads: 1877, responses: 7)
Screamer: a Common Lisp library for non-determinism
(via lemonodor)

Chris Double discusses his port of the Screamer library to Corman Lisp.

Screamer is a library for Common Lisp that provides support for non-deterministic programming. This includes backtracking, undoable side effects and constraint programming...

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.

P.S

'undoable' is a funny word. Reading it you must wonder whether the intention is to say 'un-doable' or 'undo-able'. Oh, well.


Posted to general by Ehud Lamm on 3/18/03; 11:13:27 AM

Chris Double - Re: Screamer: a Common Lisp library for non-determinism  blueArrow
3/19/2003; 5:37:06 AM (reads: 895, responses: 1)
It would appear that 'undoable' was the wrong word to use. It does in fact mean 'un-doable'.

In a similar vein to backtracing and constraints, Kenny Tilton has released his Cells library. I provide various details at: http://radio.weblogs.com/0102385/2003/03/18.html#a314

Basically it allows you to provide links between CLOS slots such that when one slot changes dependant slots are recalculated in a similar manner to the way recalculation in a spreadsheet works.

It's more sophisticated than just that though, read Kenny's site for more: http://radio.weblogs.com/0102385/2003/03/18.html#a314

Back to Screamer though. I think it's a great example of how macros can be used to extend Common Lisp. It basically adds a prior step to compilation that converts all code that calls non-deterministic functions into CPS form by providing a replacement for the DEFUN macro. And code that doesn't call non-deterministic functions is passed through unchanged.

How would other languages that don't have a macro facility add features like this in a library? Are macros in this instance a good approach to take or is it better to provide a more function oriented interface?

Isaac Gouy - Re: Screamer: a Common Lisp library for non-determinism  blueArrow
3/19/2003; 7:33:33 AM (reads: 872, responses: 0)
"We are struggling with language.
We are engaged in a struggle with language."

This includes backtracking, undoable side effects and constraint programming...
undoable (not doable) vs. undo-able (able to be undone)
The dictionary link shows not-doable, was that the intention? Or was the intention to say that Screamer supports undo for side-effects?

Chris Double - Re: Screamer: a Common Lisp library for non-determinism  blueArrow
3/19/2003; 1:24:43 PM (reads: 827, responses: 0)
The intention was to say that Screamer supports undo for side-effects when backtracking.

Ehud Lamm - Re: Screamer: a Common Lisp library for non-determinism  blueArrow
3/20/2003; 4:49:58 AM (reads: 843, responses: 0)
when one slot changes dependant slots are recalculated in a similar manner to the way recalculation in a spreadsheet works.

The second language I ever designed and implemented (very ugly Turbo Pascal code) did something like this, in a very rudimentary way.

After playing with it a bit I decided this was a great way for writing unreadable code, and started using the language for riddles and such...

Luke Gorrie - Re: Screamer: a Common Lisp library for non-determinism  blueArrow
3/24/2003; 5:09:43 AM (reads: 706, responses: 0)
Screamer looks really cool, thanks for the link!

Brent Fulgham - Re: Screamer: a Common Lisp library for non-determinism  blueArrow
3/24/2003; 1:50:16 PM (reads: 689, responses: 0)
Does anyone know if this library is being maintained? The web pages all seem to have modification dates from a year or so ago.

Chris Double - Re: Screamer: a Common Lisp library for non-determinism  blueArrow
5/29/2003; 6:37:37 PM (reads: 538, responses: 0)
The library has been inherited by CLOCC [1] and is being maintained there. There is also Screamer+ an extension to Screamer, pointers to that can be obtained from the original article.

[1] http://clocc.sf.net

Chris.