CSE 341 -- Programming Languages

Spring 1999

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor) and Jeremy Baer (teaching assistant).

Assignment L2

Version 1.01 of April 26. Subject to change.

Lisp in Depth

Due date and time: Monday, May 10, 1999, at 12:30 (at the beginning of class).

Turn in this assignment as a hardcopy printout. (This is tentative; code may be requested instead or in addition. Stay tuned...)

Title: Language, Logic, and Reasoning.

Purposes: Explore the use of Lisp to manipulate language expressions (either English text or logical formulas) and perform limited reasoning with them.

Instructions: Choose one of the following two options:

1. Doctoring up the Doctor. Have a conversation with the SHRINK program by downloading it from the web. (You also need the MATCH function and its helpers.) Notice that it doesn't do very well with punctuation, and the user always has to put the input in parentheses. Reimplement the pattern matching function and the SHRINK to work with strings rather than lists. Then alter the character to exhibit some distinct personality.

2. A Solver for Word Problems Using Algebra. An example of a word problem, encoded as a list, is the following:

     (if the area of a circle is pi times the square of the radius

     and the radius is 10 meters

     then what is the area of the circle ?)

In 1964, the Ph.D. thesis of Daniel Bobrow presented a program called STUDENT which could solve problems posed in this manner. In this option, there are two parts: first is to use modern-day Lisp facilities to reimplement STUDENT, and second is to extend its functionality in one or more of the following ways:

1. be able to handle logic problems as well as arithmetic problems.
2. be able to use a collection of formulas that express commonly used identities. For example, that the area of a circle is PI times the square of the radius. (If this were built-in, then it would not have had to be mentioned in the sample problem above.)
3. allow the program to accept its input as a well-formed English sentence instead of a list in the above format.

Here is some additional information on STUDENT.

Teamwork: You are permitted to work in teams of two on this assignment..

Programming style: Comment your function definitions clearly. In all of your exercises, use a neat and consistent format for your code, indenting subexpressions appropriately and choosing symbol names that are appropriate to the function they perform in your programs.