dibblego: You are jumping to a false conclusion, I...

2008-08-25T13:57:00.000-07:00

dibblego: You are jumping to a false conclusion, I hope my follow up post should explain my message clearer.

wren nailed it. It seems you don't understand why,...

2008-08-25T02:38:00.000-07:00

wren nailed it. It seems you don't understand why, so here is a simple proof.

Haskell has Data.List.foldl' (and foldl' runs a tail call in constant stack) -QED

Have a nice day.

[0] wren@xenobia:~/test $ cat NoTCO.java ; javac N...

2008-08-24T13:30:00.000-07:00

[0] wren@xenobia:~/test $ cat NoTCO.java ; javac NoTCO.java ; java NoTCOclass NoTCO {
// The int is a lie
static int f(int x) { int y = f(x); return y; }

public static void main(String[] args) {
System.out.println( NoTCO.f(3));
}
}
Exception in thread "main" java.lang.StackOverflowError
at NoTCO.f(NoTCO.java:3)
at NoTCO.f(NoTCO.java:3)
[...repeat 1022 more times]
[0] wren@xenobia:~/test $

wren: Almost everything you said is accurate and c...

2008-08-24T10:45:00.000-07:00

wren: Almost everything you said is accurate and correct, It also happens mostly you just repeated what I wrote. Anyway, I've written the exact (let f x = f x in f 3) function in java, along with a lazy evaluator (one which doesn't detect or optimize tail calls), and it doesn't stack overflow, (I've posted it on this site incase you like to see it).

Haskell very much does have tail call elimination,...

2008-08-23T18:32:00.000-07:00

Haskell very much does have tail call elimination, any claims to the contrary are demonstrably false. Your stack overflow issues have nothing to do with tail call elimination. You've said this yourself, though you seem not to have followed the reasoning to conclusion.

This is just a canonical issue with accumulator functions in lazy languages. All of your tail calls to cat' as you construct that accumulator are eliminated perfectly fine. The problem is that you end up with a million element thunk at the end. When you pull on that thunk there are no tail calls to eliminate.

The expression for your accumulator is: (((((((...(0 + 1) + 2) + 3)... + 1000000). (N.B. it is not (0 + (1 +...)))!) The ultimate call to seq acc will tail call the topmost (+), reusing the stack frame used by seq. But from there, since (+) is strict in its arguments it must evaluate the left hand expression before it can return. This is repeated a million times as you descend. But none of those are tail calls and so the problem has nothing whatsoever to do with GHC's eliminating tail calls.

You repeat the same problem with your Peano integers since your definition of plus requires evaluating the left-hand argument to WHNF and the left-hand argument is the one with a million-1 depth call stack. Try having your definition count down on the right operand instead. Now, cat' works perfectly fine! Of course cat will stack overflow, because now it has the same problem as cat' did with the old definition of plus; you've just exchanged which definition works in synch with the pattern of thunks.

The well known solution to this canonical interaction between accumulators and laziness is to strictly evaluate the accumulator at each step. What this does is amortize the call stack for evaluating the accumulator across all the recursive calls. The strictness call can't be eliminated because its result is needed for the recursive call, but the recursive call can be eliminated because the result of the callee is the same as the result of the caller. Thus you have a call stack depth of at most two (or rather, one plus whatever depth is needed to bring the accumulator back to WHNF).

Your infinite loops chirp away happily precisely because GHC does tail call elimination. If it did not then those functions would cause a stack overflow. Try writing those exact functions in Java and watch them explode. (Alas C is no longer a good example since the GHC folks cracked GCC open and added in TCO for everyone.) "Tail call elimination" means only that the current stack frame can be reused if the last action of the current function is to call another function. Because GHC does indeed do tail call elimination the frame for the first call to f can be reused when making the second call to f, and that frame can be reused when making the third call to f, etc. In a language without TCO each one of those calls would require an additional stack frame until you overflow.

Comments on Muad`Dib: Tail Call Optimization doesn't exist in Haskell

dibblego: You are jumping to a false conclusion, I...

wren nailed it. It seems you don't understand why,...

[0] wren@xenobia:~/test $ cat NoTCO.java ; javac N...

wren: Almost everything you said is accurate and c...

Haskell very much does have tail call elimination,...