\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#194: Procedures as Values via '''apply'''}
\date{April 30, 2004}
\author{Miguel Sofer, Joe Mistachkin}
\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 \#194}&\textbf{Procedures as Values via '''apply'''}\\\hline
Author&

Miguel Sofer \tipmail{msofer}{users.sf.net}
\par
Joe Mistachkin \tipmail{joe}{mistachkin.com}
\\
Created&Friday, \(\text{30}^{\text{th}}\) April 2004\\
Type&Project\\
Tcl Version&\(8.5\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.6 $\\
Keywords&Tcl, lambda, anonymous, command, function, functional programming\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes a new command, tentatively named \textbf{apply}, to allow procedures to be first class values. It is an alternative to the approach of \cite{tip187}, where attaining a similar goal requires a syntactic and semantic change.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

Tcl is typeless, and every first class value is a string (or at least representable as such). Strings are managed by reference counting in the Tcl core, the required memory is freed automatically when the string is no longer referenced.

Tcl commands may interpret their arguments differently. Some commands interpret some of their arguments as scripts --- \textbf{eval}, \textbf{uplevel}, and so on. But no current Tcl command is able to specify that a script is to be run in an isolated environment, free of unwanted side effects or memory leaks caused by name collisions.

In order to achieve this isolation, one has to define a new command via \textbf{proc} and assume the burden of name-collision avoidance and lifetime management, or else produce complicated scripts with ugly contorsions to avoid the name collisions.

Both \cite{tip187} and this one propose ways to provide this lacking functionality to Tcl. The approach here is to do so by creating a new \textbf{apply} command without any change to Tcl's syntax.

\section{Specification}

A reference manual page can be found at [\url{http://utdt.edu/~mig/apply2.html}]. Summarizing, the syntax of the new command is:
\begin{itemize}
\item{}
\textbf{apply} \textit{func} ?\textit{arg1 arg2 ...}?

The first argument \textit{func} is an anonymous function --- a list of two or three elements [\textbf{list} \textit{arglist body} ?\textit{namespace}?]. The first two are exactly like the arguments to \textbf{proc}, the third determines the namespace for \textbf{variable}, \textbf{namespace} and command resolution when the body is evaluated. The \textit{namespace} is interpreted as fixed, and is the interpreter's global namespace in the two-argument case.

The remaining arguments \textit{arg1 arg2 ...} are taken as values for the first formal arguments in \textit{arglist}.
\end{itemize}

The semantics of \textbf{apply} (with the exception of some of the fine details of error messages) can be described by:
\begingroup\small\begin{verbatim}
 proc apply {fun args} {
     set len [llength $fun]
     if {($len < 2) || ($len > 3)} {
         error "can't interpret \"$fun\" as anonymous function"
     }
     lassign $fun argList body ns
     set name ::$ns::[getGloballyUniqueName]
     set body0 {
         rename [lindex [info level 0] 0] {}
     }
     proc $name $argList ${body0}$body
     set code [catch {uplevel 1 $name $args} res opt]
     return -options $opt $res
 }
\end{verbatim}
\endgroup

where the availability of a \textbf{getGloballyUniqueName} procedure was assumed.

\section{Reference Implementation}

There is a patch [\url{http://sf.net/tracker/?func=detail&aid=944803&group_id=10894&atid=360894}] that implements this TIP.

The patch defines a new \textit{tclLambdaType} for \textit{Tcl\_Obj}s that caches the internal structures necessary for efficient evaluation: a Proc struct, a pointer to \textit{namespace}, and the bytecodes implementing \textit{body}. It is a small patch that relies heavily on the implementation of \textbf{proc}, producing essentially a regular \textbf{proc} with no command attached to it: an anonymous function.

All cached internal structures are freed when \textit{func} ceases to be referenced or when it loses its internal representation as a \textit{tcllambdaType} through shimmering.

Note that a similar approach is likely for a definitive implementation of \cite{tip187}.

\section{Further Functional Programming Constructs}

The availability of \textbf{apply} permits an easy and efficient access to other FP functions. For example one might define a constructor \textbf{lambda} and a \textbf{curry} command like this:
\begingroup\small\begin{verbatim}
 proc lambda {arglist body {ns {}}} {
     list ::apply [list $arglist $body $ns]
 }

 proc curry {lam args} {
     lappend lam {expand}$args
 }
\end{verbatim}
\endgroup

Function composition is also relatively easy to specify. Further examples may be seen in the Wiki, see for instance Neil Madden's \textbf{map}, \textbf{filter}, \textbf{foldl}, \textbf{foldr} [\url{http://wiki.tcl.tk/11141}] --- note that the syntax is slightly different from the one proposed here.

\section{Comparison to TIP 187 and outlook}

In terms of usage, the main difference is that where TIP 187 does:
\begingroup\small\begin{verbatim}
 set p [list lambda x {string length $x}]
 $p $foo
\end{verbatim}
\endgroup

we would do here:
\begingroup\small\begin{verbatim}
 set p [list ::apply [list x {string length $x}]]
 # or: set p [lambda x {string length $x}]
 {expand}$p $foo ;# or 'eval $p [list $foo]', or ...
\end{verbatim}
\endgroup

or else:
\begingroup\small\begin{verbatim}
 set p [list x {string length $x}]
 apply $p $foo
\end{verbatim}
\endgroup

This TIP requires no changes to the rules in Tcl(n), whereas \cite{tip187} requires a change in rule [2].

If in the future Tcl evolves a rule for automatic expansion of leading words, \textbf{apply} will provide automatically the syntax of \cite{tip187}.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\begin{thebibliography}{TIP \#1}
\addcontentsline{toc}{section}{References}
\bibitem[TIP \#187]{tip187}
Salvatore Sanfilippo,
Miguel Sofer,
Paul Nash,
\emph{Procedures as Values},
on-line at \url{http://purl.org/tcl/tip/187.html}
\end{thebibliography}
\end{document}
