Prolog Learnings: Predicates and Association of Arguments

Functions (or procedures) in Prolog are called "predicates", but unlike functions in other languages that can only evaluate inputs to create an output, predicates do not have defined inputs and outputs. In idiomatic Prolog, a predicate is a function that works both ways.

Similar to a function, the predicate reverse/2 can be defined to accept a list of 'n' elements and return a new list containing these elements reversed; reverse(List1, List2). In the examples below, reverse/2 will generate expected results when both arguments receive values, no arguments receive values, or only one argument receives a value.

Predicates[1] can only evaluate to true and false so all input and output parameters must be passed as arguments.

In the first example, Prolog is able to evaluate the predicate reverse/2 to true as the list provided in the second argument contains all the elements of the first argument, but reversed.

Prolog
1
2
?- reverse([1,2,3], [3,2,1]).
true.

In the second example, the predicate evaluates to false because [1,2,3] is not the reverse of [3,2].

Prolog
1
2
?- reverse([1,2,3], [3,2]).
false.

In the next example, to evaluate the predicate reverse/2 to true, Prolog will create and return a new list for Output containing the elements from the first list, but reversed.

Prolog
1
2
?- reverse([1,2,3], Output).
Output = [3,2,1].

Because of the relationship between the arguments, either argument can be passed a list.

Prolog
1
2
?- reverse(Input, [3,2,1]).
Input = [1,2,3].

And when values for either argument are not provided, Prolog creates a new list of anonymous variables and returns a second list with the elements reversed (anonymous variables in Prolog start with the underscore character _).

Prolog
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
?- reverse(Input, Output).

Input = Output, Output = [] ;

Input = Output, Output = [_25892180] ;

Input = [_25892180, _25893064],
Output = [_25893064, _25892180] ;

Input = [_25892180, _25893064, _25894194],
Output = [_25894194, _25893064, _25892180] ;

With each successive semicolon, Prolog will provide additional answers for which the predicate reverse/2 evaulates to true. So first a list of zero elements is reversed, then a list of one element, then two, then three, etc.

Unfortunately is is not =. is can only determine if two things are equal and cannot be reversed[2] (and all arguments must already have been instantiated). With the definition sum(X, Y, Total), we cannot, for example, query sum(3, Y, 5) and expect Prolog to return an answer of Y = 2. Just as in other languages, we will need to write specific code paths to handle each use-case. But thanks to Prolog’s support for backtracking we can implement this logic without the usual if/then/else ladder or switch construct. Depending on your point of view this style may make the code eaiser to understand, or not.

  • sum(1, 2, Total),

  • sum(1, Y, 2),

  • sum(X, 1, 2),

  • sum(1, 1, 2),

  • sum(X, Y, 3) does not make sense so fail,

  • sum(X, Y, 3) does not make sense so fail.

The sum of two arguments in Prolog
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
%% sum(X, Y, Total)
sum(X, Y, Total) :-
    not(ground(X)),
    not(ground(Y)),
    not(ground(Total)),
    !, fail.
%% sum(X, Y, 3)
sum(X, Y, Total) :-
    not(ground(X)),
    not(ground(Y)),
    !, fail.
%% sum(1, Y, 2)
sum(X, Y, Total) :-
    not(ground(Y)),
    Y is Total - X,
    !.
%% sum(X, 1, 2)
sum(X, Y, Total) :-
    not(ground(X)),
    X is Total - Y,
    !.
%% sum(1, 2, Total)
%% sum(1, 1, 2)
sum(X, Y, Total) :- Total is X + Y.

The ordering of the predicates is important as is the use of the cut (!) operator which is necessary to halt backtracking when an answer is found. Predicates should be ordered from most to least specific in the source file as this is also the order of evaluation.

We can simplify further by combining the first two predicates into one as it doesn’t matter if all three arguments are unbound, sum(X, Y, Total), or only the first two arguments are unbound, sum(X, Y, 4) as the behaviour is the same.

The sum of two arguments in Prolog
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
%% sum(X, Y, 3)
%% sum(X, Y, Total)
sum(X, Y, _) :-
    var(X),    % "var" returns true when variable is unbound
    var(Y),    % "var" should have been named "unbound"
    !,         % ensure Prolog does not backtrack and evaluate less specific predicates
    fail.      % "fail" causes the predicate to evaluate to False
%% sum(1, Y, 2)
sum(X, Y, Total) :-
    var(Y),
    Y is Total - X,
    !.
%% sum(X, 1, 2)
sum(X, Y, Total) :-
    var(X),
    X is Total - Y,
    !.
%% sum(1, 2, Total)
%% sum(1, 1, 2)
sum(X, Y, Total) :- Total is X + Y.