TIP: 327 Title: Proper Tailcalls Version: $Revision: 1.8 $ Author: Miguel Sofer Author: David S. Cargo 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.