CSC 324 Assignment 5

Idiomatic Natural Language Processing in the Blocks World

For this assignment we will be extending the interface capabilities of your simple blocks world from assignment 4 by adding basic English language processing.

You may choose to extend either your A4 Part I code, A4 Part II code, or the sample solution code which will be posted the evening of Wednesday, April 5.

You will be writing a new interpreter layer that will iteratively read an English sentence from the user, interpret the intended meaning of the sentence, translate the sentence into a query or series of queries, and perform the query (queries) on your simple blocks world.

Of course we won't ask you to parse and understand all English phrases, instead you will support a small number of typical idiomatic expressions. An idomatic expression is, roughly, phrase a typical user might use to communicate with the running application. By an idiom we will mean a collection of grammar rules with a common meaning. There may be many special (idiomatic) ways to say the same thing, that is, to convey the same meaning. This assignment is based on section 7.3 of the Prolog :- Tutorial.

A sentence might be a command to effect a change to the world. The user might say "Please place block a on block b." or "I want a on b.". These might be parsed by a simple grammar and translated into the command place(a,b), which should then be effected.

Another idiom might be a question, something like "Which block is on top of a?" or "What is on top of block b?". These might be translated into responses that give information about the on/2 relation.

Starting code: blocks5.pl and read_line.pl

Simple grammars implementing these two idioms are provided in the starting code. You can test the parsing and code that is generated using "test_parser.". Here is a sample parse for a command:

    ?- test_parser.
    ?? Please put block a on top of block b, c on d, and f on the table.

    [please, put, block, a, on, top, of, block, b, (,), c, on, d, (,), and, f, on, the, table, .]
    [place(a, b), place(c, d), place(f, table)]
    ?? ...

The first line is the successfully parsed list of words, the second is the actions that the command should execute. Sentences which are not accepted are silently ignored by the parser.

It might be useful to discuss the repeat/0 predicate: it always succeeds as a goal, and can be backtracked any number of times. If a line of execution fails for some reason (such as perhaps hitting a fail goal), repeat succeeds again and Prolog attempts the execution and prove things again.

Part I

To help you with understanding the sample code, complete the following extensions.

  1. Add support for an optional "block" prefix to question idiom q. (This should only require two minor changes.)
  2. Add code that will cause the command list generated by command idiom c to be executed. If a place command was successful, write the string "Ok.". (You might need to use cuts to prevent more than one place rule from matching.)

Part II

Complete the following idiom extensions.

  1. Formulate a new question idiom, one of whose scripts is "What is block X sitting on?".
  2. Formulate a new question idiom, one of whose scripts is "Which blocks are on the table?".
  3. 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.
  4. 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 ...") accurately.

Part III

In addition to the code you've written for this assignment, also hand in a text file demonstrating the use of your new idioms. This file should be a transcript of a session (or several sessions) of interaction with the world using each of the various idioms. Be sure to demonstrate any particularly novel or interesting extensions you have added beyond the basic scripts in Part II.