1generator(n)                Tcl Generator Commands                generator(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       generator - Procedures for creating and using generators.
9

SYNOPSIS

11       package require Tcl  8.6
12
13       package require generator  ?0.1?
14
15       generator define name params body
16
17       generator yield arg ?args..?
18
19       generator foreach varList generator varList generator ?...? body
20
21       generator next generator ?varName..?
22
23       generator exists generator
24
25       generator names
26
27       generator destroy ?generator..?
28
29       generator finally cmd ?arg..?
30
31       generator from format value
32
33       generator to format generator
34
35       generator map function generator
36
37       generator filter predicate generator
38
39       generator reduce function zero generator
40
41       generator foldl function zero generator
42
43       generator foldr function zero generator
44
45       generator all predicate generator
46
47       generator and generator
48
49       generator any generator
50
51       generator concat generator ?generator..?
52
53       generator concatMap function generator
54
55       generator drop n generator
56
57       generator dropWhile predicate generator
58
59       generator contains element generator
60
61       generator foldl1 function generator
62
63       generator foldli function zero generator
64
65       generator foldri function zero generator
66
67       generator head generator
68
69       generator tail generator
70
71       generator init generator
72
73       generator takeList n generator
74
75       generator take n generator
76
77       generator iterate function init
78
79       generator last generator
80
81       generator length generator
82
83       generator or predicate generator
84
85       generator product generator
86
87       generator repeat n value..
88
89       generator sum generator
90
91       generator takeWhile predicate generator
92
93       generator splitWhen predicate generator
94
95       generator scanl function zero generator
96
97______________________________________________________________________________
98

DESCRIPTION

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
116       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
123       exhausted, the  generator  command  returns  an  empty  list  and  then
124       destroys  itself.  Rather  than manually call a generator, however, the
125       package also provides a flexible foreach command that loops through the
126       values of one or more generators. This loop construct mimicks the func‐
127       tionality of the built-in Tcl foreach command, including handling  mul‐
128       tiple return values and looping over multiple generators at once. Writ‐
129       ing a generator is also a simple task, much like writing a normal  pro‐
130       cedure: simply use the define command to define the generator, and then
131       call yield instead of return.  For example, we can define  a  generator
132       for looping through the integers in a particular range:
133
134                  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
141
142       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
152                  generator define nats {} {
153                      while 1 { generator yield [incr nat] }
154                  }
155                  generator foreach n [nats] {
156                      if {$n > 100} { break }
157                  }
158
159

COMMANDS

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
174       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
185       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
196              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
202              until all the other generators have been destroyed or exhausted.
203
204              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
210              element 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
214       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
220       generator exists generator
221              Returns 1 if the generator (still) exists, or 0 otherwise.
222
223       generator names
224              Returns a list of all currently existing generator commands.
225
226       generator destroy ?generator..?
227              Destroys  one  or  more  generators,  freeing   any   associated
228              resources.
229
230       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
241
242
243                  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
257
258       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
263
264
265                  generator define map {f xs} {
266                      generator finally generator destroy $xs
267                      generator foreach x $xs { generator yield [{*}$f $x] }
268                  }
269
270
271       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
278       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
284
285
286                  [generator to $fmt [generator from $fmt $value]] = $value
287                  [generator from $fmt [generator to $fmt $gen]]   = $gen
288
289
290

PRELUDE

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
300       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
307
308
309                  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
315
316       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
325
326
327                  proc salary> {amount person} { expr {[dict get $person salary] > $amount} }
328                  set fat-cats [generator filter {salary> 100000} $employees]
329
330
331       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
347
348
349                  # 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
361
362       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
364       define 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
368
369
370                  proc * {x y} { expr {$x * $y} }
371                  proc prod gen { generator reduce * 0 $gen }
372                  proc fac n { prod [range 1 $n] }
373
374
375       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
379
380
381                  sum [nats]; # Never returns
382
383
384       generator foldl function zero generator
385              This is an alias for the reduce command.
386
387       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
394       generator all predicate generator
395              Returns true if all elements of the generator satisfy the  given
396              predicate.
397
398       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
402       generator any generator
403              Returns true if any of the elements of the  generator  are  true
404              (i.e., logical disjunction).
405
406       generator concat generator ?generator..?
407              Returns  a  generator  which is the concatenation of each of the
408              argument generators.
409
410       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
416       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
421       generator dropWhile predicate generator
422              Removes  all  elements from the front of the generator that sat‐
423              isfy the predicate.
424
425       generator contains element generator
426              Returns true if the generator contains the given  element.  Note
427              that this will destroy the generator!
428
429       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
434       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
439       generator foldri function zero generator
440              Right-associative version of foldli.
441
442       generator head generator
443              Returns the first element of the generator.
444
445       generator tail generator
446              Removes the first element of the generator, returning the rest.
447
448       generator init generator
449              Returns  a  new  generator consisting of all elements except the
450              last of the argument generator.
451
452       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
457       generator take n generator
458              Returns the next n elements of the generator as a new generator.
459              The old generator is destroyed.
460
461       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
466
467
468                  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
473
474       generator last generator
475              Returns the last element of the generator (if it exists).
476
477       generator length generator
478              Returns  the  length  of  the  generator,  destroying  it in the
479              process.
480
481       generator or predicate generator
482              Returns 1 if any of the elements of the  generator  satisfy  the
483              predicate.
484
485       generator product generator
486              Returns the product of the numbers in a generator.
487
488       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
493       generator sum generator
494              Returns the sum of the values in the generator.
495
496       generator takeWhile predicate generator
497              Returns a generator of the first elements in the argument gener‐
498              ator that satisfy the predicate.
499
500       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
507
508
509                  set xs [generator from list {a | b | c}]
510                  generator split {string equal "|"} $xs ;# returns a then b then c
511
512
513       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

BUGS, IDEAS, FEEDBACK

520       Please  report  any  errors  in  this  document,  or  in the package it
521       describes, to Neil Madden [mailto:nem@cs.nott.ac.uk].
522

KEYWORDS

524       control structure, coroutine, filter, foldl, foldr, foreach, generator,
525       iterator, map, reduce, scanl
526
527
528
529tcllib                                0.1                         generator(n)
Impressum