You are looking at historical revision 28169 of this page. It may differ significantly from its current revision.

This page is maintained in the package's github repository.

Nondeterminism

This is a Chicken Scheme egg which implements nondeterministic computation. Note that its results are deterministic, there are no calls to rand(). Originally from Jeff Siskind's QobiScheme.

Examples are available in the examples/ directory.

Generation

[procedure] (a-boolean)
[procedure] (an-integer-above i)
[procedure] (an-integer-below i)
[procedure] (an-integer)
[procedure] (an-integer-between i j)
[procedure] (a-member-of list)
[procedure] (a-subset-of list)
[procedure] (a-split-of list)
[procedure] (a-permutation-of list)
[procedure] (a-partition-of list)
[procedure] (a-partition-of-size size list)

Generate a number of different kinds of elements.

[syntax] (either a b)

Select either a or b, everything is built on top of this primitive.

[procedure] (fail)

Backtrack at this point.

Execution

[syntax] (for-effects . body)

Execute a nondeterministic computation only for its effects not its result.

[syntax] (all-values . body)

Execute a nondeterministic computation and produce a list of all of its possible outputs.

[syntax] (one-value . body
[syntax] (local-one-value . body)

Execute a nondeterministic computation, return one output, and discard the rest of the computation.

[syntax] (possibly? . body)

Execute a nondeterministic computation and return #f if it always fails.

[syntax] (necessarily? . body)

Execute a nondeterministic computation and return #f if it can fail.

Side-effects

[procedure] (unwind-trail)
[procedure] (unwedge-trail)

Pop the stack once or clear it entirely.

[syntax] (local-set! obj val)
[procedure] (local-set-car! x y)
[procedure] (local-set-cdr! x y)
[procedure] (local-string-set! s i x)
[procedure] (local-vector-set! v i x)

Perform operations with side-effects that will be undone when backtracking.

[syntax] (upon-failure . body)

When backtracking execute body, the above operations are implemented in terms of this primitive.

Low-level features

[procedure] *fail?*
[procedure] (top-level-fail)
[procedure] (set-fail! f)

Internal

License

 
  Copyright 1993-1995 University of Toronto. All rights reserved.
  Copyright 1996 Technion. All rights reserved.
  Copyright 1996 and 1997 University of Vermont. All rights reserved.
  Copyright 1997-2001 NEC Research Institute, Inc. All rights reserved.
  Copyright 2002-2012 Purdue University. All rights reserved.

  Contact Andrei Barbu at andrei@0xab.com.

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  You should have received a copy of the GNU General Public License
  along with this program.  If not, see http://www.gnu.org/licenses.