source: project/release/3/amb/amb.html @ 7753

Last change on this file since 7753 was 435, checked in by Thomas Chust, 14 years ago

[amb] made the egg fit for -check-imports

File size: 12.3 KB
Line 
1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
2<!-- Generated by eggdoc Revision: 1.17  -->
3<html>
4<head>
5<title>Eggs Unlimited - amb</title><style type="text/css"> <!--
6      CODE {
7            color: #666666;
8          }
9/*   DT.definition EM { font-weight: bold; font-style: normal; } */
10
11     DT.definition { 
12                   background: #eee;
13                   color: black;
14                   padding: 0.2em 1em 0.2em 0.7em;
15                   margin-left: 0.2em;
16border: 1px solid #bbc;
17                   font-family: "Andale Mono", monospace;
18                   /* font-size: 1.2em; */
19                   
20                 }
21     DD {
22                   margin-top: 0.8em;
23                   margin-bottom: 0.8em;
24     }
25     DIV.subsection {
26                    border-top: 1px solid #448;
27                    padding-left: 1em;
28     }
29         DIV.section {
30                 margin-bottom: 1.5em;
31         }
32         a:link {
33                 color: #336;
34         }
35         a:visited { color: #666; }
36         a:active  { color: #966; }
37         a:hover   { color: #669; }
38         body { margin: 0; padding: 0; background: #fff; color: #000; font: 9pt "Lucida Grande", "Verdana", sans-serif; }
39         H2 {
40                 background: #336;
41                 color: #fff;
42                 padding-top: 0.5em;
43                 padding-bottom: 0.5em;
44                 padding-left: 16px;
45                 margin: 0 0 1em 0;
46        }
47        LI {
48                list-style: none;
49        }
50        TT {
51                font-family: "Andale Mono", monospace;
52                /* font-size: 1.2em; */
53        }
54        H3 {
55                color: #113;
56                margin-bottom: 0.5em;
57        }
58     DIV#eggheader {
59         text-align: center;
60                 float: right;
61                 margin-right: 2em;
62     }
63     DIV#header IMG {
64            /* display: block; margin-left: auto; margin-right: auto;  */
65            /* float: right; */
66            border: none;  /* firefox */
67     }
68     DIV#footer {
69                background: #bbd;
70                padding: 0.7em ;
71                border-top: 1px solid #cce;
72     }
73     DIV#footer hr {
74                display: none;
75     }
76     DIV#footer a {
77                float: left;
78     }
79     DIV#revision-history {
80         float: right;
81     }
82     
83     DIV#body {
84                 margin: 1em 1em 1em 16px;
85         }
86
87     DIV#examples PRE {
88       background: #eef;
89       padding: 0.1em;
90       border: 1px solid #aac;
91     }
92     PRE#license, DIV#examples PRE {
93       padding: 0.5em;
94     }
95     DIV#examples PRE {
96       /* font-size: 85%; */
97     }
98     PRE { font-family: "Andale Mono", monospace; }
99     TABLE {
100       background: #eef;
101       padding: 0.2em;
102       border: 1px solid #aac;
103       width: 100%;
104     }
105     TABLE.symbol-table TD.symbol {
106          width: 15em;
107          font-family: "Andale Mono", monospace;
108          /* font-size: 1.2em; */
109     }
110     TH {
111       border-bottom: 1px solid black;
112     } --></style></head>
113<body>
114<div id="header">
115<h2>amb</h2>
116<div id="eggheader"><a href="index.html">
117<img src="egg.jpg" alt="[Picture of an egg]" /></a></div></div>
118<div id="body">
119<div class="section">
120<h3>Description</h3>
121<p>The non-deterministic backtracking ambivalence operator</p></div>
122<div class="section">
123<h3>Author</h3><a href="http://www.chust.org/">Thomas Chust</a></div>
124<div class="section">
125<h3>Version</h3>
126<ul>
127<li>1.2.0 Non-determinism now optional, better controllability of scope</li>
128<li>1.1.1 Fixed bug in amb.setup [Thanks to Kon Lovett]</li>
129<li>1.1.0 Renamed <tt>bag-of</tt> to <tt>amb-collect</tt> and added <tt>amb-assert</tt></li>
130<li>1.0.0 Initial release</li></ul></div>
131<div class="section">
132<h3>Usage</h3><tt>(require-extension amb)</tt></div>
133<div class="section">
134<h3>Download</h3><a href="amb.egg">amb.egg</a></div>
135<div class="section">
136<h3>Documentation</h3>
137<p>The <tt>amb</tt> operator is a nice toy and sometimes a useful tool for lightweight logic programming. Its implementation is also a good exercise in the handling of continuations.</p>
138<div class="subsection">
139<p><b>Normal interface</b></p>
140<dl>
141<dt class="definition"><strong>macro:</strong> (amb expr ...) =&gt; &lt;top&gt;</dt>
142<dd>
143<p>In the form <tt>(amb)</tt> the expression always fails.</p>
144<p>If the expression has any parameters, the first one of them is evaluated and the result is returned. If a subsequent occurrence of <tt>amb</tt> fails, though, backtracking may cause the second of the given expressions to be selected for evaluation, then the third and so forth until the whole program does not fail if at all possible.</p>
145<p>The backtracking mechanism is described along with the <tt>amb-failure-continuation</tt> parameter below.</p></dd>
146<dt class="definition"><strong>macro:</strong> (amb/random expr ...) =&gt; &lt;top&gt;</dt>
147<dd>
148<p>Works like <tt>amb</tt> but the parameters are not selected in sequence but randomly. None of them is selected more than once, though.</p></dd>
149<dt class="definition"><strong>macro:</strong> (amb-find expr #!optional failure-value) =&gt; &lt;top&gt;</dt>
150<dd>
151<p>Evaluates <tt>expr</tt> returning its value if successful (possibly after backtracking).</p>
152<p>If <tt>expr</tt> cannot be evaluated successfully and the expression tree is exhausted, <tt>failure-value</tt> is evaluated and the result is returned instead. If no <tt>failure-value</tt> is specified, an exception occurs. See the <tt>amb-failure-continuation</tt> parameter below for a description of the exception.</p></dd>
153<dt class="definition"><strong>macro:</strong> (amb-collect expr) =&gt; &lt;list&gt;</dt>
154<dd>
155<p>Evaluates <tt>expr</tt> and performs backtracking repeatedly until all possible values for it have been accumulated in a list, which is returned.</p></dd>
156<dt class="definition"><strong>macro:</strong> (amb-assert ok?) =&gt; &lt;void&gt;</dt>
157<dd>
158<p>Evaluates <tt>ok?</tt> and fails if it is <tt>#f</tt>.</p></dd></dl></div>
159<div class="subsection">
160<p><b>Additional stuff exported by amb-base</b></p>
161<dl>
162<dt class="definition"><strong>parameter:</strong> amb-failure-continuation</dt>
163<dd>
164<p>Seen in a global context, the <tt>amb</tt> operator transforms the whole program that contains it into a depth first search for return values from <tt>amb</tt> forms that will not cause failure.</p>
165<p>This is realized using a backtracking system that invokes previously stored continuations whenever an <tt>amb</tt> expression fails. The <tt>amb-failure-continuation</tt> parameter is the status variable for this system.</p>
166<p>At the start of the program, or when no further backtracking options are available, this is set to a procedure of no arguments that throws an exception of the composite <tt>(exn amb)</tt> kind (except when a <tt>amb-collect</tt> statement is being processed, where the parameter will point to a procedure signalling <tt>amb-collect</tt> that there are no more backtracking options available).</p>
167<p>In all other cases this parameter is set to a procedure of no arguments that causes backtracking to the next possible alternative in the &quot;tree&quot;.</p>
168<p>If you want to restrict the scope of backtracking to something smaller than the whole past program, use <tt>amb-find</tt> or <tt>amb-collect</tt> which restore this parameter to its original value when they are done evaluating the expressions they were given.</p></dd>
169<dt class="definition"><strong>procedure:</strong> (amb-thunks &lt;list of procedures&gt;) =&gt; &lt;top&gt;</dt>
170<dd>
171<p>The backend of <tt>amb</tt>. <tt>amb</tt> wraps all its parameters into thunks and passes a list of them into this procedure, <tt>amb/random</tt> shuffles the list first.</p></dd>
172<dt class="definition"><strong>procedure:</strong> (amb-find-thunk &lt;procedure&gt; #!optional &lt;procedure&gt;) =&gt; &lt;top&gt;</dt>
173<dd>
174<p>The backend of <tt>amb-find</tt>. <tt>amb-find</tt> wraps its parameters into thunks and passes them into this procedure.</p></dd>
175<dt class="definition"><strong>procedure:</strong> (amb-collect-thunk &lt;procedure&gt;) =&gt; &lt;list&gt;</dt>
176<dd>
177<p>The backend of <tt>amb-collect</tt>. <tt>amb-collect</tt> wraps its parameter into a thunk and passes it into this procedure.</p></dd></dl></div>
178<div class="section">
179<h3>Examples</h3>
180<div id="examples">
181<p>The following code is a rewrite of an example from the book &quot;Teach Yourself Scheme in Fixnum Days&quot; by Dorai Sitaram. The book gives the following problem setting:</p><em>
182<p>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.</p>
183<p>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: &quot;Are you a boy?&quot; Kibi answers in Kalotan, which of course Worf doesn't understand.</p>
184<p>Worf turns to the parents (who know English) for explanation. One of them says: &quot;Kibi said: 'I am a boy.'&quot; The other adds: &quot;Kibi is a girl. Kibi lied.&quot;</p>
185<p>Solve for the sex of the parents and Kibi.</p></em>
186<p>So here is the solution:</p><pre>
187<i><font color="#B22222">;;;; amb-demo.scm
188</font></i><i><font color="#B22222">;;;; A solution for the Kalotan puzzle using amb
189</font></i>
190(require-extension amb)
191
192(<b><font color="#A020F0">define</font></b> (<b><font color="#0000FF">xor</font></b> a? b?)
193  (<b><font color="#A020F0">if</font></b> (<b><font color="#A020F0">and</font></b> a? b?) #f (<b><font color="#A020F0">or</font></b> a? b?)))
194
195(<b><font color="#A020F0">define</font></b> (<b><font color="#0000FF">solve-kalotan-puzzle</font></b>)
196  (<b><font color="#A020F0">let</font></b> ((parent1 (amb 'm 'f))
197        (parent2 (amb 'm 'f))
198        (kibi (amb 'm 'f))
199        (kibi-self-desc (amb 'm 'f))
200        (kibi-lied? (amb #t #f)))
201    (amb-assert
202     (not (eq? parent1 parent2)))
203    (<b><font color="#A020F0">if</font></b> kibi-lied?
204        (amb-assert
205         (xor
206          (<b><font color="#A020F0">and</font></b> (eqv? kibi-self-desc 'm)
207               (eqv? kibi 'f))
208          (<b><font color="#A020F0">and</font></b> (eqv? kibi-self-desc 'f)
209               (eqv? kibi 'm)))))
210    (<b><font color="#A020F0">if</font></b> (not kibi-lied?)
211        (amb-assert
212         (xor
213          (<b><font color="#A020F0">and</font></b> (eqv? kibi-self-desc 'm)
214               (eqv? kibi 'm))
215          (<b><font color="#A020F0">and</font></b> (eqv? kibi-self-desc 'f)
216               (eqv? kibi 'f)))))
217    (<b><font color="#A020F0">if</font></b> (eqv? parent1 'm)
218        (amb-assert
219         (<b><font color="#A020F0">and</font></b>
220          (eqv? kibi-self-desc 'm)
221          (xor
222           (<b><font color="#A020F0">and</font></b> (eqv? kibi 'f)
223                (eqv? kibi-lied? #f))
224           (<b><font color="#A020F0">and</font></b> (eqv? kibi 'm)
225                (eqv? kibi-lied? #t))))))
226    (<b><font color="#A020F0">if</font></b> (eqv? parent1 'f)
227        (amb-assert
228         (<b><font color="#A020F0">and</font></b>
229          (eqv? kibi 'f)
230          (eqv? kibi-lied? #t))))
231    (list parent1 parent2 kibi)))
232
233(write (amb-collect (solve-kalotan-puzzle)))
234(newline)
235</pre></div></div>
236<div class="section">
237<h3>License</h3>
238<pre id="license">Copyright (c) 2005, Thomas Chust &lt;chust@web.de&gt;.  All rights reserved.
239
240Redistribution and use in source and binary forms, with or without
241modification, are permitted provided that the following conditions are met:
242
243  Redistributions of source code must retain the above copyright notice,
244  this list of conditions and the following disclaimer. Redistributions in
245  binary form must reproduce the above copyright notice, this list of
246  conditions and the following disclaimer in the documentation and/or
247  other materials provided with the distribution. Neither the name of the
248  author nor the names of its contributors may be used to endorse or
249  promote products derived from this software without specific prior
250  written permission.
251
252THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS &quot;AS
253IS&quot; AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
254THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
255PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
256CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
257EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
258PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
259PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
260LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
261NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
262SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.</pre></div></div></div>
263<div id="footer">
264<hr /><a href="index.html">&lt; Egg index</a>
265<div id="revision-history">$Revision$ $Date$</div>&nbsp;</div></body></html>
Note: See TracBrowser for help on using the repository browser.