CS 232 Assignment 6 Due: Friday, Nov. 3

Problem 1: Processing Trees

Complete the exercises in Lab #8 on processing trees in Common LISP.

Problem 2: Syntactic and Semantic Ambiguity

State why each of the following sentences is ambiguous or not. Specifically, if the sentence is ambiguous, state whether it is because there are multiple syntactic structures for the sentence, multiple word senses for some of the words, multiple semantic structures (such as ambiguous scope for a quantifier), or a combination of these factors. Give a paraphrase of each interpretation of the sentence that captures the meaning in unambiguous terms.

1. A man stopped at every truck stop.
2. Several people ate the pizza.
3. We saw her duck.

Problem 3: Semantic Processing and Thematic Roles

Section 8.6 of the "Semantics and Logical Form" chapter by James Allen (distributed in class) describes the thematic roles that are played by different words in a sentence, and how specific key words appearing in a sentence can help to identify the existence of particular thematic roles (see Figure 8.6 on page 250). The importance of thematic roles in natural language processing, and the use of a representation called "frames" to store this information, are also discussed in the Winston text on pages 209-221 (Chapter 10, "Frames and Commonsense", distributed in class). In our discussion of semantic processing, we stressed the inherent ambiguities that pose a challenge to the design of algorithms for performing such processing. A major source of this ambiguity is the existence of different word senses or meanings for many English words. The identification of thematic roles played by other words in a sentence can often help to resolve the intended meaning of words with multiple word senses.

On pages 218-220 of the Winston text, the verb take is analyzed in detail. The discussion considers a variety of meanings of take, some of the thematic roles that typically co-occur with particular meanings of this verb, and how these roles can be detected in a sentence. This analysis is applied to several sentences using take on page 220 of the text.

Suppose you speak a version of English in which the word give has only the following meanings:

• Give1 means to transfer possession of one thing to one recipient
• Give2 means to distribute copies of something to many recipients
• Give3 means to quit
• Give4 means to yield
• Give5 means to host
• Give6 means to infect
• Give7 means to emit fumes
• Give8 means to return something

Similar to Winston's analysis of the verb take, explain how you could use thematic roles and key words (prepositions and particles) to recognize which meaning is intended, and provide sample sentences exhibiting those recognizable characteristics. If any of the particular definitions given above are not clear, you can consult a dictionary.

Problem 4: CycL: The Cyc Representation Language

CycL is the formal language used to represent knowledge assertions in the Cyc system. A description of this language can be found at the following page at the Cyc website:

   http://www.cyc.com/cycdoc/ref/cycl-syntax.html

Skim through this description and compare aspects of this language to the Logical Form Language for representing semantics described in class (introduced in the "Semantics and Logical Form" chapter by Allen). Briefly describe what aspects these languages have in common.

Problem 5: Playing the Twenty Questions Game

In this problem, you will write a Common LISP function twentyQuestions to play a version of the Twenty Questions game. The user should think of an animal, and the function will try to guess the animal by asking a series of yes-no questions. An initial set of questions and possible animals can be stored in a binary tree. When your twentyQuestions function does not guess the animal correctly, the user will help your program learn new questions and animals so that it can improve its performance.

To begin, copy the file ~cs232/download/twenty.lisp onto your directory. This file contains the definition of a global variable questTree that stores an initial set of questions and animals that the function can use:

(defvar questTree '("Does it have four legs?"
                        ("Does it have hooves?"
                            ("Is it a cow?")
                            ("Is it a dog?"))
                        ("Does it swim?"
                            ("Is it a goldfish?")
                            ("Is it an ostrich?"))))

The structure of the questTree list can be represented as a binary tree, as shown below:

For the questions in each intermediate node in the tree, a response of yes from the user should cause the function to follow the left subtree of the node and a response of no should cause the function to follow the right subtree.

The following interaction between the function and the user illustrates what the twentyQuestions function should be able to do (the user's replies are shown in italics):

> (twentyQuestions questTree)
Does it have four legs? yes
Does it have hooves? no
Is it a dog? yes
I guessed it! Would you like to play again? yes
Does it have four legs? no
Does it swim? yes
Is it a goldfish? no
I give up! What is your animal? penguin
Enter a question whose answer is yes for your animal
   and no for mine: Is it black and white?
Would you like to play again? yes
Does it have four legs? no
Does it swim? yes
Is it black and white? yes
Is it a penguin? yes
I guessed it! Would you like to play again? no
NIL
>

After the user entered a new animal and question, the questTree list should be modified so that it reflects the following tree structure:

Some tips for completing the twentyQuestions function:

• format can be used for all of the printout. This function can also be used to construct the new string to be inserted into questTree that incorporates the user's new animal, such as "Is it a penguin?". If the second input to format is nil, the function returns the constructed string, rather than printing it on the screen, as shown in the following example:
  

  > (setf name "Joe")
"Joe"
> (setf string1 (format nil "Hi there ~a" name))
"Hi there Joe"
> string1
"Hi there Joe"
>

• The two functions read and read-line can be used to read in user input. The read function only reads a single word, and returns this word as a single-quoted atom. The read-line function reads all of the user's input up to a carriage return, which may contain spaces, and returns this input in a double-quoted string. The following function and its execution illustrates the use of read and read-line:

  (defun test-read ()
   (format t "Enter your name: ")
   (setf reply (read))
   (if (equal reply 'Takis)
      (format t "I know you! You are the CS chair!~%")
      (format t "Hello ~a~%" reply))
   (format t "Enter your full name: ")
   (format t "Your full name is ~a~%" (read-line)))
   
> (test-read)
Enter your name: ellen
Hello ELLEN
Enter your full name: Ellen Catherine Hildreth
Your full name is Ellen Catherine Hildreth
>

• Recursion can be used to advance the game to the next level of the tree, and to begin a new game again at the top of the questTree. The tree that is provided as input to twentyQuestions, which may be a subtree of the full questTree, can be altered using setf. Because questTree is a global variable, any modification to part of the tree permanently alters the value of the global tree.
• The progn function can be used to group together multiple lisp expressions into one statement, which can be handy when constructing elaborate if statements such as the following:

  (if (equal num 10)
    (progn (setf result (* num num)) (print result))
    (progn (setf result (+ num 2)) (print num)))


Submission Details: Hand in an electronic copy of your completed twenty.lisp code file using submit:

   submit cs232 twenty twenty.lisp

Also hand in a hardcopy of this code file.