\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#192: Lazy Lists}
\date{March 27, 2004}
\author{Salvatore Sanfilippo, Theo Verelst}
\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 \#192}&\textbf{Lazy Lists}\\\hline
Author&

Salvatore Sanfilippo \tipmail{antirez}{invece.org}
\par
Theo Verelst \tipmail{theover}{tiscali.nl}
\\
Created&Saturday, \(\text{27}^{\text{th}}\) March 2004\\
Type&Project\\
Tcl Version&\(9.0\)\\
State&Draft\\
Vote&Pending\\
Version&\tipversion$Revision: 1.2 $\\
Keywords&Tcl\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes to add a new command to generate lists of \textit{N} elements, where the \textit{i}-th element is computed as the result of an unary Tcl procedure with \textit{i} as itsargument. Implementing special handling for this kind of lists inside the Tcl core will allow generation of lists in a \textit{lazy} way. This TIP's goal is not to change the semantics of Tcl, but just to provide a different space complexity for an (often interesting) subset of Tcl lists.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

A subset of Tcl lists can be generated mapping an unary function to an integer sequence in the range [0,n), where \textit{n} is the length of the list. The following procedure implements this concept:
\begingroup\small\begin{verbatim}
proc lgen {len func} {
    set l {}
    for {set i 0} {$i < $len} {incr i} {
        lappend l [uplevel 1 [list $func $i]]
    }
    return $l
}
\end{verbatim}
\endgroup

and the following (using the \textbf{lambda} from \cite{tip187}) is an example of usage:
\begingroup\small\begin{verbatim}
proc lambda {argl body} {
    set name [info level 0]
    proc $name $argl $body
    set name
}

set mylist [lgen 10 [lambda x {incr x; expr $x*$x}]]
\end{verbatim}
\endgroup

The above code will evaluate to the same as [list 1 4 9 16 25 36 49 64 81 100]. \textbf{lgen} can be used in order to build a particularly useful Tcl procedure named \textbf{range}, returning a sequence of integers with given \textit{start} \textit{end} and (optionally) \textit{step} paramenters. The \textbf{range} function is convenient for rewriting many \textbf{for} loops in terms of \textbf{foreach} iterating over an integer range. So instead of writing:
\begingroup\small\begin{verbatim}
for {set i 0} {$i < 20} {incr i 2} {
    puts $i
}
\end{verbatim}
\endgroup

It is possible to write:
\begingroup\small\begin{verbatim}
foreach i [range 0 20 2] {
    puts $i
}
\end{verbatim}
\endgroup

That is more convenient to write and to read for the programmer. Of course it's possible to use \textbf{foreach} to iterate any sequence that \textbf{lgen} is able to generate, but \textbf{range} is probably one of the more common of the possible usages.

The TIP proposes to implement the ability to handle this kind of lists in a special way directly inside the \textit{List} object implementation. This allows these common usage patterns of the list object to not need to hold the real sequence but just the length and the unary element generator function.

The interface to the Tcl programmer is a single command similar in semantics to \textbf{lgen}, but possibly with a more suitable name.

\section{Proposed Change}

The \textit{List} object should be modified in order to have the lazy-list as subtype or alternate internal implementation. All the core should use the proper \textit{List} object API instead to access to the \textit{List} object via the internal representation.

The two calls that should be guaranteed to not alter the \textit{lazyness} of the list are \textbf{Tcl\_ListObjLength()} and \textbf{Tcl\_ListObjIndex()}. Other calls like \textbf{Tcl\_ListObjReplace()} may be optimized for the lazy-list case when possible, and the \textbf{lrange} command may be optimized (particularly when the start index is zero).

The \textit{List} will be converted into a non-lazy version if the user tries to modify it, for example using the \textbf{Tcl\_ListObjAppendElement()} function. The \textit{List} will also be converted into a non-lazy version on \textbf{Tcl\_ListObjGetElements()} calls.

It's possible to handle the \textbf{range} command as a particular case of lazy-list in order to provide a very fast implementation of foreach iterating over an integer range (probably much faster than the today \textbf{for}, being \textbf{foreach} already faster iterating over a literal list of numbers).

\subsection{Consequences: Reference Management}

The author of this TIP tried to implement the proposed changes in the HEAD, discovering that the \textbf{Tcl\_ListObjIndex()} interface creates a serious problem due to the assumption that the \textit{List} object holds at least one reference to the returned element. The implementation of \textbf{Tcl\_ListObjIndex()} in the lazy case can't just create the element object and return it with refcount of zero because it will leak if the caller does not increment the reference count itself.

It's also not safe to store a reference to the last few elements created in the lazy way inside the \textit{List} object, and release this references in order to create more elements, because in theory the caller may require a large number of elements storing pointers into an array, and finally incrementing the reference counts in a single pass.

In order to avoid this problem, the semantics of \textbf{Tcl\_ListObjIndex()} should be changed in order to always return the element with an already incremented reference count. It will be up to the caller to decrement the reference count if the object will be discarded. (This is why this change is proposed for Tcl 9.0 and not 8.5, as this has a significant impact on both the core and on extensions.)

An alternative change to \textbf{Tcl\_ListObjIndex()} (in order to make it ``compatible'' with the semantics of lazy lists) is to disallow successive calls against the same list if a previous call returned an object that the caller plans to reference the object.

So:
\begingroup\small\begin{verbatim}
Tcl_ListObjIndex(interp, myListPtr, 0, &a);
Tcl_ListObjIndex(interp, myListPtr, 0, &b);
mystruct->a = a;
mystruct->b = b;
Tcl_IncrRefCount(a);
Tcl_IncrRefCount(b);
\end{verbatim}
\endgroup

will be invalid, while:
\begingroup\small\begin{verbatim}
Tcl_ListObjIndex(interp, myListPtr, 0, &a);
Tcl_IncrRefCount(a);
mystruct->a = a;
Tcl_ListObjIndex(interp, myListPtr, 0, &b);
Tcl_IncrRefCount(b);
mystruct->b = b;
\end{verbatim}
\endgroup

is valid. This fixes any problem because the \textit{List} object can just take a reference to the last generated object and avoid any leak. A study of existing code in the core and extensions is required to see whether this will allow the majority of code to operate unchanged.

\subsection{Consequences: Non-constant Lists}

The TIP also poses another problem in the case the unary function has side effects. In this case the behaviour can be described without to violate the Tcl semantic in terms of variable traces most of the time, but actually it's possible to write code that shows that the list value is non-stable even without using variables (because Tcl has no ``object trace'' concept actually).

If this is considered a problem, the TIP may be reduced in order to only allow lazy generated lists composed of integer ranges, (but that is one of the most interesting advantages of this TIP anyway.) With integer ranges there are no side effects, so the semantical problem is not an issue, but the \textbf{Tcl\_ListObjIndex()} problem is exactly the same.

Of course, this is arguably just an unavoidable consequence and shows that not all possible unary element generator functions, but just those with a functional denotation, are necessarily reasonable choices.

\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}
