Version 11 of ::tcl::unsupported::tailcall

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:

• a proc/lambda invokes [tailcall foo [bar] $soom]
• bar is invoked and the value of soom fetched, as if [list foo [bar] $soom] had been called
• a command named foo is looked up in the current context
• the current proc/lambda replaces itself in the call stack with a call to the just found command

That is: tailcall foo [bar] $soom is very similar to return [uplevel 1 [list foo [bar] $soom]]] with two exceptions:

1. foo is looked up in the current context, not in the caller's
2. the stack frame is really gone, not just virtually. This has positive effects on memory, and a possibly confusing effect on stack traces.

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):

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

• it can be done by changing the semantics of the tailcall command - one of the reasons it is unsupported is so that we can discover what the best options are before it is frozen in a TIP
• it can be mimicked by tailcall ::eval $script (perfectly, as soon as eval is adapted to NRE)