Experimental command provided by NRE, available in HEAD and onwards from the release of Tcl8.6a2.
The command provides proper tailcalls, with the following semantics:
That is: tailcall foo [bar] $soom is very similar to return [uplevel 1 [list foo [bar] $soom]]] with two exceptions:
NEM Many thanks to MS for his hard work making this a reality! For some background, see Tail call optimization.
NEM As a test/demo of how to use this facility, here is a simple benchmark using the factorial function:
package require Tcl 8.6a1 namespace import ::tcl::mathop::* interp alias {} tailcall {} tcl::unsupported::tailcall # Naive recursive factorial function proc fac n { if {$n <= 1} { return 1 } else { * $n [fac [- $n 1]] } } # Tail-recursive factorial proc fac-tr {n {k 1}} { if {$n <= 1} { return $k } else { tailcall fac-tr [- $n 1] [* $n $k] } } # Iterative factorial proc fac-i n { for {set k 1} {$n > 1} {incr n -1} { set k [expr {$n*$k}] } return $k } proc test {} { set fmt "%-10s ..%-12.12s %s" puts [format $fmt "Implementation" "Result" "Time"] foreach n {1 5 10 100 500 1000 2500 5000 10000} { puts "\nfac $n:" foreach impl {fac fac-i fac-tr} { if {[catch { $impl $n } result]} { set result "n/a" set time "n/a" } else { set time [time [list $impl $n] 10] } puts [format $fmt $impl $result $time] } } } test
Putting this in a table, we get (timings taken on Linux box, 2.66GHz, 1GB RAM):
N | fac Time | fac-i Time | fac-tr Time |
---|---|---|---|
1 | 3.2 | 3.0 | 2.8 |
5 | 10.1 | 4.7 | 19.4 |
10 | 18.4 | 6.4 | 37.9 |
100 | 345.5 | 267.4 | 717.8 |
500 | 3133.9 | 3715.6 | 6182.5 |
1000 | n/a | 13811.7 | 19764.3 |
2500 | n/a | 65121.1 | 84556.5 |
5000 | n/a | 241176.8 | 288136.1 |
10000 | n/a | 987057.8 | 1643480.7 |
As we can see, the tail-recursive version is slightly slower than the iterative version, and unlike the naive version, manages to not blow the stack.
jima (2008-08-31)
Just a question: would it be possible to pass a sequence of commands (a script) to tailcall instead of just one command?
Would this make sense?
I understand that with uplevel this is possible: uplevel 1 { script_here... }
MS Not in the current implementation, but