diff options
Diffstat (limited to 'ps07_amb')
| -rw-r--r-- | ps07_amb/bnewbold_ps07.txt | 56 | ||||
| -rw-r--r-- | ps07_amb/bnewbold_ps07_work.scm | 219 |
2 files changed, 270 insertions, 5 deletions
diff --git a/ps07_amb/bnewbold_ps07.txt b/ps07_amb/bnewbold_ps07.txt index 27bc791..aa91f6a 100644 --- a/ps07_amb/bnewbold_ps07.txt +++ b/ps07_amb/bnewbold_ps07.txt @@ -13,7 +13,61 @@ the who-owns-what-yacht pairings by hand because it only takes one elimination. [see code in bnewbold_ps07_work.scm] -Problem 7.2: +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. diff --git a/ps07_amb/bnewbold_ps07_work.scm b/ps07_amb/bnewbold_ps07_work.scm index 9419ac8..f134fa7 100644 --- a/ps07_amb/bnewbold_ps07_work.scm +++ b/ps07_amb/bnewbold_ps07_work.scm @@ -2,7 +2,7 @@ ;;; 03/28/2009 ;;; Bryan Newbold <bnewbold@mit.edu> -;(load "load") +(load "load") ;;;------------------------------------------------------------------------ ;;; Problem 7.1: Warmup @@ -50,8 +50,9 @@ (newline) (amb)))) -(with-depth-first-schedule find-daughters) + #| +(with-depth-first-schedule find-daughters) ((ann hall) (gabrielle moore) (lorna parker) (rosaline downing) (melissa hood)) ((ann moore) (gabrielle hall) (lorna downing) (rosaline parker) (melissa hood)) ;Value: #f @@ -65,7 +66,7 @@ (lambda (return) (letrec ((hunt (lambda (s) (cond ((null? s) #f) - ((list? (car s)) (or (hunt (car s)) + ((pair? (car s)) (or (hunt (car s)) (hunt (cdr s)))) ((eq? (car s) 'snark) (return #t)) (else (hunt (cdr s))))))) @@ -74,6 +75,216 @@ #| (snark-hunt '(a (1 2 3) v w)) ; #f -(snark-hunt '(a (1 2 'snark 3) v w)) +(snark-hunt '(a (1 2 snark 3) v w)) +; #t +(snark-hunt '(((a b c) d (e f)) g (((snark . "oops") h) (i . j)))) ; #t +|# + +(define (snark-hunt/instrumented l) + (call-with-current-continuation + (lambda (return) + (letrec ((hunt (lambda (s) + (cond ((null? s) #f) + ((pair? (car s)) + (let ((result (or (hunt (car s)) + (hunt (cdr s))))) + (display ";Found: ") + (display result) + (newline) + result)) + ((eq? (car s) 'snark) (return #t)) + (else (hunt (cdr s))))))) + (hunt l))))) + + +#| +(snark-hunt/instrumented '(a (1 2 3) v w)) +;Found: #f +;Value: #f + +(snark-hunt/instrumented '(a (1 2 snark 3) v w)) +;Value: #t + +(snark-hunt/instrumented '(((a b c) d (e f)) g (((snark . "oops") h) (i . j)))) +;Found: #f +;Found: #f +;Value: #t + +|# + + +;;;------------------------------------------------------------------------ +;;; Problem 7.3 + +(define (a-pythagorean-triple-between/verbose low high) + (let ((i (an-integer-between low high))) + (let ((j (an-integer-between i high))) + (let ((k (an-integer-between j high))) + (set! count (+ count 1)) + (pp (list i j k)) + (require (= (+ (* i i) (* j j)) (* k k))) + (list i j k))))) + +(define count 0) + +#| +(begin + (init-amb) + (set! count 0) + (with-breadth-first-schedule + (lambda () (pp (a-pythagorean-triple-between/verbose 10 20))))) + +(begin + (init-amb) + (set! count 0) + (with-depth-first-schedule + (lambda () (pp (a-pythagorean-triple-between/verbose 10 20))))) +|# + +;;;------------------------------------------------------------------------ +;;; Problem 7.4 + +(define (a-nice-itinerary budget) + (let ((city (amb '(boston 0) + '(san-fransisco 250) + '(nyc 30) + '(paris 500) + '(london 500) + '(auckland 1500))) + (meal (amb '(steak 30) + '(falafel 8) + '(foi-gras 100) + '(dumpster-dive 0))) + (hotel (amb '(ritz 800) + '(hostel 20) + '(couch 0))) + (drinks (amb '(0 0) + '(1 5) + '(2 10) + '(3 15) + '(4 20) + '(5 25) + '(6 30))) + (activity (amb '(museum 15) + '(concert 20) + '(opera 100) + '(park 0)))) + ; stay on budget: + (require (>= budget + (fold + 0 (map cadr (list city meal hotel drinks activity))))) + ; mad cow: + (require (not (and (equal? meal 'steak) (equal? city 'london)))) + ; get lost: + (require (not (and (equal? city 'nyc) (> (car drinks) 3)))) + (pp (map car (list city meal hotel drinks activity))) + (amb))) + +; (a-nice-itinerary 40) + +(define (randomize l) + (if (null? l) + '() + (let ((e (list-ref l (random (length l))))) + (cons e (randomize (list-difference l (list e))))))) + +#| +(randomize '(1 2 3 4 5)) +;Value: (3 5 2 1 4) +;Value: (1 5 4 3 2) +;Value: (3 4 5 1 2) +;Value: (5 4 1 2 3) +;Value: (5 1 3 4 2) +;Value: (2 5 4 1 3) +;Value: (1 3 2 5 4) +;Value: (3 2 1 4 5) +|# + +(define (add-left-to-right alternatives) + (for-each (lambda (alternative) + (push! *search-schedule* alternative)) + (reverse alternatives))) + +(define (add-right-to-left alternatives) + (for-each (lambda (alternative) + (push! *search-schedule* alternative)) + alternatives)) + +(define (add-randomly alternatives) + (for-each (lambda (alternative) + (push! *search-schedule* alternative)) + (randomize alternatives))) + +(define (with-left-to-right-alternation thunk) + (call-with-current-continuation + (lambda (k) + (fluid-let ((add-to-search-schedule + add-left-to-right) + (*search-schedule* (empty-search-schedule)) + (*top-level* k)) + (thunk))))) + +(define (with-right-to-left-alternation thunk) + (call-with-current-continuation + (lambda (k) + (fluid-let ((add-to-search-schedule + add-right-to-left) + (*search-schedule* (empty-search-schedule)) + (*top-level* k)) + (thunk))))) + +(define (with-random-alternation thunk) + (call-with-current-continuation + (lambda (k) + (fluid-let ((add-to-search-schedule + add-randomly) + (*search-schedule* (empty-search-schedule)) + (*top-level* k)) + (thunk))))) + +#| +(begin + (init-amb) + (with-left-to-right-alternation + (lambda () + (pp (a-pythagorean-triple-between/verbose 10 20))))) + +(10 10 10) +(10 10 12) +(10 10 13) +(10 10 14) +(10 10 15) +(10 10 16) +(10 10 17) +(etc) + +(begin + (init-amb) + (with-right-to-left-alternation + (lambda () + (pp (a-pythagorean-triple-between/verbose 10 20))))) + +(20 20 20) +(19 20 20) +(19 19 20) +(19 19 19) +(18 20 20) +(18 19 20) +(etc) + + +(begin + (init-amb) + (with-random-alternation + (lambda () + (pp (a-pythagorean-triple-between/verbose 10 20))))) + +(10 13 13) +(10 13 15) +(10 13 16) +(10 13 18) +(10 13 19) +(10 13 20) +(etc) + |#
\ No newline at end of file |