\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#22: Multiple Index Arguments to lindex}
\date{January 19, 2001}
\author{David Cuthbert, Kevin Kenny, Don Porter, Donal K. Fellows}
\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 \#22}&\textbf{Multiple Index Arguments to lindex}\\\hline
Author&

David Cuthbert \tipmail{dacut}{kanga.org}
\par
Kevin Kenny \tipmail{kennykb}{acm.org}
\par
Don Porter \tipmail{dgp}{users.sourceforge.net}
\par
Donal K. Fellows \tipmail{fellowsd}{cs.man.ac.uk}
\\
Created&Friday, \(\text{19}^{\text{th}}\) January 2001\\
Type&Project\\
Tcl Version&\(8.4\alpha2\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.22 $\\
Keywords&lindex, multiple arguments, sublists\\
Post History&\\
Discussions To&news:comp.lang.tcl,mailto:kennykb@acm.org\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

Obtaining access to elements of sublists in Tcl often requires nested calls to the \textit{lindex} command. The indices are syntactically listed in most-nested to least-nested order, which is the reverse from other notations. In addition, the nesting of command substitution brackets further decreases readability. This proposal describes an extension to the \textit{lindex} command that allows it to accept multiple index arguments, in least-nested to most-nested order, to automatically extract elements of sublists.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

The heterogeneous nature of Tcl lists allows them to be applied to a number of useful data structures. In particular, lists can contain elements that are, themselves, valid lists. In this document, these elements are referred to as \textit{sublists.}

Extracting elements from sublists often requires nested calls to \textit{lindex.} Consider, for example, the following Tcl script that prints the center element of a 3-by-3 matrix:
\begingroup\small\begin{verbatim}
    set A {{1 2 3} {4 5 6} {7 8 9}}
    puts [lindex [lindex $A 2] 2]
\end{verbatim}
\endgroup

When these calls are deeply nested --- e.g., embedded in an \textit{expr} arithmetic expression, having results extracted through \textit{lrange,} etc. --- the results are difficult to read:
\begingroup\small\begin{verbatim}
# Print the sum of the center indices of two 3x3 matrices
set p [expr {[lindex [lindex $A 2] 2] + [lindex [lindex $A 2] 2]}]

# Get all but the last font in the following parsed structure:
set pstruct {text {ignored-data
                      { ... }
		       }
		       {valid-styles
			   {justifiction {left centered right full}}
			   {font {courier helvetica times}}
		       }
		 }
return [lrange [lindex [lindex [lindex $pstruct 1] 2] 2] 0 end-1]
\end{verbatim}
\endgroup

Note that the list of indices in the latter example is listed in the reverse order of vector indices. In most other languages/domains, the last line might take on one of the following forms:
\begingroup\small\begin{verbatim}
return list_range(pstruct[2][2][1], 0, end-1);

return pstruct[[2, 2, 1]][[0:-1]]

temp = pstruct(2, 2, 1);
result = range(temp, 0, length(temp) - 1);
\end{verbatim}
\endgroup

Allowing the \textit{lindex} command to accept multiple arguments would allow this more-natural style of coding to be written in Tcl.

\section{Specification}
\begin{enumerate}
\item{}
Under this proposal, the syntax for the \textit{lindex} command is to be modified to accept one of two forms:
\begingroup\small\begin{verbatim}
     lindex list indexList
\end{verbatim}
\endgroup
\end{enumerate}

 or
\begingroup\small\begin{verbatim}
     lindex list index1 index2...
\end{verbatim}
\endgroup

\begin{quote}
In either form of the command, the \textit{list} parameter is expected to be a well-formed Tcl list.
\end{quote}

\begin{quote}
In the first form of the command, the \textit{indexList} argument is expected to be a Tcl list comprising one or more list indices, each of which must be an integer, the literal string \textit{end}, or the literal string \textit{end-} followed by an integer with no intervening whitespace. The existing \textit{lindex} command is a degenerate form of this first form, where the list comprises a single index.
\end{quote}

\begin{quote}
In the second form of the command, each of the \textit{index} arguments is expected to be a list index, which again may be an integer, the literal string \textit{end}, or the literal string \textit{end-} followed by an integer with no intervening whitespace.
\end{quote}
\begin{enumerate}
\setcounter{enumi}{1}
\item{}
In either form of the command, once the \textit{indexList} parameter is expanded, there is a single \textit{list} parameter and one or more \textit{index} parameters. If there is a single \textit{index} parameter \textit{N}, the behavior is identical to today's \textit{lindex} command, and the command returns the \textit{N}th element of \textit{list}; if \textit{N} is less than zero or at least the length of the list, a null string is returned.
\setcounter{enumi}{2}
\item{}
If more than one \textit{index} parameter is given, then the behavior is defined recursively; the result of
\begingroup\small\begin{verbatim}
   lindex $list $index0 $index1 ...
\end{verbatim}
\endgroup

or
\begingroup\small\begin{verbatim}
   lindex $list [list $index0 $index1 ...]
\end{verbatim}
\endgroup

is indentical to that of
\begingroup\small\begin{verbatim}
   lindex [lindex $list $index0] $index1...
\end{verbatim}
\endgroup

or, equivalently,
\begingroup\small\begin{verbatim}
   lindex [lindex $list $index0] [list $index1...]
\end{verbatim}
\endgroup

(This specification does not constrain the implementation, which may be iterative, recursive, or even expanded inline.)
\setcounter{enumi}{3}
\item{}
When an invalid index is given, an error of the form, \textit{bad index ``invalid\_index'': must be integer or end?-integer?}, where \textit{invalid\_index} is the first invalid index encountered, must be returned.
\setcounter{enumi}{4}
\item{}
If the list argument is malformed, the error resulting from an attempt to convert the list argument to a list must be returned. This behaviour is unchanged from the current implementation.
\end{enumerate}

\section{Side Effects}
\begin{enumerate}
\item{}
Whether the result of the \textit{lindex} operation is successful, the underlying Tcl\_Obj that represents the list argument may have its internal representation invalidated or changed to that of a list.
\end{enumerate}

\section{Discussion}

Some attention must be paid to giving the \textit{lindex} command adequate performance. In particular, the implementation should address the common case of
\begingroup\small\begin{verbatim}
    lindex $list $i
\end{verbatim}
\endgroup

where \textit{\$i} is a ``pure'' integer (that is, one whose string representation has not yet been formed). If the above specification is followed naively, the flow will be as follows.

Since \textit{objc} is three, \textit{objv[2]} is expected to be a list. Since it is not, it must be converted from its string representation. It does not have one yet, so the string representation must be formed. Now the string representation is parsed as a list. An array (of length one) of Tcl\_Obj pointers is allocated to hold the list in question, and a Tcl\_Obj is allocated to hold the single element. Memory is allocated to hold the element's string representation. Now the \textit{lindex} command converts the first element of the list to an index (in this case an integer).

This elaborate ballet of type shimmering requires converting the integer to a string and back again. It also requires four calls to \textit{ckalloc:}
\begin{enumerate}
\item{}
Allocate a buffer for the string representation.
\setcounter{enumi}{1}
\item{}
Allocate the array of Tcl\_Obj pointers for the list representation.
\setcounter{enumi}{2}
\item{}
Allocate the Tcl\_Obj that represents the first (and only) element of the list.
\setcounter{enumi}{3}
\item{}
Allocate a buffer for the string representation of that element.
\end{enumerate}

And at the end, the result is the same integer that was passed as a parameter originally.

To avoid all this overhead in the common case, the proposed implementation shall (in the case where \textit{objc==3})
\begin{enumerate}
\item{}
Test whether \textit{objv[2]} designates an object whose internal representation holds an integer. If so, simply use it as an index.
\setcounter{enumi}{1}
\item{}
Test whether \textit{objv[2]} designates an object whose internal representation holds a list. If so, perform the recursive extraction of indexed elements from sublists described above.
\setcounter{enumi}{2}
\item{}
Form the string representation of \textit{objv[2]} and test whether it is \textit{end} or \textit{end-} followed by an integer. If so, use it as an index.
\setcounter{enumi}{3}
\item{}
Attempt to coerce \textit{objv[2]} to an integer; if successful, use the result as an integer.
\setcounter{enumi}{4}
\item{}
Attempt to coerce \textit{objv[2]} to a list; if successful, use the result as an index list.
\setcounter{enumi}{5}
\item{}
Report a malformed \textit{index} argument; the \textit{indexList} parameter is not a well-formed list.
\end{enumerate}

This logic handles all the cases of singleton lists transparently; it is effectively a simple-minded type inference that optimizes away needless conversions.

Assuming that the related \cite{tip33} is approved, this logic will most likely be combined with the identical logic required in that proposal for parsing \textit{index} arguments to the \textit{lset} command.

\vspace{3ex}\hrule\vspace{1.5ex}

\section{Comments}

\textit{Don Porter \tipmail{dgp}{users.sourceforge.net}}

\begin{quote}
I agree that it would be helpful to many programmers to provide a multi-dimensional array data structure that can be accessed in the manner described in this TIP. In the \textit{struct} module of \textit{tcllib}, several other data structures are being developed: graph, tree, queue, stack. I would support adding another data structure to that module that provides an interface like the one described in this TIP, with the intent that all of these helpful data structures find their way into the BI distribution.
\end{quote}

\begin{quote}
I don't see any advantage to adding complexity to [lindex] as an alternative to development of a multi-dimensional array structure. Without a compelling advantage, I'm inclined against making [lindex] more complex. I like having Tcl's built-in commands provide primitive operations, and leave it to packages to combine the primitives into more useful, more complex resources.
\end{quote}

\begin{quote}
This TIP should also consider how any changes to [lindex] mesh with the whole [listx] overhaul of Tcl's [list] command that has been discussed.
\end{quote}

\textit{Dave Cuthbert \tipmail{dacut}{kanga.org} responds}

\begin{quote}
Don makes a good point -{}- with a good set of data structures in tcllib, the need for this TIP is lessened or even eliminated. Nonetheless, I see this as a way of implementing the structures he describes. In other words, a more powerful primitive (which, in reality, adds fairly little complexity when measured in number of lines of code changed) would benefit these structures.
\end{quote}

\begin{quote}
As for the [listx] overhaul, there are many competing proposals for the specification it is difficult to come up with a metric. In writing this TIP, I assumed a vacuum -{}- that is, a listx command would not be added to the core in the near future.
\end{quote}

\textit{Donal K. Fellows \tipmail{fellowsd}{cs.man.ac.uk} points out}

\begin{quote}
Although there is tcllib and [listx] to think about, they are certainly not reasons for rejecting this TIP out of hand. The availability of tcllib is not currently anything like universal (not stating whether this is a good, bad or ugly thing) and all the [listx] work will need its own TIP to make it into the core (you tend to have availability problems if it is an extension.) It is not as if the core is short of syntactic sugar right now (the [foreach] command is ample demonstration of this.)
\end{quote}

\textit{Don Porter \tipmail{dgp}{users.sourceforge.net} follows up}

\begin{quote}
I'll leave the discussion above in place so the history of this TIP is preserved, but I have withdrawn my objection.
\end{quote}

\vspace{3ex}\hrule\vspace{1.5ex}

There was quite a discussion on \url{news:comp.lang.tcl} about using lindex to return multiple arguments. For example:
\begingroup\small\begin{verbatim}
 % set list {a {b1 b2} c d e}
 % lindex $list 1
 b1 b2
 % lindex $list 1 0
 {b1 b2} a
 % lindex $list {1 0}
 b1
\end{verbatim}
\endgroup

In other words, the list index arguments can, themselves, be lists. Only when the argument is a list would the ``recursive selection'' procedure of the TIP be used. For multiple arguments, the behaviour is akin to
\begingroup\small\begin{verbatim}
 lindex $list a b c  ->
      list [lindex $list a] [lindex $list b] [lindex $list c]
\end{verbatim}
\endgroup

\textit{Summarised by Dave Cuthbert \tipmail{dacut}{kanga.org}}

\textit{Donal K. Fellows \tipmail{fellowsd}{cs.man.ac.uk} points out}

\begin{quote}
The problems with the above version of multiple indexing are that it loses the property that [lindex] always returns a single element (making writing robust code harder) and that it forces use of the [list] constructor a lot or inefficient type handling when some of the indices must be computed. Then there is the whole question of what happens when you have indexes that are lists of lists, which is a major can of worms.
\end{quote}

\begin{quote}
Luckily, we could always put this sort of behaviour into a separate command (e.g. called [lselect]) which addresses at least the majority of my concerns, and which (in my opinion) need not even form part of this TIP.
\end{quote}

\textit{Dave Cuthbert \tipmail{dacut}{kanga.org} adds}

\begin{quote}
I intentionally left [lselect] out of the original TIP (and it is still not present in the 02-April-2001 version). As Donal points out, it is a major can of worms and, though there was general agreement on c.l.t that such a command would be useful, people had differing opinions on what form it should take.
\end{quote}

\begin{quote}
Perhaps my view on TIPs is incorrect, but I try to include only sure-fire ``yeah, we ought to have done that a few versions ago'' items.
\end{quote}

\vspace{3ex}\hrule\vspace{1.5ex}

\section{Notes on History of this TIP}

\textit{This TIP was originally written by Dave Cuthbert \tipmail{dacut}{kanga.org}, but ownership has passed (beginning of April) to Kevin Kenny \tipmail{kennykb}{acm.org}.}

This TIP underwent substantial revision in May of 2001, to add the syntax where all the \textit{index} parameters could be grouped as a list rather than placed inline on the command line.

\section{See Also}

\cite{tip33}.

\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 \#33]{tip33}
Kevin Kenny,
\emph{Add 'lset' Command to Assign to List Elements.},
on-line at \url{http://purl.org/tcl/tip/33.html}
\end{thebibliography}
\end{document}
