#lang scribble/doc @(require scribble/manual (only-in scribble/struct make-blockquote flow-paragraphs) (only-in scribble/decode decode-flow) scribble/eval (for-label scheme "amb.ss")) @define[(blockquote style . pre-content) (make-blockquote style (flow-paragraphs (decode-flow pre-content)))] @title{Ambiguous Operator} @defmodule[(planet "amb.ss" ("murphy" "amb.plt" 1 1))]{ 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. } @section{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'' @cite{t-y-scheme}. The book gives the following problem setting: @blockquote["boxed"]{ 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 @scheme[amb]: @defs+int[ #:eval (let ([sandbox (make-base-eval)]) (sandbox '(require "amb.ss")) sandbox) ( (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)) ] @section{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 @scheme[exn:fail:continuation] when they try to provide restarts for backtracking or try to initiate backtracking. @defform[(amb expr ...)]{ If no expressions are given, @scheme[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, @scheme[amb] is equivalent to that expression by itself. If more than one expression is given, @scheme[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. } @defform[(amb-assert condition)]{ Provokes failure of the current ambiguous evaluation context unless @scheme[condition] evaluates to something other than @scheme[#f]. } @deftogether[( @defform[(for/amb (for-clause ...) body ...)] @defform[(for*/amb (for-clause ...) body ...)] )]{ Iteratively evaluates the given @scheme[body] in context of the @scheme[for-clause]s like @scheme[for] or @scheme[for*] do. The loop is interrupted after each iteration, though, and the result of the last expression of @scheme[body] is returned. The result of the form is ambiguous, since a restart that resumes the loop when backtracking is registered in each iteration. } @defproc[(amb-call [thunk (-> any)] ...) any]{ Given any number of @scheme[thunk] arguments, this procedure behaves like @scheme[(amb (thunk) ...)] would. The @scheme[amb] form is based on this procedure. } @defproc[(amb-fail) any]{ Behaves like @scheme[(amb)] would. The @scheme[amb] form is based on this procedure. } @section{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. @defform[(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 @scheme[exn:fail:amb] is raised. } @defform[(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. } @defform[(in-amb expr ...)]{ Creates a sequence iterating over all possible results of the given ambiguous expressions. This form is conceptually similar to @scheme[(in-list (amb-collect (amb expr ...)))], with two important differences: @itemize{ @item{The evaluation is peformed lazily. Backtracking to produce alternative results is performed only when more elements are requested from the sequence.} @item{The expressions may result in multiple return values that are all passed through by the sequence's element generator.} } } @defproc[(call-with-amb-prompt [thunk (-> any)] [failure-result (-> any) (λ () (raise (make-exn:fail:amb ...)))]) any]{ This procedure behaves like @scheme[(amb-find (thunk))] would, except that @scheme[failure-result] is called to produce the return value(s) of @scheme[call-with-amb-prompt] if no evaluation path in @scheme[thunk] leads to a result. The forms @scheme[amb-find] and @scheme[amb-collect] are based on this procedure. } @defproc[(make-amb-sequence [thunk (-> any)]) sequence?]{ This procedure behaves like @scheme[(in-amb (thunk))] would. The @scheme[in-amb] form is based on this procedure. } @section{Exceptions} @defstruct[(exn:fail:amb exn:fail) () #:transparent]{ 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. } @section{License} Copyright (c) 2008 by @link["mailto:chust@web.de"]{Thomas Chust @""}. 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 @cite{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[ @bib-entry[#:key "t-y-scheme" #:title "Teach Yourself Scheme in Fixnum Days" #:author "Dorai Sitaram" #:url "http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html" #:is-book? #t] @bib-entry[#:key "LGPL" #:title "The GNU Lesser General Public License" #:author "The Free Software Foundation" #:url "http://www.gnu.org/licenses/lgpl-3.0.html"] ]