This exercise caused me some trouble. The version of amb provided by the swindle language doesn’t work in the same way as the authors implement it in the book. The problem is that swindle doesn’t “remember” the value of the top level definition of *unparsed* when it backtracks to the next value of the amb expression after meeting a failure. This is a problem because the authors are expecting the backtracking to continue with the value of *unparsed* as it was at the time of the evaluation of the amb expression. The swindle version of amb does not work in the same way. Once the value of *unparsed* is altered it remains the same during backtracking. In other words, once the first success condition is met *unparsed* is null. Evaluating try-again fails because, although amb continues from the correct place, the value of *unparsed* is still null. This cause parse-word to fail, so the next amb value is evaluated. Since *unparsed* is still null, that and all future attempts fail exhausting all of the remaining amb possibilites.
To solve this problem I resorted to using the r5rs language in racket, configuring it allow top-level values to be redefined and downloading the authors version of the amb evaluator (ch4-ambeval.scm which I renamed to ch4-ambeval.rkt) and the default meta-circular evaluator ch4-mceval.scm – also renamed) from the SICP website. At the top of the amb evaluator I also had to add:
(load "ch4-mceval.rkt") (define true #t) (define false #f)
To avoid having to run (driver-loop) and type program definitions I added an interpret procedure – note I couldn’t use the same interpret procedure as previously because the amb evaluator takes two extra argument – a failure procedure and a success procedure. So athe very bottom of the amb evaluator I added this:
(define the-global-environment (setup-environment))
(define (interpret input)
(ambeval input
the-global-environment
;; ambeval success
(lambda (val next-alternative)
val)
;; ambeval failure
(lambda ()
(newline)
(display "fail")
(newline))))
On to the actual exercise. I still have to use (driver-loop) to be able to use try-again but at least I can set up all of the parsing procedures through (interpret …) without having to type them.
;;; Amb-Eval input: (parse '(the professor lectures to the student in the class with the cat)) ;;; Starting a new problem ;;; Amb-Eval value: (sentence (simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb-phrase (verb-phrase (verb lectures) (prep-phrase (prep to) (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))))) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (sentence (simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb-phrase (verb lectures) (prep-phrase (prep to) (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))))))) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (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))))) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (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))))))) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (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))))))))) ;;; Amb-Eval input: try-again ;;; There are no more values of (parse '(the professor lectures to the student in the class with the cat))
The 5 possible ways to parse the sentence are:
The professor that is with the cat, lectures 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)
(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)))))
The professor lectures to the student, who is in the class with the cat
(sentence
(simple-noun-phrase (article the) (noun professor))
(verb-phrase (verb-phrase (verb lectures)
(prep-phrase (prep to) (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)))))))
The professor and the cat together, lecture to the student in the class
(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)))))
The professor, lectures only to the student with the cat, that is 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)))))))
The professor lectures to the student, in the class that has the cat
(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)))))))))
SICP exercises 
; V1: The professor lectures to the student. This lecturing takes place in the class. During this lecturing the cat is present.
; V2: The professor lectures to the student. There is a class in which a cat is present. This lecturing takes place in this class.
; V3: There is a student in the class. The professor lectures to this student. During this lecturing the cat is present.
; V4: There is a student in the class. The cat is with this student. The professor lectures to this student.
; V5: The cat is in the class. The student is in this class. The professor lectures to this student.