CMU Artificial Intelligence Repository
Home INFO Search FAQs Repository Root

SCREAMER: Adds backtracking and constraint satisfaction to Common Lisp.

Screamer is an extension of Common Lisp that adds support for nondeterministic programming. Screamer consists of two levels. The basic nondeterministic level adds support for backtracking and undoable side effects. On top of this nondeterministic substrate, Screamer provides a comprehensive constraint programming language in which one can formulate and solve mixed systems of numeric and symbolic constraints. Together, these two levels augment Common Lisp with practically all of the functionality of both Prolog and constraint logic programming languages such as CHiP and CLP(R). Furthermore, Screamer is fully integrated with Common Lisp. Screamer programs can coexist and interoperate with other extensions to Common Lisp such as CLOS, CLIM and Iterate. In several ways Screamer is more efficient than other implementations of backtracking languages. First, Screamer code is transformed into Common Lisp which can be compiled by the underlying Common Lisp system. Many competing implementations of nondeterministic Lisp are interpreters and thus are far less efficient than Screamer. Second, the backtracking primitives require fairly low overhead in Screamer. Finally, this overhead to support backtracking is only paid for those portions of the program which use the backtracking primitives. Deterministic portions of user programs pass through the Screamer-to-Common-Lisp transformation unchanged. Since in practise, only small portions of typical programs utilize the backtracking primitives, Screamer can produce more efficient code than compilers for languages in which backtracking is more pervasive. The Screamer user-contributed code includes a pedagogical implementation of the SNLP planning algorithm in Screamer and code to add a layer on top of Screamer to permit the retraction of assertions.

Version: 3.12 Ports: Symbolics (Genera 8.1.1, 8.3) Lucid CL 4.0.2, 4.1 (Sun SPARC), 4.1 (SGI MIPS), 4.0.1 (IBM RS/6000) MCL 2.0, 2.0p2 Harlequin 3.0.3+ (Sun SPARC) Allegro 4.1, 4.2beta (Sun SPARC), 4.1 (SGI MIPS) Poplog 14.2 (Sun SPARC) AKCL 1.605 (Sun SPARC) It should run under any implementation of Common Lisp which is compliant with CLtL2 and with minor revision could be made to run under implementations compliant with CLtL1 or dpANS. Copying: Use, copying, and distribution permitted, provided mandatory reporting of bugs to Bug-Screamer@AI.MIT.EDU. Notify Info-Screamer-Request@AI.MIT.EDU when you obtain a copy of SCREAMER. Updated: Wed Jan 18 16:37:25 1995 CD-ROM: Prime Time Freeware for AI, Issue 1-1 Bug Reports: Bug-Screamer@AI.MIT.EDU Mailing List: Info-Screamer@AI.MIT.EDU (send subscription requests to Info-Screamer-Request@AI.MIT.EDU) Author(s): Jeffrey Mark Siskind and David Allen McAllester. Contact: Jeffrey Mark Siskind, University of Toronto Department of Computer Science Room LP290E Toronto Ontario M5S 1A4 Canada 416/978-6114 David Allen McAllester, MIT Artificial Intelligence Laboratory 545 Technology Square Room NE43-412 Cambridge MA 02139 617/253-6599 Keywords: Authors!McAllester, Authors!Siskind, Backtracking, Code Walker, Constraint Satisfaction, Lisp!Extensions, Nondeterminism, Planning, Retract, SCREAMER, SNLP References: Jeffrey Mark Siskind and David Allen McAllester, "Screamer: A Portable Efficient Implementation of Nondeterministic Common Lisp", University of Pennsylvania Institute for Research in Cognitive Science, Tech Report IRCS-93-03, 1993. Available as the file in the distribution. The code in this paper is included in screams.lisp. [This paper describes the fundamentals of nondeterministic Common Lisp.] Jeffrey Mark Siskind and David Allen McAllester, "Nondeterministic Lisp as a Substrate for Constraint Logic Programming", Proceedings of the Eleventh National Conference on Artificial Intelligence (AAAI-93), July 1993. Available as the file in the distribution. [This paper describes the constraint package included with Screamer.] is an outdated manual for Screamer.
Last Web update on Mon Feb 13 10:29:40 1995