After completing this assignment you will learn:
Similar to Assignment 1, you are to implement a Prolog predicate to determine set equality for set of coordinate pairs.
Refer to Assignment 1 for using lists of lists to represent sets of coordinate pairs. The representation is the same except that we use Prolog's list syntax. Here is an example of four coordinate pairs using Prolog lists,
[[1,1], [1,2], [1,3], [2,2]]
This set of coordinate pairs would be equivalent,
[[2,2], [1,2], [1,1], [1,3]]
For this assignment, please make the additional assumption to restrict our list representation so that they will not contain duplicate elements. For example, we disallow lists like this,
[[2,2], [2,2]] [[1,2], [3,4], [1,2]]
Please define the predicate student_name/1 and
include this with your submission. Example:
student_name("Sally Student").
You may get a surprise if you try to test your student_name/1 predicate, because Prolog has a primitive implementation of strings and a default I/O that doesn't deal with strings.
A Prolog string is represented as a list of character codes. A character code in gprolog is an integer corresponding to the ASCII collating sequence. If you don't know what that means, type,
man ascii
at a Linux prompt.
In practice this means beginning Prolog programmers may get confused when using strings, because they can be entered with the convenient and familiar syntax (delimited by double quotes) but don't print out that way. Consider the following gprolog query,
| ?- student_name(Name). Name = [83,97,108,108,121,32,83,116,117,100,101,110,116] yes
Name gets bound to a list of integers. So if you define your student_name/1 predicate correctly, this query will return list of integers.
The automated grader program is sufficiently sophisticated to capture a string representation from your student_name/1 predicate. Other than this, the assignment does not require you to deal with Prolog strings.
Define a Prolog predicate set_eq/2 that succeeds
when both arguments, sets of coordinate pairs, are equal sets. When your
predicate succeeds, it must produce exactly one proof.
Prolog backtracking is very powerful because the engine explores all possible ways to construct a proof from the facts and rules you supply in your program. Sometimes, however, you want Prolog to produce one solution for a proof. Designing Prolog facts and rules to always yield exactly one solution requires thoughtful analysis and may require use of the cut (!) predicate to prune unwanted backtracking.
You are only required to handle the case when both arguments to
set_eq/2 are fully ground terms.
If both terms are ground, then your Prolog program must do one of two
things: Either it fails, when the sets are not equal, or it succeeds
by generating exactly one solution.
You can know your program generates exactly one solution when gprolog answers,
yes
to a query. If gprolog answers,
true ?
awaiting your response at the prompt, this means gprolog found one way to prove a solution, but there may be others.
If one or both of the arguments to set_eq/2is not
fully ground, then your Prolog program may behave in any way you see
fit. Your program may go into infinite recursion, may cause the
variable parts of the unground terms to become bound to a ground
values, or do something else. There are no requirements when running
when both arguments are not fully ground terms.
Here is an example gprolog session showing how your program might run.
$ gprolog GNU Prolog 1.3.0 By Daniel Diaz Copyright (C) 1999-2007 Daniel Diaz | ?- ['a3.pro']. compiling /home/johnnym/a3.pro for byte code... /home/johnnym/a3.pro compiled, 5 lines read - 1457 bytes written, 11 ms (1 ms) yes | ?- set_eq([],[]). yes | ?- set_eq([[3,2],[1,1]],[[1,1],[3,2]]). yes | ?- set_eq([[1,1],[1,2]],[[1,1],[2,2]]). no
One of the challenges in developing this Prolog predicate is to get it to produce exactly one solution (or fail) when the arguments are ground terms. Since Prolog's resolution engine will search for all possible ways to construct a proof, you need to design your facts and rules so that they are deterministic, i.e., the Prolog engine will arrive at a single solution to a proof. In some cases, it may be necessary to use a cut (!) to ensure determinism in your rules.
Consider the following query using the gprolog built-in, member/2.
?- member(1, [1]). true ? ; no
When gprolog prompts with "true ?" it does not yet know if there are any more solution proofs to the query. Typing ";" at the prompt tells gprolog to backtrack, which means it continues looking for other ways to prove this query. Since gprolog finds no other ways, it answers "no". This example shows there is only one solution, but gprolog still backtracks and then fails.
Consider the following query using the gprolog built-in,
member/2.
?- member(1, [1,1]). true ? ; true ? ; no
Notice there are exactly two solutions. Then execution searches three times for a proof. The first times, it find a solution,and the third time it fails.
The member/2 is not designed to produce only one
solution. Since there is sometimes a need to test for membership that
does yield exactly one solution, gprolog provides another built-in,
memberchk/2. Try running the above queries using
memberchk/2 instead of member/2.
A driver program similar to this will be used to run your program:
consult("a3.pro").
consult("a3driver.pro")
student_name(X), print(X).
a3driver(X).
Submit via e-mail using a mime-encoded, zipped attachment. (Note, most e-mail client programs do mime-encoding automatically for you, but to create the zip file attachment, you will need to use zip utility. The zipped attachment must be named, a3.zip, which contains one file, a3.pro in the current directory (i.e., root of the zip archive).
To: martin@cs.sjsu.edu Subject: A3