COSC 4480-Programming Language

Assignment 3 (Prolog Programming)

Overview

For this assignment, you will experience programming with Prolog, by write a program to solve the question below. This could be a group/solo assignment. If you choose to finish it as a group, your group consist of at most 3 people.

Problem Description

Given the partial family tree of the gods of the ancient Greeks encoded as a Prolog database

parent(chaos, gaea).

parent(gaea, cyclope).

parent(gaea, chronos).

parent(gaea, coeus).

parent(gaea, oceanus).

parent(uranus, cyclope).

parent(uranus, chronos).

parent(uranus, coeus).

parent(uranus, oceanus).

parent(chronos, hades).

parent(chronos, poseidon).

parent(chronos, zeus).

parent(rhea, hades).

parent(rhea, poseidon).

parent(rhea, zeus).

parent(coeus, leto).

parent(phoebe, leto).

parent(leto, apollo).

parent(leto, artemis).

parent(zeus, apollo).

parent(zeus, artemis).

parent(oceanus, iapetus).

parent(tethys, iapetus).

parent(hera, ares).

parent(zeus, ares).

male(chaos).

male(cyclope).

male(uranus).

male(chronos).

male(coeus).

male(oceanus).

male(hades).

male(poseidon).

male(zeus).

male(ares).

male(apollo).

male(iapetus).

female(gaea).

female(rhea).

female(leto).

female(hera).

female(phoebe).

female(tethys).

female(artemis).

Define rules for the following relationships:

a) father

b) mother

c) child

and answer the following questions:

d) Father of Ares

e) Mother of Apollo

f) Children of Uranus

Read the Assignment2-Prolog-Reading.docx before you do this problem. Given the following graph of possible flights between seven US cities, write a Prolog program that would check if there is a route from Fresno to Dallas, from Seattle to Boston, and from Atlanta to Fresno:

Warning: if there are cycles in the graph, Prolog might never find a solution and may never say that there are no solutions. If this happens in your assignment, make a note of that.

Prolog Development Environment:

SWI-Prolog is a good, standard Prolog for Windows and Linux. It's licensed under GPL.

Download and Install SWI-Prolog

You are suggested to download the stable version of SWI-Prolog: http://www.swi-prolog.org/download/stable

Youtube tutorial: https://www.youtube.com/watch?v=Ay2o3Nv1A-Q&index=1&list=PLmiQ7Pe7Po0w2uS41Bk7trE4XGN4IRYHD

Documentation:

The first thing you need to write is to put your team member names if you are doing this project as a group.

It is expected that you will follow standard practices of documentation of your program. That means that classes and methods should have header information include: Authors, date written, list and description of parameters or data members (where appropriate), type and description of return values (where appropriate), a general description of the purpose of the class or method.

You should also put in comments for code for which its meaning is not obvious. That does not mean to put in comments that a loop will loop through some values, but rather put in comments for things that it would take study or searching documentation to understand. You should also put in comments for constructs that are not common in every language (e.g. use of regular expressions).

And finally, any part of the program that asks the user for input should be proceeded with an appropriate prompt. An appropriate prompt is one that tells the user what to enter and in what form. For example, "Enter two floating-point numbers separated by whitespace on one line."

Take the screenshot of your execution result and past it in your report.

Note: You have to include the names of your team members in your code comment, in order to get grade for every member.

Deliverables:

Zip the source file(s) into one zip file, name it as source.zip

Name your document file as report.doc/report.docx.

Submit two files on Canvas: source.zip and report.docx

Graph structures and paths

This is a reading materials to finish your 2^nd lab. Regarding the graph, consider the following connected graph:

The edges can be represented in Prolog as facts:

edge(1,2).

edge(1,4).

edge(1,3).

edge(2,3).

edge(2,5).

edge(3,4).

edge(3,5).

edge(4,5).

To represent the fact that the edges are bi-directional we could either add eight more 'edge' clauses (edge(2,1),etc.) or we could try a rule like:

(*) edge(X,Y) :- edge(Y,X).

This is not a good idea, however. To see why it is not a good idea, try the following goal.

?- edge(5,1).

Notice that the rule (*) will be tried over and over in an infinite loop, so the goal will not terminate. Try it! A better way to handle this is to use a rule such as the following.

connected(X,Y) :- edge(X,Y) ; edge(Y,X).

Note the use of disjunction ';' in this rule. This rule could have been written as two rules:

connected(X,Y) :- edge(X,Y).

connected(X,Y) :- edge(Y,X).

We wish to develop a Prolog definition which generates paths between any two nodes of the graph. More specifically, we require the following (kind of) behavior for the predicate 'paths'.

?- path(1,5,P).

P = [1,2,5] ;

P = [1,2,3,5] ;

P = [1,2,3,4,5] ;

P = [1,4,5] ;

P = [1,4,3,5] ;

P = [1,4,3,2,5] ;

P = [1,3,5] ;

P = [1,3,4,5] ;

P = [1,3,2,5] ;

no

The paths are represented by the list of nodes through which one must travel to get from node 1 to node 5. Here is a definition for paths:

path(A,B,Path) :-

travel(A,B,[A],Q),

reverse(Q,Path).

travel(A,B,P,[B|P]) :-

connected(A,B).

travel(A,B,Visited,Path) :-

connected(A,C),

C \== B,

\+member(C,Visited),

travel(C,B,[C|Visited],Path).

A declarative reading for the first clause amounts to "A path from A to B is obtained if A and B are connected".

A declarative reading for the second clause amounts to "A path from A to B is obtained provided that A is connected to a node C different from B that is not on the previously visited part of the path, and one continues finding a path from C to B". Avoiding repeated nodes ensures that the program will not cycle endlessly.

=============================================================

reverse(?List1, ?List2)

Is true when the elements of List2 are in reverse order compared to List1.

member(?Elem, ?List)

True if Elem is a member of List. The SWI-Prolog definition differs from the classical one. Our definition avoids unpacking each list element twice and provides determinism on the last element. E.g. this is deterministic:

member(X, [One]).

[Head|Tail]

In this notation the variable Head represents the leftmost element of the list and the variable Tail represents the rest of the list represented as another list. A head can be anything, from a predicate to another list, but the tail is always another list. This is a combined list.

\+

It's the 'not provable' operator. It succeeds if its argument is not provable (and fails if its argument is provable).