\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#385: Functional Traces On Variables }
\date{February 13, 2011}
\author{Alexandre Ferrieux}
\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 \#385}&\textbf{Functional Traces On Variables }\\\hline
Author&

Alexandre Ferrieux \tipmail{alexandre.ferrieux}{gmail.com}
\\
Created&Sunday, \(\text{13}^{\text{th}}\) February 2011\\
Type&Project\\
Tcl Version&\(9.0\)\\
State&Draft\\
Vote&Pending\\
Version&\tipversion$Revision: 1.6 $\\
Keywords&Tcl, traces\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

Functional traces are new variants of variable traces, that rely purely on value passing rather than variable updating. Applied to array traces, they allow a much more efficient implementation of various storage backends.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

The current variable trace API does not focus on the read or written value; instead, only the variable (and array key) name is made available to the callback. Actual manipulation of the value thus involves updating the variable within the trace callback: the new, ``synthetic'' value must be written for real.

While this approach is acceptable for a scalar variable, in the case of arrays it forces the ``memoize'' pattern: whenever reads are done on an array with a read trace, the read value is actually stored in the array, with no obvious spot to unset it afterwards. Hence, although we are backing the array with a function which is called on every read, the memory usage is that of a memoized function; this does not scale up at all.

A typical situation where this matters, is the use of traces to wrap the convenient array syntax around another kind of storage (like a pre-existing dictionary or database): what is intended is that \textbf{\$a(\$x)} becomes syntactic sugar for \textbf{[dict get \$d \$x]}, but without duplicating the storage in the array. This is currently impossible.

The proposed extension to the trace API allows for ``functional'' traces, in the usual computing sense of ``no side effect'': here the value of interest is passed as an argument to a write trace callback, and taken from the return value of a read trace callback. This way, no access to the underlying variable is needed. The array syntax can become a frontend to just about anything, without any memory consumption, and with adequate preformance since values are passed as \textit{Tcl\_Obj}s. Thus functional traces could also be named ``virtual variables''.

As an extra bonus, ``read-only variables'' can be implemented efficiently, which is notably impossible with the current API (since the write trace is called after the fact, it must rely on another mechanism to retrieve the pre-write value).

\section{Definition}

The new subcommands

\begin{quote}
\textbf{trace add variable} \textit{name} \textbf{readf} \textit{cmdprefix}
\end{quote}

\begin{quote}
\textbf{trace add variable} \textit{name} \textbf{writef} \textit{cmdprefix}
\end{quote}

\begin{quote}
\textbf{trace add variable} \textit{name} \textbf{unsetf} \textit{cmdprefix}
\end{quote}

\begin{quote}
\textbf{trace add variable} \textit{name} \textbf{existsf} \textit{cmdprefix}
\end{quote}

are the functional variants of the existing \textbf{read}, \textbf{write}, and \textbf{unset} variable traces. The new \textbf{existsf} is made possible by the functional style. The \textit{cmdprefix} callback API is close to that of current traces, with two variations:
\begin{enumerate}
\item{}
For a \textbf{readf} or \textbf{existsf} trace, the callback's returned value is used as the result of the read/exists operation.
\setcounter{enumi}{1}
\item{}
For a \textbf{writef} trace, the value to be written is passed as an extra argument to the callback:

\textit{cmdprefix} \textit{name1} \textit{name2} \textbf{writef} \textit{value}
\end{enumerate}

In both cases, the value is passed efficiently as a \textbf{Tcl\_Obj}.

\section{Demos}

Here is the full code exposing a dict as an array:
\begingroup\small\begin{verbatim}
     trace add variable a readf [list trdictget ::d]
     trace add variable a writef [list trdictset ::d]
     proc trdictget {vv n1 n2 op} {
         upvar $vv v
         return [dict get $v $n2]
     }
     proc trdictset {vv n1 n2 op x} {
         upvar $vv v
         dict set v $n2 $x
     }
\end{verbatim}
\endgroup

Another example with Pascal-like 1-based numeric indices into a list, with bound checking, disguised as array keys:
\begingroup\small\begin{verbatim}
     trace add variable a readf [list trplistget ::l]
     trace add variable a writef [list trplistset ::l]
     proc trplistget {vv n1 n2 op} {
         upvar $vv v
         if {($n2<1) || ($n2>[llength $v])} {
             error "Index $n2 out of range for list $vv"
         } 
         return [lindex $v [expr {$n2-1}]]
     }
     proc trplistset {vv n1 n2 op x} {
         upvar $vv v
         if {($n2<1) || ($n2>[llength $v])} {
             error "Index $n2 out of range for list $vv"
         } 
	 lset v [expr {$n2-1}] $x
     }
\end{verbatim}
\endgroup

Obviously, the same principle can be applied to an SQLite or TDBC database; the net result is an instant-loadable ``array''.

\section{Possible Extensions}

A natural generalization would be to hook into array-level operations like \textbf{size}, \textbf{names}, \textbf{get}, \textbf{unset}, \textbf{startSearch}, etc. But then, maybe an ensemble/oo API would be preferred (hook one single command prefix for all operations concerning array \textit{a}). To be discussed.

\section{Reference Implementation}

Coming soon.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

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