\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#225: Arithmetic Series with Optimized Space Complexity}
\date{October 25, 2004}
\author{Salvatore Sanfilippo, Miguel Sofer}
\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 \#225}&\textbf{Arithmetic Series with Optimized Space Complexity}\\\hline
Author&

Salvatore Sanfilippo \tipmail{antirez}{invece.org}
\par
Miguel Sofer \tipmail{msofer}{users.sf.net}
\\
Created&Monday, \(\text{25}^{\text{th}}\) October 2004\\
Type&Project\\
Tcl Version&\(8.7\)\\
State&Draft\\
Vote&Pending\\
Version&\tipversion$Revision: 1.14 $\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes to add a new command to generate arithmetic sequences as Tcl lists that may be stored in constant space in many practical situations. The only change from the point of view of the Tcl programmer is the addition of a new command named \textbf{range}.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

An idiomatic way to assign successive elements of an arithmetic series to a variable is to use the \textbf{for} command. Usually the loop variable is initialized to the first element of the sequence, and incremented at every iteration of a given step using \textbf{incr}. The \textbf{for} test condition is used to limit the sequence generation to a given element, like in the following example:
\begingroup\small\begin{verbatim}
for {set i 0} {$i < 10} {incr i} {
    puts $i
}
\end{verbatim}
\endgroup

The Tcl programming language is at higher level than the C language, where this idiom firstly appeared, so it may be desiderable to be able to generate arithmetic sequences of integer numbers in a more comfortable way. Being the Tcl list a central data structure of the Tcl language, it apperas natural to generate a Tcl list of integers, and possibly use the \textbf{foreach} command to loop over every element, so that the above \textbf{for} loop can be translated into the following fragment of code:
\begingroup\small\begin{verbatim}
foreach i [range 0 10] {
    puts $i
}
\end{verbatim}
\endgroup

The \textbf{range} command can be also conveniently used in different contexts. The following code generates a list of squares of 0, 1, 2, 3, ... 9.
\begingroup\small\begin{verbatim}
proc map {varname script mylist} {
    upvar $varname var
    set res {}
    foreach var $mylist {
        lappend res [uplevel 1 $script]
    }
    return $res
}

puts [map x {expr {$x*$x}} [range 0 10]]

# Will output "0 1 4 9 16 25 36 49 64 81"
\end{verbatim}
\endgroup

The \textbf{range} command can be implemented in a way that makes it possible to internally store the arithmetic sequences genereated in constant space if they are only accessed using \textbf{foreach}, \textbf{llength} and \textbf{lindex} commands (\textbf{lrange} may also be handled in a special way). When needed, the object will be converted into a List object automatically. From the Tcl programmer point of view this optimization is transparent.

\section{Specification of the Behaviour}

The \textbf{range} command takes three arguments in the complete format, named \textit{start}, \textit{end} and \textit{step}, and generates a sequence of integers accordingly to the following algorithm in pseudo code:
\begingroup\small\begin{verbatim}
RangeLen(start, end, step)
1. if step = 0
2.     then ERROR
3. if start = end
4.     then return 0
5. if step > 0 AND start > end
6.     then ERROR
7. if setp < 0 AND end > start
8.     then ERROR
9. return 1+((ABS(end-start)-1)/ABS(step))

Range(start, end, step)
1. result <- EMPTY LIST
2. len <- RangeLen(start, end, step)
3. for i <- 0 to len - 1
4.     result.append(start+(i*step))
6. return result
\end{verbatim}
\endgroup

The \textit{step} argument can be omitted, and default to the value of 1, so [\textbf{range} 0 10 1] is the same as [\textbf{range} 0 10]. It's also possible to call the \textbf{range} command with a single argument, omitting both the \textit{start} and \textit{step} argument that will default respectively to 0 and 1, so that the following three commands will generate the same sequence of integers:
\begingroup\small\begin{verbatim}
range 0 10 1
range 0 10
range 10
\end{verbatim}
\endgroup

The following are examples of outputs.
\begingroup\small\begin{verbatim}
[range 0 10 1] => 0 1 2 3 4 5 6 7 8 9
[range 10 0 -2] => 10 8 6 4 2
[range 10 10] => empty list
[range 10 20 -3] => ERROR
[range 5] -> 0 1 2 3 4
\end{verbatim}
\endgroup

Infinite series and series resulting in lists bigger than the maximum list length that the Tcl code can handle are detected and reported as an error. \textit{start}, \textit{end}, and \textit{step} can be anything can fit into a Tcl wide integer.

Note that there is a practical justification for the fact that the elements generated never reach the value of the End argument, with the effect of [\textbf{range} 0 10 1] generating the sequence 0, 1, 2, ..., 9 and a range with the same value of \textit{start} and \textit{end} always generating an emtpy list. This is needed in order to make it comfortable to use \textbf{range} and \textbf{foreach} instead of \textbf{for} loops like in the following example:
\begingroup\small\begin{verbatim}
foreach i [range [llength $mylist]] {
    foobar [lindex $mylist $i]
}
\end{verbatim}
\endgroup

Because Tcl indexes are mostly zero-based, and it is often useful to access every element of a sequence given it's length, this appears to be the more sensible behaviour (this semantic is very similar to the range() function of the Python programming language, where range() is fully used to replace C-like \textit{for} loops.)

Unfortunately this behaviour is not as comfortable to run the indexes in reverse order:
\begingroup\small\begin{verbatim}
foreach i [range [expr {[llength $mylist]-1}] -1 -1] {
    foobar [lindex $mylist $i]
}
\end{verbatim}
\endgroup

But the access from the first to the last element is far more common in programs, and the range command needs to be consistent when the step is negative.

An alternative syntax for reverse-indexing is:
\begingroup\small\begin{verbatim}
foreach i [range [llength $mylist]] {
   foobar [lindex $mylist end-$i]
}
\end{verbatim}
\endgroup

\section{Proposed Change}

The change proposed is to modify the Tcl core in order to handle a new object type called ArithSeries, that is recongnized and handled as a special case by at least the \textbf{llength}, \textbf{lindex} and \textbf{foreach} commands. Syntactically, the ArithSeries object will have the string representation that is exactly that that would be produced by creating a list with the elements that would be iterated over by \textbf{foreach} as previously described. This TIP also proposes to add logic into \textit{SetListFromAny} method of the List type in order to convert an Arithmetic Series object into a List directly without to pass from the string representation.

This TIP proposes to add a \textbf{range} command to the Tcl core having the semantics specified above, and returning an Arithmetic Series object. Formally, the syntax is:

\begin{quote}
\textbf{range} ?\textit{start}? \textit{end} ?\textit{step}?
\end{quote}

The proposed changes are available as a Patch against HEAD that can be found in the SourceForge Tcl patch 1052584 [\url{http://sf.net/tracker/?func=detail&aid=1052584&group_id=10894&atid=310894}]

\section{Copyright}

This document has been placed in the public domain.

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

\section{Appendix: Reference Pure-Tcl Implementation}

It may be useful to test the behaviour of the \textbf{range} command without having to apply the Patch, so the following is a pure Tcl implementation that should be exactly equivalent in the semantic to the specification in this TIP, but of course not able to store ranges in O(1) space.
\begingroup\small\begin{verbatim}
# RangeLen(start, end, step)
# 1. if step = 0
# 2.     then ERROR
# 3. if start = end
# 4.     then return 0
# 5. if step > 0 AND start > end
# 6.     then ERROR
# 7. if setp < 0 AND end > start
# 8.     then ERROR
# 9. return 1+((ABS(end-start)-1)/ABS(step))
proc rangeLen {start end step} {
    if {$step == 0} {return -1}
    if {$start == $end} {return 0}
    if {$step > 0 && $start > $end} {return -1}
    if {$step < 0 && $end > $start} {return -1}
    expr {1+((abs($end-$start)-1)/abs($step))}
}

# Range(start, end, step)
# 1. result <- EMPTY LIST
# 2. len <- RangeLen(start, end, step)
# 3. for i <- 0 to len - 1
# 4.     result.append(start+(i*step))
# 6. return result
proc range args {
    # Check arity
    set l [llength $args]
    if {$l == 1} {
        set start 0
        set step 1
        set end [lindex $args 0]
    } elseif {$l == 2} {
        set step 1
        foreach {start end} $args break
    } elseif {$l == 3} {
        foreach {start end step} $args break
    } else {
        error {wrong # of args: should be "range ?start? end ?step?"}
    }

    # Generate the range
    set rlen [rangeLen $start $end $step]
    if {$rlen == -1} {
        error {invalid (infinite?) range specified}
    }
    set result {}
    for {set i 0} {$i < $rlen} {incr i} {
        lappend result [expr {$start+($i*$step)}]
    }
    return $result
}
\end{verbatim}
\endgroup

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

\section{Appendix: Discussion}

Does the TIP include a C-level api to ranges, or are they transparent also in C --- in the sense that they are addressable with any of the list-oriented functions of the Tcl api? What if any changes and caveats are necessary in the documentation of Tcl's C api? \textit{Miguel}

Ranges are transparent to C level too, in the proposed patch, because the logic is put inside the commands, so directly in the code implementing lindex, foreach, ... In all the other cases, when a SetListFromAny() call occurs the range is converted into a normal Tcl list object. \textit{Salvatore}

\section{Colophon}

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