TRO

Appeared in Volume 9/1, February 1996

Keywords: TRO.

kmorris692@aol.com
K. Morris
21st November 1995

A recent comp.lang.prolog posting argued that Tail Recursive Optimisation (TRO) was a bad coding choice for a novice programmer because of its complexity compared to other techniques. In addition, there would be no saving in space and speed if the particular Prolog system did not support TRO.

I disagree with this sentiment. The concept that tail-recursion is equivalent to iteration is fundamental to writing programs that work in production environments. Exploiting TRO is not an "efficiency tweek," it is the difference, very often, between programs that work on real data and those that blow up or page themselves to a snail's pace. Frankly, a Prolog implementation that cannot support TRO is not suitable for industrial applications, so the argument that TRO might not be available is irrelevant.

Too many writers for Byte, AI Expert, etc., give really bad examples of how to program in Prolog - examples that show that they can't have written serious applications in the language. Not showing a tail-recursive example to a beginner's question is a disservice to the beginner.

Let's look at the following C code which sums from 1..limit.

int sumUp(int limit)
{
  int i, sum;

  assert(limit > 0);
  for (i = 1, sum = 0; i <= limit; ++i)
    sum += i;
  return sum;
}

Let's look at somewhat similar Prolog code:

sumUp(Limit,Sum) :-
    integer(Limit),
    Limit > 0,             /* assert(limit > 0) */
    sumUp(1,Limit,0,Sum).  /* i = 1, sum = 0 */

sumUp(I0,Limit,Sum0,Sum) :-
    I0 =< Limit,           /* i <= limit */
    !,                     /* green cut */
    Sum1 is Sum0 + I0,     /* sum += i */
    I1 is I0 + 1,          /* ++i  */
    sumUp(I1,Limit,Sum1,Sum).
sumUp(I,Limit,Sum,Sum) :-
    I > Limit.             /* return sum */

Unless is/2 creates some garbage, this example should run in constant space. Notice the similar structure to the C code. I think this shows that a tail-recursive example is not too hard for beginners.

Nick@maproom.demon.co.uk
Nick Wedd
21st November 1995

I fully agree that a commercial application should be written to use TRO wherever possible. But this thread started with a posting from a beginner who did not know how to sum a list at all.

I admire the intelligence of anyone who grasps how sumUp/4 works, without first studying the two-argument version. But I wonder how many people could manage that? I am sure that I would have had difficulty learning Prolog if I had been given the 4-argument version without first seeing the 2-argument version. Or "sophisticated reverse" without first studying "naive reverse". This also goes for most of the Prolog beginners that I have trained.