4.47 Exercise 4.47

Compare Louis Reasoner’s parse-verb-phrase with the original:

; Original

(define (parse-verb-phrase)

(define (maybe-extend verb-phrase)

(amb verb-phrase

(maybe-extend (list 'verb-phrase

verb-phrase

(parse-prepositional-phrase)))))

(maybe-extend (parse-word verbs)))

; Louis Reasoner

(define (parse-verb-phrase)

(amb (parse-word verbs)

(list 'verb-phrase

(parse-verb-phrase)

(parse-prepositional-phrase))))

As stated, the main difference is that Louis chose to inline the calls to parse-verb-phrase and thereby eliminate maybe-extend. However, this is very critically wrong, and will lead to an infinite loop.

Consider what will happen when this encounters a phrase that doesn’t start with a verb, as might happen naturally during the exploration and backtracking process. First it will call (parse-word verbs), which will predictably fail. At this point it will try the second case, which requires evaluating a recursive call to (parse-verb-phrase). The first thing this will do is call (parse-word verbs) again, which will fail again and cause another recursive call. We will continue to recurse without processing another word.

The correct variant presented in the text sidesteps this problem by moving the parsing of a verb outside of the optional extension with prepositional phrases. If there is no verb, the function will fail immediately, and backtracking can proceed normally.

As a follow-up question, we are asked to consider what will happen if the order of the amb expression is changed as so:

(define (parse-verb-phrase)

(amb (list 'verb-phrase

(parse-verb-phrase)

(parse-prepositional-phrase))

(parse-word verbs)))

This really doesn’t work – the infinite recursion will happen immediately.