# TIP 327: Proper Tailcalls
Author: Miguel Sofer <[email protected]>
Author: David S. Cargo <[email protected]>
State: Final
Type: Project
Vote: Done
Created: 20-Sep-2008
Post-History:
Keywords: tailcall,NRE
Tcl-Version: 8.6
-----
# Abstract
This TIP recommends adding proper tailcalls to Tcl.
# Proposal
We propose to add a new command:
> **tailcall** _cmd_ ?_arg ..._?
The command can only be invoked in a procedure or lambda body.
The effect of this command is very similar to:
> **return [uplevel 1 [list [namespace which** _cmd_ **]**
?_arg ..._?**]]**
with the sole exception that the invocation of _cmd_ happens _after_ the
currently executing body returns and is not visible in Tcl's call stack.
# Rationale
The new Non-Recursive Engine \(NRE\) implemented in Tcl 8.6 allows support for a
number of interesting features that have previously been difficult or
impossible to implement efficiently in Tcl. One such feature is support for
_proper tailcalls_, an important feature for functional-style programming.
The new command allows unbounded recursion and enables programming in
_continuation passing style_.
# Effect on Tcl's Call Stack
**tailcall** is implemented as a new command, as opposed to an optimization
that would be done automatically by the bytecode compiler, due to the effect
it has on Tcl's call stack.
Consider the following example:
proc showStack {} {
set depth [info frame]
set res {}
for {set i 1} {$i <= $depth} {incr i} {
lappend res [info frame $i]
}
return $res
}
proc one cmd {join [$cmd] \n}
proc two {} {uplevel 1 showStack}
proc three {} {tailcall showStack}
When run at the interactive prompt, we obtain
% one two
type eval line 1 cmd {one two} level 2
type proc line -1 cmd {$cmd} proc ::one level 1
type proc line 1 cmd {uplevel 1 showStack} proc ::two
type eval line 1 cmd showStack proc ::two
type proc line 5 cmd {info frame $i} proc ::showStack level 0
% one three
type eval line 1 cmd {one three} level 2
type proc line -1 cmd {$cmd} proc ::one level 1
type proc line 5 cmd {info frame $i} proc ::showStack level 0
%
Remark how **tailcall** completely removed the proc _three_ from Tcl's
call stack. This effect is also apparent on error traces.
# Implementation
An experimental implementation of tailcalls is available in Tcl 8.6a2 in CVS
on sourceforge, in the ::tcl::unsupported namespace.
# Copyright
This document has been placed in the public domain.