221: Generator/accumulator sub-library

by John Cowan (text), Arvydas Silanskas (implementation)

Status

This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-221@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

This is a set of convenience routines for generators and accumulators intended to blend in with SRFI 158. The authors recommends that they be added to the (srfi 158) library provided by users or implementations. If they are approved by the R7RS-large process, they can also be added to (r7rs generator).

Issues

None at present.

Rationale

The procedures of this SRFI, in cooperation with those of SRFI 158, make it easier to set up and make use of pipelines of generators. In particular, the gchain-generators procedure allows the creation of just such a pipeline, starting with an initial generator and adding generator operations to it to produce a desired result.

The accumulate-generated-values procedure captures the output of a generator and passes it directly to an accumulator until the generator is exhausted. The generator can be a gchain-generators chain, which allows arbitrary transformations.

The gdelete-duplicates procedure is an enhancement of the SRFI 158 procedure gdelete-neighbor-dups that can delete duplicates without requiring them to be adjacent results.

The genumerate procedure attaches increasing non-negative exact integers to the outputs of a generator. Filtering the stream will still allow the original indices to be recovered at a later stage.

The procedure gpeek makes generators "peekable" in the sense of peek-char and peek-u8, and even "pokeable" in the sense of C's ungetc(). This partly assimilates them to character or byte ports.

The gchoice operation uses one generator to dictate which one of a number of other generators will be drawn on to provide the next value. If used with the make-categorical-generator procedure of SRFI 194 as the first argument, it can choose from the other generators using a weighted probability.

Finally, stream->generator and generator->stream allow conversion between generators and SRFI 41 streams, and indirectly between streams and SRFI 127 lazy sequences, which are either lists or improper lists with a generator in their tails.

Specification

(gchain-generators constructor operation ...)

Creates a generator from a generator constructor plus a chain of generator operations. The first argument is called with no arguments, the remaining arguments with one argument. For example, (gchain-generators gmake gfoo gbar) returns the same generator as (gbar (gfoo (gmake))).

Since it is typically necessary to pass additional arguments to the constructor and the operations, the arguments to gchain-generator will usually be lambda expressions. For example:

(gchain-generators
  (lambda () (make-iota-generator 100))
  (lambda (g) (gfilter even? g))
  (lambda (g) (ggroup 5 g)))

returns a generator that outputs the values (0 2 4 6 8), (10 12 14 16 18), ... (90 92 94 96 98). Such calls can be written more compactly using the cut macro from SRFI 26:

(gchain-generators
  (cut make-iota-generator 100)
  (cut gfilter even? <>)
  (cut ggroup 5 <>))

(accumulate-generated-values accumulator generator)

Invokes generator, passing the value it returns to accumulator. If the value was an end-of-file object, accumulate-generated-values returns whatever the accumulator returned. Otherwise, the process is repeated.

(gdelete-duplicates gen [ = ])

Creates a generator that returns whatever gen returns, except for any items that are equal to an earlier item in the sense of =, which defaults to equal?. The = predicate is passed exactly two arguments, of which the first was generated by gen before the second.

Example:
(generator->list (gdelete-duplicates (list->generator '(a a b c a a a d c))))
  ⇒ (a b c d)

(genumerate gen)

Creates a generator that returns pairs. The car of each pair is an exact integer counting up by 1 from 0. The cdr of each pair is the result of gen.

(gpeek gen)

Returns a procedure p that behaves like a generator but with more capabilities. If called with zero arguments, it invokes the underlying generator gen. However, if called with the argument peek, it retrieves the next value from gen and returns it, but also saves it in such a way that the next zero-argument call on p will return it, analogously to peek-char and peek-u8. If called with two arguments, poke and an object obj, it will save obj so that the next zero-argument call on p will return it.

(gchoice choice-gen source-gen ...)

Returns a generator g that behaves as follows:

When g is invoked, it first invokes choice-gen to return an index value i. It is an error if i is not an exact integer between 0 (inclusive) and the number of source-gens (exclusive). Then the ith source-gen is invoked and its value returned by g.

If choice-gen is exhausted, g returns an end-of-file object. If the chosen source-gen is exhausted, g remembers that fact and invokes choice-gen until it returns the index of a source-gen that has not been exhausted. When all source-gens are exhausted, g returns an end-of-file object.

Composing make-iota-generator and make-circular-generator from SRFI 158 performs round-robin selection of the source-gens.

(stream->generator stream)

Returns a generator that steps through the elements of a SRFI 41 stream.

(generator->stream generator)

Returns a SRFI 41 stream containing the values of a generator.

Implementation

The sample implementation of this SRFI is in the repository for it.

Acknowledgements

Thanks to all who participated on the SRFI mailing list.

© 2020 John Cowan (text), Arvydas Silanskas (implementation).

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


Editor: Arthur A. Gleckler