Notes on the "Sleepy" Program
David Matuszek, Villanova University

This page is a discussion of the Prolog source code for the "Sleepy" program.

The following predicates are declared dynamic because they may be changed during execution of the program:

:- dynamic at/2, i_am_at/1, i_am_holding/1, alive/1, lit/1, visible_objects/1.

The form functor/arity refers to the set of predicates with the given name, for example, at, and the given number of arguments, 2.

The turnstile ( :- ) at the very beginning of the clause indicates that this clause should be executed as soon as it is consulted. This means that the compiler has already seen the lines above it (and can use them as needed in this clause), but has not yet seen the lines below it. You should declare clause to be dynamic before the compiler gets to those actual clauses, otherwise (depending on the compiler) it may be too late.

In fact, i_am_holding/1 does not actually need to be declared dynamic, because the game starts out with no clauses of this form. The first such clause is created as you play the game, so it will automatically be dynamic.

Standard Prolog does not recognize or require dynamic, but some implementations (including SWI Prolog) require dynamic for reasons of efficiency.

The line

:- retractall(i_am_holding(_)), start.

occurs at the end of the game. If it were just :- start. then all it would do is call the start/0 predicate as soon as the game is loaded (this is a predicate defined in the game that prints out instructions). Why does it retract all clauses of  i_am_holding/1 , but not any of the other dynamic clauses?

The answer lies in the way consult/1 works.

• If you have no previous clauses of a given functor/arity, but the file you consult has such clauses, they are just added to the database.
• If you do have previous clauses of a given functor/arity, and you consult a file containing the same kind of clause, the new clauses replace the old ones.
• If you have previous clauses of a given functor/arity, and the file you consult has no such clauses, the old clauses are left unchanged.

So here's what happened. While I was writing and debugging the game, I edited and consulted the file sleepy.pl (and played the game) many times. But when I was partway through the game, and found and fixed a bug, I consulted the file again, and played again from the beginning--I thought. But since at that point I might have been holding the flyswatter, and since the file I consulted had no clauses of i_am_holding/1 in it, my consult left me holding the flyswatter--not exactly the way the game should start out. So this is a case where Prolog's "intelligent" consult caused a subtle problem.

I included a dump/0 predicate for debugging. This predicate lists all my dynamic clauses, that is, the things that I want to look at and see if they are getting updated correctly. The form listing(functor) will list all clauses with that functor; the form listing(functor/arity) will list clauses with the given functor and the given arity.

Note that the usual rule is to put specific clauses before more general ones. For example, take(fly) and take('light switch') precede take(X). This is because clauses are tried in the order in which they appear, and if you put take(X) first, it would be used even when you tried to take the fly or the light switch.

I like to put the "failure" cases first--all the things that can go wrong. That way you don't have to check for them again in the "success" case. (This isn't primarily a matter of efficiency, but of "safe" programming--if you have to check for the same thing in two different places, there's always the danger that you will change or fix one place, and forget to change or fix the other.)

For example, take/1 checks first for trying to take the fly or the light switch, then for whether you are already holding the object. Only after that does take/1 actually try to pick up the object. The other failure case, that the object is not in the same room as you are, is very difficult to put first, because negation in Prolog is tricky. Always try to avoid negation.

In this game negation gave me quite a lot of trouble, because some things depended on the room being lit, and others on it being dark. I didn't want to have both lit/1 and dark/1 predicates, because (again) having the same thing in two places is unsafe programming. So I had to use negation, and juggling the clauses around to minimize the number of negations took quite a bit of time.

Why avoid negation? Because negation in Prolog doesn't behave logically! Negation is an extra-logical predicate.

The basic problem with negation is that it does not "instantiate" (find a value for) variables. There are only a finite number of values that can satisfy a test (because of Prolog's "closed world assumption"), but there are infinitely many that fail to satisfy the test.

A negated test can never instantiate variables. Consider \+foo(X).   If foo(X) fails, that means it didn't find a suitable value for X; so \+foo(X) succeeds, but without a value for X. If foo(X) succeeds, then Prolog found a value of X that satisfies foo(X), but it doesn't satisfy \+foo(X), which fails and forces Prolog to backtrack--even if we could keep the value for X, we couldn't proceed and do anything with it.

For example, if we say
     \+ i_am_at(X)
this does not set X to some value that I'm not at. Since there are an infinite number of such values (not all of them "rooms"), this makes sense. It also means that a double negation, such as
     \+ \+ i_am_at(X)
does not instantiate X, although logically it would make sense to do so.

Another consequence is more subtle, but even more of a trap. Conjunction (and) should be commutative: A and B logically means the same thing as B and A. But negation in Prolog destroys commutativity.

Suppose you have the facts:

     female(jane).
     female(mary).
     rich(mary).

Prolog behaves as follows:

     ?- female(X), \+rich(X).

     X = jane

     Yes
     ?- \+rich(X), female(X).

     No

This seems like a serious bug in Prolog, which is supposed to be a logical language. In fact, it's a deliberate design decision, because otherwise answering queries requires exponential time (it's an NP-complete problem).

You can use negation in Prolog if you understand it well enough (or if you're lucky!), but experienced Prolog programmers try to avoid negations.

Prolog's "cut," ! (that's an exclamation mark), is what I like to call a commit point; it prevents trying any more alternatives. When you reach a commit point, anything that previously occurred in this clause, such as instantiating variables, cannot be undone--you are committed and cannot backtrack. In addition, you are committed to this clause; if something later in the clause causes it to fail, you cannot go on to try other clauses in this predicate.