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
|
;;; 6.945 Problem Set #4 Comments
;;; 03/04/2009
;;; Bryan Newbold <bnewbold@mit.edu>
Problem 4.1: Warmup
---------------------
The way I interpreted this question, all the parameters are passed in one list,
as opposed to a finite list of specified parameters plus an arbitrary length
list containing all the "left over" parameters.
Problem 4.2: Infix Notation
-----------------------------
I attacked this problem with the natural language pattern matching technique
described in SICP. First I wrote a crude register-machine-style parser which
turns the infix string into a list which is easier to parse and match over.
Each element in the list is tagged with it's type (eg, number, variable,
open-parenthesis, etc). Then I identified the following types of expressions:
number: [number]
variable: [variable]
binary: [expression] [oper] [expression]
chunk: [open-paren] [expression] [close-paren]
function: [variable] [open-paren] [expression] [close-paren]
There's potential for an infinite loop when trying to match an expression
as a binary expression starting with an expression starting with a binary
expression [etc etc], so I defined "simple-expressions" as any of the above
types minus binary, and redefined binary as:
binary: [simple-expression] [oper] [expression]
I'm pretty sure this keeps the system general.
Then I do amb-style pattern matching with requires, and finally "lispify"
the resulting parse tree into an s-expression and evaluate it.
To do the final evaluation of the parsed code I added this line to
load-amb.scm:
(define (eval-in-amb exp)
(eval exp generic-evaluation-environment))
This doesn't really work the way I want, but the-global-environment apparently
isn't a real environment (?!?!) and I can't get the usual
nearest-repl/environment. Variables defined in the
generic-evaluation-environment are substituted properly into the final
evaluation. Eg:
;;; Amb-Eval input:
(define y 10)
;;; Starting a new problem
;;; Amb-Eval value:
Number of alts considered: 0
y
;;; Amb-Eval input:
(infix "y")
;;; Starting a new problem
;Unbound variable: y
But then,
1 ]=> (define x 5)
;Value: x
1 ]=> (go)
;;; Amb-Eval input:
(infix "x")
;;; Starting a new problem
;;; Amb-Eval value:
Number of alts considered: 4
5
There are one or two other missing pieces: all operators are binary without the
appropriate precedence, decimal numbers aren't recognized, variables have to
be lowercase, negative numbers don't work (use, eg, 0-45 instead), and operators
are just any string of characters made up of "*+/-^" passed straight through,
so exponentiation doesn't work.
[see code in bnewbold_ps04_work.scm]
Problem 4.38
-----------------------------------
This was only a one line change in the code, remove the line:
(require (not (= (abs (- fletcher smith)) 1)))
By trying it in the evaluator, I found 5 possible solutions:
((baker 1) (cooper 2) (fletcher 4) (miller 3) (smith 5))
((baker 1) (cooper 2) (fletcher 4) (miller 5) (smith 3))
((baker 1) (cooper 4) (fletcher 2) (miller 5) (smith 3))
((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
((baker 3) (cooper 4) (fletcher 2) (miller 5) (smith 1))
Problem 4.39
-----------------------------------
The order matters in that it can change the order that solutions are found,
and definately changes the speed with which they are found. The actual set of
solutions does not change; all solutions will still meet the requirements.
The given order of the requirements actually does a reasonable job optimizing
for the speed of the search. Putting the most restrictive requirements first
will help reduce the number of checks and backtraces performed, so I would put
the (require (> miller cooper)) first.
Problem 4.40
-----------------------------------
There are 5^5=3125 assignments before the distinct requirement and 5!=120 after.
Here's my fast version:
(define (multiple-dwelling-fast)
(let ((fletcher (amb 1 2 3 4 5)))
(require (not (= fletcher 5)))
(require (not (= fletcher 1)))
(let ((cooper (amb 1 2 3 4 5)))
(require (not (= cooper 1)))
(require (not (= (abs (- fletcher cooper)) 1)))
(let ((miller (amb 1 2 3 4 5)))
(require (> miller cooper))
(let ((smith (amb 1 2 3 4 5)))
(require (not (= (abs (- smith fletcher)) 1)))
(let ((baker (amb 1 2 3 4 5)))
(require (not (= baker 5)))
(require
(distinct (list baker cooper fletcher miller smith)))
(list (list 'baker baker)
(list 'cooper cooper)
(list 'fletcher fletcher)
(list 'miller miller)
(list 'smith smith))))))))
Of coure a big help would be simply removing the impossible floors from the amb
statements for individual people; eg because Cooper can't live on the first
floor, just remove 1 from that amb statement.
Problem 4.4: Profiling AMB
----------------------------
My version ("multiple-dwelling-fast") makes 210 alternative attempts, while the
original makes 1840 attempts.
The changes I made were to analyze-amb.scm:
(define *amb-count* 0)
(define (show-amb-count)
(display "Number of alts considered: ")
(display *amb-count*)
(newline)
(set! *amb-count* 0))
and repl-amb.scm:
(define (driver-loop)
(define (internal-loop try-again)
(let ((input
(prompt-for-command-expression input-prompt)))
(if (eq? input 'try-again)
(try-again)
(begin
(newline)
(display ";;; Starting a new problem ")
(evaluator
input
(lambda (val next-alternative)
(display output-prompt)
(show-amb-count) ;;;;;;;;; THIS LINE ADDED
(pp val)
(internal-loop next-alternative))
(lambda ()
(display ";;; There are no more values of ")
(pp input)
(driver-loop)))))))
(internal-loop
(lambda ()
(display ";;; There is no current problem")
(driver-loop))))
#| Example:
eval> (multiple-dwelling)
;;; Starting a new problem
;;; Amb-Eval value:
Number of alts considered: 1840
((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
|#
|
