On 18/05/07, Albert Y. C. Lai
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@gmail.com