Version 6 of Tail call optimisation

Updated 2004-07-08 08:48:59 by MSW

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] ;# => 1836311903

(mjk: remember to add here a short explanation, what the code does.)

---

MSW: 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.

 Tail call
 [ frame ] <-- call new function in the very same frame.

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.

---