\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#327: Proper Tailcalls}
\date{September 20, 2008}
\author{Miguel Sofer, David S. Cargo}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#327}&\textbf{Proper Tailcalls}\\\hline
Author&

Miguel Sofer \tipmail{msofer}{users.sf.net}
\par
David S. Cargo \tipmail{escargo}{skypoint.com}
\\
Created&Saturday, \(\text{20}^{\text{th}}\) September 2008\\
Type&Project\\
Tcl Version&\(8.6\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.8 $\\
Keywords&tailcall, NRE\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP recommends adding proper tailcalls to Tcl.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Proposal}

We propose to add a new command:

\begin{quote}
\textbf{tailcall} \textit{cmd} ?\textit{arg ...}?
\end{quote}

The command can only be invoked in a procedure or lambda body.

The effect of this command is very similar to:

\begin{quote}
\textbf{return [uplevel 1 [list [namespace which} \textit{cmd} \textbf{]} ?\textit{arg ...}?\textbf{]]}
\end{quote}

with the sole exception that the invocation of \textit{cmd} happens \textit{after} the currently executing body returns and is not visible in Tcl's call stack.

\section{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 \textit{proper tailcalls}, an important feature for functional-style programming. The new command allows unbounded recursion and enables programming in \textit{continuation passing style}.

\section{Effect on Tcl's Call Stack}

\textbf{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:
\begingroup\small\begin{verbatim}
 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}
\end{verbatim}
\endgroup

When run at the interactive prompt, we obtain
\begingroup\small\begin{verbatim}
 % 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
 % 
\end{verbatim}
\endgroup

Remark how \textbf{tailcall} completely removed the proc \textit{three} from Tcl's call stack. This effect is also apparent on error traces.

\section{Implementation}

An experimental implementation of tailcalls is available in Tcl 8.6a2 in CVS on sourceforge, in the ::tcl::unsupported namespace.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
