Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
More Induction
Induction is fundamental to programming in Prolog, so it’s worth going over it a little more. Before we do, let’s take a look at the principle data structure in Prolog: the list.
Lists in Prolog are defined inductively according to the following two rules:
- [], the empty list, is a list.
- [X|List] is a list for any X if List is a list.
We use lists a lot in Prolog. To start with, we’ll define a predicate for adding all of the numbers in a list, using induction. The base case here is obvious; the sum of all the numbers in a list with one element is that element. We can write this as follows:
sum([X],X).
This example makes use of Prolog’s pattern-matching abilities. Since we’ve used the variable X twice, this predicate will evaluate to true only if the same value is used in both places; sum([1],1) will succeed, sum([1],2) will not. If we leave X undefined in some places, Prolog will assign the value to X that’s used in other places. We can see this in the Prolog interpreter:
?- sum([1],S). S = 1 Yes ?- sum([S],1). S = 1 Yes
Next, we must define the inductive case. Induction on lists typically uses the [Head|Tail] construction. This sets Head to the first element of a list and Tail to the remainder of the list; in the case of a single element list, Tail will be the empty list. To sum the elements in a list inductively, we add the first element to the sum of the remaining ones. In Prolog we say this:
sum([H|T], S) :- sum(T,X), S is H + X.
The left side of this statement will match any list, and split it so that H is the first element and T is a list of the others. We then use the same predicate to make X the sum of all the elements of T, and then set S to this plus the first element. We can test this principle by loading the file sum.pro from the source file for this article:
?- sum([1,2,3],X). X = 6 Yes
Another common pattern in Prolog is tail-recursion, which is popular because it’s easy for the compiler to optimize. A tail-recursive predicate is one in which the recursive call in the inductive step is the last part of the clause. Confused? Here’s how we would write the sum predicate in a tail-recursive manner:
sum([],X,X). sum([H|T], A, S) :- A2 is A + H, sum(T,A2,S).
Note that in the tail-recursive version we need to add an accumulator, A, to store intermediate results. In this example, the accumulator keeps a running total. When we get to the base case, we simply return the accumulator. This is faster because Prolog has to keep track of far fewer intermediate steps. In the previous version, every recursive step required Prolog to keep track of the fact that it would need to perform the addition later, while in the tail-recursive version the base case will return immediately.
The tail-recursive version isn’t as friendly to use, though, since you have to initialize the accumulator when you use it. To get around this restriction, we can define a sum/2 predicate that uses our sum/3 predicate:
sum(L,S) :- sum(L,0,S).