[1] Our program uses the following function to determine if the elements of a list are distinct:
function distinct(items) {	
    return is_null items 
        ? true
        : is_null(tail(items))
          ? true
          : is_null(member(head(items), tail(items)))
            ? distinct(tail(items))
            : false;
}
The function member_equal is like member except that it uses equal instead of === to test for equality.
[2] This is taken from a booklet called Problematical Recreations, published in the 1960s by Litton Industries, where it is attributed to the Kansas State Engineer.
[3] 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.
[4] Notice that parse_word, uses assignment to modify the unparsed input list. For this to work, our amb evaluator must undo the effects of assignment operations when it backtracks.
[5] Observe that this definition is recursive—a verb may be followed by any number of prepositional phrases.
[6] 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.
[7] 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.41 for a way to deal with this.
4.3.2 Examples of Nondeterministic Programs