4.3.2 Examples of Nondeterministic Programs

Section 4.3.3 describes the implementation of the amb evaluator. First, however, we give some examples of how it can be used. The advantage of nondeterministic programming is that we can suppress the details of how search is carried out, thereby expressing our programs at a higher level of abstraction.

Logic Puzzles

The following puzzle (adapted from Dinesman 1968) is typical of a large class of simple logic puzzles:

The software company Gargle is expanding, and Alyssa, Ben, Cy, Lem, and Louis are moving into a row of five private offices in a new building. Alyssa does not move into the last office. Ben does not move into the first office. Cy takes neither the first nor the last office. Lem moves into an office after Ben's. Louis's office is not next to Cy's. Cy's office is not next to Ben's. Who moves into which office?

We can determine who moves into which office in a straightforward way by enumerating all the possibilities and imposing the given restrictions:[1]

function office_move() {
    const alyssa = amb(1, 2, 3, 4, 5);
    const ben = amb(1, 2, 3, 4, 5);
    const cy = amb(1, 2, 3, 4, 5);
    const lem = amb(1, 2, 3, 4, 5);
    const louis = amb(1, 2, 3, 4, 5);
    require(distinct(list(alyssa, ben, cy, lem, louis)));
    require(alyssa !== 5);
    require(ben !== 1);
    require(cy !== 5);
    require(cy !== 1);
    require(lem > ben);
    require(math_abs(louis - cy) !== 1);
    require(math_abs(cy - ben) !== 1);
    return list(list("alyssa", alyssa),
                list("ben", ben),
                list("cy", cy),
                list("lem", lem),
                list("louis", louis));
}

Evaluating the expression office_move() produces the result

list(list("alyssa", 3), list("ben", 2), list("cy", 4),
     list("lem", 5), list("louis", 1))

Although this simple function works, it is very slow. Exercises 4.37 and 4.38 discuss some possible improvements.

Exercise 4.36 Modify the office-move function to omit the requirement that Louis's office is not next to Cy's. How many solutions are there to this modified puzzle?

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.37 Does the order of the restrictions in the office-move function affect the answer? Does it affect the time to find an answer? If you think it matters, demonstrate a faster program obtained from the given one by reordering the restrictions. If you think it does not matter, argue your case.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.38 In the office move problem, how many sets of assignments are there of people to offices, both before and after the requirement that office assignments be distinct? It is very inefficient to generate all possible assignments of people to offices and then leave it to backtracking to eliminate them. For example, most of the restrictions depend on only one or two of the person-office names, and can thus be imposed before offices have been selected for all the people. Write and demonstrate a much more efficient nondeterministic function that solves this problem based upon generating only those possibilities that are not already ruled out by previous restrictions.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.39 Write an ordinary JavaScript program to solve the office move puzzle.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.40 Solve the following Liars puzzle (adapted from Phillips 1934):

Alyssa, Cy, Eva, Lem, and Louis meet for a business lunch at SoSoService. Their meals arrive one after the other, a considerable time after they placed their orders. To entertain Ben, who expects them back at the office for a meeting, they decide to each make one true statement and one false statement about their orders:

Alyssa: Lem's meal arrived second. Mine arrived third.

Cy: Mine arrived first. Eva's arrived second.

Eva: Mine arrived third, and poor Cy's arrived last.

Lem: Mine arrived second. Louis's arrived fourth.

Louis: Mine arrived fourth. Alyssa's meal arrived first.

What was the real order in which the five diners received their meals?

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.41 Use the amb evaluator to solve the following puzzle (adapted from Phillips 1961):

Alyssa, Ben, Cy, Eva, and Louis each pick a different chapter of SICP JS and solve all the exercises in that chapter. Louis solves the exercises in the Functions chapter, Alyssa the ones in the Data chapter, and Cy the ones in the State chapter. They decide to check each other's work, and Alyssa volunteers to check the exercises in the Meta chapter. The exercises in the Register Machines chapter are solved by Ben and checked by Louis. The person who checks the exercises in the Functions chapter solves the exercises that are checked by Eva. Who checks the exercises in the Data chapter?

Try to write the program so that it runs efficiently (see exercise 4.38). Also determine how many solutions there are if we are not told that Alyssa checks the exercises in the Meta chapter.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.42 Exercise 2.42 described the eight-queens puzzle of placing queens on a chessboard so that no two attack each other. Write a nondeterministic program to solve this puzzle.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Parsing natural language

Programs designed to accept natural language as input usually start by attempting to parse the input, that is, to match the input against some grammatical structure. For example, we might try to recognize simple sentences consisting of an article followed by a noun followed by a verb, such as The cat eats. To accomplish such an analysis, we must be able to identify the parts of speech of individual words. We could start with some lists that classify various words:[2]

const nouns = list("noun", "student", "professor", "cat", "class");

const verbs = list("verb", "studies", "lectures", "eats", "sleeps");

const articles = list("article", "the", "a");

We also need a grammar, that is, a set of rules describing how grammatical elements are composed from simpler elements. A very simple grammar might stipulate that a sentence always consists of two pieces—a noun phrase followed by a verb—and that a noun phrase consists of an article followed by a noun. With this grammar, the sentence The cat eats is parsed as follows:

list("sentence",
     list("noun-phrase", list("article", "the"), list("noun", "cat"),
     list("verb", "eats"))

We can generate such a parse with a simple program that has separate functions for each of the grammatical rules. To parse a sentence, we identify its two constituent pieces and return a list of these two elements, tagged with the symbol sentence:

function parse_sentence() {      
    return list("sentence",
                parse_noun_phrase(),
                parse_word(verbs));
}

A noun phrase, similarly, is parsed by finding an article followed by a noun:

function parse_noun_phrase() {
    return list("noun-phrase",
                parse_word(articles),
                parse_word(nouns));
}

At the lowest level, parsing boils down to repeatedly checking that the next not-yet-parsed word is a member of the list of words for the required part of speech. To implement this, we maintain a global variable not_yet_parsed, which is the input that has not yet been parsed. Each time we check a word, we require that not_yet_parsed must be nonempty and that it should begin with a word from the designated list. If so, we remove that word from not_yet_parsed and return the word together with its part of speech (which is found at the head of the list):[3]

function parse_word(word_list) {      
    require(! is_null(not_yet_parsed));
    require(! is_null(member(head(not_yet_parsed), tail(word_list))));
    const found_word = head(not_yet_parsed);
    not_yet_parsed = tail(not_yet_parsed);
    return list(head(word_list), found_word);
}

To start the parsing, all we need to do is set not_yet_parsed to be the entire input, try to parse a sentence, and check that nothing is left over:

let not_yet_parsed = null;

function parse_input(input) {
    not_yet_parsed = input;
    const sent = parse_sentence();
    require(is_null(not_yet_parsed));
    return sent;
}

We can now try the parser and verify that it works for our simple test sentence:

amb-evaluate input:

parse_input(list("the",  "cat",  "eats"));

Starting a new problem
amb-evaluate value:
list("sentence",
     list("noun-phrase", list("article", "the"), list("noun", "cat")),
     list("verb", "eats"))

The amb evaluator is useful here because it is convenient to express the parsing constraints with the aid of require. Automatic search and backtracking really pay off, however, when we consider more complex grammars where there are choices for how the units can be decomposed.

Let's add to our grammar a list of prepositions:

const prepositions = list("prep", "for", "to", "in", "by", "with");

and define a prepositional phrase (e.g., for the cat) to be a preposition followed by a noun phrase:

function parse_prepositional_phrase() {      
    return list("prep-phrase",
                parse_word(prepositions),
                parse_noun_phrase());
}

Now we can define a sentence to be a noun phrase followed by a verb phrase, where a verb phrase can be either a verb or a verb phrase extended by a prepositional phrase:[4]

function parse_sentence() {
    return list("sentence",
                parse_noun_phrase(),
                parse_verb_phrase());
}
function parse_verb_phrase() {
    function maybe_extend(verb_phrase) {
        return amb(verb_phrase,
                   maybe_extend(list("verb-phrase",
                                     verb_phrase,
                                     parse_prepositional_phrase())));
    }		   
    return maybe_extend(parse_word(verbs));
}

While we're at it, we can also elaborate the definition of noun phrases to permit such things as a cat in the class. What we used to call a noun phrase, we'll now call a simple noun phrase, and a noun phrase will now be either a simple noun phrase or a noun phrase extended by a prepositional phrase:

function parse_simple_noun_phrase() {      
    return list("simple-noun-phrase",
                parse_word(articles),
                parse_word(nouns));
}
function parse_noun_phrase() {
    function maybe_extend(noun_phrase) {
        return amb(noun_phrase,
                   maybe_extend(list("noun-phrase",
                                     noun_phrase,
                                     parse_prepositional_phrase())));
    }
    return maybe_extend(parse_simple_noun_phrase());
}

Our new grammar lets us parse more complex sentences. For example

parse_input(list("the", "student", "with", "the", "cat",
                 "sleeps", "in", "the", "class"));

produces

list("sentence",
     list("noun-phrase",
          list("simple-noun-phrase", 
               list("article", "the"), list("noun", "student")),
          list("prep-phrase", list("prep", "with"),
               list("simple-noun-phrase",
                    list("article", "the"),
                    list("noun", "cat")))),
     list("verb-phrase",
          list("verb", "sleeps"),
          list("prep-phrase", list("prep", "in"),
               list("simple-noun-phrase", 
                    list("article", "the"),
                    list("noun", "class")))))

Observe that a given input may have more than one legal parse. In the sentence The professor lectures to the student with the cat, it may be that the professor is lecturing with the cat, or that the student has the cat. Our nondeterministic program finds both possibilities:

parse_input(list("the", "professor", "lectures",
                 "to", "the", "student", "with", "the", "cat"));

produces

list("sentence",
     list("simple-noun-phrase",
          list("article", "the"), list("noun", "professor")),
     list("verb-phrase",
          list("verb-phrase",
               list("verb", "lectures"),
               list("prep-phrase", list("prep", "to"),
                    list("simple-noun-phrase",
                    list("article", "the"),
		    list("noun", "student")))),
          list("prep-phrase", list("prep", "with"),
               list("simple-noun-phrase",
                    list("article", "the"),
                    list("noun", "cat")))))

Asking the evaluator to retry yields

list("sentence",
     list("simple-noun-phrase", 
          list("article", "the"), list("noun", "professor")),
     list("verb-phrase",
          list("verb", "lectures"),
          list("prep-phrase", list("prep", "to"),
               list("noun-phrase",
                    list("simple-noun-phrase",
                         list("article", "the"),
                         list("noun", "student")),
                    list("prep-phrase", list("prep", "with"),
                         list("simple-noun-phrase",
                              list("article", "the"),
                              list("noun", "cat")))))))

Exercise 4.43 With the grammar given above, the following sentence can be parsed in five different ways: The professor lectures to the student in the class with the cat. Give the five parses and explain the differences in shades of meaning among them.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.44 The evaluators in sections 4.1 and 4.2 do not determine what order argument expressions are evaluated in. We will see that the amb evaluator evaluates them from left to right. Explain why our parsing program wouldn't work if the argument expressions were evaluated in some other order.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.45 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 declare the function parse_verb_phrase as follows (and similarly for noun phrases):

function parse_verb_phrase() {
    return 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?

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.46 Extend the grammar given above to handle more complex sentences. For example, you could extend noun phrases and verb phrases to include adjectives and adverbs, or you could handle compound sentences.[5]

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.47 Alyssa P. Hacker is more interested in generating interesting sentences than in parsing them. She reasons that by simply changing the function parse_word so that it ignores the input sentence and instead always succeeds and generates an appropriate word, we can use the programs we had built for parsing to do generation instead. Implement Alyssa's idea, and show the first half-dozen or so sentences generated.[6]

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.