6.001, Fall 2007—Recitation 20 — 11/16/2007 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsFall 2007Recitation 20 — 11/16/2007Amb EvaluatorAMB EvalThe AMB evaluator adds one new sp ecial form called amb which takes a set of possible values andreturns one of them. For example,(amb 1 2 3) could take on the value 1, 2, or 3.amb called w ith no values represents a failure: there are no possible values, so the evaluator needsto backtrack and try another value.In addition to the new special form, a new procedure named require is often useful:(define (require p)(if (not p) (amb)))One way to read that definition is to check the condition p, and if it is true, th en proceed, otherwisebacktrack to try some other set of values before proceeding.Example:(let ((a (amb 1 2 3 4)))(require (even? a))(require (> a 3))a)How about this version?(let ((a (an-element-of (list 1 2 3 4))))(require (even? a))(require (odd? a))a)Implementing AMB as an evaluatorIn the normal version of the analyze evaluator, analyze takes in an expression, and returns aprocedure that takes in an environment as argument an d carries out that operation.In amb-eval the procedures returned are different and all look like this:6.001, Fall 2007—Recitation 20 — 11/16/2007 2(define (analyze-self-evaluating exp)(lambda (env succeed fail)(succeed exp fail)))Rather than return a value, they all pass the value to success: nothing ever returns!The difference is an alyze-amb:(define (analyze-amb exp)(let ((cprocs (map analyze (amb-choices exp))))(lambda (env succeed fail)(define (try-next choices)(if (null? choices)(fail)((car choices) envsucceed(lambda ()(try-next (cdr choices))))))(try-next cprocs))))This one does call the failure continuation, to backtrack to the last branch point.The rest of the amb definition are in SICP11If you want to try out amb in DrScheme, you can either run all t he code for the amb evaluator (in SICP), or youcan add the following definitions which will let you use amb in normal DrScheme. Don’t ask me how this works (Ididn’t write it!), though if you lo ok at it you’ll see that it has success and failure continuations just like the amb-evalversion. Note that there are two different quote characters here: normal quote (’) and backquote (‘).(define amb-fail ’*)(define initialize-amb-fail(lambda ()(set! amb-fail(lambda ()(error "amb tree exhausted")))))(initialize-amb-fail)(define-macro amb(lambda alts‘(let ((+prev-amb-fail amb-fail))(call/cc(lambda (success),@(map (lambda (alt)‘(call/cc(lambda (fail)(set! amb-fail(lambda ()(set! amb-fail +prev-amb-fail)(fail ’fail)))(success ,alt))))alts)(+prev-amb-fail))))))6.001, Fall 2007—Recitation 20 — 11/16/2007 38 QueensSuppose you have a n × n chessboard. How can you place n queens on the board such that all thepositions are safe (no other queen can capture one of the others in a single move).For n = 2, there are no solutions, though for n = 8 there are several, one of which is:********Write a procedu re queens which uses amb to produce solutions to this puzzle.To begin with, notice that any solution will have exactly one queen in each r ow and column of thesolution. As such let’s represent a solution as a list of n elements: each element represents the rowthat that column’s queen is in. For example (queens 4) =⇒ (2 4 1 3) is one possible solution.The followin g helper procedures may be useful:(define (an-element-of items)(require (not (null? items)))(amb (car items) (an-element-of (cdr items))))(define (distinct? items)(cond ((null? items) #t)((null? (cdr items)) #t)((member (car items) (cdr items)) #f)(else (distinct? (cdr items)))))(define (enumerate-interval l u)(if (> l u) ’()(cons l (enumerate-interval (+ l 1) u))))(define (except n lst)(filter (lambda (x) (not (eq? x n)))
View Full Document
Unlocking...