Structure and Interpretation of Computer Programs (79 page)

Evaluating the expression
(multiple-dwelling)
produces the
result

((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))

Although this simple procedure works, it is very slow.
Exercises 
4.39
and 
4.40
discuss some possible
improvements.

Exercise 4.38.
  Modify the multiple-dwelling procedure to omit the requirement that
Smith and Fletcher do not live on adjacent floors. How many solutions
are there to this modified puzzle?

Exercise 4.39.
  Does the order of the restrictions in the multiple-dwelling procedure
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.

Exercise 4.40.
  In the multiple dwelling problem, how many sets of assignments are
there of people to floors, both before and after the requirement that
floor assignments be distinct? It is very inefficient to generate all
possible assignments of people to floors and then leave it to
backtracking to eliminate them. For example, most of the restrictions
depend on only one or two of the person-floor variables, and can thus
be imposed before floors have been selected for all the people.
Write and demonstrate a much more efficient
nondeterministic procedure 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.)

Exercise 4.41.
  
Write an ordinary Scheme program to solve the multiple dwelling puzzle.

Exercise 4.42.
  
Solve the following “Liars” puzzle (from Phillips 1934):

Five schoolgirls sat for an examination. Their parents – so they
thought – showed an undue degree of interest in the result. They
therefore agreed that, in writing home about the examination, each
girl should make one true statement and one untrue one. The following
are the relevant passages from their letters:

• Betty: “Kitty was second in the examination. I was only third.”
  
• Ethel: “You'll be glad to hear that I was on top. Joan was second.”
  
• Joan: “I was third, and poor old Ethel was bottom.”
  
• Kitty: “I came out second. Mary was only fourth.”
  
• Mary: “I was fourth. Top place was taken by Betty.”
  

What in fact was the order in which the five girls were placed?

Exercise 4.43.
  Use the
amb
evaluator to solve the following puzzle:
⁴⁹

Mary Ann Moore's father has a yacht and so has each of his four
friends: Colonel Downing, Mr. Hall, Sir Barnacle Hood, and Dr.
Parker. Each of the five also has one daughter and each has named his
yacht after a daughter of one of the others. Sir Barnacle's yacht is
the Gabrielle, Mr. Moore owns the Lorna; Mr. Hall the Rosalind. The
Melissa, owned by Colonel Downing, is named after Sir Barnacle's
daughter. Gabrielle's father owns the yacht that is named after Dr.
Parker's daughter. Who is Lorna's father?

Exercise 4.44.
  
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.

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:
⁵⁰

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

(sentence (noun-phrase (article the) (noun cat))
          (verb eats))

We can generate such a parse with a simple program that has separate
procedures 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
:

(define (parse-sentence)
  (list 'sentence
         (parse-noun-phrase)
         (parse-word verbs)))

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

(define (parse-noun-phrase)
  (list 'noun-phrase
        (parse-word articles)
        (parse-word nouns)))

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

(define (parse-word word-list)
  (require (not (null? *unparsed*)))
  (require (memq (car *unparsed*) (cdr word-list)))
  (let ((found-word (car *unparsed*)))
    (set! *unparsed* (cdr *unparsed*))
    (list (car word-list) found-word)))

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

(define *unparsed* '())
(define (parse input)
  (set! *unparsed* input)
  (let ((sent (parse-sentence)))
    (require (null? *unparsed*))
    sent))

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

;;; Amb-Eval input:
(parse '(the cat eats))
;;; Starting a new problem
;;; Amb-Eval value:
(sentence (noun-phrase (article the) (noun cat)) (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:

(define prepositions '(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:

(define (parse-prepositional-phrase)
  (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:
⁵²

(define (parse-sentence)
  (list 'sentence
         (parse-noun-phrase)
         (parse-verb-phrase)))
(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)))

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:

(define (parse-simple-noun-phrase)
  (list 'simple-noun-phrase
        (parse-word articles)
        (parse-word nouns)))
(define (parse-noun-phrase)
  (define (maybe-extend noun-phrase)
    (amb noun-phrase
         (maybe-extend (list 'noun-phrase
                             noun-phrase
                             (parse-prepositional-phrase)))))
  (maybe-extend (parse-simple-noun-phrase)))

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

(parse '(the student with the cat sleeps in the class))

produces

(sentence
 (noun-phrase
  (simple-noun-phrase (article the) (noun student))
  (prep-phrase (prep with)
               (simple-noun-phrase
                (article the) (noun cat))))
 (verb-phrase
  (verb sleeps)
  (prep-phrase (prep in)
               (simple-noun-phrase
                (article the) (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 '(the professor lectures to the student with the cat))

produces

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

Asking the evaluator to try again yields

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

Exercise 4.45.
  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.

Exercise 4.46.
  
The evaluators in sections 
4.1
and
4.2
do not determine what order operands 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 operands were evaluated
in some other order.

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
?

Exercise 4.48.
  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.
⁵³

Exercise 4.49.
  
Alyssa P. Hacker is more interested in generating interesting
sentences than in parsing them. She reasons that by simply changing
the procedure
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.
⁵⁴

The evaluation of an ordinary Scheme expression may return a value,
may never terminate, or may signal an error. In nondeterministic
Scheme the evaluation of an expression may in addition result in the
discovery of a dead end, in which case evaluation must backtrack to a previous
choice point. The interpretation of nondeterministic Scheme is
complicated by this extra case.

We will construct the
amb
evaluator for nondeterministic Scheme
by modifying the analyzing evaluator of section 
4.1.7
.
⁵⁵
As in the analyzing evaluator, evaluation of an expression is
accomplished by calling an
execution procedure produced by analysis of
that expression. The difference between the interpretation of ordinary
Scheme and the interpretation of nondeterministic Scheme will be entirely
in the execution procedures.

Recall that the execution procedures for the ordinary evaluator take
one argument: the environment of execution. In contrast, the
execution procedures in the
amb
evaluator take three arguments:
the environment, and two procedures called
continuation
procedures
. The evaluation of an expression will finish by calling
one of these two continuations: If the evaluation results in a value,
the
success continuation
is called with that value; if the
evaluation results in the discovery of a dead end, the
failure
continuation
is called. Constructing and calling appropriate
continuations is the mechanism by which the nondeterministic evaluator
implements backtracking.