Ambiguous Operator
| (require (planet "amb.ss" ("murphy" "amb.plt" 1 0))) |
An enhanced version of the classic backtracking ambiguous operator. The implementation provides a fair amount of syntactic sugar and uses delimited continuations for the backtracking restarts which enables the conversion of ambiguous expressions into sequence generators.
1 An Example
The ambiguous operator can be used to solve logic problems by exhaustive search. The following code is a rewrite of an example from the book “Teach Yourself Scheme in Fixnum Days” [t-y-scheme]. 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.
So here is the solution using amb:
| (define (flip-gender gender) |
| (case gender |
| [(m) 'f] |
| [(f) 'm])) |
| (define (solve-kalotan-puzzle) |
| (let* ([parent1 (amb 'm 'f)] |
| [parent2 (flip-gender parent1)] |
| [kibi (amb 'm 'f)] |
| [kibi-self-desc (amb 'm 'f)] |
| [kibi-lied? (not (eqv? kibi-self-desc kibi))]) |
| (amb-assert |
| (if (eqv? kibi 'm) (not kibi-lied?) #t)) |
| (amb-assert |
| (case parent1 |
| [(m) |
| (and |
| (eqv? kibi-self-desc 'm) |
| (or |
| (and (eqv? kibi 'f) (not kibi-lied?)) |
| (and (eqv? kibi 'm) kibi-lied?)))] |
| [(f) |
| (and (eqv? kibi 'f) kibi-lied?)])) |
| (list parent1 parent2 kibi))) |
| > (amb-collect (solve-kalotan-puzzle)) |
((f m f)) |
2 Creating Ambiguous Expressions
The following forms and procedures may only be used within the dynamic context of a form or procedure collecting the ambiguous results. Such a form is called an ambiguous evaluation context.
If the forms and procedures in this section are used outside such a suitable context, they may cause exceptions of type exn:fail:continuation when they try to provide restarts for backtracking or try to initiate backtracking.
| (amb expr ) |
If no expressions are given, amb represents an unconditional failure of the current ambiguous evaluation context and initiates backtracking to the next restart point.
If exactly one expression is given, amb is equivalent to that expression by itself.
If more than one expression is given, amb evaluates its first argument and returns the result(s). A restart for backtracking is registered in the ambiguous evaluation context that evaluates the second argument instead and so forth.
The restart after the last expression provokes failure of the current ambiguous evaluation context and initiates backtracking again.
| (amb-assert condition) |
Provokes failure of the current ambiguous evaluation context unless condition evaluates to something other than #f.
| |
|
Iteratively evaluates the given body in context of the for-clauses like for or for* do.
The loop is interrupted after each iteration, though, and the result of the last expression of body is returned.
The result of the form is ambiguous, since a restart that resumes the loop when backtracking is registered in each iteration.
| (amb-call thunk ) → any |
| thunk : (-> any) |
Given any number of thunk arguments, this procedure behaves like (amb (thunk) ...) would.
The amb form is based on this procedure.
3 Collecting Ambiguous Results
The forms and procedures in this section provide an ambiguous evaluation context to expressions contained within them or procedures called from them.
| (amb-find expr ) |
Evaluates the given expressions in an ambiguous evaluation context. Backtracking is performed as necessary until the result(s) of the last given expression can be returned.
If all alternative evaluation paths have been exhausted and no result could be generated, an exception of the type exn:fail:amb is raised.
| (amb-collect expr ) |
Evaluates the given expressions in an ambiguous evaluation context. When the last given expression produces a result, it is collected. Backtracking is repeated until all possible evaluation paths leading to a result have been tried.
The form returns a list containing all the generated results. That list may be empty if no evaluation path led to a result.
| (in-amb expr ) |
Creates a sequence iterating over all possible results of the given ambiguous expressions.
This form is conceptually similar to (in-list (amb-collect (amb expr ))), with two important differences:
The evaluation is peformed lazily. Backtracking to produce alternative results is performed only when more elements are requested from the sequence.
The expressions may result in multiple return values that are all passed through by the sequence’s element generator.
| (call-with-amb-prompt thunk [failure-result]) → any | ||||||||||||
| thunk : (-> any) | ||||||||||||
|
This procedure behaves like (amb-find (thunk)) would, except that failure-result is called to produce the return value(s) of call-with-amb-prompt if no evaluation path in thunk leads to a result.
The forms amb-find and amb-collect are based on this procedure.
| (make-amb-sequence thunk) → sequence? |
| thunk : (-> any) |
This procedure behaves like (in-amb (thunk)) would.
The in-amb form is based on this procedure.
4 Exceptions
| ||||||||||
An exception of this type is raised to indicate the failure when an expression expects to obtain at least one (set of) result(s) from an ambiguous evaluation context, but all evaluation paths have led to failure, ie. a final backtracking step is initiated but there are no more restarts to try.
5 License
Copyright (c) 2008 by Thomas Chust <[email protected]>.
This package 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 [LGPL].
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.
Bibliography
| [t-y-scheme] | Dorai Sitaram, Teach Yourself Scheme in Fixnum Days. http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html | |
| [LGPL] | The Free Software Foundation, “The GNU Lesser General Public License.” http://www.gnu.org/licenses/lgpl-3.0.html |