source: project/wiki/eggref/5/amb @ 39048

Last change on this file since 39048 was 39048, checked in by Kon Lovett, 2 months ago

rel 3.0.2

File size: 8.7 KB
Line 
1[[tags: egg]]
2
3== amb
4
5The Non-Deterministic Backtracking Ambivalence Operator
6
7[[toc:]]
8
9
10== Documentation
11
12The {{amb}} operator is a nice toy and sometimes a useful tool for
13lightweight logic programming. Its implementation is also a good exercise in
14the handling of continuations.
15
16Installs the ''amb'', and the ''amb-extras'' extension, plus examples.
17
18=== Usage
19
20<enscript language=scheme>
21(import amb)
22</enscript>
23
24=== amb-random-function
25
26<procedure>(amb-random-function) -> procedure</procedure>
27<procedure>(amb-random-function RAND)</procedure>
28
29The random function {{parameter}}. Default is {{(chicken random) pseudo-random-integer}}.
30
31=== amb-failure-continuation
32
33<procedure>(amb-failure-continuation) -> STATUS-VARIABLE</procedure>
34<procedure>(amb-failure-continuation STATUS-VARIABLE)</procedure>
35
36Seen in a global context, the {{amb}} operator transforms the whole program
37that contains it into a depth first search for return values from {{amb}} forms
38that will not cause failure.
39
40This is realized using a backtracking system that invokes previously stored
41continuations whenever an {{amb}} expression fails. The
42{{amb-failure-continuation}} parameter is the status variable for this system.
43
44At the start of the program, or when no further backtracking options are
45available, this is set to a procedure of no arguments that raises an exception
46condition {{(exn amb)}} (except when a {{amb-collect}} statement is being
47processed, where the parameter will point to a procedure signalling
48{{amb-collect}} that there are no more backtracking options available).
49
50In all other cases this parameter is set to a procedure of no arguments that
51causes backtracking to the next possible alternative in the ''tree''.
52
53If you want to restrict the scope of backtracking to something smaller than the
54whole past program, use {{amb-find}} or {{amb-collect}} which restore this
55parameter to its original value when they are done evaluating the expressions
56they were given.
57
58=== amb
59
60<syntax>(amb EXPRESSION...) -> TOP</syntax>
61
62If the {{EXPRESSION}} has any parameters, the first one of them is evaluated
63and the result is returned. If a subsequent occurrence of {{amb}} fails,
64though, backtracking may cause the second of the given {{EXPRESSION...}} to be
65selected for evaluation, then the third and so forth until the whole program
66does not fail if at all possible.
67
68The form {{(amb)}} always fails.
69
70=== amb/random
71
72<syntax>(amb/random EXPRESSION...) -> TOP</syntax>
73
74Works like {{amb}} but the parameters are not selected in sequence but
75randomly. None of them is selected more than once, though.
76
77=== amb-find
78
79<syntax>(amb-find EXPRESSION [FAILURE-VALUE]) -> *</syntax>
80
81Evaluates {{EXPRESSION}} returning its value if successful (possibly after
82backtracking).
83
84If {{EXPRESSION}} cannot be evaluated successfully and the expression tree is
85exhausted, {{FAILURE-VALUE}} is evaluated and the result is returned instead.
86
87If no {{FAILURE-VALUE}} is specified, an exception occurs. See the
88{{amb-failure-continuation}} parameter below for a description of the
89exception.
90
91=== amb-collect
92
93<syntax>(amb-collect EXPRESSION) -> list</syntax>
94
95Evaluates {{EXPRESSION}} and performs backtracking repeatedly until all possible
96values for it have been accumulated in a list, which is returned.
97
98=== amb-assert
99
100<syntax>(amb-assert OK?)</syntax>
101
102Evaluates {{OK?}} and fails when {{#f}}.
103
104=== amb-thunks
105
106<procedure>(amb-thunks THUNKS) -> TOP</procedure>
107
108The backend of {{amb}}.
109
110{{amb}} wraps all its parameters into thunks and passes a list of them into
111this procedure, {{amb/random}} shuffles the list first.
112
113=== amb-thunks-shuffled
114
115<procedure>(amb-thunks-shuffled THUNKS) -> TOP</procedure>
116
117As {{amb-thunks}} after {{(shuffle THUNKS
118
119=== amb-find-thunk
120
121<procedure>(amb-find-thunk THUNK [FAILURE]) -> TOP</procedure>
122
123The backend of {{amb-find}}.
124
125{{amb-find}} wraps its parameters into thunks and passes them into this
126procedure.
127
128=== amb-collect-thunk
129
130<procedure>(amb-collect-thunk THUNK) -> list</procedure>
131
132The backend of {{amb-collect}}.
133
134{{amb-collect}} wraps its parameter into a thunk and passes it into this
135procedure.
136
137==== shuffle
138
139<procedure>(shuffle LS RAND) -> list</procedure>
140
141Returns a new {{list}} from the randomly-shuffled elements of {{LS}}.
142
143{{RAND}} is a procedure returning a random {{integer}} in {{[0, N-1]}}.
144
145
146=== Extension ''amb-extras''
147
148==== Usage
149
150<enscript language=scheme>
151(import amb-extras)
152</enscript>
153
154==== amb1
155
156<syntax>(amb1 LS) -> TOP</syntax>
157
158{{amb}} but with a single list argument {{LS}}.
159
160==== choose
161
162<syntax>(choose LS) -> TOP</syntax>
163
164{{amb/random}} but with a single list argument {{LS}}.
165
166==== one-of
167
168<syntax>(one-of EXPRESSION) -> *</syntax>
169
170{{amb-find}} synonym.
171
172==== all-of
173
174<syntax>(all-of EXPRESSION) -> list</syntax>
175
176{{amb-collect}} synonym.
177
178==== required
179
180<syntax>(required EXPRESSION ...)</syntax>
181
182Conjunction of {{(amb-assert EXPRESSION) ...}}.
183
184==== distinct?
185
186<procedure>(distinct? LS [eql? equal?]) -> boolean</procedure>
187
188Is, using {{eql?}} for comparison, {{LS}} a {{list}} of distinct elements?
189
190==== count-member
191
192<procedure>(count-member OBJECT LS [eql? equal?]) -> integer</procedure>
193
194Returns, using {{eql?}} for comparison, the number of times {{OBJECT}}
195referenced in {{LS}}.
196
197==== list-constantly
198
199<procedure>(list-constantly LS) -> list</procedure>
200
201Returns a new list where each element, {{ELT}}, of {{LS}} is represented by
202{{(constantly ELT)}}.
203
204
205== Examples
206
207<enscript language=scheme>
208(import amb amb-extras)
209
210;; Baker, Cooper, Fletcher, Miller, and Smith live on different
211;; floors of an apartment house that contains only five floors. Baker
212;; does not live on the top floor. Cooper does not live on the bottom
213;; floor. Fletcher does not live on either the top or the bottom
214;; floor. Miller lives on a higher floor than does Cooper. Smith does not
215;; live on a floor adjacent to Fletcher's. Fletcher does not live on a
216;; floor adjacent to Cooper's.
217;;
218;; Where does everyone live?
219
220(define (solve-dwelling-puzzle)
221
222  (let ((baker    (amb 1 2 3 4 5))
223        (cooper   (amb 1 2 3 4 5))
224        (fletcher (amb 1 2 3 4 5))
225        (miller   (amb 1 2 3 4 5))
226        (smith    (amb 1 2 3 4 5)) )
227
228    (required
229      ;
230      ; They live on different floors.
231      (distinct? (list baker cooper fletcher miller smith))
232      ;
233      ; Baker does not live on the top floor.
234      (not (= baker 5))
235      ;
236      ; Cooper does not live on the bottom floor.
237      (not (= cooper 1))
238      ;
239      ; Fletcher does not live on either the top or the bottom floor.
240      (not (= fletcher 5))
241      (not (= fletcher 1))
242      ;
243      ; Miller lives on a higher floor than does Cooper.
244      (> miller cooper)
245      ;
246      ; Smith does not live on a floor adjacent to Fletcher's.
247      (not (= (abs (- smith fletcher)) 1))
248      ;
249      ; Fletcher does not live on a floor adjacent to Cooper's.
250      (not (= (abs (- fletcher cooper)) 1)) )
251
252    `((baker    ,baker)
253      (cooper   ,cooper)
254      (fletcher ,fletcher)
255      (miller   ,miller)
256      (smith    ,smith))) )
257
258(solve-dwelling-puzzle) ;=> ((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
259</enscript>
260
261
262== Notes
263
264* The use of {{amb}}, or {{amb/random}}, without {{amb-collect}} or
265{{amb-find}} can be confusing. See the '''chicken-users''' mailing list for the
266subject "Using the amb egg".
267
268
269== Requirements
270
271[[srfi-1]]
272
273
274== Author
275
276[[/users/thomas-chust|Thomas Chust]]
277[[/users/kon-lovett|Kon Lovett]]
278
279
280== Version history
281
282; 3.0.2 : Remove dependencies, add {{srfi-1}}.
283; 3.0.1 : .
284; 3.0.0 : CHICKEN 5 release.
285; 2.3.0 : Add {{shuffle}} & {{list-constantly}}.
286; 2.2.0 : Add {{amb-thunks-shuffled}} & {{count-member}}.
287; 2.1.7 : Use test.
288; 2.1.0 : Use of "check-errors" extension.
289; 2.0.0 : Chicken 4 release. [[/users/kon-lovett|Kon Lovett]]
290
291
292== License
293
294Copyright (C) 2009 Thomas Chust <chust@web.de>..  All rights reserved.
295
296Permission is hereby granted, free of charge, to any person obtaining a
297copy of this software and associated documentation files (the Software),
298to deal in the Software without restriction, including without limitation
299the rights to use, copy, modify, merge, publish, distribute, sublicense,
300and/or sell copies of the Software, and to permit persons to whom the
301Software is furnished to do so, subject to the following conditions:
302
303The above copyright notice and this permission notice shall be included
304in all copies or substantial portions of the Software.
305
306THE SOFTWARE IS PROVIDED ASIS, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
307IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
308FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
309THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
310OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
311ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
312OTHER DEALINGS IN THE SOFTWARE.
Note: See TracBrowser for help on using the repository browser.