Performance, tail recursion and immutability

On building algorithms

Items to discuss: performance aspects, tail and non-tail recursion, immutability and sharing, and generating combinations and searching the space of solutions. We start with lists, then generalise to other data types, meanwhile presenting libraries and introducing some non-relational constructs.

Performance considerations

Traditionally, Prolog is known for not being "as fast as" C, though professional implementations are actually rather fast.

Recall our approach to performance:

• address the problem only if we have requirements that are not met;
• still, we have to know the implications of our programming choices, and choose slower implementations only if they have other good properties, e.g. simplicity or clarity.

How can we characterise the performance of a predicate? First of all, in terms of the number of resolution steps. Each step requires a search for a matching rule, the computation of an MGU, and an update of the resolvent under the new substitution. We might assume that a step costs a constant, but it actually depends on the number of rules, of variables, of goals, and so on.

Tail recursion in Prolog

A recursion is tail if the recursive call is the last operation executed before returning. Nothing is left to be done when the base case is reached, hence computation is done before that, namely while recursing. So an optimisation can (at least in principle) avoid the cost of creating activation records for the nested calls. Often (not always), tail recursions are obtained by putting extra arguments in the call, modelling the state evolution during recursion.

In Prolog, tail-recursive calls are characterised by rules where the head predicate occurs only as the last goal in the body. The resolution "chain" is such that computation is done in arguments or substitutions, until the base case is reached. Note that non-tail recursions are often more idiomatic. And Prolog supports tail-recursive foldright-like list construction, which functional programming cannot do!

Non-tail recursion with sum/2 (foldleft-like)

File sum-nontail.pl:

sum([10,20,30], S)
sum([20,30], S'), S is 10 + S'
sum([30], S''), S' is 20 + S'', S is 10 + S'
sum([], S'''), S'' is 30 + S''', S' is 20 + S'', S is 10 + S'
S'' is 30 + 0, S' is 20 + S'', S is 10 + S'
S' is 20 + 30, S is 10 + S'
S is 10 + 50
{S/60}

Notes: the program is quite idiomatic; the computation occurs as the recursion is over; the resolvent can become quite big; many resolution steps are needed (about 2 · n).

Tail recursion with sum/2

File sum-tail.pl. The relation sum/2 is defined through an accumulator in sum/3:

sum([10,20,30], S)
sum([10,20,30], 0, S)
N2' is 0+10, sum([20,30], N2', S)
sum([20,30], 10, S)
N2'' is 10+20, sum([30], N2'', S)
sum([30], 30, S)
N2''' is 30+30, sum([], N2''', S)

Notes: the program is rather less direct; the computation occurs during the recursion; the resolvents are much simpler.

The two versions side by side. On a list of 100 000 numbers both take about 2 · n resolution steps (the inferences reported by time/1): the difference is not in the number of steps but in the size of the resolvent, hence in memory. With three million numbers the non-tail version runs out of stack, while the tail-recursive one runs in constant stack space:

Tail recursion with join/3 (foldright-like)

File join-tail.pl:

join([10,20],[30,40,50],L)
join([20],[30,40,50],T2')    : {L/[10|T2']}
join([],[30,40,50],T2'')     : {L/[10|T2'], T2'/[20|T2'']}
{L/[10|T2'], T2'/[20|T2''], T2''/[30,40,50]} ≡ {L/[10,20,30,40,50]}

Notes: foldright-like functions are very easily expressed, and the corresponding recursion is tail! The output list is constructed by the [H|T2] unification during the recursion. This is not achieved by functional programming with immutable structures.

Immutability and sharing: update/4

File update.pl:

update([10,20,30,40],20,21,L)
update([20,30,40],20,21,T2')  : {L/[10|T2']}
{L/[10|T2'], T2'/[21|[30,40]]} ≡ {L/[10,21,30,40]}

How is the output list related to the input one? Prolog has immutability of data: terms get unified, never modified. The output list actually shares [30, 40] with the input list. Hence Prolog has intrinsic immutability and sharing of structures. SWI-Prolog can check the sharing: same_term/2 is true when two arguments are the very same object in memory.

Immutability of Prolog terms

Computation happens only by resolution and unification. Hence data values, which are terms, have no concept of mutability. Terms are just manipulated by unification of the terms in the resolvent and of the terms occurring in cloned copies of applied rules.

Computationally, a term is an entity that never changes; its subparts can be shared with other terms. A "declarative" form of side effect is achieved by unification: a non-ground term could at some point have a variable be "bound" to an actual term.