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]
Although this simple
procedurefunction
works, it is very slow.
Exercises 4.48
and 4.49 discuss some possible
improvements.
Exercise 4.47
Modify the office-move
procedurefunction
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.48
Does the order of the restrictions in the office-move
procedurefunction
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.49
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
variables,names,
and can thus be imposed before offices have been selected for all the people.
Write and demonstrate a much more efficient nondeterministic
procedurefunction
that solves this problem based upon generating only those possibilities that
are not already ruled out by previous restrictions.
(Hint: This will require a nest of let
expressions.)
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.50
Write an ordinary
SchemeJavaScript
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.51
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:
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.52
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.49). 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.53
Exercise 2.43 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]
Original
JavaScript
(define nouns '(noun student professor cat class))
(define verbs '(verb studies lectures eats sleeps))
(define articles '(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:
We can generate such a parse with a simple program that has separate
proceduresfunctions
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_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
unparsednot-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
*unparsed*,
not_yet_parsed,
which is the input that has not yet been parsed. Each time we check a word,
we require that
*unparsed*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
*unparsed*not_yet_parsed
and return the word together with its part of speech (which is found at
the head of the list):[3]
To start the parsing, all we need to do is set
*unparsed*not_yet_parsed
to be
the entire input, try to parse a sentence, and check that nothing is
left over:
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:
Original
JavaScript
;;; Amb-Eval input:
(parse '(the cat eats))
;;; Starting a new problem
;;; Amb-Eval value:
(sentence (noun-phrase (article the) (noun cat)) (verb eats))
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.
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:
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:
Original
JavaScript
(parse '(the professor lectures to the student with the cat))
Exercise 4.54
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.55
The
evaluators in sections 4.1 and
4.2 do not determine what order
operandsargument 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
operandsargument 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.56
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
definedeclare
the
procedurefunctionparse-verb-phraseparse_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.57
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.58
Alyssa P. Hacker is more interested in
generating interesting sentences
than in parsing them. She reasons that by simply changing the
procedure
parse-wordfunction
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.
[1]
Our program uses the following
procedurefunction
to determine if the elements of a list are distinct:
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-wordparse_word
uses
set!assignment
to modify the
unparsednot-yet-parsed
input list. For this to work, our
amb evaluator must undo the effects of
set! operationsassignments
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.