AMG: The [tailcall] command has been moved out of the tcl::unsupported namespace. See tailcall for more information. Discussion on this page should be migrated.
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