Screamer - A Nondeterministic Programming Library

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 such as 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 by 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.

Screamer was originally written by Jeffrey Mark Siskind and David Allen McAllester, see file LICENSE for licensing information (1-clause MIT License).

Contribution policy

This policy is meant to guide contributions to screamer and better inform users about what they can expect from the library:

General guidelines:

• screamer/core is stable (i.e. not subject to backwards incompatibility) and will not accept changes to intended functionality.
  • Additions to intended functionality are possible but dispreferred, and ideally should only be for the purpose of better fulfilling the existing scope of screamer/core.
• screamer is stable.
  • Changes or additions to intended functionality are possible, though the standard recommendation is to create an extension sub-system instead.
• Extensions and other sub-systems will be stable within major versions.
  • Further stability guarantees are per the sub-system’s maintainers’ judgement.
• Systems labeled experimental or with sub-1.0 version numbers are not stable.

To make backwards incompatible changes to the behavior of an existing subsystem

• If the change is to fix deviation from the intended behavior / experience, approval is at the discretion of the code owner.
• If the change is to modify the intended behavior / experience, the recommendation is to provide a different endpoint while maintaining the existing API
• If the change does not allow maintaining the existing API, create a new sub-system instead of modifying the existing one.

Of the above cases, the first and second cases would require a version bump to release in master, with the level (e.g. major/minor/etc.) determined by the code-owner.

Deployment process (subject to change)

Changes should first be merged into the dev branch. A change is considered released when it is merged from dev to master.

To test changes to an existing subsystem

If the changes do not need to be published to be tested, modifications can be in forks or other branches.

If the changes need to be published to be tested, it is recommended to make another subsystem with the suffix “experimental”, which either replaces or patches the subsystem being tested. Changes can be made in this experimental sub-system and then released to the original subsystem after being tested.

Changes

See CHANGELOG.org

Incompatible changes from Screamer 4 to Screamer 5

• Multiple new symbols exported from the screamer package
• *nondeterministic-context* is now a hash-table when non-NIL, rather than just equaling t as it previously did.
• NOTE: Bugfixes are not specifically enumerated as backwards incompatible, but there are multiple logic errors in older Screamer versions which have been fixed since then. These may invalidate code depending on the incorrect assumptions, but the API contract defined by documentation, docstrings, and symbol-names has not been violated, and in fact is followed more accurately after these fixes.

Examples

See http://nikodemus.github.io/screamer/ for some examples of the core Screamer functionality.

Related projects

Screamer+

This project attempts to enhance the expressiveness of Screamer Repos:

• https://github.com/danlentz/screamer-plus
• https://github.com/yakovzaytsev/screamer-plus (may be slightly less cleaned-up)