summaryrefslogtreecommitdiffstats
path: root/ps04_combinators_amb/bnewbold_ps04.txt
diff options
context:
space:
mode:
Diffstat (limited to 'ps04_combinators_amb/bnewbold_ps04.txt')
-rw-r--r--ps04_combinators_amb/bnewbold_ps04.txt174
1 files changed, 173 insertions, 1 deletions
diff --git a/ps04_combinators_amb/bnewbold_ps04.txt b/ps04_combinators_amb/bnewbold_ps04.txt
index 0203e57..58d49b1 100644
--- a/ps04_combinators_amb/bnewbold_ps04.txt
+++ b/ps04_combinators_amb/bnewbold_ps04.txt
@@ -4,15 +4,187 @@
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
-Problem 4.3: Programming with AMB
+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))
+|#