From 1bb045d3580d2b21794d109461fbe064ae38f3b8 Mon Sep 17 00:00:00 2001 From: bnewbold Date: Sun, 8 Mar 2009 23:04:16 -0400 Subject: as submitted --- ps04_combinators_amb/bnewbold_ps04.txt | 174 ++++++++++++++++++++++++++++++++- 1 file changed, 173 insertions(+), 1 deletion(-) (limited to 'ps04_combinators_amb/bnewbold_ps04.txt') 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)) +|# -- cgit v1.2.3