This is Screamer - an extension of Common Lisp that adds support for nondeterministic programming. This code is base on the version 3.24 from Jeffrey Mark Siskind. This code should run on any ANSI Common Lisp. This software is Copyright (C) by Jeffrey Mark Siskind. It is hereby released undef the GNU Lesser General Public License. See also . Note that it may take a long time to compile Screamer (i.e. 1.5 hours using the Lucid production compiler on a Sun SPARCstation 2). This directory contains the following files: screamer.lisp - The source code for Screamer. iterate.lisp - The source code for Jonathan Amsterdam's Iterate macro. This has been modified slightly. This file is not need to run Screamer but is needed to run the examples in primordial.lisp, screams.lisp, and equations.lisp. primordial.lisp - A sort of torture test to determine whether Screamer is working. To run, first compile and load Screamer and Iterate, compile and load this file, type (IN-PACKAGE :PRIMORDIAL), and then type (PRIME-ORDEAL). If no errors result then Screamer is probably working correctly. screams.lisp - A file containing all of the examples from the Screamer manual and the two papers ircs-93-03 and aaai93. To use, first compile and load Screamer and Iterate, compile and load this file, and then type (IN-PACKAGE :SCREAMS). equations.lisp - A file containing some equations for testing Screamer's numeric constraint satisfaction procedures. To use, first compile and load Screamer, compile and load this file, and then type (IN-PACKAGE :SCREAMS). iscream.el - If you run Lisp on Unix under GNUEmacs using ILisp you can load this Emacs Lisp file (preferably byte compiled first). You must also then set the variable SCREAMER:*ISCREAM?* to T. This will enable the Screamer macro LOCAL-OUTPUT and improve the behavior of Y-OR-N-P and PRINT-VALUES under ILisp. doc/screamer.dvi doc/screamer.ps - DVI and Postscript versions of an outdated manual for Screamer. The code in this manual has some bugs but corrected versions are included in screams.lisp. doc/ircs-93-03.dvi doc/ircs-93-03.ps - DVI and Postscript versions of a paper describing the fundamentals of nondeterministic CommonLisp. This paper is available at Technical Report 93-03 of the University of Pennsylvania Institute for Research in Cognitive Science. The appropriate BibTeX entry is: \newcommand{\Screamer}{{\mbox{\sc Screamer}}} \newcommand{\CommonLisp}{{\mbox{\sc Common Lisp}}} @string{IRCS = {University of Pennsylvania Institute for Research in Cognitive Science}} @techreport{SiskindM93, author = {Jeffrey Mark Siskind and David Allen McAllester}, title = {{\Screamer:} A Portable Efficient Implementation of Nondeterministic {\CommonLisp}}, institution = IRCS, year = 1993, number = {IRCS--93--03}} The code in this paper is included in screams.lisp. doc/aaai93.dvi doc/aaai93.ps - DVI and Postscript versions of a paper describing the constraint package included with Screamer. This paper will appear in the Proceedings of AAAI-93. The appropriate BibTeX entry is: The code in this paper is also included in screams.lisp. \newcommand{\Lisp}{{\mbox{\sc Lisp}}} @string{AAAI93 = {Proceedings of the Eleventh National Conference on Artifical Intelligence}} @inproceedings{SiskindM93a, author = {Jeffrey Mark Siskind and David Allen McAllester}, title = {Nondeterministic {\Lisp} as a Substrate for Constraint Logic Programming}, booktitle = AAAI93, year = 1993, month = jul} Incompatibilities between Screamer 3.20 and Screamer 2.4: Screamer 3.20 contains numerous bug fixes, performance enhancements and novel features over Screamer 2.4, the prior widely released version. I do not have the time to describe all such improvements. Until the completion of a new Screamer manual you must resort to looking at the source code. At the beginning of the file there is a fairly extensive change log. A small number of incompatibilities have been introduced in the transition from Screamer 2.4 to Screamer 3.20. These are summarized below. Those already familiar with Screamer should have no difficulty modifying their code modulo these changes. 1. All Screamer code must be recompiled. The Screamer 3.20 runtime is incompatibile with the Screamer 2.4 compiler. 2. The function MAP-VALUES has been removed. An expression such as: (MAP-VALUES function expression) can be rewritten using the new FOR-EFFECTS macro as follows: (FOR-EFFECTS (FUNCALL function expression)) The new syntax is every bit as powerful as the old syntax. In fact it is more powerfull. MAP-VALUES used to require that the function argument be a deterministic expression while the new syntax makes no such requirement. (Note that FUNCALL still requires that its first argument evaluate to a deterministic function.) 3. You no longer need to reload Screamer after doing an UNWEDGE-SCREAMER since Screamer keeps track of which functions are intrinsic and UNWEDGE-SCREAMER does not purge those functions. 4. The following functions have been renamed: NUMBERV -> NUMBERPV REALV -> REALPV INTEGERV -> INTEGERPV BOOLEANV -> BOOLEANPV The original names were inconsistent with the naming convention that every function ending in V names a lifted version of the function name without the V. I.e. NUMBERV would have been a lifted version of a function NUMBER but there is no ground function. NUMBERV was really a lifted version of NUMBERP and thus should have been named NUMBERPV. 5. A new naming convention has been introduced. All nondeterministic `generators' now begin with the prefix A- or AN-. This results in the following name changes: INTEGER-BETWEEN -> AN-INTEGER-BETWEEN MEMBER-OF -> A-MEMBER-OF FLIP -> A-BOOLEAN Furthermore, `lifted generators' both begin with A- or AN- and end with V. This results in the following name changes: REAL-ABOVEV -> A-REAL-ABOVEV REAL-BELOWV -> A-REAL-BELOWV REAL-BETWEENV -> A-REAL-BETWEENV INTEGER-ABOVEV -> AN-INTEGER-ABOVEV INTEGER-BELOWV -> AN-INTEGER-BELOWV INTEGER-BETWEENV -> AN-INTEGER-BETWEENV 6. The variable *FUZZ* has been eliminated. The functionality of this variable has been replaced by additional arguments to the REORDER function. 7. REORDER now takes four arguments: (COST-FUNCTION TERMINATE? ORDER FORCE-FUNCTION) instead of one. The FORCE-FUNCTION is the same as the prior lone argument. The COST-FUNCTION is a function to be applied to each VARIABLE at each reordering step to return its cost. Typical values for COST-FUNCTION are #'DOMAIN-SIZE or #'RANGE-SIZE. The COST-FUNCTION can return NIL which causes REORDER to not consider that variable for further forcing. ORDER is a two argument predicate applied to the non-NIL cost functions computed for the variables at each reordering step. Typical values are #'<, to choose the least cost, and #'>, to choose the greatest cost variable to force next. TERMINATE? is a one argument predicate applied to the (non-NIL) cost function computed for the variable chosen to force next. If TERMINATE? returns T then the variable reordering and forcing terminates. The following is a typical call to REORDER used to solve numerical constraints: (REORDER #'RANGE-SIZE #'(LAMBDA (X) (< X 1E-6)) #'> #'DIVIDE-AND-CONQUER-FORCE) The following is a typical call to REORDER used to solve symbolic constraints: (REORDER #'DOMAIN-SIZE #'(LAMBDA (X) (DECLARE (IGNORE X)) NIL) #'< #'LINEAR-FORCE) 8. Instead of the standard Screamer file preamble which used to be: (IN-PACKAGE :) (USE-PACKAGE '(:LISP :SCREAMER)) (SHADOWING-IMPORT '(SCREAMER::DEFUN)) there is now a different standard preamble. Loading Screamer creates a predefined package SCREAMER-USER which is useful for small student and demonstration programs. If you wish your file to be in the SCREAMER-USER package the single line: (IN-PACKAGE :SCREAMER-USER) should be placed at the top of the file. In addition: (IN-PACKAGE :SCREAMER-USER) should be typed to the Listener after loading Screamer. More complex programs typically reside in their own package. You can place a program in its own package by using the following preamble to your file: (IN-PACKAGE :CL-USER) (SCREAMER:DEFINE-SCREAMER-PACKAGE : ) (IN-PACKAGE :MY-PACKAGE) Note that DEFINE-SCREAMER-PACKAGE doesn't work under AKCL or Poplog so on these systems you must either use the SCREAMER-USER package or figure out on your own how to appropriately define a Screamer package.