TIP #225: Arithmetic Series with Optimized Space Complexity

Abstract

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 range.

Rationale

An idiomatic way to assign successive elements of an arithmetic series to a variable is to use the 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 incr. The for test condition is used to limit the sequence generation to a given element, like in the following example:

for {set i 0} {$i < 10} {incr i} {
    puts $i
}

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 foreach command to loop over every element, so that the above for loop can be translated into the following fragment of code:

foreach i [range 0 10] {
    puts $i
}

The range command can be also conveniently used in different contexts. The following code generates a list of squares of 0, 1, 2, 3, ... 9.

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"

The 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 foreach, llength and lindex commands (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.

Specification of the Behaviour

The range command takes three arguments in the complete format, named start, end and step, and generates a sequence of integers accordingly to the following algorithm in pseudo code:

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

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

range 0 10 1
range 0 10
range 10

The following are examples of outputs.

[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

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. start, end, and 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 [range 0 10 1] generating the sequence 0, 1, 2, ..., 9 and a range with the same value of start and end always generating an emtpy list. This is needed in order to make it comfortable to use range and foreach instead of for loops like in the following example:

foreach i [range [llength $mylist]] {
    foobar [lindex $mylist $i]
}

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 for loops.)

Unfortunately this behaviour is not as comfortable to run the indexes in reverse order:

foreach i [range [expr {[llength $mylist]-1}] -1 -1] {
    foobar [lindex $mylist $i]
}

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:

foreach i [range [llength $mylist]] {
   foobar [lindex $mylist end-$i]
}

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 llength, lindex and 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 foreach as previously described. This TIP also proposes to add logic into 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 range command to the Tcl core having the semantics specified above, and returning an Arithmetic Series object. Formally, the syntax is:

range ?start? end ?step?

The proposed changes are available as a Patch against HEAD that can be found in the SourceForge Tcl patch 1052584 [1]

Copyright

This document has been placed in the public domain.

Appendix: Reference Pure-Tcl Implementation

It may be useful to test the behaviour of the 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.

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

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? 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. Salvatore

[Index] [History] [HTML Format] [Source Format] [LaTeX Format] [Text Format] [XML Format] [*roff Format (experimental)] [RTF Format (experimental)]