chickadee » nondeterminism

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

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

a-booleanprocedure
an-integer-above iprocedure
an-integer-below iprocedure
an-integerprocedure
an-integer-between i jprocedure
a-member-of listprocedure
a-subset-of listprocedure
a-split-of listprocedure
a-permutation-of listprocedure
a-partition-of listprocedure
a-partition-of-size size listprocedure

Generate a number of different kinds of elements.

(either a b)syntax

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

failprocedure

Backtrack at this point.

Execution

(for-effects . body)syntax

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

(all-values . body)syntax

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

(one-value . bodysyntax
(local-one-value . body)syntax

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

(possibly? . body)syntax

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

(necessarily? . body)syntax

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

Side-effects

unwind-trailprocedure
unwedge-trailprocedure

Pop the stack once or clear it entirely.

(local-set! obj val)syntax
local-set-car! x yprocedure
local-set-cdr! x yprocedure
local-string-set! s i xprocedure
local-vector-set! v i xprocedure

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

(upon-failure . body)syntax

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

Low-level features

*fail?*procedure
top-level-failprocedure
set-fail! fprocedure

Internal

Example

The following code is a rewrite of an example from the book "Teach Yourself Scheme in Fixnum Days" by Dorai Sitaram. The book gives the following problem setting:

The Kalotans are a tribe with a peculiar quirk. Their males always tell the truth. Their females never make two consecutive true statements, or two consecutive untrue statements.

An anthropologist (let's call him Worf) has begun to study them. Worf does not yet know the Kalotan language. One day, he meets a Kalotan (heterosexual) couple and their child Kibi. Worf asks Kibi: "Are you a boy?" Kibi answers in Kalotan, which of course Worf doesn't understand.

Worf turns to the parents (who know English) for explanation. One of them says: "Kibi said: 'I am a boy.'" The other adds: "Kibi is a girl. Kibi lied."

Solve for the sex of the parents and Kibi.

(define (solve-kalotan-puzzle)
 (define (xor a? b?) (if (and a? b?) #f (or a? b?)))
 (one-value
  (let ((parent1 (either 'male 'female))
        (parent2 (either 'male 'female))
        (kibi (either 'male 'female))
        (kibi-self-desc (either 'male 'female))
        (kibi-lied? (a-boolean)))
   (unless (not (eq? parent1 parent2)) (fail))
   (when kibi-lied?
    (unless (xor (and (eq? kibi-self-desc 'male)
                    (eq? kibi 'female))
                 (and (eq? kibi-self-desc 'female)
                    (eq? kibi 'male)))
     (fail)))
   (unless kibi-lied?
    (unless (xor (and (eq? kibi-self-desc 'male)
                    (eq? kibi 'male))
                 (and (eq? kibi-self-desc 'female)
                    (eq? kibi 'female)))
     (fail)))
   (when (eq? parent1 'male)
    (unless (and (eq? kibi-self-desc 'male)
               (xor (and (eq? kibi 'female)
                       (not kibi-lied?))
                    (and (eq? kibi 'male)
                       kibi-lied?)))
     (fail)))
   (when (eq? parent1 'female)
    (unless (and (eq? kibi 'female) 
               kibi-lied?)
     (fail)))
   (list parent1 parent2 kibi))))

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-2013 Purdue University. All rights reserved.
  Contact Andrei Barbu at andrei@0xab.com. Originally written by Jeff Siskind.
  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser 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 Lesser General Public License for more details.
  You should have received a copy of the GNU Lesser General Public License
  along with this program.  If not, see http://www.gnu.org/licenses.

Contents »