Looking at LISP's SERIES extension

Arjen Markus Inspired by a message from Andreas Kupries, regarding a macro package available for Common LISP, I wrote the script below. But let's start with the description of SERIES:

The original package http://lambda-the-ultimate.org/node/1451

The benefits of programming in a functional style are well known. In particular, algorithms that are expressed as compositions of functions operating on series/vectors/streams of data elements are much easier to understand and modify than equivalent algorithms expressed as loops. Unfortunately, many programmers hesitate to use series expressions. In part, this is due to the fact that series expressions are typically implemented very inefficiently.

A Common Lisp macro package (called Series) has been implemented that can evaluate a wide class of series expressions very efficiently by transforming them into iterative loops. When using this class of series expressions, programmers can obtain the advantages of expressing computations as series expressions without incurring any run-time overhead.

http://series.sourceforge.net/

My translation into Tcl

Reading the documentation on SERIES, I started off with what they call scanners. The script below presents Tcl procedures that create a "series". For the sake of this page: a series is a procedure that returns the next value in an (in principle) endless series of values.

Currently they have two subcommands:

  • next: return the next value
  • restart: start from the beginning

I have implemented two kinds:

  • simple arithmetic progressions, like 1, 3, 5, 7, 9, 11, ... or 1, 3, 5, 1, 3, 5, ...
  • function-based series, like the Fibonaci series

This is a first attempt only - ideas are welcome.


 # rangefunc.tcl --
 #     Provide procedures that can return sequences of numbers (ranges,
 #     Fibonaci numbers ...) in a lazy way
 #

 namespace eval ::Series {
     variable privcnt 0
 }

 # make-range --
 #     Make a range procedure
 # Arguments:
 #     start       Starting value
 #     end         End value (if empty: infinite; defaults to {})
 #     step        Step to take (defaults to 1)
 # Returns:
 #     Name of the new procedure
 #
 proc ::Series::make-range {start {end {}} {step 1}} {
     variable privcnt
     interp alias {} ::Series::RANGE$privcnt {} ::Series::RANGE ::Series::RANGE$privcnt $start $end $step $start

     set prev $privcnt
     incr privcnt

     return ::Series::RANGE$prev
 }

 # RANGE --
 #     Private procedure implementing a range
 # Arguments:
 #     alias       Alias for this range command
 #     start       Starting value
 #     end         End value (if empty: infinite; defaults to {})
 #     step        Step to take (defaults to 1)
 #     current     Current value
 #     cmd         Command (subrange, next, restart)
 # Returns:
 #     Value or a list of values
 #
 proc ::Series::RANGE {alias start end step current cmd} {

     switch -- $cmd {
     "next" {
         set next [expr {$current+$step}]
         if { $end != {} } {
             if { $step > 0 && $next > $end } {
                 set next $start
             }
             if { $step < 0 && $next < $end } {
                 set next $start
             }
         }
         interp alias {} $alias {} ::Series::RANGE $alias $start $end $step $next
         return $current
     }
     "restart" {
         interp alias {} $alias {} ::Series::RANGE $alias $start $end $step $step
     }
     default {
         return -code error "Unknown subcommand: $cmd"
     }
     }
 }

 # make-fct-series --
 #     Make a procedure that generates a series via a function
 # Arguments:
 #     fct         Function to be invoked
 #     first       First number
 #     values      List of values with which to generate the second number
 # Returns:
 #     Name of the new procedure
 # Note:
 #     fct is the name of a function that behaves thus:
 #     - It accepts a list of values with which it can determine the _next_ value
 #     - It returns a list of two elements, the first is the new value
 #       and the second is the list of values for the next entry in the
 #       series
 #     See fibonaci for a simple example
 #
 proc ::Series::make-fct-series {fct first values} {
     variable privcnt
     interp alias {} ::Series::FCT$privcnt {} ::Series::FCT ::Series::FCT$privcnt $fct $first $values $values $first

     set prev $privcnt
     incr privcnt

     return ::Series::FCT$prev
 }

 # FCT --
 #     Private procedure implementing a series determined by a function
 # Arguments:
 #     alias       Alias for this range command
 #     fct         Name of the function to invoke
 #     firstvalue  First value in the series
 #     initvalues  Initial arguments to the function for determining the first value
 #     values      Arguments to the function for determining the next value
 #     current     Current value
 #     cmd         Command (subrange, next, restart)
 # Returns:
 #     Value or a list of values
 #
 proc ::Series::FCT {alias fct firstvalue initvalues values current cmd} {

     switch -- $cmd {
     "next" {
         foreach {next newvalues} [$fct $values] break
         interp alias {} $alias {} ::Series::FCT $alias $fct $firstvalue $initvalues $newvalues $next
         return $current
     }
     "restart" {
         interp alias {} $alias {} ::Series::FCT $alias $fct $firstvalue $initvalues $initvalues $firstvalue
     }
     default {
         return -code error "Unknown subcommand: $cmd"
     }
     }
 }

 # fibonaci --
 #     Sample procedure to generate a series of numbers
 # Arguments:
 #     values      Arguments to the function for determining the next value
 # Returns:
 #     List of two elements, the next value and the list of arguments for
 #     determining the value after that
 #
 proc fibonaci {values} {

     foreach {first second} $values break

     set next [expr {$first+$second}]
     return [list $next [list $second $next]]
 }

 # main --
 #     Testing what we have sofar
 #

 set r [::Series::make-range 0 {} 1]
 set x [$r next]
 while { $x < 10 } {
     puts $x
     set x [$r next]
 }
 puts "Restarting ..."
 $r restart
 puts [$r next]

 puts "New range"
 set r [::Series::make-range 0 10 2]
 set x [$r next]
 set c 0
 while { $c < 10 } {
     puts $x
     set x [$r next]
     incr c
 }

 puts "Now somewhat adacious: Fibonaci series"
 #
 # Note: the start is somewhat different than usual - we want to capture
 # the first value too
 #
 set f [::Series::make-fct-series fibonaci 1 {0 1}]

 set c 0
 while { $c < 30 } {
     puts -nonewline "[$f next] "
     incr c
     if { $c == 10 } {
         puts "\nRestart ..."
         $f restart
     }
 }

See also iterators, generators.

iu2 - You might find interesting Python's addictive syntax for generators [2 ] and the itertools library [1 ]


[ Category Language ]