diff options
Diffstat (limited to 'js/games/nluqo.github.io/~bh/61a-pages/Solutions/week14')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/61a-pages/Solutions/week14 | 1404 |
1 files changed, 1404 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week14 b/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week14 new file mode 100644 index 0000000..53486bd --- /dev/null +++ b/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week14 @@ -0,0 +1,1404 @@ +CS61A Week 11 solutions + +LAB: +---- + +4.27 Lazy vs. mutation + +The first time you type COUNT you get 1; the second time you get 2. +Why? When you say + (define w (id (id 10))) +the DEFINE special form handler eval-definition EVALs its second +argument (id (id 10)). Given an application, EVAL calls APPLY +to invoke ID for the outer invocation, but the inner invocation +is providing an argument to a compound procedure, so it's delayed. +That's why COUNT is 1 -- the outer call to ID has actually happened, +but not the inner one. + +The value of W is therefore a promise to compute (id 10), since +ID returns its argument. When you ask the evaluator to print W, +that promise is fulfilled, and so COUNT becomes 2. + + +4.29 Memoizing or not + +You'd expect a program that uses the same argument repeatedly to +be most strongly affected. For example, I wrote + +(define (n-copies n stuff) + (if (= n 0) + '() + (cons stuff (n-copies (- n 1) stuff)))) + +Then if you use n-copies with something requiring a fair amount +of computation, such as + +(n-copies 6 (factorial 7)) + +you can see a dramatic difference. + +About their square/id example, remember to (set! count 0) before +each experiment. Then the memoizing version leaves count at 1, +whereas the non-memoizing version sets count to 2. + + + +4.35 an-integer-between + +(define (an-integer-between low high) + (if (> low high) + (amb) + (amb low (an-integer-between (+ low 1) high)))) + + +4.38 adjacent floors + +Remove the line (require (not (= (abs (- smith fletcher)) 1))) + + +[The continuation part of the lab was just try-this.] + + + +HOMEWORK: +--------- + + +4.25 UNLESS in normal vs. applicative order + +In ordinary (applicative order) Scheme, this version of FACTORIAL +will be an infinite loop, because the argument subexpression +(* n (factorial (- n 1))) is evaluated before UNLESS is called, +whether or not n is 1. + +In normal order Scheme it'll work fine, because the argument +subexpressions aren't evaluated until they're needed. What +will actually happen is that each use of the special form IF +within UNLESS will force the computation of (= n 1), but +no multiplications will happen until the evaluator tries to +print the result. In effect, (factorial 5) returns the thunk + (lambda () (* 5 (* 4 (* 3 (* 2 (* 1 1)))))) +and that gets evaluated just in time to print the answer. + + +4.26 Normal order vs. special forms + +For Ben's side of the argument we must implement UNLESS as a +derived expression: + +(define (unless->if exp) + (make-if (unless-predicate exp) + (unless-consequent exp) + (unless-alternative exp))) + +(define unless-predicate cadr) +(define unless-alternative caddr) +(define unless-consequent cadddr) + +Notice that we reversed the order of the last two subexpressions in +the call to make-if. + +Then we just add a clause + ((unless? exp) (eval (unless->if exp) env)) +to the ordinary metacircular evaluator, or + ((unless? exp) (analyze (unless->if exp))) +to the analyzing evaluator. + +For Alyssa's side of the argument, we need a case in which it's useful to +have a Scheme special form available as an ordinary procedure. The only +thing we can do with ordinary procedures but not with special forms is use +them as arguments to higher-order procedures. An example using UNLESS will +be a little strained, so first we'll look at a more common situation +involving a different special form, namely AND. We'd like to be able to say + +(define (all-true? tf-list) + (accumulate and tf-list)) + +Now, here's the strained example using UNLESS: Suppose we have a list of +true-false values and we'd like to add up the number of true ones. Here's a +somewhat strange way to do it: + +(define zero-list (cons 0 '())) +(set-cdr! zero-list zero-list) + +(define one-list (cons 1 '())) +(set-cdr! one-list one-list) + +(define (howmany-true tf-list) + (apply + (map unless tf-list zero-list one-list))) + +Zero-list is an infinite list of zeros; one-list is an infinite list +of ones. We make use of the fact that MAP's end test is that its +first argument is empty, so MAP will return a list the same size as +the argument tf-list. For example, if tf-list is + (#t #t #f #t) +then map will return + (1 1 0 1) +created, in effect, this way: + (list (unless #t 0 1) + (unless #t 0 1) + (unless #f 0 1) + (unless #t 0 1)) +And so + will return 3, the number of trues in the list. + + +4.28 Why force the operator of a combination? + +Thunks are made by APPLY, representing arguments to defined procedures. +So we need a case in which the operator of an expression is the returned +argument of a defined procedure. Here's an example: + +(((lambda (a b) a) + -) 2 3) + + +4.30 Side effects vs. lazy evaluation + +(a) Why is Ben right about for-each? + +For-each includes the expression (proc (car items)). As we +discussed in ex. 4.28, the lazy evaluator will force the +operator of that expression, i.e., PROC. The resulting +procedure has two invocations of primitives, NEWLINE and +DISPLAY. Evaluating those invocations will actually call +the procedures, and the argument X to DISPLAY will be +evaluated because DISPLAY is primitive. + +(b) What happens in Cy's example? + +First of all, in ordinary Scheme both (p1 1) and (p2 1) give +the result (1 2). + +With the book's version of eval-sequence, (p1 1) is still (1 2) +but (p2 1) is 1, because the SET! will never happen. The +subprocedure P has a two-expression sequence as its body, and +the first expression will never be evaluated. + +With Cy's version both (p1 1) and (p2 1) are (1 2), as in +ordinary Scheme. + +(c) Why doesn't Cy's version change part (a)? + +The change isn't as dramatic as it may seem. Don't think that +the original eval-sequence calls delay-it! It calls EVAL, and +most of the time EVAL does return a value, not a thunk. In +particular, a procedure call is carried out right away; it's +only the *arguments* to the procedure that are delayed. That's +why Cy had to use a weird example in which a SET! expression +is used as an argument to a procedure in order to get the wrong +result. + +(d) What's the right thing to do? + +The combination of lazy evaluation and mutation in the same language +is so confusing that programmers would be surprised no matter which +choice we made. That's why, in the real world, the languages that +use normal order evaluation are *functional* languages in which +there is no mutation or other side effects. In such a language, +there are no sequences (if there are no side effects, what would +be the point?) and the problem doesn't arise. + +But if we really wanted to have a normal-order Scheme, we'd +probably want to change the semantics of the language as little +as possible -- programs that work in ordinary Scheme should work +in lazy Scheme too. So I think Cy is right. + + +4.32 Lazy trees + +One possibility is to use doubly-lazy lists as an alternative to +interleaving, when dealing with a naturally two-dimensional problem. +For example, to get pairs of integers, we could say + +(define (pairs a b) + (cons (map (lambda (x) (cons (car a) x)) b) + (pairs (cdr a) b))) + +Then we could use this data structure with two-dimensional versions +of the usual higher order procedures. For example: + +(define (2dfilter pred s) + (if (null? s) + '() + (cons (filter pred (car s)) + (2dfilter pred (cdr s))))) + + +4.33 Quoted lazy lists + +Instead of + ((quoted? exp) (text-of-quotation exp)) +we need a more complicated treatment to turn the ordinary lists +of the underlying Scheme into lazy lists. + + ((quoted? exp) (process-quotation (text-of-quotation exp) env)) + +(define (process-quotation quoted env) + (if (pair? quoted) + (lazy-cons (process-quotation (car quoted) env) + (process-quotation (cdr quoted) env) + env) + quoted)) + +(define (lazy-cons x y env) + (make-procedure '(m) (list (list 'm x y)) env)) + +or alternatively + +(define (lazy-cons x y env) + (apply (lookup-variable-value 'cons env) + (list x y))) + +This lazy-cons is the below-the-line equivalent of the above-the-line +CONS on page 409. + + + +4.36 all Pythagorean triples + +Replacing an-integer-between with an-integer-starting-from won't +work because the AMB that provides the value for K will never fail, +and so I and J will always be 1 forever. + +To make this work, we note that K must always be larger than I or J, +so I and J can be restricted to finite ranges if we choose a value +for K first: + +(define (a-pythgorean-triple) + (let ((k (an-integer-starting-from 1))) + (let ((i (an-integer-between 1 (- k 1)))) + (let ((j (an-integer-between i (- k 1)))) + (require (= (+ (* i i) (* j j)) (* k k))) + (list i j k))))) + + +4.42 liars + +(define (liars) + (define (onetrue? x y) + (if x (if y #f #t) y)) + (let ((betty (amb 1 2 3 4 5)) + (ethel (amb 1 2 3 4 5)) + (joan (amb 1 2 3 4 5)) + (kitty (amb 1 2 3 4 5)) + (mary (amb 1 2 3 4 5))) + (require (distinct? (list betty ethel joan kitty mary))) + (require (onetrue? (= kitty 2) (= betty 3))) + (require (onetrue? (= ethel 1) (= joan 2))) + (require (onetrue? (= joan 3) (= ethel 5))) + (require (onetrue? (= kitty 2) (= mary 4))) + (require (onetrue? (= mary 4) (= betty 1))) + (list (list 'betty betty) (list 'ethel ethel) (list 'joan joan) + (list 'kitty kitty) (list 'mary mary)))) + +As in the multiple dwelling puzzle, this program can be made much more +efficient by checking for distinct values as we go along instead of +after all values have been assigned: + +(let ((betty (amb 1 2 3 4 5)) + (ethel (amb 1 2 3 4 5))) + (require (distinct? (list betty ethel))) + (let ((joan (amb 1 2 3 4 5))) + (require (distinct? (list betty ethel joan))) + ... + + +4.45 ambiguous sentence + +(sentence + (simple-noun-phrase (article the) (noun professor)) + (verb-phrase + (verb lectures) + (prep-phrase (prep to) + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase (prep in) + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase (prep with) + (simple-noun-phrase (article the) + (noun cat))))))))) + +This version means that a cat is a student in the class, and the professor +lectures to another student in the class. + +(sentence + (simple-noun-phrase (article the) (noun professor)) + (verb-phrase + (verb lectures) + (prep-phrase (prep to) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase (prep in) + (simple-noun-phrase (article the) (noun class)))) + (prep-phrase (prep with) + (simple-noun-phrase (article the) + (noun cat))))))) + +This version means that the professor lectures to a student, and that that +student is in the class and has a cat, which may or may not be present. + +(sentence + (simple-noun-phrase (article the) (noun professor)) + (verb-phrase + (verb-phrase + (verb lectures) + (prep-phrase (prep to) + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase (prep in) + (simple-noun-phrase (article the) (noun class)))))) + (prep-phrase (prep with) + (simple-noun-phrase (article the) + (noun cat))))) + +This version means that the professor brings a cat along while lecturing +to the student who is in the class. + +(sentence + (simple-noun-phrase (article the) (noun professor)) + (verb-phrase + (verb-phrase + (verb-phrase + (verb lectures) + (prep-phrase (prep to) + (noun-phrase + (simple-noun-phrase (article the) (noun student))))) + (prep-phrase (prep in) + (simple-noun-phrase (article the) (noun class)))) + (prep-phrase (prep with) + (simple-noun-phrase (article the) + (noun cat))))) + +This version means that the professor does the lecturing in the class, +bringing a cat along, to some student about whom we know nothing. + +(sentence + (simple-noun-phrase (article the) (noun professor)) + (verb-phrase + (verb-phrase + (verb lectures) + (prep-phrase (prep to) + (noun-phrase + (simple-noun-phrase (article the) (noun student))))) + (prep-phrase (prep in) + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase (prep with) + (simple-noun-phrase (article the) + (noun cat))))))) + +This version means that the professor does the lecturing in a class +that includes a cat as a member, to a student about whom we know nothing. + + +4.47 left-recursive grammar + +As Louis' programs go, this one is pretty successful! It does generate +the two correct parsings for "The professor lectures to the student +with the cat," in the opposite order from what's shown in the book. +But if you say try-again again, instead of reporting that there are +no more values, the parser gets in an infinite loop. + +What happens is this: (parse-word verbs) fails, so parse-verb-phrase +is called recursively. In that recursive call, (parse-word verbs) fails, +so parse-verb-phrase is called recursively. In that recursive call... +and so on. + +Interchanging the order of expressions in the AMB just makes things +worse; this infinite recursion happens the *first* time, so you don't +even see the correct parsings before it loops. + + +4.48 grammar extensions + +For compound sentences, first rename parse-sentence as parse-simple-sentence: + +(define (parse-simple-sentence) + (list 'simple-sentence + (parse-noun-phrase) + (parse-verb-phrase))) + +(define (parse-sentence) + (define (maybe-extend sentence) + (amb sentence + (maybe-extend (list 'sentence + sentence + (parse-word connectors) + (parse-simple-sentence))))) + (maybe-extend (parse-simple-sentence))) + +(define connectors '(connector and or but)) + +For adjectives, we have to provide for the possibility of them +between the article and the noun: + +(define (parse-simple-noun-phrase) + (cons 'simple-noun-phrase + (append (list (parse-word articles)) + (maybe-some adjectives) + (list (parse-word nouns))))) + +(define adjectives '(adjective big tiny silly robust enthusiastic)) + +(define (maybe-some words) + (amb (cons (parse-word words) + (maybe-some words)) + '())) + +Note that unlike most of the parsing procedures, maybe-some doesn't fail if +it can't find what it wants. If it can't find any adjectives it just +returns an empty list. That's why parse-simple-noun-phrase has to use +append, to avoid seeing + + (simple-noun-phrase (article the) () (noun cat)) + +Adverbs are similar except that they go into parse-verb-phrase. + + +4.49 generating sentences + +(define (parse-word word-list) + (define (iter words) + (if (null? words) + (amb) + (amb (car words) (iter (cdr words))))) + (list (car word-list) (iter (cdr word-list)))) + +Here are the first several sentences it creates: +(sentence (noun-phrase (article the) (noun student)) (verb studies)) +(sentence (noun-phrase (article the) (noun student)) (verb lectures)) +(sentence (noun-phrase (article the) (noun student)) (verb eats)) +(sentence (noun-phrase (article the) (noun student)) (verb sleeps)) +(sentence (noun-phrase (article the) (noun professor)) (verb studies)) +(sentence (noun-phrase (article the) (noun professor)) (verb lectures)) +(sentence (noun-phrase (article the) (noun professor)) (verb eats)) +(sentence (noun-phrase (article the) (noun professor)) (verb sleeps)) +(sentence (noun-phrase (article the) (noun cat)) (verb studies)) + + +4.50 random choice + +We must write ANALYZE-RAMB, a variant on the ANALYZE-AMB of p. 434: + +(define (analyze-ramb exp) + (let ((cprocs (map analyze (amb-choices exp)))) + (lambda (env succeed fail) + (define (try-next choices) + (if (null? choices) + (fail) + (let ((random-order (rotate choices (random (length choices))))) + ((car random-order) env + succeed + (lambda () + (try-next (cdr random-order))))))) + (try-next cprocs)))) + +(define (rotate seq num) + (if (= num 0) + seq + (rotate (append (cdr seq) (list (car seq))) + (- num 1))) + +Then we must add a clause to ANALYZE to check for and handle RAMB, +similar to the one for AMB. + + +It's not actually so easy to use RAMB to get good sentences. The problem +is that we really don't want a more complicated choice to be just as likely +as a simple choice, or our sentences will be too long. If we change +every AMB in the parser to RAMB, I get these results: + +[Note: The second one is really long! I suggest reading this in emacs +and using control-meta-F to skip over it.] + +(sentence + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase (prep with) + (noun-phrase + (simple-noun-phrase (article a) (noun cat)) + (prep-phrase (prep for) + (simple-noun-phrase (article a) (noun student)))))) + (verb studies)) + +(sentence + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase (prep with) + (noun-phrase + (simple-noun-phrase (article a) (noun cat)) + (prep-phrase (prep for) + (simple-noun-phrase (article a) + (noun student)))))) + (verb-phrase + (verb-phrase + (verb studies) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep in) + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep by) + (noun-phrase + (simple-noun-phrase (article a) (noun class)) + (prep-phrase + (prep with) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep to) + (simple-noun-phrase (article the) (noun student)))) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep with) + (simple-noun-phrase (article the) (noun professor)))))) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun student)))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) (noun professor)))))) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article a) (noun professor)) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) + (noun student)))))))))))))))) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun student)))) + (prep-phrase + (prep with) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep in) + (simple-noun-phrase (article the) (noun cat)))) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep with) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) (noun professor)) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) (noun professor)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) + (noun student)))) + (prep-phrase + (prep with) + (simple-noun-phrase (article a) + (noun professor)))))) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep with) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep to) + (simple-noun-phrase (article the) + (noun class)))))) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) + (noun student)))))))))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article a) (noun professor)) + (prep-phrase + (prep with) + (noun-phrase + (simple-noun-phrase (article a) (noun professor)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun student)))))))) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun class)))))) + (prep-phrase + (prep to) + (simple-noun-phrase (article the) (noun class)))) + (prep-phrase + (prep in) + (simple-noun-phrase (article a) (noun student)))))))))) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep in) + (simple-noun-phrase (article a) (noun student)))) + (prep-phrase + (prep with) + (noun-phrase + (simple-noun-phrase (article a) (noun class)) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) (noun professor)))))))) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun student)))) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun student)))))))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun professor)))))) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article a) (noun professor)) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article the) + (noun professor)) + (prep-phrase + (prep to) + (simple-noun-phrase + (article a) + (noun class)))))))))))))))))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article a) (noun cat)) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) (noun student)))))) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) (noun class)))))))) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun professor)))))) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase + (prep by) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep to) + (simple-noun-phrase (article the) (noun student)))) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun professor)))) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun student)))) + (prep-phrase + (prep in) + (simple-noun-phrase (article the) (noun professor)))) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun student)))))) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) (noun student)))) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep with) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) (noun class)) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun professor)))) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun cat)) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun professor)))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase + (prep with) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep with) + (simple-noun-phrase (article a) (noun student)))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) (noun student)))) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) + (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) + (noun student)))) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) + (noun class)))) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) + (noun class)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) + (noun class)))) + (prep-phrase + (prep in) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) + (noun professor)) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article a) + (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase + (article the) + (noun student)))))) + (prep-phrase + (prep by) + (simple-noun-phrase (article a) + (noun class)))))))) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article the) + (noun professor)) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article the) + (noun professor)) + (prep-phrase + (prep for) + (simple-noun-phrase + (article the) + (noun student)))))))))))) + (prep-phrase + (prep with) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep by) + (simple-noun-phrase (article a) + (noun student)))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase + (prep to) + (simple-noun-phrase + (article the) + (noun professor)))))))))))))))))) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun class)))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun student)))))) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) + (noun student)))) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) + (noun professor)) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep by) + (noun-phrase + (simple-noun-phrase (article a) + (noun student)) + (prep-phrase + (prep in) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) + (noun student)) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article the) + (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase + (article a) + (noun professor)))))) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) + (noun cat)))))))))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article a) + (noun professor)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) + (noun student)))))))) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article a) (noun cat)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) + (noun professor)))) + (prep-phrase + (prep by) + (simple-noun-phrase (article a) + (noun professor)))))))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun cat)) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article a) (noun professor)) + (prep-phrase + (prep with) + (simple-noun-phrase (article the) (noun cat)))))))) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun cat)))))) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun student)))))) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun professor)))))))) + (prep-phrase + (prep to) + (noun-phrase + (simple-noun-phrase (article a) (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun student)))))))))))) + (prep-phrase + (prep with) + (simple-noun-phrase (article a) (noun student)))))) + (prep-phrase + (prep for) + (noun-phrase + (simple-noun-phrase (article the) (noun professor)) + (prep-phrase + (prep in) + (noun-phrase + (simple-noun-phrase (article the) (noun class)) + (prep-phrase + (prep to) + (simple-noun-phrase (article a) (noun student)))))))))) + (prep-phrase + (prep to) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun cat)) + (prep-phrase + (prep for) + (noun-phrase + (noun-phrase + (simple-noun-phrase (article the) (noun student)) + (prep-phrase + (prep for) + (simple-noun-phrase (article the) (noun professor)))) + (prep-phrase + (prep for) + (simple-noun-phrase (article a) (noun student)))))) + (prep-phrase + (prep in) + (simple-noun-phrase (article a) (noun student))))))) + +We can improve on this by making the addition of a prepositional +phrase less likely. For example, we could rewrite PARSE-NOUN-PHRASE +and PARSE-VERB-PHRASE this way: + +(define (parse-noun-phrase) + (define (maybe-extend noun-phrase) + (ramb noun-phrase + noun-phrase + noun-phrase + noun-phrase + noun-phrase + (maybe-extend (list 'noun-phrase + noun-phrase + (parse-prepositional-phrase))))) + (maybe-extend (parse-simple-noun-phrase))) + +(define (parse-verb-phrase) + (define (maybe-extend verb-phrase) + (ramb verb-phrase + verb-phrase + verb-phrase + verb-phrase + verb-phrase + (maybe-extend (list 'verb-phrase + verb-phrase + (parse-prepositional-phrase))))) + (maybe-extend (parse-word verbs))) + +With these changes, here are the first few sentences I get: + +(sentence (simple-noun-phrase (article a) (noun professor)) (verb sleeps)) + +(sentence (simple-noun-phrase (article a) (noun professor)) (verb sleeps)) + +(sentence (simple-noun-phrase (article a) (noun professor)) + (verb-phrase + (verb sleeps) + (prep-phrase (prep for) + (simple-noun-phrase (article a) (noun student))))) + +(sentence + (simple-noun-phrase (article a) (noun professor)) + (verb-phrase (verb sleeps) + (prep-phrase (prep for) + (simple-noun-phrase (article a) (noun student))))) + +This is still not quite what we want, but with more fine tuning we can +probably get to a reasonable sentence generator. + + +4.52 if-fail + +To add a new special form we add a clause to ANALYZE, which should call +this new procedure: + +(define (analyze-if-fail exp) + (let ((trial (analyze (if-fail-trial exp))) + (failure (analyze (if-fail-failure exp)))) + (lambda (env succeed fail) + (trial env + succeed + (lambda () (failure env succeed fail)))))) + +(define if-fail-trial cadr) +(define if-fail-failure caddr) + +Here's a version to go with vambeval, the ambeval without analysis: + +(define (eval-if-fail exp env succeed fail) + (vambeval (if-fail-trial exp) + env + succeed + (lambda () (vambeval (if-fail-failure exp) + env + succeed + fail)))) + + +Extra for Experts +================= + +4.31 + +Despite what the exercise says, there's no need to change the procedures that +determine the DEFINE syntax, because it doesn't check that the formal +parameters are symbols. Even MAKE-PROCEDURE doesn't check. + +The hard part is in procedure invocation. The original metacircular evaluator +has this in the big COND in EVAL: + + ((application? exp) + (mc-apply (MC-EVAL (operator exp) env) + (LIST-OF-VALUES (operands exp) env))) + +The lazy evaluator in the book changes that to + + ((application? exp) + (mc-apply (ACTUAL-VALUE (operator exp) env) + (operands exp) ; no LIST-OF-VALUES + ENV)) ; added argument + +(For this exercise, it's easier to work with the book's version than with +the slightly different alternative shown in the lecture notes.) + +So now we're giving APPLY expressions rather than values, and we're also +giving APPLY an environment in which to evaluate or thunkify the values. +We don't have to make any change to the book's EVAL; the hard part is in +APPLY, in which we have to decide whether to evaluate or thunkify. + +Here's the book's lazy APPLY: + +(define (mc-apply procedure arguments env) + (cond ((primitive-procedure? procedure) + (apply-primitive-procedure + procedure + (LIST-OF-ARG-VALUES ARGUMENTS ENV))) ; *** + ((compound-procedure? procedure) + (eval-sequence + (procedure-body procedure) + (extend-environment + (procedure-parameters procedure) + (LIST-OF-DELAYED-ARGS ARGUMENTS ENV) ; *** + (procedure-environment procedure)))) + (else + (error + "Unknown procedure type -- APPLY" procedure)))) + +The two commented lines handle evaluation, for primitive procedures, and +thunking, for non-primitive procedures. It's the latter we have to change; +the args may be evaluated, thunked with memoization, or thunked without +memoization. To make this decision, we have to look at the formal parameters +of the procedure we're calling. So the second commented line above will +change to + + (PROCESS-ARGS arguments (PROCEDURE-PARAMETERS PROCEDURE) env) + +Two things have changed; we're calling a not-yet-written procedure +PROCESS-ARGS instead of LIST-OF-DELAYED-ARGS, and we're giving that procedure +the formal parameters as well as the actual argument expressions. + +One more thing has to change in APPLY: Since the list returned by +PROCEDURE-PARAMETERS is no longer a list of symbols, but can now include +sublists such as (B LAZY), we have to extract the real formal parameter +names from it. So the final version of APPLY is this: + +(define (mc-apply procedure arguments env) + (cond ((primitive-procedure? procedure) + (apply-primitive-procedure + procedure + (list-of-arg-values arguments env))) + ((compound-procedure? procedure) + (eval-sequence + (procedure-body procedure) + (extend-environment + (EXTRACT-NAMES (procedure-parameters procedure)) ; *** + (PROCESS-ARGS arguments (PROCEDURE-PARAMETERS PROCEDURE) env) ; *** + (procedure-environment procedure)))) + (else + (error + "Unknown procedure type -- APPLY" procedure)))) + +Now comes the actual work, in EXTRACT-NAMES and in PROCESS-ARGS. + +EXTRACT-NAMES takes as its argument a list such as + (A (B LAZY) C (D LAZY-MEMO)) +and returns a list with just the variable names: + (A B C D) + +(define (extract-names formals) + (cond ((null? formals) '()) + ((pair? (car formals)) ; CAR is (VAR TYPE), so keep CAAR in result + (cons (caar formals) (extract-names (cdr formals)))) + (else (cons (car formals) (extract-names (cdr formals)))))) + +PROCESS-ARGS takes an argument list, let's say + ((+ 2 3) (- 4 5) (* 6 7) (/ 8 9)) +and a parameter list, such as + (A (B LAZY) C (D LAZY-MEMO)) +and matches them up. It pays no attention to the variable names in the +parameter list; it's only looking for LAZY or LAZY-MEMO type tags. It returns +a list of argument values-and-thunks: + (5 (THUNK-NOMEMO (- 4 5) <env>) 42 (THUNK-MEMO (/ 8 9) <env>)) +where <env> represents an actual environment, not the word ENV. The argument +expressions (+ 2 3) and (* 6 7) correspond to non-lazy parameters A and C, +so they've been evaluated; the other arguments have been turned into thunks +by combining them with a type-tag (THUNK-NOMEMO or THUNK-MEMO as appropriate) +and an environment. Instead of the book's DELAY-IT procedure we have to use +two different procedures, DELAY-NOMEMO and DELAY-MEMO, to construct the thunks. + +(define (process-args args formals env) + (cond ((null? args) '()) + ((null? formals) + (error "Too many arguments")) + ((pair? (car formals)) + (cond ((eq? (cadar formals) 'lazy) + (cons (delay-nomemo (car args) env) + (process-args (cdr args) (cdr formals) env))) + ((eq? (cadar formals) 'lazy-memo) + (cons (delay-memo (car args) env) + (process-args (cdr args) (cdr formals) env))) + (else (error "Unrecognized parameter type" (cadar formals))))) + (else (cons (EVAL (car args)) + (process-args (cdr args) (cdr formals) env))))) + +Note the call to EVAL in capital letters two lines up. Should that be EVAL +or ACTUAL-VALUE? The issue is what behavior we want when a procedure with a +non-lazy parameter is called with a thunk (created by calling some other +non-primitive procedure) as the argument: + + (define (foo x) + x) + + (define (baz (lazy x)) + x) + + (define p (foo (baz (/ 1 0)))) + +What should happen? FOO's argument is non-lazy, so we evaluate the argument +expression (BAZ (/ 1 0)). BAZ's argument is lazy, so we make a thunk that +promises to compute (/ 1 0) later, and that becomes the argument to FOO. +If we use EVAL up there, as written, then FOO will get a thunk as its +argument, and will return the thunk, which will become the value of P. If +we make it ACTUAL-VALUE, then the thunk will be forced, and we'll get an +error dividing by zero, and P won't get a value. + +I think the procedure FOO probably doesn't care whether or not its argument is +a thunk, and therefore the argument shouldn't be forced. If the return value +from FOO is used in some context where a real value is needed (for example, +if we said + (foo (baz (/ 1 0))) +at the Scheme prompt instead of inside a DEFINE, then the value will be +forced.) But you'd like to be able to write something like + + (define (cadr seq) (car (cdr seq))) + +and if this is applied to a list of thunks, the result should be a +thunk, not the value promised by the thunk. + +Perhaps there should be a third parameter type tag, so you could say + + (define (f a (b lazy) c (d lazy-memo) (e forced)) + ...) + +allowing the user to choose between EVAL and ACTUAL-VALUE here. This would +add a COND clause in APPLY: + + ((eq? (cadar formals) 'forced) + (cons (actual-value (car args) env) + (process-args (cdr args) (cdr formals) env))) + + +Now we have to do a little data abstraction: + +(define (delay-nomemo exp env) + (list 'THUNK-NOMEMO exp env)) + +(define (delay-memo exp env) + (list 'THUNK-MEMO exp env)) + +Note that the thunk constructors don't have to do any real memoization or +non-memoization work; they just construct thunks that "know" which kind they +are. It's when the thunks are forced that we have to take the difference +into account: + +(define (force-it obj) + (cond ((THUNK-MEMO? obj) ; two kinds of thunk testers + (let ((result (actual-value + (thunk-exp obj) + (thunk-env obj)))) + (set-car! obj 'evaluated-thunk) + (set-car! (cdr obj) result) ; replace exp with its value + (set-cdr! (cdr obj) '()) ; for memoized thunk + result)) + ((THUNK-NOMEMO? OBJ) ; nomemo thunk is EVALed each time it's forced + (ACTUAL-VALUE (THUNK-EXP OBJ) (THUNK-ENV OBJ))) + ((evaluated-thunk? obj) + (thunk-value obj)) + (else obj))) + +(define (thunk-memo? exp) + (tagged-list? exp 'thunk-memo)) + +(define (thunk-nomemo? exp) + (tagged-list exp 'thunk-nomemo)) + +Note that for both kinds of thunks we call ACTUAL-VALUE to cash in the promise; +the difference is that for a memoized thunk we remember the result, whereas for +a non-memoized thunk we don't. + + + +Handle-infix: See proj4b solutions. |