Introduction and MotivationNondeterminstic EvaluatorRecursive AmbFootnote on Order of EvaluationBelow the LineSuccess or FailureContinuationsContinuations for Success and FailureNONDETERMINISTIC EVALUATOR 24GEORGE [email protected] of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyAugust 3, 2010To load the nondeterministic evaluator, say:(load "~cs61a/lib/ambeval.scm")1 Introduction and MotivationMany problems are of the form “Find all A such that B” or “find an A such that B.” For example: Find aneven integer that is not the sum of two primes; find a set of integers a, b, c, and n such that an+ bn= cnandn > 2. (These problems might not be about numbers: Find all the states in the United States whose first andlast letters are the same.)In each case, the set A (even integers, sets of four integers, or states) is called the solution space. The conditionB is a predicate function of a potential solution that’s true for actual solutions.One approach to solving problems of this sort is to represent the solution space as a stream, and usestream-filter to select the elements that satisfy the predicate:(stream-filter sum-of-two-primes? even-integers)(stream-filter Fermat?(pairs (pairs integers integers) (pairs integers integers)))(stream-filter (lambda (x) (equal? (first x) (last x))) states)The stream technique is particularly elegant for infinite problem spaces, because the program seems to begenerating the entire solution space A before checking the predicate B. Of course, we know that the stepsof the computation are reordered so that the elements are tested as they are generated.This week we consider a different way to express the same sort of computation, a way that makes thesequence of events in time more visible. In effect we’ll say:1. Pick a possible solution.2. See if it’s really a solution.13. If so, return it; if not, try another.Here’s an example of the notation:> (let ((a (amb 2 3 4))(b (amb 6 7 8)))(require (= (remainder b a) 0))(list a b))(2 6)> try-again(2 8)> try-again(3 6)> try-again(4 8)> try-againThere are no more solutions.2 Nondeterminstic EvaluatorThe main new thing here is the special form amb.1This is not part of ordinary Scheme! We are adding itas a new feature in the metacircular evaluator. Amb takes any number of argument expressions and returnsthe value of one of them. You can think about this using either of two metaphors:• The computer clones itself into as many copies as there are arguments; each clone gets a differentvalue.• The computer magically knows which argument will give rise to a solution to your problem andchooses that one.What really happens is that the evaluator chooses the first argument and returns its value, but if the com-putation later fails, then it tries again with the second argument, and so on until there are no more to try.This introduces another new idea: the possibility of the failure of a computation. That’s not the same thingas an error! Errors (such as taking the car of an empty list) are handled the same in this evaluator as inordinary Scheme; they result in an error message and the computation stops. A failure is different; it’s whathappens when you call amb with no arguments, or when all the arguments you gave have been tried andthere are no more left.In the example above I used require to cause a failure of the computation if the condition is not met.Require is a simple procedure in the metacircular Scheme-with-amb:(define (require condition)(if (not condition) (amb)))So here’s the sequence of events in the computation above:a=2b=6; 6 is a multiple of 2, so return (2 6)[try-again]b=7; 7 isn’t a multiple of 2, so fail.b=8; 8 is a multiple of 2, so return (2 8)[try-again]1Amb Eval should really stand for Ambivalent, not Ambiguous as the notes/book argues. I think that it’s not that the value that isunclear, but that there are multiple simultaneous values.2No more values for b, so fail.a=3b=6; 6 is a multiple of 3, so return (3 6)[try-again]b=7; 7 isn’t a multiple of 3, so fail.b=8; 8 isn’t a multiple of 3, so fail.No more values for b, so fail.a=4b=6; 6 isn’t a multiple of 4, so fail.b=7; 7 isn’t a multiple of 4, so fail.b=8; 8 is a multiple of 4, so return (4 8)[try-again]No more values for b, so fail.No more values for a, so fail.(No more pending AMBs, so report failure to user.)2.1 Recursive AmbSince amb accepts any argument expressions, not just literal values as in the example above, it can be usedrecursively:(define (an-integer-between from to)(if (> from to)(amb)(amb from (an-integer-between (+ from 1) to))))or if you prefer:(define (an-integer-between from to)(require (>= to from))(amb from (an-integer-between (+ from 1) to)))Further, since amb is a special form and only evaluates one argument at a time, it has the same delayingeffect as cons-stream and can be used to make infinite solution spaces:(define (an-integer-from from) (amb from (an-integer-from (+ from 1))))This an-integer-from computation never fails—there is always another integer—and so it won’t workto say(let ((a (an-integer-from 1)) (b (an-integer-from 1))) ...)because a will never have any value other than 1, because the second amb never fails. This is analogous tothe problem of trying to append infinite streams; in that case we could solve the problem with interleavebut it’s harder here.2.2 Footnote on Order of EvaluationIn describing the sequence of events in these examples, I’m assuming that Scheme will evaluate the ar-guments of the unnamed procedure created by a let from left to right. If I wanted to be sure of that, Ishould use let*instead of let. But it matters only in my description of the sequence of events; consid-ered abstractly, the program will behave correctly regardless of the order of evaluation, because all possiblesolutions will eventually be tried—although maybe not in the order shown here.33 Below the Line3.1 Success or FailureIn the implementation of amb, the most difficult change to the evaluator is that any computation mayeither succeed or fail. The most obvious way to try to represent this situation is to have eval returnsome special value, let’s say the symbol =failed=, if a computation fails. (This is analogous to the use of=no-value= in the Logo interpreter project.) The trouble is that if an amb fails, we don’t want to continuethe computation; we want to “back up” to an earlier stage in the computation. Suppose we are
View Full Document
Unlocking...