Homework 7

Prolog

out:12/2, due: 12/11

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.