Summary  edit

Like [uplevel 1] except that it also causes the current scope to terminate, though the command is looked up in the current context first.

Synopsis  edit

tailcall command ?arg...?

See Also  edit

Tail call optimization

TIP#327

Description  edit

[Tailcall] is made possible by NRE. It first became available as [::tcl::unsupported::tailcall] in the release of Tcl8.6a2. It 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.

Usage  edit

While [uplevel] takes a script, [tailcall] takes a command. If you want to [tailcall] a script do it as follows:

tailcall try $script

---

WHD: Let me see if I understand what this does.

proc fred {} {
    george
}

proc george {} {
     tailcall harry
}

If I call fred, it's almost as though fred called harry directly, instead of george. Not so?

MS: yup - all traces of george are gone from the program stack when harry is called. Now, if harry resolves to a different command in george's current namespace than it would under fred's, the harry that is called is george's and not fred's (no diff if the commands are FQ, of course).

I think this does pretty much what delegation is supposed to do, right?

---

jima 2009-10-15: Perhaps this has been asked before or somewhere else...

Is this an optimization that takes place at bytecode generation time?

I mean, once fred knows that has to call harry directly the bytecodes generated would be the ones equivalent to have said:

proc fred {} {
    harry
}

I reckon I am not familiar with all the internals of Tcl but I find this would be an interesting thing. Wouldn't this be a new way to have some sort of macros?

MS: Currently, [tailcall] is not byte compiled. Everything happens at runtime. That extremely simple example could indeed be bytecoded in a minute, but things get more involved as soon as [fred] has a bit more structure to it: arguments, local variables, namespace issues both for variable and command lookup, multiple exit points with different (or no) [tailcall] in them, etc.

jima: Thanks a lot Miguel for the answer. I see the point. I guess this is the same with [uplevel 1], isn't it?

proc fred {} {
    uplevel 1 {
        #code here
    }
}

Would it be interesting to define a case (like a contract) saying if your proc is simple enough then it gets bytecompiled and you get some benefits?

MS: you do not mean "bytecompiled" but rather "inlined into the caller", as all [proc] bodies get bytecompiled. There are quite a few other issues with that, especially to accomodate Tcl's dynamic nature. Changing one inlined proc would cause a spoiling of all bytecodes and recompilation of the world, at least with the current approach to bytecode lifetime management.

---

AMG: Sounds a lot like exec in Unix shells. See execline for more information on a noninteractive Unix shell where everything is done with exec/tailcall.

Interaction with [try]

% proc foo {} {puts "I'm foo"}
% proc bar {} {puts "I'm bar"; try { tailcall foo } finally { puts "exitting" }}
% foo
I'm foo
% bar
I'm bar
exitting
I'm foo

---

wdb: Apparently, the command [tailcall] closes one of the last gaps in Tcl: Tail recursion as known in Scheme.

Example: Factorial  edit

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.

Emulating [Tailcall]  edit

Lars H 2010-05-09: As of late, when writing an [uplevel], I've sometimes found myself thinking "That would be slicker with [tailcall], but I can't rely on 8.6 features in this project". Today it occurred to me that one can however use a [proc] to emulate the properties of [tailcall] that would be needed in these cases, and thus provide a route for forward compatibility.

The main situation I've encountered is that of delegating to another command which may make use of [upvar] or [uplevel]. That's basically taken care of by

proc utailcall {args} {uplevel 2 $args}

although it's safer to make it

proc utailcall {args} {return -code return [uplevel 2 $args]}

in case the "terminate proc early" aspect of [tailcall] is relied upon; this is easy to do without thinking much about it.

Another aspect of [tailcall] is the name resolution of the called command. This can be done as follows

proc ntailcall {cmd args} {
    return -code return [
        [uplevel 1 [list ::namespace which $cmd]] {*}$args
    ]
}

but it's almost as easy to do both at the same time

proc untailcall {cmd args} {
    return -code return [
        uplevel 2 [list [uplevel 1 [list ::namespace which $cmd]]] $args
    ]
}

A word of warning here is that this will produce a very confusing error message if the command is undefined, as [namespace which] returns an empty string in that case.

A third aspect is that of preserving [return] levels.

proc rtailcall {args} {
    catch $args result options
    dict incr options -level 2
    return -options $options $result
}

This leaves some extra material in the errorInfo, but one can probably live with that. Combining the "r" and "u" aspects is straightforward, but will leave even more:

proc rutailcall {args} {
    catch {uplevel 2 $args} result options
    dict incr options -level 2
    return -options $options $result
}

To complete the set, one might just as well write down the combination of the "r" and "n" aspects

proc rntailcall {cmd args} {
    catch {
        [uplevel 1 [list ::namespace which $cmd]] {*}$args
    } result options
    dict incr options -level 2
    return -options $options $result
}

and of all three

proc rnutailcall {cmd args} {
    catch {
        uplevel 2 [list [uplevel 1 [list ::namespace which $cmd]]] $args
    } result options
    dict incr options -level 2
    return -options $options $result
}

But note: all of the above will fail if used for tail recursion, as soon as the loops get long enough.

Replacement for [uplevel]  edit

AMG: [uplevel] has limitations with respect to bytecode compilation and interpretation of [return]. If [uplevel]'s level count is 1, and if it's the last thing being done in the [proc], these limitations can be avoided by using [tailcall] instead. Note that [uplevel] takes a script whereas [tailcall] takes a command. If you want to pass a script to [tailcall], make it be the sole argument to [try].

See Possible uplevel deficiencies. Also see When to use uplevel for more on when to use or avoid [uplevel]. See eval vs bytecode for discussion and performance numbers regarding bytecode compilation with [eval], [uplevel], [try], and others.

---

HaO 2012-12-14: Is it a good idea to replace any code:

proc proc1 {arg1 arg2} {
    # do something here which finds arg3 and arg4
    return [proc2 $arg3 $arg4]
}

by

proc proc1 {arg1 arg2} {
    # do something here which finds arg3 and arg4
    tailcall proc2 $arg3 $arg4
}

If proc2 is for sure found in the caller namespace?

Is this an intelligent optimization?

I came to this idea, as the TI C compiler calls this "tailcall optimization".

AMG: Yes, except in a highly unlikely situation where [proc2] needs [proc1] to be visible in the stack. Procedures really ought not to care who called them, but Tcl makes all sorts of things possible, including stupid things.

Misc  edit

NEM: Many thanks to MS for his hard work making this a reality!

---