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
|
;;; 6.945 Problem Set #7 Comments
;;; 03/28/2009
;;; Bryan Newbold <bnewbold@mit.edu>
Problem 7.1: Warmup
--------------------------------
It's Lorna Downing; if we don't know that it's Ann Moore, it could also be
Lorna Parker.
My implementation could be greatly optimized by removing the redundant ambs
for Ann and Melissa, but it's nicely symmetric as it is. Also I just derived
the who-owns-what-yacht pairings by hand because it only takes one elimination.
[see code in bnewbold_ps07_work.scm]
Problem 7.2: Continuation Returning
---------------------------------------
At the return of every branch I printed the result; if a #t result thunked up
through the return structure normally, there would be a series of statements
printed, instead there's just the #t.
[see code in bnewbold_ps07_work.scm]
Problem 7.3: Depth vs. Breadth
--------------------------------
The breadth-first essentially trys all combinations by incrementing the final
element of the triple while the depth first increments the first digit; the
first-digit incrementing comes to (12 16 20) with fewer steps. I checked this
by pp-ing every tested triple.
The extra fail calls are coming from the require in integer-between; eg when
i=10, j increments up to j=20 at which point the selection of k fails.
The depth-first method would try to first enumerate all possible first-digits
then proceed to the second digits; with a-pythagorean-triple-from, the number
of possible first-digits is infinite, so evaluation would never proceed beyond
that point.
[see code in bnewbold_ps07_work.scm]
Problem 7.4: No Such Problem?
-----------------------------------------------
Problem 7.5: Alternative Alternation Orders
-----------------------------------------------
I wrote an itinerary generator based on budget; you wouldn't want to go through
the itineraries with a regular left-to-right type schedule or really any order,
you would want a randomly different itinerary (fitting the constraints and
not something you've done before) every time.
In the end though, the list comes out fairly ordered, I guess the only way to
really get a totally random list would be to build an entire search schedule
without evaluating the last step of each, then randomize the entire schedule
and go through evaluating.
[see code in bnewbold_ps07_work.scm]
Problem 7.6:
--------------------------------
This doesn't seem too mysterious to me, maybe I don't fully understand the
question. When each variable {x,y,z} is assigned an amb value withing a let,
that value (within the let environment) is stored in following continuations.
When using set! the variable values are not stored in later continuations, or
more technically, the set! alters the value of the variables in all
continuations (globally). So when a continuation gets called, the value of
{x,y,z} is not the value from when that continuation was stored, but global
value, aka the last value set!.
When going depth-first, the continuations reach back far enough that the
variables get reset properly. Another way of stating this is that the order of
evaluation procedes in just the right order so that the globaly set! value
is the appropriate one for each individual alternative continuation.
|
