[[tags: egg data]]
[[toc:]]

This page is maintained in the package's
[[https://github.com/abarbu/nondeterminism|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>
<procedure>(an-integer-above i)</procedure>
<procedure>(an-integer-below i)</procedure>
<procedure>(an-integer)</procedure>
<procedure>(an-integer-between i j)</procedure>
<procedure>(a-member-of list)</procedure>
<procedure>(a-subset-of list)</procedure>
<procedure>(a-split-of list)</procedure>
<procedure>(a-permutation-of list)</procedure>
<procedure>(a-partition-of list)</procedure>
<procedure>(a-partition-of-size size list)</procedure>

Generate a number of different kinds of elements.

<macro>(either a b)</macro>

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

<procedure>(fail)</procedure>

Backtrack at this point.

=== Execution

<macro>(for-effects . body)</macro>

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

<macro>(all-values . body)</macro>

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

<macro>(one-value . body</macro>
<macro>(local-one-value . body)</macro>

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

<macro>(possibly? . body)</macro>

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

<macro>(necessarily? . body)</macro>

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

=== Side-effects

<procedure>(unwind-trail)</procedure>
<procedure>(unwedge-trail)</procedure>

Pop the stack once or clear it entirely.

<macro>(local-set! obj val)</macro>
<procedure>(local-set-car! x y)</procedure>
<procedure>(local-set-cdr! x y)</procedure>
<procedure>(local-string-set! s i x)</procedure>
<procedure>(local-vector-set! v i x)</procedure>

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

<macro>(upon-failure . body)</macro>

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

=== Low-level features

:<nowiki>*</nowiki>fail?*
<procedure>(top-level-fail)</procedure>
<procedure>(set-fail! f)</procedure>

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.
   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.