Important advice on Assignment 1 of AIT SDT Course

(Version 1.1)


This page gives some important advice on Assignment 1 of the SDT course.


In this assignment you are writing a predicate that delivers just a "yes or no" answer, without binding any variables. For such predicates, the Prolog interactive top level prints out "yes" as soon as the predicate exits successfully, and does not give the user the option of exploring if there are any other ways in the program for arriving at a successful exit.

However, this is an important issue, so you should check what your predicate does when you re-enter it through the Redo port (after it has exited successfully). Here is one way of doing that, for a hypothetical predicate foo, which takes a list of integers as an argument:

| ?- foo([2,0,3]), write(true), nl, fail. true true no

If your program prints just one line containing the atom true, then everything is OK. However, if you see two or more lines containing true (as in the example above), that means that there are two or more paths in your program through which it can return successfully. (It may also happen that the predicate succeeds an infinite number of times, in which case you better interrupt using Ctrl-c.)

The problem with this is that Prolog explores all such paths. When you have two or more calls to such predicates in a row (which you probably will have), then all possible combinations of these paths are potentially explored. If you just have two ways of arriving at success (as above) and you call the given predicate. say. 20 times, then 220 paths will be explored, when the 21st call fails...

By tracing the above call you can find the point where a second successful path exits. A frequent cause of such behaviour is when you have a clause for handling an empty list, a singleton list and a general list, e.g.:

foo([]). foo([X]) :- bar(X). foo([X|L]) :- bar(X), foo(L).

Notice that for solving the goal | ?- foo([1]). Prolog can use the second clause on it own, or the third and the first one together. In this example the remedy is simply to remove the second clause, which is unnecessary.

If, for some reason, you do want to handle singleton lists differently, than you should make sure that the recursive clause is not applicable to singleton lists. Two examples for doing that are shown below:

foo([]). foo([]). foo([X]) :- foo([X|L]) :- bar1(X). ( L = [] -> bar1(X) foo([X|L]) :- ; bar2(X), L = [_|_], foo(L) bar2(X), ). foo(L).

Another typical cause of the "multiple yes answers" syndrome is the use of disjunction in a place where if-then-else should be used:

product_is_zero(A, B) :- product_is_zero(A, B) :- ( A = 0 ( A = 0 -> true ; B = 0 ; B = 0 ). ).

If both A and B happens to be 0, then the predicate using disjunction (left hand side) succeeds twice, while the one using if-then-else succeeds only once.


Last modified by Péter Szeredi, szeredi@cs.bme.hu, on 1.11.2017.