TIP #225: Arithmetic Series with Optimized Space Complexity

• Previous message: Pat Thoyts: "ANNOUNCE: tclstorage and stgvfs"
• Next in thread: Andreas Leitgeb: "Re: TIP #225: Arithmetic Series with Optimized Space Complexity"
• Reply: Andreas Leitgeb: "Re: TIP #225: Arithmetic Series with Optimized Space Complexity"
• Reply: Frank Pilhofer: "Re: TIP #225: Arithmetic Series with Optimized Space Complexity"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Tue, 26 Oct 2004 00:44:12 +0000 (UTC)

 TIP #225: ARITHMETIC SERIES WITH OPTIMIZED SPACE COMPLEXITY
=============================================================
 Version: $Revision: 1.1 $
 Author: Salvatore Sanfilippo <antirez_at_invece.org>
 State: Draft
 Type: Project
 Tcl-Version: 8.5
 Vote: Pending
 Created: Monday, 25 October 2004
 URL: http://purl.org/tcl/tip/225.html
 WebEdit: http://purl.org/tcl/tip/edit/225
 Post-History:

-------------------------------------------------------------------------

 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 /step/ 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
 [<URL:http://sf.net/tracker/?func=detail&aid=1052584&group_id=10894&atid=310894>]

 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
   }

-------------------------------------------------------------------------

 TIP AutoGenerator - written by Donal K. Fellows

[[Send Tcl/Tk announcements to tcl-announce@mitchell.org
  Announcements archived at http://groups.yahoo.com/group/tcl_announce/
  Send administrivia to tcl-announce-request@mitchell.org
  Tcl/Tk at http://tcl.tk/ ]]

• Previous message: Pat Thoyts: "ANNOUNCE: tclstorage and stgvfs"
• Next in thread: Andreas Leitgeb: "Re: TIP #225: Arithmetic Series with Optimized Space Complexity"
• Reply: Andreas Leitgeb: "Re: TIP #225: Arithmetic Series with Optimized Space Complexity"
• Reply: Frank Pilhofer: "Re: TIP #225: Arithmetic Series with Optimized Space Complexity"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]