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

Last change on this file since 36216 was 36216, checked in by Kon Lovett, 2 years ago

rel 3.0.0

File size: 8.6 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
182{{amb-assert}} synonym.
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    ;; They live on different floors.
229    (required (distinct? (list baker cooper fletcher miller smith)))
230
231    ;; Baker does not live on the top floor.
232    (required (not (= baker 5)))
233
234    ;; Cooper does not live on the bottom floor.
235    (required (not (= cooper 1)))
236
237    ;; Fletcher does not live on either the top or the bottom floor.
238    (required (not (= fletcher 5)))
239    (required (not (= fletcher 1)))
240
241    ;; Miller lives on a higher floor than does Cooper.
242    (required (> miller cooper))
243
244    ;; Smith does not live on a floor adjacent to Fletcher's.
245    (required (not (= (abs (- smith fletcher)) 1)))
246
247    ;; Fletcher does not live on a floor adjacent to Cooper's.
248    (required (not (= (abs (- fletcher cooper)) 1)))
249
250    `((baker ,baker) (cooper ,cooper) (fletcher ,fletcher) (miller ,miller) (smith ,smith))) )
251
252(solve-dwelling-puzzle) ;=> ((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
253</enscript>
254
255
256== Notes
257
258* The use of {{amb}}, or {{amb/random}}, without {{amb-collect}} or
259{{amb-find}} can be confusing. See the '''chicken-users''' mailing list for the
260subject "Using the amb egg".
261
262
263== Requirements
264
265[[check-errors]]
266[[condition-utils]]
267
268
269== Author
270
271[[/users/thomas-chust|Thomas Chust]]
272[[/users/kon-lovett|Kon Lovett]]
273
274
275== Version history
276
277; 3.0.0 : CHICKEN 5 release.
278; 2.3.0 : Add {{shuffle}} & {{list-constantly}}.
279; 2.2.0 : Add {{amb-thunks-shuffled}} & {{count-member}}.
280; 2.1.7 : Use test.
281; 2.1.0 : Use of "check-errors" extension.
282; 2.0.0 : Chicken 4 release. [[/users/kon-lovett|Kon Lovett]]
283
284
285== License
286
287Copyright (C) 2009 Thomas Chust <chust@web.de>..  All rights reserved.
288
289Permission is hereby granted, free of charge, to any person obtaining a
290copy of this software and associated documentation files (the Software),
291to deal in the Software without restriction, including without limitation
292the rights to use, copy, modify, merge, publish, distribute, sublicense,
293and/or sell copies of the Software, and to permit persons to whom the
294Software is furnished to do so, subject to the following conditions:
295
296The above copyright notice and this permission notice shall be included
297in all copies or substantial portions of the Software.
298
299THE SOFTWARE IS PROVIDED ASIS, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
300IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
301FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
302THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
303OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
304ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
305OTHER DEALINGS IN THE SOFTWARE.
Note: See TracBrowser for help on using the repository browser.