\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#187: Procedures as Values}
\date{April 20, 2004}
\author{Salvatore Sanfilippo, Miguel Sofer, Paul Nash}
\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 \#187}&\textbf{Procedures as Values}\\\hline
Author&

Salvatore Sanfilippo \tipmail{antirez}{invece.org}
\par
Miguel Sofer \tipmail{msofer}{users.sf.net}
\par
Paul Nash \tipmail{webscool}{ihug.co.nz}
\\
Created&Tuesday, \(\text{20}^{\text{th}}\) April 2004\\
Type&Project\\
Tcl Version&\(8.6\)\\
State&Rejected\\
Vote&Done\\
Version&\tipversion$Revision: 1.14 $\\
Keywords&Tcl, lambda, anonymous, command, function\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP describes a change in the semantics of Tcl to allow procedures to be first class values, being represented as strings, and in particular as three element lists.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

The Tcl programming language is an homoiconic-form language. Program and data are both presented as strings. A Tcl procedure's arguments list and body are not an exception to this rule, but the procedure itself is handled as a name bound to a particular couple of arguments list and body. This name lives in a separated namespace and does not collide with variables names.

The first argument of every Tcl command should be the name of a built-in command, or a procedure (actually a procedure is a user defined command). In the latter case, the Tcl interpreter performs a lookup in a virtual table (that is indirectly accessible using \textbf{proc} and \textbf{info} commands), in order to check if there is a procedure with the specified name, and to call the procedure using the associated arguments list and body. If a procedure with the specified name is not present (nor a built-in command), the interpreter calls a special procedure named unknown to handle the exception, or raises an error if the unknown procedure does not exists.

This TIP proposes to modify the Tcl semantic in order to check if the command name is a valid, three-elements Tcl list with the first element of the list being the string \textbf{lambda}, before to lookup any built-in command or procedure. In such a case Tcl will call the procedure that is represented by the arguments list and body that are the second and third elements of the list. Procedures represented as three-elements lists are called \textit{anonymous procedures} in this TIP, and are first class values as any other Tcl list.

The storage of an anonymous procedure is handled like any other Tcl object. Memory management is one of the main problems of procedures created ``on the fly'' in Tcl, so that to create anonymous procedures in Tcl in order to emulate the lambda operator, was and is a problem. With this TIP, anonymous procedures can be created just using the list command. The following is an example:
\begingroup\small\begin{verbatim}
        set p [list lambda x {string length $x}]
        $p foo
\end{verbatim}
\endgroup

The above script evaluates to 3. Fast, reliable anonymous procedures may allow Tcl to better support a functional approach that is very interesting to use in a language where the list is the main data structure.

\subsection{Examples}

The following Tcl scripts (based on the classic list combinators from functional programming languages) should look very natural to most experienced Tcl programmers:

\subsubsection{Example 1: Use of Anonymous Commands with a [map] Command}
\begingroup\small\begin{verbatim}
    proc map {list proc} {
        set res {}
        foreach e $list {
            lappend res [$proc $e]
        }
        return $res
    }

    set a [list one two three four five]
    set b [map $a [list lambda x {string length $x}]]
\end{verbatim}
\endgroup

This evaluates to [list 3 3 5 4 4]

\subsubsection{Example 2: Use of Anonymous Commands with a [filter] Command}
\begingroup\small\begin{verbatim}
    proc filter {list proc} {
        set res {}
        foreach e $list {
            if {![$proc $e]} {
                lappend res $e
            }
        }
        return $res
    }

    set a [list 1 10 100 4 5]
    set b [filter $a [list lambda x {expr $x<10}]]
\end{verbatim}
\endgroup

This evaluates to [list 10 100]

Note: In practice, defining an alias, \textbf{lambda}, for \textbf{list lambda} leads to more natural-looking code.

\tiplangle{}PN\tiprangle{} 
\begingroup\small\begin{verbatim}
    (bin) 20 % list lambda x {string length $x}
    lambda x {string length $x}
    (bin) 21 % lambda x {string length $x}
    lambda x {string length $x}
    (bin) 22 % 
\end{verbatim}
\endgroup

No alias is required \tiplangle{}/PN\tiprangle{}

The author of this TIP thinks that many Tcl programmers will enjoy the ability to use this programming style. The Tcl folklore actually implemented different versions of \textbf{lambda} in the past, but no one is suitable for prime time.

Still, the ability to manipulate lists in a simpler way can make Tcl more enjoyable.

The new semantic introduced by this TIP is not only needed to use operators like \textit{map} and \textit{filter}, but generally makes Tcl able to address high-order programming in a clean way: procedures that returns procedures, Currying, and functional composition are all possible using the TIP's first class procedures in a straightforward way.

There are probably other interesting applications in the field of the Object Oriented Programming.

\section{Proposed Change}

The proposed change is to check if the first argument of a command is an anonymous procedure before to perform any other lookup. This test should be fast using the object's string representation because a Tcl list having as first argument the string ``lambda'' must start in a proper way that is easy to detect.

The procedure can be byte-compiled when it's called the first time, the byte-compiled version can be referenced from the internal representation of the \textit{Tcl\_Obj} representing the procedure. The original string representation of the anonymous procedure can be cached inside the \textit{Tcl\_Obj} in order to be able to recreate it when needed as for \textit{Tcl\_Obj} semantic.

Actually the implementation may create a conventional Tcl procedure associated and referenced by the anonymous procedure's object, that can be released when the internal representation of the anonymous procedure's \textit{Tcl\_Obj} is freed.

The real Tcl procedure may live in the \textbf{::lambda} namespace in order to be self-introspective.

\section{Reference Implementation}

A reference implementation is being developed in Patch \#940207 (superseeding the previous \#939190) [\url{https://sourceforge.net/tracker/index.php?func=detail&aid=940207&group_id=10894&atid=310894}]

It follows this tip fairly closely in its effects, but diverges in the implementation strategy. It implements autocleaning procs, and defines lambda expressions as autocleaning procs in (for instance) the ::tcl::lambda namespace. The example above can be defined equivalently as
\begingroup\small\begin{verbatim}
   set p [lambda x {string length $x}]
   set p [list ::tcl::lambda:: x {string length $x}]
   set p {::tcl::lambda:: x {string length $x}}
\end{verbatim}
\endgroup

although the last version will prevent autocleanup (due to the name being stored in a shared literal).

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

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