TIP #327: Proper Tailcalls
_____________________________________________________________________________
TIP:	327
Title:	Proper Tailcalls
Version:	$Revision: 1.8 $
Authors:	Miguel Sofer <msofer@users.sf.net>
	David S. Cargo <escargo@skypoint.com>
State:	Final
Type:	Project
Tcl-Version:	8.6
Vote:	Done
Created:	Sat Sep 20 00:00:00 UTC 2008
Keywords:	tailcall, NRE
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] 
 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.
_____________________________________________________________________________
Colophon
TIP AutoGenerator - written by Donal K. Fellows