CS 61A Week 8 Solutions LAB === 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))) 4.55 (supervisor ?x (Bitdiddle Ben)) (job ?x (accounting . ?y)) (address ?x (Slumerville . ?y)) The dots are needed because (accounting ?y), for example, would match only entries in which there was a single element after the word "accounting." That is, (accounting ?y) would match (accounting scrivener) but not (accounting chief accountant). 4.62 The base case here involves a 1-element list, not the empty list. (rule (last-pair (?x) (?x))) (rule (last-pair (?y . ?z) ?x) (last-pair ?z ?x)) HOMEWORK ======== 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.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: (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) ........ ;; it seems to me that (if-fail a b) as described has the ;; same semantics as as (amb a b) ;; so why not do this? ;; RJF ;; in analyze change one clause from ((amb? exp)..) to ... ((or (amb? exp)(if-fail? exp)) (analyze-amb exp)) (define (if-fail? x)(tagged-list? x 'if-fail)) One possibility is that the author of the question does not somehow wish to consider the second expression to be allowed to fail. 4.56 (and (supervisor ?x (Bitdiddle Ben)) (address ?x ?y)) (and (salary ?x ?s1) (salary (Bitdiddle Ben) ?s2) (lisp-value < ?s1 ?s2)) (and (supervisor ?who ?boss) (not (job ?boss (computer . ?y))) (job ?boss ?z)) The key point here is that we use the same variable name twice if we want it to match the same item both times. 4.57 (rule (same ?x ?x)) ;; Don't use (lisp-value eq? ....) (rule (replace ?p1 ?p2) (and (or (and (job ?p1 ?x) (job ?p2 ?x)) (and (job ?p1 ?x) (job ?p2 ?y) (can-do-job ?x ?y))) (not (same ?p1 ?p2)))) (replace ?x (Fect Cy D)) (and (replace ?x ?y) (salary ?x ?s1) (salary ?y ?s2) (lisp-value < ?s1 ?s2)) 4.65 This problem requires understanding the basic idea of how the query system works (read Section 4.4.3). To respond to a query, the query system generates a stream of frames which are then used to "instantiate" the query. In this case, the stream will include frames containing all bindings of ?middle-manager, ?person and ?x satisfying the body of the rule, and also with ?who bound to ?person. Since Warbucks supervises Bitdiddle and Scrooge, each of who manages other people, there will be more than one of these frames. Hence Warbucks appears more than once in the output. EXTRA PRACTICE 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.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.58 Note the definition of a sub-rule to make things more manageable. (rule (sup-in-div ?p ?x) (and (supervisor ?p ?boss) (job ?p (?x . ?y)) (job ?boss (?x . ?z)))) (rule (big-shot ?person ?division) (and (job ?person (?division . ?x)) (not (sup-in-div ?person ?division))))