TIP #327: Proper Tailcalls

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.

[Index] [History] [HTML Format] [Source Format] [LaTeX Format] [Text Format] [XML Format] [*roff Format (experimental)] [RTF Format (experimental)]