TIP:            327
Title:          Proper Tailcalls
Version:        $Revision: 1.8 $
Author:         Miguel Sofer <msofer@users.sf.net>
Author:         David S. Cargo <escargo@skypoint.com>
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.
