Prolog Guide - How Does it work?

Guide to Prolog Programming

© Roman Barták, 1998

Prolog in Examples

Previous | Contents | Next

How does it work?

In this lesson I try to collect some features of Prolog language which I have found to be difficult to understand by students accustomed to procedural style of programming.

"is" is a build-in arithmetic evaluator in Prolog. "X is E" first computes the arithmetic expression E and then unifies the result with X. E can contain variables but these variables has to be bound to numbers, e.g., "X=5, Y is 2*X" is correct Prolog goal. Note, that we can use unification to bind variables but do not interchange unification and evaluation. Also, do not use "is" in the same way as assignment in procedural languages! Following examples shows wrong usage of "is":
?-X is Y+2.              % arithmetic expression cannot be evaluated because Y is free
?-H=5,T=[], L is [H|T].  % expression [H|T] is not arithmetic
?-X is 2, X is 3.        % fails because it is impossible to change the value of X from 2 to 3

Unification is used to bind variables as well as to compare data structures in both directions. Unification does not evaluate expressions.
?-X=f(Y).         % returns X/f(Y)
?-f(g(Y))=f(X).   % returns X/g(Y)
?-X=1+2.          % returns X/1+2
?-3=1+2.          % fails (3 is syntactically different from 1+2)

Backtracking is a powerful feature of Prolog that simplifies development of many programs. It enables the program to use other alternative if the previous alternative fails. Thus, programming of generate and test algorithms is natural in Prolog. Also, it is usually possible to find one solution as well as all solutions using the same program.

declarative character
Declarative character of many Prolog programs enables one to use the same procedure in different ways. Note, that it is not distinguished whether the argument of the procedure is input or output in Prolog. Thus, it is possible to use one argument as input in one call and use the same argument as output in other call. See following example:
?-member(1,[1,2,3]).  % usage as a test
?-member(X,[1,2,3]).  % usage as a member generator (returns successively X=1, X=2, X=3)
?-member(1,L).        % usage as a list generator (returns L=[1|_], L=[_,1|_], L=[_,_,1|_] etc.)
?-member(X,L).        % generator of general lists containing X (returns L=[X|_], L=[_,X|_], L=[_,_,X|_] etc.)

Operators simplify entry of Prolog programs. They are only used to define syntactic conventions of program and data entry. The definition of operators helps Prolog to understand expression like 1+2+3*4 which is translated into notation +(+(1,2),*(3,4)).

Cut is a feature of Prolog (not logic programming) that is used to cut alternative branches of computation and, thus, these branches are not explored by backtracking. Cut can improve efficiency of Prolog programs, however, it also changes the clear operational behaviour of programs. Use "cut" carefully as the programs containing cut are usually harder to read. The following example explains the behaviour of cut.
?-member(Y,[[1,2],[3,4]]),member(X,Y).     % returns X=1,X=2,X=3,X=4 successively
?-member(Y,[[1,2],[3,4]]),member(X,Y),!.   % returns X=1 only
?-member(Y,[[1,2],[3,4]]),!,member(X,Y).   % returns X=1, X=2 successively
?-!,member(Y,[[1,2],[3,4]]),member(X,Y).   % returns X=1,X=2,X=3,X=4 successively

Because of complexity reasons, Prolog does not contain full logic negation. Instead of it, Prolog uses negation as failure which is based on Closed World Assumption. The operational behaviour of this type of negation can be expressed by the following program:
not P:-P,!,fail.
not P.
Negation in Prolog can be safely used only as a test. Assure that all variables in negated goal are bound, otherwise you can get "strange" results as following examples show:
?-not p(X), q(X).   % fails
?-q(X), not p(X).   % succeeds with X=c

If you do not understand how does something work, then try some simple examples.


Designed and maintained by Roman Barták

Previous | Contents | Next