CSCI.4430/6430 Programming Languages Spring 2015
Programming Assignment #1

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 help from the TAs or the instructor. You are encouraged to use the LMS Discussions page to post problems so that other students can also answer/see the answers.

Constraint Solving and Natural Language Processing with Prolog

Part 1. Puzzle Solving.

Image of puzzle to solve

In the image presented above, there are nine circles. Each circle must be assigned a number between 1-9 exactly once. Find the satisfying assignment of numbers such that the sum of the numbers across each side and the horizontal is 17. For example, the sum of the numbers filled in circles a, b, and d must add up to 17. Likewise, the sum of the numbers filled in circles d, e, and f must add up to 17.

Your final solution should have a one argument predicate called puzzle. The predicate's argument should represent the number assignments for each slot in the puzzle. The ordering of the list should be [A,B,C,D,E,F,G,H,I], where the letters represent the slots in the above image.

By entering the following Prolog query, your program should return a valid solution to the puzzle:

?- puzzle(Solution).

Hitting semicolon should return alternate solutions.

Your code should be placed in a file called

Part 2. Sentence Parsing.

Here, you will create a grammar the accepts a set of sentences. You will then use this grammar to output a parse tree for a given input.

Below is the set of sentences that your grammar must be able to accept.

You will create a predicate called loop to allow the user to continuously input sentences and receive the resulting parse tree.


?- loop.
|: a train flew.
|: every train arrived.

To assist you with this part, we have provided you with the read_line predicate, which can be found in

UPDATE 2/5/2015: To provide further assistance with Part 2 and Part 3, we have provided sample code, which can be found in This example program will show you how to load code from a separate file and how to use DCG syntax to accept a grammar and generate a simple parse tree.

The parse tree generated by your program must use the following predicates:

Note: the number next to the predicate represents the number of arguments it expects.

Your code should be placed in a file called

Extra Credit (Up to 10% bonus)

Given an input parse tree, output the sentence formed from the tree.

Part 3. Simple DB.

For this part, you will be extending your grammar from Part 2 to simulate a simple database. You will write a loop predicate that will continuously prompt the user to enter a command or query. The program should output a 'yes' or 'no' in response to entering a query.

Commands to the database must take the following forms:

the <noun> _ <verb>.
the <noun> _ did not <pres_verb>.

<noun> is one of the nouns from Part 2.

<verb> is one of the verbs from Part 2.

<pres_verb> is either leave,fly, arrive, or stay.

_ is any word.


the person jane left.
the person jack did not leave.
The effect of entering a command should be the creation of a fact in your knowledge base (the Prolog program).

Queries to the database must take the following forms:
did a <noun> <pres_verb>?
did every <noun> <pres_verb>?


did a train arrive?
did every bike stay?
A query must output either a 'yes' or a 'no' depending on whether the statement is true or false. Semantically, 'a' represents the existential quantifier and 'every' represents the universal quantifier. For queries using 'every', output 'yes' if there are no facts to query.


?- loop.
|: the person john left.
|: the person jane left.
|: did a person leave?
|: did every person leave?
|: the person jake did not leave.
|: did a person leave?
|: did every person leave?
|: did a train arrive?
|: did every train arrive?

Note: For simplicity, you can assume that duplicate commands or contradictory commands will not be given by the user.

Your code should be placed in a file called

Extra Credit (Up to 15% bonus)

Allow your database to accept duplicate/contradictory commands by issuing warnings and overriding previous knowledge. Extend your language to enable more interesting commands/queries.

Due Date:
Received Time Grade Modification
before Tuesday, 02/17, 6:00PM +10%
before Wednesday, 02/18, 6:00PM no modification (on time)
before Thursday 02/19, 6:00PM -10%
before Saturday, 02/21, 6:00PM -25%
after Saturday, 02/21, 6:01PM 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 LMS user name(s) as the filename, either or Only submit one assignment per pair via LMS.