CSCI.4430/6969 Programming Languages Spring 2005
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 TAs or the instructor. You are encouraged to use the WebCT Discussions page to post problems so that other students can also answer/see the answers.

Natural Language Processing with Building-Blocks

You are to take an existing Prolog program and extend it to add new features. blocks.pl 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: read_line.pl (must be loaded first) and blocks.pl.

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 on 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 

 c
 b
 a  d
---------
then after the script is run you should have 
    b
 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 (10% bonus if working individually, required for full credit if working in a pair).

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

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

Reading Material:

The assignment builds on an example from section 2.19 and chapter 7 of the tutorial at http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html .However, if you are new to Prolog, you might want to start with the tutorial at http://www.coli.uni-saarland.de/~kris/learn-prolog-now. Be sure to read chapters 7 and 8 in the second tutorial which talk about natural language processing in prolog.


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

Grading: 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). 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 userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via WebCT.