TIP: 327
Title: Proper Tailcalls
Version: $Revision: 1.8 $
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.