[Haskell-cafe] Debunking tail recursion

[David House]

On 18/05/07, Albert Y. C. Lai <trebla at vex.net> wrote:
> Lazy evaluation says, to evaluate x, call f first, then x is the last
> call.

x may be the last to be evaluated, but you still have to pass through
f's call context 'on the way out'. For example, suppose in the
expression 'f x y' you have f = (+), x = 2 and y = 3, then lazy
evaluation looks something like the following:

f x y
(+) x y
(+) 2 3
5

Notice that you still have to evaluate x and y before you can perform
the addition. In other words, although you may perform the
manipulations that the definition of f describes on thunks, and only
later force those thunks, you still have the call context of the f to
pass through: you're not evaluating those thunks for no particular
reason, you're evaluating them so that f may return.

Your argument also seems to be using the reflexivity of the =
operation, which doesn't really hold at the binding level. To
exemplify, set f = (:) and y = 1, so that you have:

(0)   x  = (:) 1 x
(1)   (:) 1 x = x

The first sets up a binding for 'x', that when evaluated will yield
the infinite list [1, 1,  1, ...]. The second sets up a binding for
the function '(:)', which when given two arguments, the first of which
is 1, will evaluate to its second. I don't really see these as being
the same expression.

> Define
>
> (2)    cs = 'c' : cs
>
> Is (2) a tail recursion?

No, for the same reason discussed above: you still have to pass
through the call context of (:) once cs is evaluated. What I'm trying
to do is disassociate the concept of tail recursion from evaluation
order. To say something is tail recursive is to say that a call to
itself appears at the top of the call stack: to say it's the "last
thing you do" is helpful intuitively but starts to fall apart once you
move away from the traditional strict evaluation order semantics.

Let's have one more example to explain what I mean by 'call stack'.
The classic tail recursive function is foldl, contrasting with the
non-tail recursive function foldr. Equations from both these functions
are shown below, with their right-hand sides transformed into a tree
(ASCII art: don't use a proportional font):

foldl f z (x:xs) = foldl f (f z x) xs

foldl-+--+-----+
      |  |     |
      f  f--+  xs
         |  |
         z  x

foldr f z (x:xs) = f x (foldr f z xs)

f-+--+
  |  |
  x  foldr-+--+--+
           |  |  |
           f  z  xs

Tail recursion, then, expresses the idea that a function appears at
the top of its call stack, or at the top of the tree of its right-hand
side. It's got nothing to do with evaluation order.

-- 
-David House, dmhouse at gmail.com