Exercise 4.47.  Louis Reasoner suggests that, since a verb phrase is 
either a verb or a verb phrase followed by a prepositional phrase, it 
would be much more straightforward to define the procedure 
parse-verb-phrase as follows (and similarly for noun phrases):

(define (parse-verb-phrase)
  (amb (parse-word verbs)
       (list 'verb-phrase
             (parse-verb-phrase)
             (parse-prepositional-phrase))))

Does this work? Does the program's behavior change if we interchange the 
order of expressions in the amb?

————————————————————————————————————————————————————————————————————————

The definition of parse-verb-phrase from the text for comparison:

(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)))

In the version given in the text, (parse-word verbs) is called first, 
which will succeed if a verb can be parsed.  Then, ambiguously, the 
program will either attempt to parse a prepositional phrase, or not.

If it does try to parse a prepositional phrase, and if parsing the 
prepositional phrase succeeds, then the result will be passed to 
maybe-extend again, and it will again ambiguously either return the 
current result, or try to parse another prepositional phrase.

There is a relationship between the input that is consumed and the 
ambiguous branches that are generated.  Every time parse-verb-phrase 
makes an ambiguous choice, it does so only after consuming input.

This is why this program, in all its branches, terminates.

By always consuming input before making an ambiguous branch, the version 
given in the text limits the branching, to at most a few branches per 
input token, after which all branches will begin to fail.

In Louis's code, the order of ambiguous choice and input consumption is 
changed.  First his program makes an ambiguous choice between attempting 
to parse a verb or a verb phrase.  In the first case, the verb must be 
consumed, or this branch of execution will fail.  In the second case, 
however, this first makes a recursive call to parse-verb-phrase, without 
having yet consumed any input.  This call is effectively the same as the 
one we were already in, and therein lies the rub.

Consider Louis's verb-phrase parser applied to the input "sleeps in the 
class".

The first result will be:

(verb sleeps)

This will fail since the parser expects to consume the entire input.

The next result will be:

(verb-phrase (verb sleeps) (prep-phrase ...))

This corresponds to taking the second branch in the first call to 
parse-verb-phrase, and taking the first branch in the second call.  The 
inner call consumes "sleeps" and the outer call then parses the 
prepositional phrase.

On attempting to find the third result, the interpreter will try:

(verb-phrase (verb-phrase (verb sleeps) (prep-phrase ...)) (prep-phrase ...))

This represents three calls to parse-verb-phrase.  The innermost call 
will succeed on the first branch, consuming "sleeps".  The second call 
will then succeed, consuming the prepositional phrase.  The first, 
outermost, call will then fail, since there is no more input for the 
prepositional phrase.

The interpreter will then try the next branch at the innermost (that is, 
most recent) choice point.  The innermost amb is the one which consumed 
"sleep", so this will be toggled to the second branch.  This corresponds 
to trying the parse:

(verb-phrase (verb-phrase (verb-phrase (verb sleeps) ...

Of course this one will fail and the interpreter will try an infinite 
chain of doomed parses of the form:

(verb-phrase (verb-phrase (verb-phrase (verb-phrase ...

all of which would fail, but of which there is an infinite supply.

The problem is that the parser commits to the branch that requires the 
prepositional phrase before attempting to parse the prepositional phrase 
that would complete it.

Thus Louis's parse-verb-phrase will first, correctly, find all the verb 
phrases which can be constructed, and then after the last one, fall into 
an infinite stream of failure.

If the order of expressions in the amb is reversed:

(define (parse-verb-phrase)
  (amb (list 'verb-phrase
             (parse-verb-phrase)
             (parse-prepositional-phrase))
       (parse-word verbs)))

then, since the first branch is now the one that leads to the infinite 
stream of failure, not even the first correct results will ever be 
returned.

This is the problem of left-recursion in recursive descent parsers, in 
which a rule which first attempts to parse itself at the same position, 
will not terminate.

As in the stream example in a previous chapter, Louis has written a 
program which calculates the correct result, but takes infinitely long 
to do so.  The correctness of a program and whether it terminates are 
both interesting properties and both must be considered, often 
separately.