See also:
mjk: Here is a simple example of using the after for tail-recursive calls. The following example calculates Fibonacci numbers without exhausting the stack.
proc _fib {i a b} {
if {$i <= 2} then {
set ::_fibretval [expr $a + $b]
} else {
after 0 _fib [expr $i - 1] $b [expr $a + $b]
}
}
proc fib {i} {
after 0 _fib $i 0 1
vwait ::_fibretval
return $::_fibretval
}
puts [fib 1] ;# => 1
puts [fib 2] ;# => 1
puts [fib 3] ;# => 2
puts [fib 10] ;# => 55
puts [fib 30] ;# => 832040
puts [fib 46] ;# => 1836311903MSW: Basically it's turning the stack by 90 degrees and is using time as stack. Not exactly what I would call a tail call optimisation (Reuse of the same stack) but rather a stack consumption workaround ...
Usual recursion | after-workaround
|
[ frame ] - return & wreck | [ frame ] - alter & wait & wreck
[ frame ] - return & wreck | [ frame ] - alter & wait & wreck
[ frame ] - return & wreck | [ frame ] - alter & wait & wreck
---> result | ---> result
Mind the functional nature | Mind the imperative nature
Tail recursion
[ frame ] <-- loop here & return result. Reuse stack frame. Still functional
Tail call
[ frame ] <-- call new function in the very same frame. Still not imperative !Tail call support really means reusing the very same stack, the optimisation being not only stopping the burn of stack frames but especially saving the costs of building them up just to tear them down again. A tail recursive function is equivalent to a loop in execution, which can't be said about the after way to implement it. I suppose having a look at Guy Steele's original paper [L1 ] might save some confusion.
mjk: You are correct. My example was inspired by a comment at the after page, where Arjen mentioned that after can be used to implement tail-recursive calls. Or tail-recursive-like calls. In my case, I think that "the end justifies the means", because I can't come up a way to implement this kind of behaviour with using only the pure Tcl. Is that even possible (there's no goto, but foreach and while can be used)? However, using after, it is possible to achieve similar results. But that's true, that in the spirit of the real tail-recursiveness, my example is just a workaround.
MSW: About "real" tail calls in pure tcl, Check Tcl 9.0 Wishlist (search 53. MSW & its answers :) and Tail call optimization.
mjk: Thanks for the pointers. And now I feel myself a bit dumb, because there seems to be an example Arjen mentiones (at the Tail call optimization page), which will make my example redundant. Anyway, great to see that the tail-call optimization is considered in the next major release. It would be a great thing and I'd love to see it in the Tcl some day.
MSW That and Closures and Continuations ... :) --- I'm not sure it's considered for the next release either, it was just my windowing shell...