[1] Our program uses the following procedure function to determine if the elements of a list are distinct:
Original JavaScript
(define (distinct? items) (cond ((null? items) true) ((null? (cdr items)) true) ((member (car items) (cdr items)) false) (else (distinct? (cdr items))))) function distinct(items) { return is_null(items) ? true : is_null(tail(items)) ? true : is_null(member(head(items), tail(items))) ? distinct(tail(items)) : false; }
Member is like memq except that it uses equal? instead of eq? to test for equality.
[2] Here we use the convention that the first element of each list designates the part of speech for the rest of the words in the list.
[3] Notice that parse-word parse_word uses set! assignment to modify the unparsed not-yet-parsed input list. For this to work, our amb evaluator must undo the effects of set! operations assignments when it backtracks.
[4] Observe that this definition is recursive—a verb may be followed by any number of prepositional phrases.
[5] This kind of grammar can become arbitrarily complex, but it is only a toy as far as real language understanding is concerned. Real natural-language understanding by computer requires an elaborate mixture of syntactic analysis and interpretation of meaning. On the other hand, even toy parsers can be useful in supporting flexible command languages for programs such as information-retrieval systems. Winston 1992 discusses computational approaches to real language understanding and also the applications of simple grammars to command languages.
[6] Although Alyssa's idea works just fine (and is surprisingly simple), the sentences that it generates are a bit boring—they don't sample the possible sentences of this language in a very interesting way. In fact, the grammar is highly recursive in many places, and Alyssa's technique falls into one of these recursions and gets stuck. See exercise 4.59 for a way to deal with this.
4.3.2   Examples of Nondeterministic Programs