forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-28.html
1749 lines (1306 loc) · 90.4 KB
/
book-Z-H-28.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http:https://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http:https://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta name="generator" content="HTML Tidy for Linux (vers 7 December 2008), see www.w3.org" />
<title>Structure and Interpretation of Computer Programs</title>
<link href="book-Z-C.css" title="default" rel="stylesheet" type="text/css" />
<meta name="robots" content="noindex,follow" />
</head>
<body>
<mbp:pagebreak />
<p><a name="%_sec_4.3"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_4.3">4.3 Variations on a
Scheme -- Nondeterministic Computing</a></h2>
<p><a name="%_idx_4806"></a> <a name="%_idx_4808"></a>In this
section, we extend the Scheme evaluator to support a programming
paradigm called <em>nondeterministic computing</em> by building
into the evaluator a facility to support automatic search. This
is a much more profound change to the language than the
introduction of lazy evaluation in section <a href="book-Z-H-27.html#%_sec_4.2">4.2</a>.</p>
<p><a name="%_idx_4810"></a>Nondeterministic computing, like
stream processing, is useful for ``generate and test''
applications. Consider the task of starting with two lists of
positive integers and finding a pair of integers -- one from the
first list and one from the second list -- whose sum is prime. We
saw how to handle this with finite sequence operations in
section <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a> and
with infinite streams in section <a href="book-Z-H-24.html#%_sec_3.5.3">3.5.3</a>. Our approach was to
generate the sequence of all possible pairs and filter these to
select the pairs whose sum is prime. Whether we actually generate
the entire sequence of pairs first as in chapter 2, or
interleave the generating and filtering as in chapter 3, is
immaterial to the essential image of how the computation is
organized.</p>
<p><a name="%_idx_4812"></a>The nondeterministic approach evokes
a different image. Imagine simply that we choose (in some way) a
number from the first list and a number from the second list and
require (using some mechanism) that their sum be prime. This is
expressed by following procedure:</p>
<p><tt><a name="%_idx_4814"></a>(define (prime-sum-pair list1 list2)<br />
(let ((a (an-element-of list1))<br />
(b (an-element-of list2)))<br />
(require (prime? (+ a b)))<br />
(list a b)))<br /></tt></p>
<p>It might seem as if this procedure merely restates the
problem, rather than specifying a way to solve it. Nevertheless,
this is a legitimate nondeterministic program.<a href="#footnote_Temp_598" name="call_footnote_Temp_598" id="call_footnote_Temp_598"><sup><small>42</small></sup></a></p>
<p>The key idea here is that expressions in a nondeterministic
language can have more than one possible value. For instance,
<tt>an-element-of</tt> might return any element of the given
list. Our nondeterministic program evaluator will work by
automatically choosing a possible value and keeping track of the
choice. If a subsequent requirement is not met, the evaluator
will try a different choice, and it will keep trying new choices
until the evaluation succeeds, or until we run out of choices.
Just as the lazy evaluator freed the programmer from the details
of how values are delayed and forced, the nondeterministic
program evaluator will free the programmer from the details of
how choices are made.</p>
<p><a name="%_idx_4820"></a>It is instructive to contrast the
different images of time evoked by nondeterministic evaluation
and stream processing. Stream processing uses lazy evaluation to
decouple the time when the stream of possible answers is
assembled from the time when the actual stream elements are
produced. The evaluator supports the illusion that all the
possible answers are laid out before us in a timeless sequence.
With nondeterministic evaluation, an expression represents the
exploration of a set of possible worlds, each determined by a set
of choices. Some of the possible worlds lead to dead ends, while
others have useful values. The nondeterministic program evaluator
supports the illusion that time branches, and that our programs
have different possible execution histories. When we reach a dead
end, we can revisit a previous choice point and proceed along a
different branch.</p>
<p>The nondeterministic program evaluator implemented below is
called the <tt>amb</tt> evaluator because it is based on a new
special form called <tt>amb</tt>. We can type the above
definition of <tt>prime-sum-pair</tt> at the <tt>amb</tt>
evaluator driver loop (along with definitions of <tt>prime?</tt>,
<tt>an-element-of</tt>, and <tt>require</tt>) and run the
procedure as follows:</p>
<p><tt><i>;;; Amb-Eval input:</i><br />
(prime-sum-pair '(1 3 5 8) '(20 35 110))<br />
<i>;;; Starting a new problem</i><br />
<i>;;; Amb-Eval value:</i><br />
<i>(3 20)</i><br /></tt></p>
<p>The value returned was obtained after the evaluator repeatedly
chose elements from each of the lists, until a successful choice
was made.</p>
<p>Section <a href="#%_sec_4.3.1">4.3.1</a> introduces
<tt>amb</tt> and explains how it supports nondeterminism through
the evaluator's automatic search mechanism. Section <a href="#%_sec_4.3.2">4.3.2</a> presents examples of nondeterministic
programs, and section <a href="#%_sec_4.3.3">4.3.3</a> gives
the details of how to implement the <tt>amb</tt> evaluator by
modifying the ordinary Scheme evaluator.</p>
<p><a name="%_sec_4.3.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.3.1">4.3.1 Amb and
Search</a></h3>
<p><a name="%_idx_4822"></a>To extend Scheme to support
nondeterminism, we introduce a new special form called
<tt>amb</tt>.<a href="#footnote_Temp_599" name="call_footnote_Temp_599" id="call_footnote_Temp_599"><sup><small>43</small></sup></a> The
expression <tt>(amb <<em><em>e</em><sub>1</sub></em>>
<<em><em>e</em><sub>2</sub></em>> <tt>...</tt>
<<em><em>e</em><sub><em>n</em></sub></em>>)</tt> returns
the value of one of the <em>n</em> expressions
<<em><em>e</em><sub><em>i</em></sub></em>> ``ambiguously.''
For example, the expression</p>
<p>
<tt>(list (amb 1 2 3) (amb 'a 'b))<br />
</tt></p>
<p>can have six possible values:</p>
<table border="0">
<tr>
<td valign="top"><tt>(1 a)</tt></td>
<td valign="top"><tt>(1 b)</tt></td>
<td valign="top"><tt>(2 a)</tt></td>
<td valign="top"><tt>(2 b)</tt></td>
<td valign="top"><tt>(3 a)</tt></td>
<td valign="top"><tt>(3 b)</tt></td>
</tr>
</table><tt>Amb</tt> with a single choice produces an ordinary
(single) value.
<p><a name="%_idx_4826"></a><tt>Amb</tt> with no choices -- the
expression <tt>(amb)</tt> -- is an expression with no acceptable
values. Operationally, we can think of <tt>(amb)</tt> as an
expression that when evaluated causes the computation to
``fail'': The computation aborts and no value is produced. Using
this idea, we can express the requirement that a particular
predicate expression <tt>p</tt> must be true as follows:</p>
<p><tt><a name="%_idx_4828"></a>(define (require p)<br />
(if (not p) (amb)))<br /></tt></p>
<p>With <tt>amb</tt> and <tt>require</tt>, we can implement the
<tt>an-element-of</tt> procedure used above:</p>
<p><tt><a name="%_idx_4830"></a>(define (an-element-of items)<br />
(require (not (null? items)))<br />
(amb (car items) (an-element-of (cdr items))))<br />
</tt></p>
<p><tt>An-element-of</tt> fails if the list is empty. Otherwise
it ambiguously returns either the first element of the list or an
element chosen from the rest of the list.</p>
<p>We can also express infinite ranges of choices. The following
procedure potentially returns any integer greater than or equal
to some given <em>n</em>:</p>
<p><tt><a name="%_idx_4832"></a>(define (an-integer-starting-from n)<br />
(amb n (an-integer-starting-from (+ n 1))))<br />
</tt></p>
<p>This is like the stream procedure
<tt>integers-starting-from</tt> described in
section <a href="book-Z-H-24.html#%_sec_3.5.2">3.5.2</a>,
but with an important difference: The stream procedure returns an
object that represents the sequence of all integers beginning
with <em>n</em>, whereas the <tt>amb</tt> procedure returns a
single integer.<a href="#footnote_Temp_600" name="call_footnote_Temp_600" id="call_footnote_Temp_600"><sup><small>44</small></sup></a></p>
<p><a name="%_idx_4834"></a>Abstractly, we can imagine that
evaluating an <tt>amb</tt> expression causes time to split into
branches, where the computation continues on each branch with one
of the possible values of the expression. We say that
<tt>amb</tt> represents a <a name="%_idx_4836"></a><em>nondeterministic choice point</em>. If we
had a machine with a sufficient number of processors that could
be dynamically allocated, we could implement the search in a
straightforward way. Execution would proceed as in a sequential
machine, until an <tt>amb</tt> expression is encountered. At this
point, more processors would be allocated and initialized to
continue all of the parallel executions implied by the choice.
Each processor would proceed sequentially as if it were the only
choice, until it either terminates by encountering a failure, or
it further subdivides, or it finishes.<a href="#footnote_Temp_601" name="call_footnote_Temp_601" id="call_footnote_Temp_601"><sup><small>45</small></sup></a></p>
<p><a name="%_idx_4840"></a>On the other hand, if we have a
machine that can execute only one process (or a few concurrent
processes), we must consider the alternatives sequentially. One
could imagine modifying an evaluator to pick at random a branch
to follow whenever it encounters a choice point. Random choice,
however, can easily lead to failing values. We might try running
the evaluator over and over, making random choices and hoping to
find a non-failing value, but it is better to <a name="%_idx_4842"></a><a name="%_idx_4844"></a><em>systematically
search</em> all possible execution paths. The <tt>amb</tt>
evaluator that we will develop and work with in this section
implements a systematic search as follows: When the evaluator
encounters an application of <tt>amb</tt>, it initially selects
the first alternative. This selection may itself lead to a
further choice. The evaluator will always initially choose the
first alternative at each choice point. If a choice results in a
failure, then the evaluator <a name="%_idx_4846"></a><a name="%_idx_4848"></a><a name="%_idx_4850"></a>automagically<a href="#footnote_Temp_602" name="call_footnote_Temp_602" id="call_footnote_Temp_602"><sup><small>46</small></sup></a>
<a name="%_idx_4852"></a><em>backtracks</em> to the most recent
choice point and tries the next alternative. If it runs out of
alternatives at any choice point, the evaluator will back up to
the previous choice point and resume from there. This process
leads to a search strategy known as <a name="%_idx_4854"></a><a name="%_idx_4856"></a><a name="%_idx_4858"></a><em>depth-first search</em> or <em>chronological
backtracking</em>.<a href="#footnote_Temp_603" name="call_footnote_Temp_603" id="call_footnote_Temp_603"><sup><small>47</small></sup></a></p>
<p><a name="%_sec_Temp_604"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_604">Driver
loop</a></h4>
<p><a name="%_idx_4908"></a>The driver loop for the <tt>amb</tt>
evaluator has some unusual properties. It reads an expression and
prints the value of the first non-failing execution, as in the
<tt>prime-sum-pair</tt> example shown above. If we want to see
the value of the next successful execution, we can ask the
interpreter to backtrack and attempt to generate a second
non-failing execution. This is signaled by typing the symbol
<a name="%_idx_4910"></a><tt>try-again</tt>. If any expression
except <tt>try-again</tt> is given, the interpreter will start a
new problem, discarding the unexplored alternatives in the
previous problem. Here is a sample interaction:</p>
<p><tt><i>;;; Amb-Eval input:</i><br />
(prime-sum-pair '(1 3 5 8) '(20 35 110))<br />
<i>;;; Starting a new problem</i><br />
<i>;;; Amb-Eval value:</i><br />
<i>(3 20)</i><br />
<i>;;; Amb-Eval input:</i><br />
try-again<br />
<i>;;; Amb-Eval value:</i><br />
<i>(3 110)</i><br />
<i>;;; Amb-Eval input:</i><br />
try-again<br />
<i>;;; Amb-Eval value:</i><br />
<i>(8 35)</i><br />
<i>;;; Amb-Eval input:</i><br />
try-again<br />
<i>;;; There are no more values of</i><br />
<i>(prime-sum-pair (quote (1 3 5 8)) (quote (20 35 110)))</i><br />
<i>;;; Amb-Eval input:</i><br />
(prime-sum-pair '(19 27 30) '(11 36 58))<br />
<i>;;; Starting a new problem</i><br />
<i>;;; Amb-Eval value:</i><br />
<i>(30 11)</i><br /></tt></p>
<p><a name="%_thm_4.35"></a> <b>Exercise
4.35.</b> <a name="%_idx_4912"></a><a name="%_idx_4914"></a>Write a procedure <tt>an-integer-between</tt>
that returns an integer between two given bounds. This can be
used to implement a procedure that finds Pythagorean triples,
i.e., triples of integers (<em>i</em>,<em>j</em>,<em>k</em>)
between the given bounds such that <em>i</em> <u><</u>
<em>j</em> and <em>i</em><sup>2</sup> + <em>j</em><sup>2</sup> =
<em>k</em><sup>2</sup>, as follows:</p>
<p>
<tt>(define (a-pythagorean-triple-between low high)<br />
(let ((i (an-integer-between low high)))<br />
(let ((j (an-integer-between i high)))<br />
(let ((k (an-integer-between j high)))<br />
(require (= (+ (* i i) (* j j)) (* k k)))<br />
(list i j k)))))<br />
</tt></p>
<p><a name="%_thm_4.36"></a> <b>Exercise
4.36.</b> <a name="%_idx_4916"></a><a name="%_idx_4918"></a>Exercise <a href="book-Z-H-24.html#%_thm_3.69">3.69</a> discussed how to generate
the stream of <em>all</em> Pythagorean triples, with no upper
bound on the size of the integers to be searched. Explain why
simply replacing <tt>an-integer-between</tt> by
<tt>an-integer-starting-from</tt> in the procedure in
exercise <a href="#%_thm_4.35">4.35</a> is not an adequate
way to generate arbitrary Pythagorean triples. Write a procedure
that actually will accomplish this. (That is, write a procedure
for which repeatedly typing <tt>try-again</tt> would in principle
eventually generate all Pythagorean triples.)</p>
<p><a name="%_thm_4.37"></a> <b>Exercise
4.37.</b> <a name="%_idx_4920"></a><a name="%_idx_4922"></a>Ben Bitdiddle claims that the following method
for generating Pythagorean triples is more efficient than the one
in exercise <a href="#%_thm_4.35">4.35</a>. Is he correct?
(Hint: Consider the number of possibilities that must be
explored.)</p>
<p>
<tt>(define (a-pythagorean-triple-between low high)<br />
(let ((i (an-integer-between low high))<br />
(hsq (* high high)))<br />
(let ((j (an-integer-between i high)))<br />
(let ((ksq (+ (* i i) (* j j))))<br />
(require (>= hsq ksq))<br />
(let ((k (sqrt ksq)))<br />
(require (integer? k))<br />
(list i j k))))))<br />
</tt></p>
<p><a name="%_sec_4.3.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.3.2">4.3.2 Examples of
Nondeterministic Programs</a></h3>
<p>Section <a href="#%_sec_4.3.3">4.3.3</a> describes the
implementation of the <tt>amb</tt> evaluator. First, however, we
give some examples of how it can be used. The advantage of
nondeterministic programming is that we can suppress the details
of how search is carried out, thereby <a name="%_idx_4924"></a>expressing our programs at a higher level of
abstraction.</p>
<p><a name="%_sec_Temp_608"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_608">Logic
Puzzles</a></h4>
<p><a name="%_idx_4926"></a><a name="%_idx_4928"></a><a name="%_idx_4930"></a> <a name="%_idx_4932"></a>The following puzzle
(taken from Dinesman 1968) is typical of a large class of simple
logic puzzles:</p>
<blockquote>
Baker, Cooper, Fletcher, Miller, and Smith live on different
floors of an apartment house that contains only five floors.
Baker does not live on the top floor. Cooper does not live on
the bottom floor. Fletcher does not live on either the top or
the bottom floor. Miller lives on a higher floor than does
Cooper. Smith does not live on a floor adjacent to Fletcher's.
Fletcher does not live on a floor adjacent to Cooper's. Where
does everyone live?
</blockquote>
<p>We can determine who lives on each floor in a straightforward
way by enumerating all the possibilities and imposing the given
restrictions:<a href="#footnote_Temp_609" name="call_footnote_Temp_609" id="call_footnote_Temp_609"><sup><small>48</small></sup></a></p>
<p><tt><a name="%_idx_4938"></a>(define (multiple-dwelling)<br />
(let ((baker (amb 1 2 3 4 5))<br />
(cooper (amb 1 2 3 4 5))<br />
(fletcher (amb 1 2 3 4 5))<br />
(miller (amb 1 2 3 4 5))<br />
(smith (amb 1 2 3 4 5)))<br />
(require<br />
(distinct? (list baker cooper fletcher miller smith)))<br />
(require (not (= baker 5)))<br />
(require (not (= cooper 1)))<br />
(require (not (= fletcher 5)))<br />
(require (not (= fletcher 1)))<br />
(require (> miller cooper))<br />
(require (not (= (abs (- smith fletcher)) 1)))<br />
(require (not (= (abs (- fletcher cooper)) 1)))<br />
(list (list 'baker baker)<br />
(list 'cooper cooper)<br />
(list 'fletcher fletcher)<br />
(list 'miller miller)<br />
(list 'smith smith))))<br />
</tt></p>
<p>Evaluating the expression <tt>(multiple-dwelling)</tt>
produces the result</p>
<p>
<tt>((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))<br />
</tt></p>
<p>Although this simple procedure works, it is very slow.
Exercises <a href="#%_thm_4.39">4.39</a> and <a href="#%_thm_4.40">4.40</a> discuss some possible improvements.</p>
<p><a name="%_thm_4.38"></a> <b>Exercise
4.38.</b> Modify the multiple-dwelling procedure to
omit the requirement that Smith and Fletcher do not live on
adjacent floors. How many solutions are there to this modified
puzzle?</p>
<p><a name="%_thm_4.39"></a> <b>Exercise
4.39.</b> Does the order of the restrictions in the
multiple-dwelling procedure affect the answer? Does it affect the
time to find an answer? If you think it matters, demonstrate a
faster program obtained from the given one by reordering the
restrictions. If you think it does not matter, argue your
case.</p>
<p><a name="%_thm_4.40"></a> <b>Exercise 4.40.</b> In
the multiple dwelling problem, how many sets of assignments are
there of people to floors, both before and after the requirement
that floor assignments be distinct? It is very inefficient to
generate all possible assignments of people to floors and then
leave it to backtracking to eliminate them. For example, most of
the restrictions depend on only one or two of the person-floor
variables, and can thus be imposed before floors have been
selected for all the people. Write and demonstrate a much more
efficient nondeterministic procedure that solves this problem
based upon generating only those possibilities that are not
already ruled out by previous restrictions. (Hint: This will
require a nest of <tt>let</tt> expressions.)</p>
<p><a name="%_thm_4.41"></a> <b>Exercise
4.41.</b> <a name="%_idx_4940"></a>Write an ordinary
Scheme program to solve the multiple dwelling puzzle.</p>
<p><a name="%_thm_4.42"></a> <b>Exercise
4.42.</b> <a name="%_idx_4942"></a>Solve the following
``Liars'' puzzle (from Phillips 1934):</p>
<blockquote>
Five schoolgirls sat for an examination. Their parents -- so
they thought -- showed an undue degree of interest in the
result. They therefore agreed that, in writing home about the
examination, each girl should make one true statement and one
untrue one. The following are the relevant passages from their
letters:
<ul>
<li>Betty: ``Kitty was second in the examination. I was only
third.''</li>
<li>Ethel: ``You'll be glad to hear that I was on top. Joan
was second.''</li>
<li>Joan: ``I was third, and poor old Ethel was
bottom.''</li>
<li>Kitty: ``I came out second. Mary was only fourth.''</li>
<li>Mary: ``I was fourth. Top place was taken by
Betty.''</li>
</ul>
<p>What in fact was the order in which the five girls were
placed?</p>
</blockquote>
<p><a name="%_thm_4.43"></a> <b>Exercise 4.43.</b> Use
the <tt>amb</tt> evaluator to solve the following puzzle:<a href="#footnote_Temp_616" name="call_footnote_Temp_616" id="call_footnote_Temp_616"><sup><small>49</small></sup></a></p>
<blockquote>
Mary Ann Moore's father has a yacht and so has each of his four
friends: Colonel Downing, Mr. Hall, Sir Barnacle Hood, and Dr.
Parker. Each of the five also has one daughter and each has
named his yacht after a daughter of one of the others. Sir
Barnacle's yacht is the Gabrielle, Mr. Moore owns the Lorna;
Mr. Hall the Rosalind. The Melissa, owned by Colonel Downing,
is named after Sir Barnacle's daughter. Gabrielle's father owns
the yacht that is named after Dr. Parker's daughter. Who is
Lorna's father?
</blockquote>Try to write the program so that it runs efficiently
(see exercise <a href="#%_thm_4.40">4.40</a>). Also
determine how many solutions there are if we are not told that
Mary Ann's last name is Moore.
<p><a name="%_thm_4.44"></a> <b>Exercise
4.44.</b> <a name="%_idx_4944"></a><a name="%_idx_4946"></a><a name="%_idx_4948"></a><a name="%_idx_4950"></a>Exercise <a href="book-Z-H-15.html#%_thm_2.42">2.42</a> described the
``eight-queens puzzle'' of placing queens on a chessboard so that
no two attack each other. Write a nondeterministic program to
solve this puzzle.</p>
<p><a name="%_sec_Temp_618"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_618">Parsing
natural language</a></h4>
<p><a name="%_idx_4952"></a><a name="%_idx_4954"></a> Programs
designed to accept natural language as input usually start by
attempting to <em>parse</em> the input, that is, to match the
input against some grammatical structure. For example, we might
try to recognize simple sentences consisting of an article
followed by a noun followed by a verb, such as ``The cat eats.''
To accomplish such an analysis, we must be able to identify the
parts of speech of individual words. We could start with some
lists that classify various words:<a href="#footnote_Temp_619" name="call_footnote_Temp_619" id="call_footnote_Temp_619"><sup><small>50</small></sup></a></p>
<p><tt><a name="%_idx_4956"></a>(define nouns '(noun student professor cat class))<br />
<a name="%_idx_4958"></a>(define verbs '(verb studies lectures eats sleeps))<br />
<a name="%_idx_4960"></a>(define articles '(article the a))<br />
</tt></p>
<p><a name="%_idx_4962"></a>We also need a <em>grammar</em>, that
is, a set of rules describing how grammatical elements are
composed from simpler elements. A very simple grammar might
stipulate that a sentence always consists of two pieces -- a noun
phrase followed by a verb -- and that a noun phrase consists of
an article followed by a noun. With this grammar, the sentence
``The cat eats'' is parsed as follows:</p>
<p>
<tt>(sentence (noun-phrase (article the) (noun cat))<br />
(verb eats))<br />
</tt></p>
<p>We can generate such a parse with a simple program that has
separate procedures for each of the grammatical rules. To parse a
sentence, we identify its two constituent pieces and return a
list of these two elements, tagged with the symbol
<tt>sentence</tt>:</p>
<p><a name="%_idx_4964"></a></p>
<p><tt>(define (parse-sentence)<br />
(list 'sentence<br />
(parse-noun-phrase)<br />
(parse-word verbs)))<br />
</tt></p>
<p>A noun phrase, similarly, is parsed by finding an article
followed by a noun:</p>
<p><tt>(define (parse-noun-phrase)<br />
(list 'noun-phrase<br />
(parse-word articles)<br />
(parse-word nouns)))<br />
</tt></p>
<p>At the lowest level, parsing boils down to repeatedly checking
that the next unparsed word is a member of the list of words for
the required part of speech. To implement this, we maintain a
global variable <tt>*unparsed*</tt>, which is the input that has
not yet been parsed. Each time we check a word, we require that
<tt>*unparsed*</tt> must be non-empty and that it should begin
with a word from the designated list. If so, we remove that word
from <tt>*unparsed*</tt> and return the word together with its
part of speech (which is found at the head of the list):<a href="#footnote_Temp_620" name="call_footnote_Temp_620" id="call_footnote_Temp_620"><sup><small>51</small></sup></a></p>
<p><tt>(define (parse-word word-list)<br />
(require (not (null? *unparsed*)))<br />
(require (memq (car *unparsed*) (cdr word-list)))<br />
(let ((found-word (car *unparsed*)))<br />
(set! *unparsed* (cdr *unparsed*))<br />
(list (car word-list) found-word)))<br />
</tt></p>
<p>To start the parsing, all we need to do is set
<tt>*unparsed*</tt> to be the entire input, try to parse a
sentence, and check that nothing is left over:</p>
<p><tt>(define *unparsed* '())<br />
<a name="%_idx_4966"></a>(define (parse input)<br />
(set! *unparsed* input)<br />
(let ((sent (parse-sentence)))<br />
(require (null? *unparsed*))<br />
sent))<br /></tt></p>
<p>We can now try the parser and verify that it works for our
simple test sentence:</p>
<p><tt><i>;;; Amb-Eval input:</i><br />
(parse '(the cat eats))<br />
<i>;;; Starting a new problem</i><br />
<i>;;; Amb-Eval value:</i><br />
<i>(sentence (noun-phrase (article the) (noun cat)) (verb eats))</i><br />
</tt></p>
<p>The <tt>amb</tt> evaluator is useful here because it is
convenient to express the parsing constraints with the aid of
<tt>require</tt>. Automatic search and backtracking really pay
off, however, when we consider more complex grammars where there
are choices for how the units can be decomposed.</p>
<p>Let's add to our grammar a list of prepositions:</p>
<p><tt><a name="%_idx_4968"></a>(define prepositions '(prep for to in by with))<br />
</tt></p>
<p>and define a prepositional phrase (e.g., ``for the cat'') to
be a preposition followed by a noun phrase:</p>
<p><tt>(define (parse-prepositional-phrase)<br />
(list 'prep-phrase<br />
(parse-word prepositions)<br />
(parse-noun-phrase)))<br />
</tt></p>
<p>Now we can define a sentence to be a noun phrase followed by a
verb phrase, where a verb phrase can be either a verb or a verb
phrase extended by a prepositional phrase:<a href="#footnote_Temp_621" name="call_footnote_Temp_621" id="call_footnote_Temp_621"><sup><small>52</small></sup></a></p>
<p><tt>(define (parse-sentence)<br />
(list 'sentence<br />
(parse-noun-phrase)<br />
(parse-verb-phrase)))<br />
(define (parse-verb-phrase)<br />
(define (maybe-extend verb-phrase)<br />
(amb verb-phrase<br />
(maybe-extend (list 'verb-phrase<br />
verb-phrase<br />
(parse-prepositional-phrase)))))<br />
(maybe-extend (parse-word verbs)))<br /></tt></p>
<p>While we're at it, we can also elaborate the definition of
noun phrases to permit such things as ``a cat in the class.''
What we used to call a noun phrase, we'll now call a simple noun
phrase, and a noun phrase will now be either a simple noun phrase
or a noun phrase extended by a prepositional phrase:</p>
<p><tt>(define (parse-simple-noun-phrase)<br />
(list 'simple-noun-phrase<br />
(parse-word articles)<br />
(parse-word nouns)))<br />
(define (parse-noun-phrase)<br />
(define (maybe-extend noun-phrase)<br />
(amb noun-phrase<br />
(maybe-extend (list 'noun-phrase<br />
noun-phrase<br />
(parse-prepositional-phrase)))))<br />
(maybe-extend (parse-simple-noun-phrase)))<br /></tt></p>
<p>Our new grammar lets us parse more complex sentences. For
example</p>
<p>
<tt>(parse '(the student with the cat sleeps in the class))<br />
</tt></p>
<p>produces</p>
<p><tt>(sentence<br />
(noun-phrase<br />
(simple-noun-phrase (article the) (noun student))<br />
(prep-phrase (prep with)<br />
(simple-noun-phrase<br />
(article the) (noun cat))))<br />
(verb-phrase<br />
(verb sleeps)<br />
(prep-phrase (prep in)<br />
(simple-noun-phrase<br />
(article the) (noun class)))))<br />
</tt></p>
<p>Observe that a given input may have more than one legal parse.
In the sentence ``The professor lectures to the student with the
cat,'' it may be that the professor is lecturing with the cat, or
that the student has the cat. Our nondeterministic program finds
both possibilities:</p>
<p>
<tt>(parse '(the professor lectures to the student with the cat))<br />
</tt></p>
<p>produces</p>
<p><tt>(sentence<br />
(simple-noun-phrase (article the) (noun professor))<br />
(verb-phrase<br />
(verb-phrase<br />
(verb lectures)<br />
(prep-phrase (prep to)<br />
(simple-noun-phrase<br />
(article the) (noun student))))<br />
(prep-phrase (prep with)<br />
(simple-noun-phrase<br />
(article the) (noun cat)))))<br />
</tt></p>
<p>Asking the evaluator to try again yields</p>
<p><tt>(sentence<br />
(simple-noun-phrase (article the) (noun professor))<br />
(verb-phrase<br />
(verb lectures)<br />
(prep-phrase (prep to)<br />
(noun-phrase<br />
(simple-noun-phrase<br />
(article the) (noun student))<br />
(prep-phrase (prep with)<br />
(simple-noun-phrase<br />
(article the) (noun cat)))))))<br />
</tt></p>
<p><a name="%_thm_4.45"></a> <b>Exercise
4.45.</b> With the grammar given above, the following
sentence can be parsed in five different ways: ``The professor
lectures to the student in the class with the cat.'' Give the
five parses and explain the differences in shades of meaning
among them.</p>
<p><a name="%_thm_4.46"></a> <b>Exercise
4.46.</b> <a name="%_idx_4970"></a>The evaluators in
sections <a href="book-Z-H-26.html#%_sec_4.1">4.1</a> and
<a href="book-Z-H-27.html#%_sec_4.2">4.2</a> do not determine
what order operands are evaluated in. We will see that the
<tt>amb</tt> evaluator evaluates them from left to right. Explain
why our parsing program wouldn't work if the operands were
evaluated in some other order.</p>
<p><a name="%_thm_4.47"></a> <b>Exercise
4.47.</b> Louis Reasoner suggests that, since a verb
phrase is either a verb or a verb phrase followed by a
prepositional phrase, it would be much more straightforward to
define the procedure <tt>parse-verb-phrase</tt> as follows (and
similarly for noun phrases):</p>
<p><tt>(define (parse-verb-phrase)<br />
(amb (parse-word verbs)<br />
(list 'verb-phrase<br />
(parse-verb-phrase)<br />
(parse-prepositional-phrase))))<br />
</tt></p>
<p>Does this work? Does the program's behavior change if we
interchange the order of expressions in the <tt>amb</tt>?</p>
<p><a name="%_thm_4.48"></a> <b>Exercise
4.48.</b> Extend the grammar given above to handle
more complex sentences. For example, you could extend noun
phrases and verb phrases to include adjectives and adverbs, or
you could handle compound sentences.<a href="#footnote_Temp_626" name="call_footnote_Temp_626" id="call_footnote_Temp_626"><sup><small>53</small></sup></a></p>
<p><a name="%_thm_4.49"></a> <b>Exercise
4.49.</b> <a name="%_idx_4976"></a>Alyssa P. Hacker is
more interested in generating interesting sentences than in
parsing them. She reasons that by simply changing the procedure
<tt>parse-word</tt> so that it ignores the ``input sentence'' and
instead always succeeds and generates an appropriate word, we can
use the programs we had built for parsing to do generation
instead. Implement Alyssa's idea, and show the first half-dozen
or so sentences generated.<a href="#footnote_Temp_628" name="call_footnote_Temp_628" id="call_footnote_Temp_628"><sup><small>54</small></sup></a></p>
<p><a name="%_sec_4.3.3"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_4.3.3">4.3.3 Implementing
the <tt>Amb</tt> Evaluator</a></h3>
<p><a name="%_idx_4978"></a> The evaluation of an ordinary Scheme
expression may return a value, may never terminate, or may signal
an error. In nondeterministic Scheme the evaluation of an
expression may in addition result in the discovery of a dead end,
in which case evaluation must backtrack to a previous choice
point. The interpretation of nondeterministic Scheme is
complicated by this extra case.</p>
<p><a name="%_idx_4980"></a>We will construct the <tt>amb</tt>
evaluator for nondeterministic Scheme by modifying the analyzing
evaluator of section <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>.<a href="#footnote_Temp_629" name="call_footnote_Temp_629" id="call_footnote_Temp_629"><sup><small>55</small></sup></a> As in
the analyzing evaluator, evaluation of an expression is
accomplished by calling an <a name="%_idx_4982"></a>execution
procedure produced by analysis of that expression. The difference
between the interpretation of ordinary Scheme and the
interpretation of nondeterministic Scheme will be entirely in the
execution procedures.</p>
<p><a name="%_sec_Temp_630"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_630">Execution
procedures and continuations</a></h4>
<p><a name="%_idx_4984"></a> <a name="%_idx_4986"></a>Recall that
the execution procedures for the ordinary evaluator take one
argument: the environment of execution. In contrast, the
execution procedures in the <tt>amb</tt> evaluator take three
arguments: the environment, and two procedures called
<em>continuation procedures</em>. The evaluation of an expression
will finish by calling one of these two continuations: If the
evaluation results in a value, the <a name="%_idx_4988"></a><em>success continuation</em> is called with
that value; if the evaluation results in the discovery of a dead
end, the <a name="%_idx_4990"></a><em>failure continuation</em>
is called. Constructing and calling appropriate continuations is
the mechanism by which the nondeterministic evaluator implements
backtracking.</p>
<p>It is the job of the success continuation to receive a value
and proceed with the computation. Along with that value, the
success continuation is passed another failure continuation,
which is to be called subsequently if the use of that value leads
to a dead end.</p>
<p>It is the job of the failure continuation to try another
branch of the nondeterministic process. The essence of the
nondeterministic language is in the fact that expressions may
represent choices among alternatives. The evaluation of such an
expression must proceed with one of the indicated alternative
choices, even though it is not known in advance which choices
will lead to acceptable results. To deal with this, the evaluator
picks one of the alternatives and passes this value to the
success continuation. Together with this value, the evaluator
constructs and passes along a failure continuation that can be
called later to choose a different alternative.</p>
<p>A failure is triggered during evaluation (that is, a failure
continuation is called) when a user program explicitly rejects
the current line of attack (for example, a call to
<tt>require</tt> may result in execution of <tt>(amb)</tt>, an
expression that always fails -- see section <a href="#%_sec_4.3.1">4.3.1</a>). The failure continuation in hand at
that point will cause the most recent choice point to choose
another alternative. If there are no more alternatives to be
considered at that choice point, a failure at an earlier choice
point is triggered, and so on. Failure continuations are also
invoked by the driver loop in response to a <tt>try-again</tt>
request, to find another value of the expression.</p>
<p>In addition, if a side-effect operation (such as assignment to
a variable) occurs on a branch of the process resulting from a
choice, it may be necessary, when the process finds a dead end,
to undo the side effect before making a new choice. This is
accomplished by having the side-effect operation produce a
failure continuation that undoes the side effect and propagates
the failure.</p>
<p>In summary, failure continuations are constructed by</p>
<ul>
<li><tt>amb</tt> expressions -- to provide a mechanism to make
alternative choices if the current choice made by the
<tt>amb</tt> expression leads to a dead end;</li>
<li>the top-level driver -- to provide a mechanism to report
failure when the choices are exhausted;</li>
<li>assignments -- to intercept failures and undo assignments
during backtracking.</li>
</ul>
<p>Failures are initiated only when a dead end is encountered.
This occurs</p>
<ul>
<li>if the user program executes <tt>(amb)</tt>;</li>
<li>if the user types <tt>try-again</tt> at the top-level
driver.</li>
</ul>
<p>Failure continuations are also called during processing of a
failure:</p>
<ul>
<li>When the failure continuation created by an assignment
finishes undoing a side effect, it calls the failure
continuation it intercepted, in order to propagate the failure
back to the choice point that led to this assignment or to the
top level.</li>
<li>When the failure continuation for an <tt>amb</tt> runs out
of choices, it calls the failure continuation that was
originally given to the <tt>amb</tt>, in order to propagate the
failure back to the previous choice point or to the top
level.</li>
</ul>
<p><a name="%_sec_Temp_631"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_631">Structure of
the evaluator</a></h4>
<p><a name="%_idx_4992"></a>The syntax- and data-representation
procedures for the <tt>amb</tt> evaluator, and also the basic
<tt>analyze</tt> procedure, are identical to those in the
evaluator of section <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>, except for the fact
that we need additional syntax procedures to recognize the
<tt>amb</tt> special form:<a href="#footnote_Temp_632" name="call_footnote_Temp_632" id="call_footnote_Temp_632"><sup><small>56</small></sup></a></p>
<p>
<tt>(define (amb? exp) (tagged-list? exp 'amb))<br />
(define (amb-choices exp) (cdr exp))<br /></tt></p>
<p>We must also add to the dispatch in <tt>analyze</tt> a clause
that will recognize this special form and generate an appropriate
execution procedure:</p>
<p><tt>((amb? exp) (analyze-amb exp))<br /></tt></p>
<p>The top-level procedure <tt>ambeval</tt> (similar to the
version of <tt>eval</tt> given in section <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>) analyzes the given
expression and applies the resulting execution procedure to the
given environment, together with two given continuations:</p>
<p><tt><a name="%_idx_4994"></a>(define (ambeval exp env succeed fail)<br />
((analyze exp) env succeed fail))<br />
</tt></p>
<p><a name="%_idx_4996"></a><a name="%_idx_4998"></a><a name="%_idx_5000"></a>A success continuation is a procedure of two
arguments: the value just obtained and another failure
continuation to be used if that value leads to a subsequent
failure. A failure continuation is a procedure of no arguments.
So <a name="%_idx_5002"></a>the general form of an execution
procedure is</p>
<p><tt>(lambda (env succeed fail)<br />
<em>;; <tt>succeed</tt> is <tt>(lambda (value fail) </tt>...</em>)</tt><br />
<em>;; <tt>fail</tt> is <tt>(lambda () </tt>...</em>)<br />
<tt>...</tt>)<br /></p>
<p>For example, executing</p>
<p><tt>(ambeval <<em>exp</em>><br />
the-global-environment<br />
(lambda (value fail) value)<br />
(lambda () 'failed))<br />
</tt></p>
<p>will attempt to evaluate the given expression and will return
either the expression's value (if the evaluation succeeds) or the
symbol <tt>failed</tt> (if the evaluation fails). The call to
<tt>ambeval</tt> in the driver loop shown below uses much more
complicated continuation procedures, which continue the loop and
support the <tt>try-again</tt> request.</p>
<p>Most of the complexity of the <tt>amb</tt> evaluator results
from the mechanics of passing the continuations around as the
execution procedures call each other. In going through the
following code, you should compare each of the execution
procedures with the corresponding procedure for the ordinary
evaluator given in section <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>.</p>