'''[http://www.tcl-lang.tkorg/man/tcl/TclCmd/tailcall.htm%|%tailcall]''', a [Tcl Commands%|%built-in] [Tcl] command, executes a command in place of the current
command.
** Synopsis **
: '''tailcall''' ''command'' ?''arg''...?
** See Also **
[Tail call optimization]:
[TIP]#[http://tip.tcl.tk/327%|%327]:
[wrapping commands]: wrap commands by using `[interp invokehidden]` together with `tailcall`
`[ycl%|%ycl eval upcall]`: Finds a routine for a command at the current level, as `[tailcall]` does, and executes the command at the specified level, as `[uplevel]` does.
** Description **
'''`tailcall`''' interprets its arguments as a command and executes the
command,replacing the [stack frame%|%execution frame] of the command that
invoked `tailcall`. Unlike `[uplevel]`, it does not [eval%|%evaluate] its
arguments as a script, so [double substitution] does not occur.
Unlike some other languages, `tailcall` is not limited to executing only its
caller, but can execute any command. The command to be executed is resolved in
the current context before `tailcall` replaces the context.
`tailcall` is made possible by [NRE]. It first became available as
`[::tcl::unsupported::tailcall]` in the release of Tcl8.6a2.
Contrast the following two commands:
======
tailcall foo [bar] $var
return [uplevel 1 [list foo [bar] $var1]]
======
There are a couple of differences:
1. '''foo''' is resolved inat the '''current'' cont[lextvel]''', not in the caller's
1. theIn stack fontramest wisth ''r`[upleavelly'']`, gonthe, currenot julevel ist ''virtueally'' replaced. This has positive effects on memory, and a possibly confusing effect on stack traces.
To `tailcall` a script:
======
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 bytecompiled. 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 procedure
is simple enough then it gets bytecompiled and you get some benefits?
[MS]: you do not mean "bytecompiled" but rather "inlined into the caller", asall `[proc%|%procedure]` 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.
----
[PYK] 2015-12-06: Combine `tailcall` with an [identity function%|%identity]
command to emulate `[return]`:
======
proc p1 {} {
tailcall lindex {Hello from p1}
}
======
** Interaction with `[try]` **
===none
'''%''' proc foo {} {puts {I'm foo}}
'''%''' proc bar {} {puts {I'm bar}; try {tailcall foo} finally {puts exiting}}
'''%''' foo
''I'm foo''
'''%''' bar
''I'm bar''
''exiting''
''I'm foo''
===3
[HE] 2015-03-20315: [HE] I'm sure ;-) that I don't understood what happend there. Why "exiting" is printed before "I'm foo" when I call bar?
If I change bar to
======
proc bar {} {puts {I'm bar}; try {puts tryBody; tailcall foo} finally {puts exiting}; puts afterwards}
======
and call it, I get:
======none
I'm bar
tryBody
exiting
I'm foo
======
What I see is that tailcall replaces the rest of proc even inside the body of `[try]`.
But then, why is the `finally` clause execvaluated?
And even, if we assume the `finally` clause has to be execvaluated because it is documented always to be execvaluated,
then there would be the question, why before the execution of the tailcall command?
[AMG]: [[foo]] is invoked by replacing [[bar]] which implies the intervening [[[try]]] block must exit before [[foo]] can start.
----
[wdb]: Apparently, the `tailcall` closes one of the last gaps in
Tcl: Tail recursion as known in [Scheme].
** Example: Cause Caller to Return **
======
proc one {} {
two
return 8
}
proc two {} {
tailcall return 5
}
one ;# -> 5
======
`one` returns `5`, not `8`, because by invoking two, which, through `[tailcall]`, is replaced by `[return]`.
** Example: Factorial **
[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.
** Using Tailcall for Callbacks **
[Napier / Dash Automation] 2015-12-28:
Someone (I forget who now) gave me this little snippet which I love and handles many cases for me. I use it with the -command switches throughout my scripts:
======
proc callback {args} {tailcall namespace code $args}
namespace eval foo {
proc myProc var {puts $var}
proc myCall {} { after 5000 [callback myProc $::myVar] }
}
set myVar "Cool!"
foo::myCall
======
** Emulating `tailcall` **
[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]` **
[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 [http://wiki.tcl.tk/1507#pagetocc0434a60%|%Possible uplevel deficiencies%|%].
Also see [http://wiki.tcl.tk/1507#pagetocb7539876%|%When to use uplevel] for
more on when to use or avoid `[uplevel]`. See
[http://wiki.tcl.tk/1017#pagetoc74fae1d9%|%eval vs bytecode] for discussion and
performance numbers regarding [bytecode] compilation with `[eval]`,
`[uplevel]`, `[try]`, and others.
** When to apply `tailcall` optimization **
[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 **
[NEM]: Many thanks to [MS] for his hard work making this a reality!
<<categories>> Command | Concept | Control structure | Functional Programming