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.
reverse/2
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.
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].
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.
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.
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 _).
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.
sum/3 using CLP(FD), CLP(Z)
In Prolog, is is used when evaluating arithmetic expressions. However is can
only determine if two things are equal and cannot be
reversed[2] (and all arguments must already have
been instantiated).
Fortunately Prolog supports CLP(FD) and CLP(Z) and which means we get to have
our cake and eat it. For example using #= instead of = or is means Sum =
3 when ?- Sum #= 1 + 2. And Y = 2 for 3 #= 1 + Y.
So we can write a defintion for sum(X, Y, Total) where a query sum(3, Y, 5)
returns an answer of Y = 2. If we use is instead, then 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.
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.
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.