Prolog: How to Write Programs

How to write Prolog programs

Prolog is a notation for stating logical relations that happens to be executable. It has few control structures, because it is very difficult to assign meanings to control structures. Accordingly, you should try to learn how to write declarative programs. Avoid using the control structures listed below. If you find Prolog frustrating and difficult, you are probably still programming procedurally.

A Prolog predicate consists of multiple clauses. It is useful to think of each clause as coding a separate ``case''--first describe what constitutes the case, then describe the result for that case. For example, the absolute value of a number is (1) the negation of the number, if it is negative, or (2) the number itself, if it isn't negative.

	abs(X, Y) :- X < 0, Y is -X.
	abs(X, X) :- X >= 0.

If a case has subcases, feel free to invent another predicate to deal with the subcases.

Remember that parameter transmission is by unification. You can do a lot of your work right in the parameter list. For example:

	second([_, X | _], X).	/* 2nd argument is 2nd element of list. */

You can often simplify code by writing parameters that match only the specific case you are interested in. See member and append for examples. (Note: when you must program procedurally, by convention the ``result'' is the last argument.)

Recursion is fully supported. In other languages you must always test for the base case first; in Prolog, the base case can (and should) go last, if it is such that the more general clauses will fail--see append. If the predicate is to fail in the base case, it can (and should) be omitted; for example, the base case for member is the unnecessary clause:

	member(_, []) :- fail.	/* No 1st parameter is a member of [] */

You can't keep a value for future use by ``assigning it to a variable.'' If it is temporary, local information, you can pass it around as a parameter; if it is relatively permanent information that should be globally accessible, you can put it in the database (see assert and retract below). Prolog has no functions, so ``results'' must be returned by instantiating one or more parameters.

Many predicates can be used as generators, to generate one solution after another until later conditions are met. For example,

	member(X, [1, 2, 3, 4, 5]), X > 3.

succeeds and instantiates X to 4. If backed into, it re-instantiates X to 5. (But if you think declaratively, this just says ``X is a member of the list [1, 2, 3, 4, 5] that is greater than 3.'')

When one clause fails, the next one is tried. If you want the failure of a clause to cause the failure of the entire predicate, you can use a cut-fail combination:

	sqrt(X, RootX) :- X < 0, !, fail.
	(more clauses of sqrt should follow)

This is a procedural shortcut that avoids the necessity of having X <= 0 in every clause; it is justified only if the test is complex and there are many clauses.

Arithmetic is performed only upon request. For example, 2+2=4 will fail, because 4 is a number but 2+2 is a structure with functor '+'. Prolog cannot work arithmetic backwards; the following definition of square root ought to work when called with sqrt(25, R), but it doesn't.

	sqrt(X, Y) :- X is Y * Y.	/* Requires that Y be instantiated. */

Arithmetic is procedural because Prolog isn't smart enough to solve equations, even simple ones. This is a research area.

It is possible to build a so-called fail loop in Prolog. Such a loop has the form generate-process-test; the loop repeats if the test fails. For example, the following will print the elements of a list, one per line:

	print_elements(List) :- member(Element, List), write(Element), nl, fail.

However, if the processing is at all complex, it may be difficult to backtrack over it safely. Tail recursion is safer, cleaner, and usually more efficient:

	print_elements([Head | Tail]) :- write(Head), nl, print_elements(Tail).

Both of these fail after printing the list. If this is undesirable (and it probably is), a simple idiom is to add another clause whose purpose is to unconditionally succeed after the first clause is done:

	print_elements(_).