1generator(n) Tcl Generator Commands generator(n)
2______________________________________________________________________________
6
8 generator - Procedures for creating and using generators.
9
11 package require Tcl 8.6
12 package require generator ?0.2?
14 generator define name params body
16 generator yield arg ?args..?
18 generator foreach varList generator varList generator ?...? body
20 generator next generator ?varName..?
22 generator exists generator
24 generator names
26 generator destroy ?generator..?
28 generator finally cmd ?arg..?
30 generator from format value
32 generator to format generator
34 generator map function generator
36 generator filter predicate generator
38 generator reduce function zero generator
40 generator foldl function zero generator
42 generator foldr function zero generator
44 generator all predicate generator
46 generator and generator
48 generator any generator
50 generator concat generator ?generator..?
52 generator concatMap function generator
54 generator drop n generator
56 generator dropWhile predicate generator
58 generator contains element generator
60 generator foldl1 function generator
62 generator foldli function zero generator
64 generator foldri function zero generator
66 generator head generator
68 generator tail generator
70 generator init generator
72 generator takeList n generator
74 generator take n generator
76 generator iterate function init
78 generator last generator
80 generator length generator
82 generator or predicate generator
84 generator product generator
86 generator repeat n value..
88 generator sum generator
90 generator takeWhile predicate generator
92 generator splitWhen predicate generator
94 generator scanl function zero generator
96______________________________________________________________________________
98
100 The generator package provides commands to define and iterate over gen‐
101 erator expressions. A generator is a command that returns a sequence of
102 values. However, unlike an ordinary command that returns a list, a gen‐
103 erator yields each value and then suspends, allowing subsequent values
104 to be fetched on-demand. As such, generators can be used to efficiently
105 iterate over a set of values, without having to generate all answers
106 in-memory. Generators can be used to iterate over elements of a data
107 structure, or rows in the result set of a database query, or to decou‐
108 ple producer/consumer software designs such as parsers and tokenizers,
109 or to implement sophisticated custom control strategies such as back‐
110 tracking search. Generators reduce the need to implement custom control
111 structures, as many such structures can be recast as generators, lead‐
112 ing to both a simpler implementation and a more standardised interface.
113 The generator mechanism is built on top of the Tcl 8.6 coroutine mecha‐
114 nism.
115 The package exports a single ensemble command, generator. All function‐
117 ality is provided as subcommands of this command. The core subcommands
118 of the package are define, yield, and foreach. The define command works
119 like Tcl's proc command, but creates a generator procedure; that is, a
120 procedure that returns a generator when called. The generator itself
121 is a command that can be called multiple times: each time it returns
122 the next value in the generated series. When the series has been ex‐
123 hausted, the generator command returns an empty list and then destroys
124 itself. Rather than manually call a generator, however, the package
125 also provides a flexible foreach command that loops through the values
126 of one or more generators. This loop construct mimicks the functional‐
127 ity of the built-in Tcl foreach command, including handling multiple
128 return values and looping over multiple generators at once. Writing a
129 generator is also a simple task, much like writing a normal procedure:
130 simply use the define command to define the generator, and then call
131 yield instead of return. For example, we can define a generator for
132 looping through the integers in a particular range:
133 generator define range {n m} {
135 for {set i $n} {$i <= $m} {incr i} { generator yield $i }
136 }
137 generator foreach x [range 1 10] {
138 puts "x = $x"
139 }
140 The above example will print the numbers from 1 to 10 in sequence, as
143 you would expect. The difference from a normal loop over a list is that
144 the numbers are only generated as they are needed. If we insert a break
145 into the loop then any remaining numbers in the sequence would never be
146 generated. To illustrate, we can define a generator that produces the
147 sequence of natural numbers: an infinite series. A normal procedure
148 would never return trying to produce this series as a list. By using a
149 generator we only have to generate those values which are actually
150 used:
151 generator define nats {} {
153 while 1 { generator yield [incr nat] }
154 }
155 generator foreach n [nats] {
156 if {$n > 100} { break }
157 }
158
161 generator define name params body
162 Creates a new generator procedure. The arguments to the command
163 are identical to those for proc: a name, a list of parameters,
164 and a body. The parameter list format is identical to a proce‐
165 dure. In particular, default values and the ?args? syntax can be
166 used as usual. Each time the resulting generator procedure is
167 called it creates a new generator command (coroutine) that will
168 yield a list of values on each call. Each result from a genera‐
169 tor is guaranteed to be a non-empty list of values. When a gen‐
170 erator is exhausted it returns an empty list and then destroys
171 itself to free up resources. It is an error to attempt to call
172 an exhausted generator as the command no longer exists.
173 generator yield arg ?args..?
175 Used in the definition of a generator, this command returns the
176 next set of values to the consumer. Once the yield command has
177 been called the generator will suspend to allow the consumer to
178 process that value. When the next value is requested, the gener‐
179 ator will resume as if the yield command had just returned, and
180 can continue processing to yield the next result. The yield com‐
181 mand must be called with at least one argument, but can be
182 called with multiple arguments, in which case this is equivalent
183 to calling yield once for each argument.
184 generator foreach varList generator varList generator ?...? body
186 Loops through one or more generators, assigning the next values
187 to variables and then executing the loop body. Works much like
188 the built-in foreach command, but working with generators rather
189 than lists. Multiple generators can be iterated over in paral‐
190 lel, and multiple results can be retrieved from a single genera‐
191 tor at once. Like the built-in foreach, the loop will continue
192 until all of the generators have been exhausted: variables for
193 generators that are exhausted early will be set to the empty
194 string.
195 The foreach command will automatically clean-up all of the gen‐
197 erators at the end of the loop, regardless of whether the loop
198 terminated early or not. This behaviour is provided as a conve‐
199 nience to avoid having to explicitly clean up a generator in the
200 usual cases. Generators can however be destroyed before the end
201 of the loop, in which case the loop will continue as normal un‐
202 til all the other generators have been destroyed or exhausted.
203 The foreach command does not take a snapshot of the generator.
205 Any changes in the state of the generator made inside the loop
206 or by other code will affect the state of the loop. In particu‐
207 lar, if the code in the loop invokes the generator to manually
208 retrieve the next element, this element will then be excluded
209 from the loop, and the next iteration will continue from the el‐
210 ement after that one. Care should be taken to avoid concurrent
211 updates to generators unless this behaviour is required (e.g.,
212 in argument processing).
213 generator next generator ?varName..?
215 Manually retrieves the next values from a generator. One value
216 is retrieved for each variable supplied and assigned to the cor‐
217 responding variable. If the generator becomes exhausted at any
218 time then any remaining variables are set to the empty string.
219 generator exists generator
221 Returns 1 if the generator (still) exists, or 0 otherwise.
222 generator names
224 Returns a list of all currently existing generator commands.
225 generator destroy ?generator..?
227 Destroys one or more generators, freeing any associated re‐
228 sources.
229 generator finally cmd ?arg..?
231 Used in the definition of a generator procedure, this command
232 arranges for a resource to be cleaned up whenever the generator
233 is destroyed, either explicitly or implicitly when the generator
234 is exhausted. This command can be used like a finally block in
235 the try command, except that it is tied to the life-cycle of the
236 generator rather than to a particular scope. For example, if we
237 create a generator to iterate over the lines in a text file, we
238 can use finally to ensure that the file is closed whenever the
239 generator is destroyed:
240 generator define lines file {
244 set in [open $file]
245 # Ensure file is always closed
246 generator finally close $in
247 while {[gets $in line] >= 0} {
248 generator yield $line
249 }
250 }
251 generator foreach line [lines /etc/passwd] {
252 puts "[incr count]: $line"
253 if {$count > 10} { break }
254 }
255 # File will be closed even on early exit
256 If you create a generator that consumes another generator (such as the
259 standard map and filter generators defined later), then you should use
260 a finally command to ensure that this generator is destroyed when its
261 parent is. For example, the map generator is defined as follows:
262 generator define map {f xs} {
266 generator finally generator destroy $xs
267 generator foreach x $xs { generator yield [{*}$f $x] }
268 }
269 generator from format value
272 Creates a generator from a data structure. Currently, supported
273 formats are list, dict, or string. The list format yields each
274 element in turn. For dictionaries, each key and value are
275 yielded separately. Finally, strings are yielded a character at
276 a time.
277 generator to format generator
279 Converts a generator into a data structure. This is the reverse
280 operation of the from command, and supports the same data struc‐
281 tures. The two operations obey the following identity laws
282 (where = is interpreted appropriately):
283 [generator to $fmt [generator from $fmt $value]] = $value
287 [generator from $fmt [generator to $fmt $gen]] = $gen
288
292 The following commands are provided as a standard library of generator
293 combinators and functions that perform convenience operations on gener‐
294 ators. The functions in this section are loosely modelled on the equiv‐
295 alent functions from the Haskell Prelude. Warning: most of the func‐
296 tions in this prelude destroy any generator arguments they are passed
297 as a side-effect. If you want to have persistent generators, see the
298 streams library.
299 generator map function generator
301 Apply a function to every element of a generator, returning a
302 new generator of the results. This is the classic map function
303 from functional programming, applied to generators. For example,
304 we can generate all the square numbers using the following code
305 (where nats is defined as earlier):
306 proc square x { expr {$x * $x} }
310 generator foreach n [generator map square [nats]] {
311 puts "n = $n"
312 if {$n > 1000} { break }
313 }
314 generator filter predicate generator
317 Another classic functional programming gem. This command returns
318 a generator that yields only those items from the argument gen‐
319 erator that satisfy the predicate (boolean function). For exam‐
320 ple, if we had a generator employees that returned a stream of
321 dictionaries representing people, we could filter all those
322 whose salaries are above 100,000 dollars (or whichever currency
323 you prefer) using a simple filter:
324 proc salary> {amount person} { expr {[dict get $person salary] > $amount} }
328 set fat-cats [generator filter {salary> 100000} $employees]
329 generator reduce function zero generator
332 This is the classic left-fold operation. This command takes a
333 function, an initial value, and a generator of values. For each
334 element in the generator it applies the function to the current
335 accumulator value (the zero argument initially) and that ele‐
336 ment, and then uses the result as the new accumulator value.
337 This process is repeated through the entire generator (eagerly)
338 and the final accumulator value is then returned. If we consider
339 the function to be a binary operator, and the zero argument to
340 be the left identity element of that operation, then we can con‐
341 sider the reduce command as folding the operator between each
342 successive pair of values in the generator in a left-associative
343 fashion. For example, the sum of a sequence of numbers can be
344 calculated by folding a + operator between them, with 0 as the
345 identity:
346 # sum xs = reduce + 0 xs
350 # sum [range 1 5] = reduce + 0 [range 1 5]
351 # = reduce + [+ 0 1] [range 2 5]
352 # = reduce + [+ 1 2] [range 3 5]
353 # = ...
354 # = reduce + [+ 10 5] <empty>
355 # = ((((0+1)+2)+3)+4)+5
356 # = 15
357 proc + {a b} { expr {$a + $b} }
358 proc sum gen { generator reduce + 0 $gen }
359 puts [sum [range 1 10]]
360 The reduce operation is an extremely useful one, and a great variety of
363 different operations can be defined using it. For example, we can de‐
364 fine a factorial function as the product of a range using generators.
365 This definition is both very clear and also quite efficient (in both
366 memory and running time):
367 proc * {x y} { expr {$x * $y} }
371 proc prod gen { generator reduce * 0 $gen }
372 proc fac n { prod [range 1 $n] }
373 However, while the reduce operation is efficient for finite generators,
376 care should be taken not to apply it to an infinite generator, as this
377 will result in an infinite loop:
378 sum [nats]; # Never returns
382 generator foldl function zero generator
385 This is an alias for the reduce command.
386 generator foldr function zero generator
388 This is the right-associative version of reduce. This operation
389 is generally inefficient, as the entire generator needs to be
390 evaluated into memory (as a list) before the reduction can com‐
391 mence. In an eagerly evaluated language like Tcl, this operation
392 has limited use, and should be avoided if possible.
393 generator all predicate generator
395 Returns true if all elements of the generator satisfy the given
396 predicate.
397 generator and generator
399 Returns true if all elements of the generator are true (i.e.,
400 takes the logical conjunction of the elements).
401 generator any generator
403 Returns true if any of the elements of the generator are true
404 (i.e., logical disjunction).
405 generator concat generator ?generator..?
407 Returns a generator which is the concatenation of each of the
408 argument generators.
409 generator concatMap function generator
411 Given a function which maps a value to a series of values, and a
412 generator of values of that type, returns a generator of all of
413 the results in one flat series. Equivalent to concat applied to
414 the result of map.
415 generator drop n generator
417 Removes the given number of elements from the front of the gen‐
418 erator and returns the resulting generator with those elements
419 removed.
420 generator dropWhile predicate generator
422 Removes all elements from the front of the generator that sat‐
423 isfy the predicate.
424 generator contains element generator
426 Returns true if the generator contains the given element. Note
427 that this will destroy the generator!
428 generator foldl1 function generator
430 A version of foldl that takes the zero argument from the first
431 element of the generator. Therefore this function is only valid
432 on non-empty generators.
433 generator foldli function zero generator
435 A version of foldl that supplies the integer index of each ele‐
436 ment as the first argument to the function. The first element in
437 the generator at this point is given index 0.
438 generator foldri function zero generator
440 Right-associative version of foldli.
441 generator head generator
443 Returns the first element of the generator.
444 generator tail generator
446 Removes the first element of the generator, returning the rest.
447 generator init generator
449 Returns a new generator consisting of all elements except the
450 last of the argument generator.
451 generator takeList n generator
453 Returns the next n elements of the generator as a list. If not
454 enough elements are left in the generator, then just the remain‐
455 ing elements are returned.
456 generator take n generator
458 Returns the next n elements of the generator as a new generator.
459 The old generator is destroyed.
460 generator iterate function init
462 Returns an infinite generator formed by repeatedly applying the
463 function to the initial argument. For example, the Fibonacci
464 numbers can be defined as follows:
465 proc fst pair { lindex $pair 0 }
469 proc snd pair { lindex $pair 1 }
470 proc nextFib ab { list [snd $ab] [expr {[fst $ab] + [snd $ab]}] }
471 proc fibs {} { generator map fst [generator iterate nextFib {0 1}] }
472 generator last generator
475 Returns the last element of the generator (if it exists).
476 generator length generator
478 Returns the length of the generator, destroying it in the
479 process.
480 generator or predicate generator
482 Returns 1 if any of the elements of the generator satisfy the
483 predicate.
484 generator product generator
486 Returns the product of the numbers in a generator.
487 generator repeat n value..
489 Returns a generator that consists of n copies of the given ele‐
490 ments. The special value Inf can be used to generate an infinite
491 sequence.
492 generator sum generator
494 Returns the sum of the values in the generator.
495 generator takeWhile predicate generator
497 Returns a generator of the first elements in the argument gener‐
498 ator that satisfy the predicate.
499 generator splitWhen predicate generator
501 Splits the generator into lists of elements using the predicate
502 to identify delimiters. The resulting lists are returned as a
503 generator. Elements matching the delimiter predicate are dis‐
504 carded. For example, to split up a generator using the string
505 "|" as a delimiter:
506 set xs [generator from list {a | b | c}]
510 generator split {string equal "|"} $xs ;# returns a then b then c
511 generator scanl function zero generator
514 Similar to foldl, but returns a generator of all of the interme‐
515 diate values for the accumulator argument. The final element of
516 this generator is equivalent to foldl called on the same argu‐
517 ments.
518
520 Please report any errors in this document, or in the package it de‐
521 scribes, to Neil Madden [mailto:nem@cs.nott.ac.uk].
522
524 control structure, coroutine, filter, foldl, foldr, foreach, generator,
525 iterator, map, reduce, scanl
526tcllib 0.2 generator(n)