CS61A Summer 2010 George Wang, Jonathan Kotker, Seshadri Mahalingam, Steven Tang, Eric Tzeng Notes courtesy of Chung Wu and Justin Chen 1 CS61A Notes – Week 07b: Nondeterministic and Logic programming Nondeterministic and Indecisive The nondeterministic evaluator extends the metacircular evaluator with nondeterministic searching. It’s good, clean American fun. First we take a look at the new special form, amb, which takes in any number of arguments. If there are no arguments, it fails. If there are arguments, it chooses the first one; if the first one causes a failure, it chooses the second one; if that one causes a failure, it chooses the third, etc., until it runs out of arguments, at which point it itself signals a failure. A companion to amb is require, which takes in a predicate value, and causes a failure if the value is #f: (define (require pred?) (if (not pred?) (amb))) Since you are trained on the imperative and functional ways of programming, this makes the structure of your program very unintuitive. But just imagine that the nondeterministic evaluator works magically; when an error is signaled by (amb), you are allowed to fly to the nearest non-empty call to amb, try the next option and start over. The book and the lectures already present several examples of programs written for the nondeterministic evaluator. But I will provide another motivating example… Consider the problem of finding a path in a binary tree from the root to an element. Consider this tree t: 3 / \ 5 6 / \ / \ 1 30 2 5 / / \ / \ 20 0 12 1 32 Note that this is not a binary search tree! Here’s what we’d like: > (path-to t 12) (r l r) ;; to get from root to 12, go right, left, right > (path-to t 32) (r r r) ;; to get to 32, go right, right, right > (path-to t 19) #f ;; 19 is not in the tree Here’s how we’d need to write path-to in good old Scheme: (define (path-to tree x) (cond ((empty-tree? tree) #f) ((eq? (datum tree) x) ‘()) (else (let ((result (path-to (left-branch tree) x))) (if result (cons ‘L result) (let ((result (path-to (right-branch tree) x))) (if result (cons ‘R result) #f))))))) An ugly little thing! But suppose you take advantage of the nondeterministic evaluator: (define (path-to tree x) (cond ((empty-tree? tree) (amb)) ((eq? (datum tree) x) ‘()) (else (amb (cons ‘L (path-to (left-branch tree) x)) (cons ‘R (path-to (right-branch tree) x))))))CS61A Summer 2010 George Wang, Jonathan Kotker, Seshadri Mahalingam, Steven Tang, Eric Tzeng Notes courtesy of Chung Wu and Justin Chen 2 In the recursive case, we use amb to choose either walking down the left branch or the right branch of the tree. Suppose we chose left; then, if, eventually, we reach an empty tree, we’re going to signal an error, causing us to switch to right. If that throws another error, we ourselves will signal an error (since our amb has run out of options), and our parent will explore other options (either trying the right branch or signaling failure to its parent). Even better – if there are two elements in the tree, we can get the path to one and, after entering try-again, can get the path to the other. Think of the nightmare of doing that with regular Scheme! QUESTIONS 1. Suppose we type the following into the amb evaluator: > (* 2 (if (amb #t #f #t) (amb 3 4) 5)) What are all possible answers we can get? 2. Write a function an-atom-of that dispenses the atomic elements of a deep list (not including empty lists). For example, > (an-atom-of ‘((a) ((b (c))))) => a > try-again => b 3. Use an-atom-of to write deep-member?. 4. Fill in the blanks: > (define (choose-member L R) (cond ((null? R) (amb)) ((= (car L) (car R)) (car L)) (else (amb (choose-member L (cdr R)) (choose-member (cdr L) R))))) > (choose-member ‘(1 2 3) ‘(4 2 3)) _________________________ > try-again _________________________ > try-again _________________________CS61A Summer 2010 George Wang, Jonathan Kotker, Seshadri Mahalingam, Steven Tang, Eric Tzeng Notes courtesy of Chung Wu and Justin Chen 3 Paradigm Shift Again (Why Not?) With this many paradigm shifts in a single semester, we expect you to at least be able to pronounce the word “paradigm” correctly after this class. To reiterate, we are now in the realm of logic or declarative programming. Here in the magical world of the non-imperative, we can say exactly what we want – and have the computer figure out how to get it for us. Instead of saying how to get the solution, we describe – declare – what the solution looks like. The mind-boggling part of all of this is that it all just works through pattern matching. That is, there are no “procedures” in the way you’re used to; when you write out a parenthesized statement, it’s not really a procedure call, and you don’t really get a return value. Instead, either you get entries from some database, or nothing at all. Be Assertive And Ask Questions (Fitter, Happier, More Productive) There are two things you can type into our query system: an assertion and a query. A query asks whether a given expression matches some fact that is already in the database. If the query matches, then the system prints out all matches in the database. If the query doesn’t match to anything, you get no results. An assertion states something true; it adds an entry to the database. You can either assert a simple fact, or a class of facts (specified by a “rule”). So here is an assertion that you have seen: (assert! (jon likes omnom)) You can also assert rules. In general, a rule looks like: (rule <conclusion> <subconditions>) And it’s read: “conclusion is true if and only if all the subconditions are true”. Note that you don’t have to have subconditions! Here’s a very simple rule: (rule (same ?x ?x)) The above says two things satisfy the “same” relation if they can be bound to the same variable. It’s deceptively simple – no subconditions are provided to check the “sameness” of the two arguments. Instead, either the query
View Full Document
Unlocking...