> y{x @ R[\bjbj004`RR$6666\R7\R477777777wQyQyQyQyQyQyQ$PTRV|Q977777Q77QhIhIhI777wQXI7wQhIhIK/L776H> KwQQ0RL,WGl\/L/LW\$N77FI77777QQr (let ((a (amb 2 3 4))
(b (amb 6 7 8)))
(require (= (remainder b a) 0))
(list a b))0(2 6)0> try-again0(2 8)
> try-again0(3 6)
> try-again(4 8)
> try-again0There are no more solutions.
2. amb: an-integer-between
(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)))
require
(define (require condition)
(if (not condition) (amb)))
continuation
(* 3 (square 5)) is the same as
(define (square x continuation)
(continuation (* x x)))
> (square 5 (lambda (y) (* y 3)))
75
3. amb responses, final 1998
(define (foo x)
(cond ((not pair? x)) (amb))
((word? (cdr x)) (cdr x))
(else (foo ((amb car cdr) x)))))
A common set of wrong answers was C, F, I. This is what you get if you scan the argument for close parentheses. But the C is not the CDR of anything! It's the second element of a list, so it's the CAR of the second pair in the list.
Scoring: We accepted F and I in either order, and any text in the third slot indicating a failure. The only one-point solution had (F) and (I) instead of F and I, missing the fact that the procedure returns (CAR X) and not simply X.
4. Non-deteministic DL
(define (an-atom-of DL) (cond ((null? DL) (amb))
((atom? x) x)
(else (amb (an-atom-of (car DL))
(an-atom-of (cdr DL))))))
(define (deep-member? x DL)
(let
((maybe-x (an-atom-of DL)))
(require (equal? x maybe-x))
#t))
Logic
Brian Harvey Notes
> (load "~cs61a/lib/query.scm")
> (query)
;;; Query input:
(assert! (Brian likes potstickers))
and ask questions about the facts:
;;; Query input:
(?who likes potstickers)
;;; Query results:
(BRIAN LIKES POTSTICKERS)
(assert! (rule (grandmother ?elder ?younger)
(and (mother ?elder ?mom)
(mother ?mom ?younger) )))
;;;;; In file cs61a/lectures/4.4/logic-utility.scm
(assert! (rule (append (?u . ?v) ?y (?u . ?z))
(append ?v ?y ?z)))
(assert! (rule (append () ?y ?y)))
;;; Query input:
(append (a b) (c d e) ?what)
;;; Query results:
(APPEND (A B) (C D E) (A B C D E))
So far this is just like what we could do in Scheme.
;;; Query input:
(append ?what (d e) (a b c d e))
;;; Query results:
(APPEND (A B C) (D E) (A B C D E))
;;; Query input:
(append (a) ?what (a b c d e))
;;; Query results:
(APPEND (A) (B C D E) (A B C D E))
;;; Query input:
(append ?this ?that (a b c d e))
;;; Query results:
(APPEND () (A B C D E) (A B C D E))
(APPEND (A) (B C D E) (A B C D E))
(APPEND (A B) (C D E) (A B C D E))
(APPEND (A B C) (D E) (A B C D E))
(APPEND (A B C D) (E) (A B C D E))
(APPEND (A B C D E) () (A B C D E))
week 7 review, not tested
1. (load "lib/query") (load "lectures/4.4/append") (query-driver-loop)
(append (a b) (c d) ?x)
(append ?x ?y (a b c d)) ; result is a b c d, list all the inputs
(aa '(rule (reverse (?a . ?x) ?y)
(and (reverse ?x ?z)
(append ?z (?a) ?y) )))
(aa '(reverse () ()))
(assert! (rule (reverse (?a . ?x) ?y)
(and (reverse ?x ?z)
(append ?z (?a) ?y) )))
(assert! (reverse () ())
(reverse (a b c) ?result)
(define (reverse a)
(if (null? a) '()
(cons (append (reverse (cdr a)) (list (car a))))))
(aa '(rule (reverse (?car-a . ?cdr-a) ?y)
(and (reverse ?cdr-a ?z)
(append ?z (?car-a) ?y) )))
(aa '(reverse () ()))
2. (query-driver-loop)
;;; Query input
(assert! (rule (append (?car . ?cdr) ?y (?z-car . ?z-cdr))
(append ?cdr ?y ?z-cdr)))
-> assertion added to data base
;;; Query input
(assert! (rule (append () ?y ?y)))
-> assertion added to data base
(append ?a ?b (A B C D E)) ->...
3. (assert! (rule (reverse (?car . ?cdr)
(append (reverse (cdr a)) (list (car a)))
(assert! (rule (reverse (?car . ?cdr) ?z)
(and (reverse ?cdr ?x)
(append ?x (?car) ?z))))
(reverse (a b c) ?what)
-> (reverse (a b c) (c b a))
(reverse ?what (c b a))
-> infinite loop-
> (assert! (my-list (1 2 3 4)))
> (?x (1 2 ?y 4))
> (?x (1 ?y)) -> '()
> (?x (1 . ?y)) -> ;bind x to my-list, bind y to '(2 3 4)
> (? x (1. (2 . ?y))) -> ; bind x to my-list, bidn y to '(3 4)
rotate-forward
(rule (rotate-forward (?x-car . ?x-cdr) (?y-car . ?y-cdr) ?y)
(append ?x-cdr (?x-car) ?y))
(rule (rotate-backward ?x ?y)
(rotate-forward ?y ?x))
(a) Less
less ?x (a a a)) should give the results
(less () (a a a)) (less (a) (a a a)) (less (a a) (a a a))
The solution we were expecting was this:
(rule (less () (a . ?y))) ; 0 < anything positive
(rule (less (a . ?x) (a . ?y)) ; if x < y then x+1 < y+1
(less ?x ?y))
Several variants were also okay. The first rule above could be replaced by
(rule (less () ?x)
(not (same ?x ())))
(b) (times (a a) ?what (a a a a a a))
gives the result
(times (a a) (a a a) (a a a a a a))
Your job is to write a divide logic rule or rules with places for the dividend, the divisor, the quotient, and the remainder:
(divide (a a a a a a a) (a a a) ?quo ?rem)
should give the result
(divide (a a a a a a a) (a a a) (a a) (a))
indicating that 7 divided by 3 gives a quotient of 2 with remainder 1.
Note: Don't write rules for plus or times; assume you are given those!
(rule (divide ?dividend ?divisor ?quotient ?remainder)
(and (times ?divisor ?quotient ?x)
(plus ?x ?remainder ?dividend)
(less ?remainder ?divisor)))
multiply, 1998 final
The rules for addition are just a special case of the rules for appending lists:
(rule (plus () ?y ?y))
(rule (plus (a . ?x) ?y (a . ?z))
(plus ?x ?y ?z))
(a) Write the base case rule for multiplying zero by anything.
(b) Now write the rule for multiplying a nonzero number by anything. Don't worry about whether your rule will "run backwards"; all we require is that, for example, the query
(times (a a) (a a a) ?x)
should give the single result
(times (a a) (a a a) (a a a a a a))
General Coding
num-sum of expression, 1998 final
(define (num-sum exp)
(cond
((null? exp) 0)
((number? exp)
exp)
((atom? exp) 0)
(else
(+ (num-sum (car exp))
(num-sum (cdr exp))))))
Environment Diagram (EnvDraw)
Steps: 1. Evaluate Procedures
2. Evaluate Arguments
3. Make Frame
4. Evaluate Body in that Fram
Notes
(let (()) ) ---> ((lambda () ) )
Analyzing Evaluator vs Metacircular Evaluator
(define (eval-if exp env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))
(define (analyze-if exp)
(lambda (env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env))))
OOP Language (Brian Harvey Notes)
1. (ask