CSCI.4430/6969 Programming Languages Fall 2003
Programming Assignment #3

This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get all the help you need from the TA or the instructor. You are encouraged to use the WebCT Discussions page to post problems so that other students can also see the answers.

Natural Language Processing with Building-Blocks

You are to take an existing Prolog program and extend it to add new features. is a program that allows the user to manipulate a set of blocks on a table. The user can place blocks on other blocks or on empty spots on the table using natural language. A simple grammar can parse certain commands such as "Please place block a on block b." or "I want a on b.". The parser converts these sentences into simple commands (e.g. on(a,b)). There are also limitations, because a block cannot be moved if it is under another block or if you are trying to move it on top of a covered block or onto the table when there are no free table positions. To start the read-eval-print loop, execute "place_blocks." in Prolog after the appropriate files are loaded. This assignment was changed slightly from the example described in section 7.3 of an extensive Prolog tutorial. The assigned extensions are the same, while some details are somewhat different (the tutorial works toward an animation which is not part of this assignment).

Starting files: (must be loaded first) and

Part 1. Complete the following idiom extensions.

(a) Formulate a new question idiom, one of whose scripts is "What is block X sitting on?".

(b) Formulate a new question idiom, one of whose scripts is "Which blocks are on the table?".

(c) Formulate a new command idiom, one of whose scripts is "Put all of the blocks in a single pile.". This is an interesting idiom, because the abstract meaning is ambiguous -- that is, there could be more than one abstract meaning for this idiom. Assume that one abstract meaning is no better or worse than another; just generate one of them as "the" meaning.

(d) Formulate a new command idiom, one of whose scripts is "Put the block on top of X on top of block y." (or on the table). This will involve interpreting the definite description ("the ...") acurately.

(e) Formulate a new command idiom, one of whose scripts is "Put the highest block on top of block y." (or the table). This will involve interpreting the definite description ("the ...") acurately.

Part 2. Reading command / question scripts.

Implement a program that executes command or question text-based "scripts". The user can type any commands or questions from the original grammar or the extended grammar of Part 1. The scripts should allow access to the most recently accessed block using the keyword "result". Basically, wherever "result" is used, it should work as if "result" was replaced by the block letter that was last queried. See script.eng for an example script. If the setup before is

 a  d
then after the script is run you should have
 a  d  c

Some notes: "result" should be bound to the last valid block that is the result of a question or command as follows.

The value of result should remain fixed throughout other questions / commands. Result has no initial value. Result should remain fixed if queries fail.

Part 2 Extra Credit. Extra script features.

Allow the script to have an if ... then ... else command.

Allow the script to have a repeat ... while ... command.

Due Date:
Received Time Grade Modification
before Monday, November 17, 11:59PM +10%
Tuesday, November 18, from 12:00AM to 11:59PM no modification (on time)
Wednesday, November 19, from 12:00AM to 11:59PM -10%
from Thursday, November 20, 12:00AM to 
Friday, November 21, 11:59PM
after Saturday, November 22, 12:00AM not accepted

Grading: The programs will be tested on the CS network version of Prolog. The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!).  See the professor or TAs, if you have ideas for other extensions for this assignment and would like extra credit for implementing them.

Submission Requirements: Please submit a ZIP file with your code, including a README file. In the README file, place the names of each group member (up to two), and the version(s) of Prolog that you have tested it under.  Your code will be tested on the CS machines, so make sure it works there.  Your README file should also have a list of specific features / bugs in your solution. Your ZIP file should be named with your WebCT user name(s) as the filename, either or Only submit one assignment per pair via WebCT.