This assignment is will give you an opportunity to get your feet wet
with Prolog. We have a version of sicstus proplog available on gl which you can invoke with the prolog command. If you want to install prolog on your own computer, we recommend the open source SWI-Prolog which is available for Windows, Linux and MAC OSX.
Read the chapter 16 in our text (Logic Programming
Languages) as chapter eight in the SICStus Prolog User's
Manual which provides
a
terse introduction to Prolog as well as Chapters One
(How
to run Prolog) and Two
(Debugging).
You might also find this Prolog tutorial helpful.
1 Append [10]
This is just to help those who are very new to Prolog get started.
Define the append predicate by typing the clauses directly into the
Prolog interpreter. Here is a sample
session with Sicstus Prolog. The first line ( [user].)
tells Prolog to consult , or read new clauses to be added to
the database, the user. That is, clauses will be read from the
terminal and added to the database. The next two lines are the two
clauses that will define append/3 (i.e., a predicate named
append with three arguments). The (control-D) is how one signals
an "end of file" to the Prolog reader. In this case it causes
the Prolog reader to stop "consulting the user". Note that
the periods at the end of the first three lines are required.
Now try to append the list [a,b,c] to the list [1,2,3] by
typing in the goal append([a,b,c],[1,2,3],X).. If this is
successful, the binding for the variable X will be displayed and
the interpreter will wait for you to type a carriage-return
(indicating that you want no more answers) or a semi-colon (indicating
you want to to seek another answer). To help you understand how this
definition of append works, you can cause the interpreter to
trace the append predicate by issuing the command
trace(append/3). This will cause the interpreter to print
informative messages when it is executing append/3. Note that it
pauses whenever the predicate is called, typing an $h$ will show the
possible responses and typing a carriage-return will cause it to
continue ("creep").
Now try some other ways to use your append predicate.
Show what happens when you ask Prolog to solve each of the following goals. capture the session results in a file session1.txt.
- append([a,b,c],X,[a,b,c,d,e,f]).
- append(X,[d,e,f],[a,b,c,d,e,f]).
- append(X,Y,[a,b,c,d,e,f]).
- append(X,[d,e,f],Y).
- append(X,Y,Z).
Note: you can easily capture an interactive session on Unix using the standard unix script command (type man script for information on the script command).
1 Kinship Relationships [50]
This problem will give you some experience designing a simple logic
programming database in terms of primitive facts and rules. The domain
is one we are all familiar with - kinship relations.
Our western-European culture considers a number of kinship relations
to be especially meaningful and gives them names. Other cultures have
developed a much richer set of relationships. Most of these relations
can be defined in terms of a small number of primitive relations and
attributes, such as those having to do parenthood, marriage, gender,
age, etc. Your task is to:
- Choose a set of primitive relationships to encode as facts that
will allow you to define the rest of the relations as rules.
For example, you might choose to present child/2 as a primitive relation and define parent/2 in terms of child using the rule parent(X,Y) :- child(Y,X). Put the definitions and rules in a file kinship.pl. You can start with kinship_stub.pl if you like and replace the fail/0 predicates with appropriate code.
- Test out your database design by creating a file the facts about your
own immediate family. Name this myfamily.pl. You can view myfamily.pl as an example.
Demonstrate that your representation works via a session showing a query for each of the predicates (facts and rules). Capture the session in a file session.txt.
- versity that your representation works using the file hw7test.pl. Load this into prolog and it will print out all of the relations than can be proven.
- Hand in the
three two files kinship.pl and myfamily.pl and session.txt
The relationships you must define are the following:
- child(X,Y) - true if X is a child of Y.
- daughter(X,Y) - true if X is a daughter of Y.
- parent(X,Y) - true if X is a parent of Y.
- mother(X,Y) - true if X is the mother of Y.
- sibling(X,Y) - true if X and Y are siblings (i.e. have
the same biological parents). Be sure your definition does not lead
to one being one's own sibling.
- brother(X,Y) - true if X is a brother of Y.
- grandparent(X,Y) - true if X is a grandparent of Y.
- grandmother(X,Y) - true if X is a grandmother of Y.
- uncle(X,Y) - true if X is an uncle of Y. Be sure to
include uncles by marriage (e.g. your mother's husband) as well as
uncles by blood (e.g. your mother's brother).
- sister_in_law(X,Y) - true if X is a sister-in-law of Y.
- mother_in_law(X,Y) - true if X is a mother-in-law of Y.
- spouse(X,Y) - true if X and Y are married.
- wife(X,Y) - true if X is the wife of Y.
- ancestor(X,Y) - true if X is a direct ancestor of Y
(i.e. a parent or an ancestor of a parent).
- descendant(X,Y) - true if X is a descendant of Y (i.e. a
child or an ancestor of a child).
- relative_by_blood(X,Y) - true if X is a blood relative of
Y (i.e. related through some combination of offspring relations).
Hint: your blood relatives are just those people with whom you share a
common ancestor.
-
relative(X,Y) - true if X and Y are related somehow (i.e.
through some combination of offspring and marriage relations). Hint:
this is easy to define in terms of relative-by-blood and spouse!
- male(X) - true if X is male.
- female(X) - true if X is female.
The goal is to devise a good representation -- one that is intuitive
and natural and would be easy to extend. You may need to (or want to)
define other relations, e.g., a gender/2 relation. Watch out for
"loops", or, more accurately, unterminating recursion. For example,
you do not want a rule like spouse(X,Y) :- spouse(Y,X), which
will lead to infinite recursion if you try to find all solutions to a
query about the spouse relation.
3 Growing a Language [40 ]
Watch the video of the
talk Growing a Language
by Guy
Steele which was given as a keynote talk at
the OOPSLA
Conference. in 1998.
Write a short review of at least 500 250 words intended for an audience of
Junior Computer Science majors. Your review should include a short
factual description covering the basic facts, e.g., who is the
speaker, when and where was the talk given, that is the topic, what
qualifications does the speaker have relative to the topic. It should
also briefly state the major position or points the speaker made in
the talk. Finally, you should express your own opinion about the talk,
e.g., do you recommend it to other computer science majors? Why or why
not? Is it still relevant after 13 years? Does Dr. Steele's rhetorical
trick of starting with a simple subset of English help or obscure his
point. Did the talk give you new insights into the design and
evolution of programming languages?
Submit your review as a pdf document named growing.pdf.
Testing your code
See hw7test.pl for a prolog file you can consult. Running it with myfamily.pl should result in something like the following output: hw7out.txt.
What to hand in
Submit the files session1.txt, kinship.pl, myfamily.pl, session2.pl, growing.pdf.
|