TIP #327: PROPER TAILCALLS ============================ Version: $Revision: 1.8 $ Author: Miguel Sofer David S. Cargo State: Final Type: Project Tcl-Version: 8.6 Vote: Done Created: Saturday, 20 September 2008 URL: https://tip.tcl-lang.org327.html Post-History: ------------------------------------------------------------------------- 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. ------------------------------------------------------------------------- TIP AutoGenerator - written by Donal K. Fellows