generator(3tcl) Tcl Generator Commands generator(3tcl)
______________________________________________________________________________
NAME
generator - Procedures for creating and using generators.
SYNOPSIS
package require Tcl 8.6
package require generator ?0.1?
generator define name params body
generator yield arg ?args..?
generator foreach varList generator varList generator ?...? body
generator next generator ?varName..?
generator exists generator
generator names
generator destroy ?generator..?
generator finally cmd ?arg..?
generator from format value
generator to format generator
generator map function generator
generator filter predicate generator
generator reduce function zero generator
generator foldl function zero generator
generator foldr function zero generator
generator all predicate generator
generator and generator
generator any generator
generator concat generator ?generator..?
generator concatMap function generator
generator drop n generator
generator dropWhile predicate generator
generator contains element generator
generator foldl1 function generator
generator foldli function zero generator
generator foldri function zero generator
generator head generator
generator tail generator
generator init generator
generator takeList n generator
generator take n generator
generator iterate function init
generator last generator
generator length generator
generator or predicate generator
generator product generator
generator repeat n value..
generator sum generator
generator takeWhile predicate generator
generator splitWhen predicate generator
generator scanl function zero generator
______________________________________________________________________________
DESCRIPTION
The generator package provides commands to define and iterate over gen-
erator expressions. A generator is a command that returns a sequence of
values. However, unlike an ordinary command that returns a list, a gen-
erator yields each value and then suspends, allowing subsequent values
to be fetched on-demand. As such, generators can be used to efficiently
iterate over a set of values, without having to generate all answers
in-memory. Generators can be used to iterate over elements of a data
structure, or rows in the result set of a database query, or to decou-
ple producer/consumer software designs such as parsers and tokenizers,
or to implement sophisticated custom control strategies such as back-
tracking search. Generators reduce the need to implement custom control
structures, as many such structures can be recast as generators, lead-
ing to both a simpler implementation and a more standardised interface.
The generator mechanism is built on top of the Tcl 8.6 coroutine mecha-
nism.
The package exports a single ensemble command, generator. All function-
ality is provided as subcommands of this command. The core subcommands
of the package are define, yield, and foreach. The define command works
like Tcl's proc command, but creates a generator procedure; that is, a
procedure that returns a generator when called. The generator itself
is a command that can be called multiple times: each time it returns
the next value in the generated series. When the series has been ex-
hausted, the generator command returns an empty list and then destroys
itself. Rather than manually call a generator, however, the package
also provides a flexible foreach command that loops through the values
of one or more generators. This loop construct mimicks the functional-
ity of the built-in Tcl foreach command, including handling multiple
return values and looping over multiple generators at once. Writing a
generator is also a simple task, much like writing a normal procedure:
simply use the define command to define the generator, and then call
yield instead of return. For example, we can define a generator for
looping through the integers in a particular range:
generator define range {n m} {
for {set i $n} {$i <= $m} {incr i} { generator yield $i }
}
generator foreach x [range 1 10] {
puts "x = $x"
}
The above example will print the numbers from 1 to 10 in sequence, as
you would expect. The difference from a normal loop over a list is that
the numbers are only generated as they are needed. If we insert a break
into the loop then any remaining numbers in the sequence would never be
generated. To illustrate, we can define a generator that produces the
sequence of natural numbers: an infinite series. A normal procedure
would never return trying to produce this series as a list. By using a
generator we only have to generate those values which are actually
used:
generator define nats {} {
while 1 { generator yield [incr nat] }
}
generator foreach n [nats] {
if {$n > 100} { break }
}
COMMANDS
generator define name params body
Creates a new generator procedure. The arguments to the command
are identical to those for proc: a name, a list of parameters,
and a body. The parameter list format is identical to a proce-
dure. In particular, default values and the ?args? syntax can be
used as usual. Each time the resulting generator procedure is
called it creates a new generator command (coroutine) that will
yield a list of values on each call. Each result from a genera-
tor is guaranteed to be a non-empty list of values. When a gen-
erator is exhausted it returns an empty list and then destroys
itself to free up resources. It is an error to attempt to call
an exhausted generator as the command no longer exists.
generator yield arg ?args..?
Used in the definition of a generator, this command returns the
next set of values to the consumer. Once the yield command has
been called the generator will suspend to allow the consumer to
process that value. When the next value is requested, the gener-
ator will resume as if the yield command had just returned, and
can continue processing to yield the next result. The yield com-
mand must be called with at least one argument, but can be
called with multiple arguments, in which case this is equivalent
to calling yield once for each argument.
generator foreach varList generator varList generator ?...? body
Loops through one or more generators, assigning the next values
to variables and then executing the loop body. Works much like
the built-in foreach command, but working with generators rather
than lists. Multiple generators can be iterated over in paral-
lel, and multiple results can be retrieved from a single genera-
tor at once. Like the built-in foreach, the loop will continue
until all of the generators have been exhausted: variables for
generators that are exhausted early will be set to the empty
string.
The foreach command will automatically clean-up all of the gen-
erators at the end of the loop, regardless of whether the loop
terminated early or not. This behaviour is provided as a conve-
nience to avoid having to explicitly clean up a generator in the
usual cases. Generators can however be destroyed before the end
of the loop, in which case the loop will continue as normal un-
til all the other generators have been destroyed or exhausted.
The foreach command does not take a snapshot of the generator.
Any changes in the state of the generator made inside the loop
or by other code will affect the state of the loop. In particu-
lar, if the code in the loop invokes the generator to manually
retrieve the next element, this element will then be excluded
from the loop, and the next iteration will continue from the el-
ement after that one. Care should be taken to avoid concurrent
updates to generators unless this behaviour is required (e.g.,
in argument processing).
generator next generator ?varName..?
Manually retrieves the next values from a generator. One value
is retrieved for each variable supplied and assigned to the cor-
responding variable. If the generator becomes exhausted at any
time then any remaining variables are set to the empty string.
generator exists generator
Returns 1 if the generator (still) exists, or 0 otherwise.
generator names
Returns a list of all currently existing generator commands.
generator destroy ?generator..?
Destroys one or more generators, freeing any associated re-
sources.
generator finally cmd ?arg..?
Used in the definition of a generator procedure, this command
arranges for a resource to be cleaned up whenever the generator
is destroyed, either explicitly or implicitly when the generator
is exhausted. This command can be used like a finally block in
the try command, except that it is tied to the life-cycle of the
generator rather than to a particular scope. For example, if we
create a generator to iterate over the lines in a text file, we
can use finally to ensure that the file is closed whenever the
generator is destroyed:
generator define lines file {
set in [open $file]
# Ensure file is always closed
generator finally close $in
while {[gets $in line] >= 0} {
generator yield $line
}
}
generator foreach line [lines /etc/passwd] {
puts "[incr count]: $line"
if {$count > 10} { break }
}
# File will be closed even on early exit
If you create a generator that consumes another generator (such as the
standard map and filter generators defined later), then you should use
a finally command to ensure that this generator is destroyed when its
parent is. For example, the map generator is defined as follows:
generator define map {f xs} {
generator finally generator destroy $xs
generator foreach x $xs { generator yield [{*}$f $x] }
}
generator from format value
Creates a generator from a data structure. Currently, supported
formats are list, dict, or string. The list format yields each
element in turn. For dictionaries, each key and value are
yielded separately. Finally, strings are yielded a character at
a time.
generator to format generator
Converts a generator into a data structure. This is the reverse
operation of the from command, and supports the same data struc-
tures. The two operations obey the following identity laws
(where = is interpreted appropriately):
[generator to $fmt [generator from $fmt $value]] = $value
[generator from $fmt [generator to $fmt $gen]] = $gen
PRELUDE
The following commands are provided as a standard library of generator
combinators and functions that perform convenience operations on gener-
ators. The functions in this section are loosely modelled on the equiv-
alent functions from the Haskell Prelude. Warning: most of the func-
tions in this prelude destroy any generator arguments they are passed
as a side-effect. If you want to have persistent generators, see the
streams library.
generator map function generator
Apply a function to every element of a generator, returning a
new generator of the results. This is the classic map function
from functional programming, applied to generators. For example,
we can generate all the square numbers using the following code
(where nats is defined as earlier):
proc square x { expr {$x * $x} }
generator foreach n [generator map square [nats]] {
puts "n = $n"
if {$n > 1000} { break }
}
generator filter predicate generator
Another classic functional programming gem. This command returns
a generator that yields only those items from the argument gen-
erator that satisfy the predicate (boolean function). For exam-
ple, if we had a generator employees that returned a stream of
dictionaries representing people, we could filter all those
whose salaries are above 100,000 dollars (or whichever currency
you prefer) using a simple filter:
proc salary> {amount person} { expr {[dict get $person salary] > $amount} }
set fat-cats [generator filter {salary> 100000} $employees]
generator reduce function zero generator
This is the classic left-fold operation. This command takes a
function, an initial value, and a generator of values. For each
element in the generator it applies the function to the current
accumulator value (the zero argument initially) and that ele-
ment, and then uses the result as the new accumulator value.
This process is repeated through the entire generator (eagerly)
and the final accumulator value is then returned. If we consider
the function to be a binary operator, and the zero argument to
be the left identity element of that operation, then we can con-
sider the reduce command as folding the operator between each
successive pair of values in the generator in a left-associative
fashion. For example, the sum of a sequence of numbers can be
calculated by folding a + operator between them, with 0 as the
identity:
# sum xs = reduce + 0 xs
# sum [range 1 5] = reduce + 0 [range 1 5]
# = reduce + [+ 0 1] [range 2 5]
# = reduce + [+ 1 2] [range 3 5]
# = ...
# = reduce + [+ 10 5] <empty>
# = ((((0+1)+2)+3)+4)+5
# = 15
proc + {a b} { expr {$a + $b} }
proc sum gen { generator reduce + 0 $gen }
puts [sum [range 1 10]]
The reduce operation is an extremely useful one, and a great variety of
different operations can be defined using it. For example, we can de-
fine a factorial function as the product of a range using generators.
This definition is both very clear and also quite efficient (in both
memory and running time):
proc * {x y} { expr {$x * $y} }
proc prod gen { generator reduce * 0 $gen }
proc fac n { prod [range 1 $n] }
However, while the reduce operation is efficient for finite generators,
care should be taken not to apply it to an infinite generator, as this
will result in an infinite loop:
sum [nats]; # Never returns
generator foldl function zero generator
This is an alias for the reduce command.
generator foldr function zero generator
This is the right-associative version of reduce. This operation
is generally inefficient, as the entire generator needs to be
evaluated into memory (as a list) before the reduction can com-
mence. In an eagerly evaluated language like Tcl, this operation
has limited use, and should be avoided if possible.
generator all predicate generator
Returns true if all elements of the generator satisfy the given
predicate.
generator and generator
Returns true if all elements of the generator are true (i.e.,
takes the logical conjunction of the elements).
generator any generator
Returns true if any of the elements of the generator are true
(i.e., logical disjunction).
generator concat generator ?generator..?
Returns a generator which is the concatenation of each of the
argument generators.
generator concatMap function generator
Given a function which maps a value to a series of values, and a
generator of values of that type, returns a generator of all of
the results in one flat series. Equivalent to concat applied to
the result of map.
generator drop n generator
Removes the given number of elements from the front of the gen-
erator and returns the resulting generator with those elements
removed.
generator dropWhile predicate generator
Removes all elements from the front of the generator that sat-
isfy the predicate.
generator contains element generator
Returns true if the generator contains the given element. Note
that this will destroy the generator!
generator foldl1 function generator
A version of foldl that takes the zero argument from the first
element of the generator. Therefore this function is only valid
on non-empty generators.
generator foldli function zero generator
A version of foldl that supplies the integer index of each ele-
ment as the first argument to the function. The first element in
the generator at this point is given index 0.
generator foldri function zero generator
Right-associative version of foldli.
generator head generator
Returns the first element of the generator.
generator tail generator
Removes the first element of the generator, returning the rest.
generator init generator
Returns a new generator consisting of all elements except the
last of the argument generator.
generator takeList n generator
Returns the next n elements of the generator as a list. If not
enough elements are left in the generator, then just the remain-
ing elements are returned.
generator take n generator
Returns the next n elements of the generator as a new generator.
The old generator is destroyed.
generator iterate function init
Returns an infinite generator formed by repeatedly applying the
function to the initial argument. For example, the Fibonacci
numbers can be defined as follows:
proc fst pair { lindex $pair 0 }
proc snd pair { lindex $pair 1 }
proc nextFib ab { list [snd $ab] [expr {[fst $ab] + [snd $ab]}] }
proc fibs {} { generator map fst [generator iterate nextFib {0 1}] }
generator last generator
Returns the last element of the generator (if it exists).
generator length generator
Returns the length of the generator, destroying it in the
process.
generator or predicate generator
Returns 1 if any of the elements of the generator satisfy the
predicate.
generator product generator
Returns the product of the numbers in a generator.
generator repeat n value..
Returns a generator that consists of n copies of the given ele-
ments. The special value Inf can be used to generate an infinite
sequence.
generator sum generator
Returns the sum of the values in the generator.
generator takeWhile predicate generator
Returns a generator of the first elements in the argument gener-
ator that satisfy the predicate.
generator splitWhen predicate generator
Splits the generator into lists of elements using the predicate
to identify delimiters. The resulting lists are returned as a
generator. Elements matching the delimiter predicate are dis-
carded. For example, to split up a generator using the string
"|" as a delimiter:
set xs [generator from list {a | b | c}]
generator split {string equal "|"} $xs ;# returns a then b then c
generator scanl function zero generator
Similar to foldl, but returns a generator of all of the interme-
diate values for the accumulator argument. The final element of
this generator is equivalent to foldl called on the same argu-
ments.
BUGS, IDEAS, FEEDBACK
Please report any errors in this document, or in the package it de-
scribes, to Neil Madden [mailto:nem@cs.nott.ac.uk].
KEYWORDS
control structure, coroutine, filter, foldl, foldr, foreach, generator,
iterator, map, reduce, scanl
tcllib 0.1 generator(3tcl)