Lecture Notes on Tail Recursion and call/cc

Tail recursion

A function is said to be tail recursive when the recursive call is the last function invoked in the evaluation of the body of the function.

Example:

sumAux [] c = c
sumAux (x:xs) c = sumAux xs (c+x)

sumIter xs = sumAux xs 0

The function SumAux is tail recursive because after the recursive call there is nothing else left to do.

If we define the same function without tail recursion we get

sum [] = 0
sum (x:xs) = x + (sum xs)

Try and see by yourself what happens during the evaluation of sum on a list, say (2 4 6 1 3). You need to leave a number of additions uncompleted until you reach the base case. When the base case is reached, all the additions can be made.
In a sense, you need a stack to remember what "remains to be computed".
Now, mimic the evaluation of sumIter on the same input. You need to remember nothing, since no operation is left to be computed.

Tail recursion, in a sense, correspond to the notion of iteration in functional programming (indeed you can translate tail recursive functions in an imperative language by using a simple loop. The translation of a non tail recursive function, instead, will definitely use a stack, or something equivalent.)

In the function sumAux (used by sumIter) the argument 'c' plays the role of an accumulator. In each recursive call a shorter list is passed to aux, while the accumulator is "extended" with the first element of the list. In a sense, each recursive call is like an iteration that modifies a variable, the accumulator, and the "assignment" of a new value to the accumulator is mimicked by passing the new value as second argument of the recursive call.

It is possible to provide iterative versions of all the functions, not always easily.

Let us see a few tail recursive versions of well known functions

reverseIterAux [] as = as
reverseIterAux (x:xs) as = reverseIterAux xs (x:as)

reverseIter xs = reverseIterAux xs []

appendIterAux [] [] as = reverseIter as
appendIterAux [] ys as = appendIterAux ys [] 
appendIterAux (x:xs) ys  as = appendIterAux xs ys (x:as)

appendIter xs ys = appendIter xs ys []

In this definitions there is a "hidden" iterative imperative algorithm.
Tail recursion can be thought of as the functional counterpart of Iteration.

(To be read after studying Prolog)
Also in Prolog we can have tail recursive programs. An example of tail recursive Prolog program is the one finding all the possible paths between two nodes in a non oriented graph (see [JRF]).
A non tail-recursive version of such a program can be found in the exercises page (exercise 15 of Prolog Exercises).

In the page of Haskell Exercises, the same problem is solved in Haskell in a tail recursive and non tail-recursive way.
Notice how the tail-recursive solution in Haskell uses the operator >>=. In fact the list type-constructor [_] in Haskell is a Monad.

call/cc (call with current continuation)

We do not explain how these particular Scheme operator, and other similar operators in functional programming languages, works.
We just show an example of the sort problems these kind of operators have been devised for.

(define (Mt tree) 
  (if (emptytree? tree) 
      1 
      (if (= (label tree) 0) 
          0 
          (* (label tree) 
	     (Mt (rightchild tree)) 
	     (Mt (leftchild tree))))))  

The above function computes the product of all the nodes of a binary tree with numeric labels.

Let's assume we want to apply it to the following tree:

         2 
       /   \ 
      5     0 
     / \   / \ 
    3  6  1   7 
	       \ 
	        2 
 

The right subtree of the upper node 2 has the root with label zero. So the function Mt applied to this subtree returns 0 as result. This means that the product of all the nodes of the tree will be also 0, by the property of multiplication. However, the interpreter proceeds in the computation, evaluating also (Mt (leftchild tree)), even if such evaluation is completely useless. There is no way to prevent this waste of computation if you do not use call/cc or something similar since, even if at a certain point you could stop the computation, you are sort of "obliged" to complete the recursive calls present on the "stack".
In cases like our example, the use of the operator call/cc enables you to stop the computation as soon as we meet a 0, by "removing" all that is still on the "stack".

In general, call/cc work on the remaining part of the computation. In the above example, call/cc can be used to take the remaining part of the computation and to throw it away, so performing a sort of "exit" that stops the computation and empties the stack.