Lab: Prolog

CSC261 - Artificial Intelligence - Weinman

Summary:

We explore writing programs and posing queries to the GNU Prolog environment.

Preparation

1. Make a directory for this lab.

   $ mkdir somewhere/prolog

   $ cd somewhere/prolog
2. Open Emacs and create a new Prolog program called blocks.pl in your new directory.
3. In emacs, type

   M-x prolog-mode 

   to change from Perl (the default for a pl extension) to Prolog mode.

Exercises

A: Facts

1. Using the predicate on, and the names of the blocks as well as table, define the ground facts for the blocks world above in your prolog file blocks.pl.
2. Save your file, start prolog, and load your program. Fix any syntax errors. For example:

   $ prolog

   ?- ['blocks'].

   true

   ?- 

   Note that, like other shells, this prolog interpreter allows you to use the up and down arrows to navigate through your command history.
3. Test one on relationship you expect to be true and another you expect to fail.
4. Use a query to find a substitution that tells you what block a is on.
5. Use another query to find all substitutions that tell you all on relations.

B: Rules

1. What should the "base case" for this predicate relation be? That is, what is the simplest (or most direct) way for a block to be above another?
2. Write the body for this base form of the rule using the head above(X,Y).
3. What should the "recursive case" for this predicate be? That is, what if you had a stack of ten blocks? How would you go about reasoning that the top one is indeed above the bottom block?
4. Write the body for this recursive form of the rule using the head above(X,Y).
5. Save your file and re-load your program in your prolog shell. Fix any syntax errors.
6. Test your "base case" of B.2. For example

   ?- above(a,b).  

   true 

   At this point, prolog is waiting for you press return to terminate the query. You could (don't do it yet!) type ; to continue the search for another solution, or you could type Enter to stop the search.
   1. What do you expect to happen if you type ;?
   2. Verify your prediction.
   3. The (perhaps peculiar) value of false displayed next means it could not find any other unifying matches.
7. Test several other examples of this base case.
8. Test your "recursive" case of B.4. For example

   ?- above(a,c).

   If prolog terminates with a stack overflow error, you haven't architected your recursive case in such a way that the chaining can successfully terminate. If you do not see how to fix this, review AIMA section 9.4.4. Remember that prolog tries to unify rule heads from top to bottom (in the file) and atoms from left to right (in a rule body).
9. Ask prolog to identify all the blocks above a. What do you expect it to produce? Verify your prediction.
10. Ask prolog to identify all the blocks below a for you. What result do you expect? You will need to use the same interaction commands mentioned in B.6.
11. Ask prolog to identify all the blocks that are above one another.

C: Prolog Shell Responses: true, false, and nothing.

1. When the interpreter shell reports true, the query was satisfied without any variable substitutions to fill in. For example, try the following query

   ?- above(a,b).

   Because no substitutions in the query are necessary, it simply reports true. But it also waits for your response to continue chaining.
   1. Type ; to ask for the next unifier. What response do you get?
   2. The answer false means it has finished iterating (chaining) over all possible unifiers and found no further solutions.
   3. Type the same query again. This time, press Enter after it responds true and waits for your response. The enter key tells Prolog to stop iterating over all other possible matches and rules. What response do you get?
   4. The silent answer means it has not finished iterating and there may be further solutions.
2. Here are some more examples to help make sure you understand the distinction.
   1. Run following query to verify how Prolog responds for a ground fact

      ?- on(a,b).
   2. What do you expect the following query to produce (there should be no available unifier)?

      ?- on(X,a).

      Verify your prediction.
   3. Run the following query to verify how Prolog responds when there are available unifiers (but don't type anything further yet).

      ?- above(a,X).
   4. After running the query above, you should have seen the first unifier Prolog discovered. If you now press Enter, its silence will indicate that there are more iterations to run through. (Go ahead and do so now.) This silence means there may be more unifiers; it does not mean there are more unifiers (it simply has not yet concluded there aren't more).
   5. Run the query again, but type a single semicolon (;) after the first unifier. Prolog should iterate far enough to show you the next unifier, once again waiting for your response.
   6. Continue by typing one more semicolon so that Prolog has shown you three possible unifiers, but is still waiting to do more searching. Now press Enter. You should see by its silence that although you asked for the next unifier twice, Prolog has not yet exhausted its iterations.
   7. Run the query one last time, repeatedly typing a semicolon until the matching is exhausted. You should finally get a confirming false.

D: Tracing the Chain

1. Turn on the trace capability by running the trace procedure as follows.

   ?- trace.

   true.

    

   [trace] ?-
2. Let's trace the query from the previous exercise. Issue it as before.

   [trace] ?- above(a,X).

   You should now see a stack frame with the ground symbol a and a generic variable name in place of X. The debugger is waiting for you to step the chaining algorithm. Press Enter to step (or "creep", as it says). Continue pressing Enter (slowly!) until the first unifier is found.
   Try to understand how the execution of the chaining algorithm reached the first unifier.
3. At the unifier prompt, type ; to continue searching for additional unifiers. Then, continue pressing Enter (slowly!) to trace the subsequent search. Make sure you can follow and understand the steps of the algorithm.
4. To turn off the tracing behavior, give the nodebug command.

   [trace] ?- nodebug.

E: [Optional] Interpreting failure

1. Think about how you would define (in English) the clear predicate.
2. What additional machinery do you need prolog to incorporate in order to define the predicate you've concocted?
3. When you have your answer, review the note below.¹
4. Define the rule with head clear(X).
5. Save your file and reload your program in prolog. Note that if prolog warns you about unused ("singleton") variables in an expression, you can replace these variables with the anonymous placeholder _.
6. Test your definition of clear on blocks you know should succeed and blocks you know should fail.
7. Ask prolog to list all the blocks that are clear. Explain the result.

Lab Assignment

Footnotes:

\+ P

try to satisfy P; if it is satisfied then fail, otherwise, succeed.