A methodology of Prolog programming
3.9. A methodology of Prolog programming#
At the end of this chapter, we spend a few words on the methodology of writing Prolog programs. Given a problem to solve, how do I obtain the program solving the problem? This is the fundamental problem of software engineering. Here, we can only scratch the surface of this question: we will concentrate on the subtask of writing relatively simple predicates which use no more than two other predicates.
Consider the following problem: define a predicate which, given a number \(n\), partitions a list of numbers into two lists: one containing numbers smaller than \(n\), and the other containing the rest. So we need a predicate partition/4:
% partition(L,N,Littles,Bigs) <- Littles contains numbers
% in L smaller than N,
% Bigs contains the rest
Since the only looping structure of Prolog is recursion, simple predicates like this will typically be recursive. This means that
there is a base case, and one or more recursive clauses;
there is a recursion argument distinguishing between the base case and the recursive clauses.
For list predicates, the recursion argument is typically a list, and the distinction is typically between empty and non-empty lists. For the partition/4 predicate, the recursion argument is the first list. The base case is easily identified: the empty list is partitioned in two empty lists, no matter the value of N. This gives us the following skeleton:
partition([],N,[],[]).
partition([Head|Tail],N,?Littles,?Bigs):-
/* do something with Head */
partition(Tail,N,Littles,Bigs).
The question marks denote output arguments, whose relation to the variables in the recursive call still has to be decided. It should be noted that not all predicates are tail recursive, so it is not yet known whether the recursive call will be last indeed. Notice also that the output arguments in the recursive call have been given meaningful names, which is, in general, a good idea.
Once we have ‘chopped off’ the first number in the list, we have to do something with it. Depending on whether it is smaller than N or not, it has to be added to the Littles or the Bigs. Suppose Head is smaller than N:
partition([Head|Tail],N,?Littles,?Bigs):-
Head < N,
partition(Tail,N,Littles,Bigs).
Thus, Head must be added to Littles. In this case, it does not matter in which position it is added: obviously, the most simple way is to add it to the head of the list:
?Littles = [Head|Littles]
In such cases, where output arguments are simply constructed by unification, the unification is performed implicitly in the head of the clause (the fourth argument remains unchanged):
partition([Head|Tail],N,[Head|Littles],Bigs):-
Head < N,
partition(Tail,N,Littles,Bigs).
A second recursive clause is needed to cover the case that Head is larger than or equal to N, in which case it must be added to Bigs. The final program looks as follows:
% partition(L,N,Littles,Bigs) <- Littles contains numbers
% in L smaller than N,
% Bigs contains the rest
partition([],_N,[],[]).
partition([Head|Tail],N,[Head|Littles],Bigs):-
Head < N,
partition(Tail,N,Littles,Bigs).
partition([Head|Tail],N,Littles,[Head|Bigs]):-
Head >= N,
partition(Tail,N,Littles,Bigs).
The approach taken here can be formulated as a general strategy for writing Prolog predicates. The steps to be performed according to this strategy are summarised below:
write down a declarative specification;
identify the recursion argument, and the output arguments;
write down a skeleton;
complete the bodies of the clauses;
fill in the output arguments.
Notice that step 4 comprises most of the work, while the other steps are meant to make this work as easy as possible.
Implement a predicate permutation/2, such that permutation(L,P) is true if P contains the same elements as the list L but (possibly) in a different order, following these steps. (One auxiliary predicate is needed.)
As a second example, consider the problem of sorting a list of numbers. The declarative specification is as follows:
% mySort(L,S) <- S is a sorted permutation of list L
Note that this specification can immediately be translated to Prolog:
mySort(L,S):-
permutation(L,S),
sorted(S).
This program first guesses a permutation of L, and then checks if the permutation happens to be sorted. Declaratively, this program is correct; procedurally, it is extremely inefficient since there are \(n!\) different permutations of a list of length \(n\). Thus, we have to think of a more efficient algorithm.
The recursion and output arguments are easily identified as the first and second argument, respectively. The base case states that the empty list is already sorted, while the recursive clause states that a non-empty list is sorted by sorting its tail separately:
mySort([],[]).
mySort([Head|Tail],?Sorted):-
/* do something with Head */
mySort(Tail,Sorted).
It remains to decide what the relation is between ?Sorted, Head and Sorted. Obviously, Head cannot be simply added to the front of Sorted, but has to be inserted in the proper place. We thus need an auxiliary predicate insert/3, to add Head at the proper position in Sorted. Note that tail recursion is not applicable in this case, since we have to insert Head in an already sorted list. We thus arrive at the following definition:
mySort([],[]).
mySort([Head|Tail],WholeSorted):-
mySort(Tail,Sorted),
insert(Head,Sorted,WholeSorted).
In order to implement insert/3, we follow the same steps. The second argument is the recursion argument, and the third is the output argument. This gives the following skeleton:
insert(X,[],?Inserted).
insert(X,[Head|Tail],?Inserted):-
/* do something with Head */
insert(X,Tail,Inserted).
The base case is simple: ?Inserted = [X]. In the recursive clause, we have to compare X and Head. Suppose X is greater than Head:
insert(X,[Head|Tail],?Inserted):-
X > Head,
insert(X,Tail,Inserted).
We have to construct the output argument ?Inserted. Since X has already been properly inserted to Tail, it remains to add Head to the front of Inserted:
?Inserted = [Head|Inserted]
A third clause is needed if X is not greater than Head (note that this clause, being non-recursive, is a second base case):
insert(X,[Head|Tail],?Inserted):-
X =< Head.
In this case, X should be added before Head:
?Inserted = [X,Head|Tail]
The complete program is given below:
insert(X,[],[X]).
insert(X,[Head|Tail],[Head|Inserted]):-
X > Head,
insert(X,Tail,Inserted).
insert(X,[Head|Tail],[X,Head|Tail]):-
X =< Head.