generator.ss

_generator.ss_

Python/Ruby style generators for PLT Scheme


Introduction
------------

This package provides a simple syntax for defining generators
similar to those in Python or Ruby.  As a quick-and-dirty example,
once generator.ss has been required, we can define the following:

    > (define-generator (integers n)
       (let loop ([n n])
         (yield n)
         (loop (add1 n))))

This defines a generator function called INTEGERS that produces
generator values.  Each generator value returns successive
values to its caller by using the YIELD keyword.  We can extract
sequential values out of a generator by using GENERATOR-NEXT:

    > (define my-nums (integers 42))
    > (generator-next my-nums)
    42
    > (generator-next my-nums)
    43

    
Here is another simple example:
    
    > (define-generator (rotate . args)
        (let loop ()
          (for-each yield args)
          (loop)))
    > (define colors (rotate 'green 'yellow 'red 'yellow))
    > (generator-next colors)
    green
    > (generator-next colors)
    yellow
    > (generator-next colors)
    red
    > (generator-next colors)
    yellow
    > (generator-next colors)
    green
    > (generator-next colors)
    yellow
    

Within the body of a DEFINE-GENERATOR, the YIELD keyword suspends
the generator's context and raises the yielded value back to the caller.
Subsequent calls to GENERATOR-NEXT will restore the generator's
context and let it continue processing.


The rest of the documentation here will present the API and
some more examples.


    
_generator.ss_: generator iteration support

Structures
==========

> generator

> exn:fail:generator-exhausted


API
===

> (define-generator (name args ...) body ...)              SYNTAX

Defines a generator function that, when called, produces a generator
struct.  Values can be extracted by the generator by using
GENERATOR-NEXT.  In the context of the body, the YIELD keyword
is used to send values back to the caller.


> (yield a-value)                                          SYNTAX
Keyword for sending values to the caller.  Useful only in the context
of a DEFINE-GENERATOR form.  If used outside of DEFINE-GENERATOR,
it should raise a proper syntax error.


> (generator? datum)

Returns #t if the datum is a generator.


> (generator-next generator [finished-f])                  FUNCTION

Returns the next element in the generator.  By default,
if there are no more elements, raises exn:fail:generator-exhausted.
But if finished-f is provided, finished-f is applied.  finished-f
must be a function that takes a single exception argument --- the
exn:fail:generator-exhausted instance.


> (generator-fold fold-f accumulator generator)            FUNCTION

Performs a standard fold of fold-f across the items in the
generator.


> (generator-for-each f generator)                         FUNCTION

Performs a standard for-each iteration of f across the items
in the generator.


> (make-generator seed-function)                           FUNCTION

Low-level function for creating generators.  The DEFINE-GENERATOR
macro expands to a use of MAKE-GENERATOR.  To a first approximation,

  (define-generator (repeat-forever thing)
    (let loop ()
      (yield thing)))
  
is equivalent to:

  (define (repeat-forever thing)
    (make-generator
     (lambda (yield)
       (let loop ()
         (yield thing)
         (loop)))))


Example functions
=================

> (list/gen a-list)                                        FUNCTION
Takes a list and returns a generator that iterates across the
items in the list.

> (list->flattened/gen list)                               FUNCTION
Takes a list and returns a generator that iterates deeply across
the datums of the list.






More examples 
-------------

Here are a few more examples to show how we can define and
use generators:

(Note: most of these are just cribbed from: 
       http://linuxgazette.net/100/pramode.html)


List flattening:

    (define (flatten l)
      (reverse 
       (generator-fold cons '() (list->flattened/gen l))))


Yielding just 1 and 2:

    (define-generator (one-and-two)
      (yield 1)
      (yield 2))
        
Approximations to PI:

    (define-generator (pi-series)
      (let loop ([i 1.0]
                 [j 1]
                 [sum 0])
        (yield (* 4 sum))
        (loop (+ i 2) (* j -1) (+ sum (/ j i)))))
    
First n elements of a generator:

    (define-generator (first-n gen n)
      (let loop ([n n])
        (cond [(= n 0) 'done]
              [else
               (yield (generator-next gen))
               (loop (sub1 n))])))

Displaying the first twenty elements of PI-SERIES:

    (generator-for-each 
     (lambda (x) 
       (display x) 
       (newline)) 
     (first-n (pi-series) 20))

    
    

Development History
-------------------

I want to describe how this module got started, since this was
a good learning project for me.

Nusret asked a question on how the continuation/tree-traversal example
in "Teach Yourself Scheme in Fixnum Days" worked:

    http://list.cs.brown.edu/pipermail/plt-scheme/2006-April/012417.html

I saw this as an opportunity to make sure I really understood
continuations, so I wrote a tutorial on the concepts behind that
example:

    http://list.cs.brown.edu/pipermail/plt-scheme/2006-April/012418.html

Much of this I borrowed from material in PLAI and The Little Schemer
books.

I thought that I should polish this and make it a PLaneT package,
so I asked for some recommendations on making things nicer.  I got a
bit of friendly feedback, and incorporated what I could.

Ryan Culpepper suggested that I use syntax-parameterize to bind YIELD 
hygienically:

    http://list.cs.brown.edu/pipermail/plt-scheme/2006-April/012463.html

which was something I had always wanted to learn how to do.



References
----------

Programming Languages: Application and Interpretation, Ch 19.5.
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/

Python PEP 255: Simple Generators
http://www.python.org/dev/peps/pep-0255/

Generators in Icon, Python, and Scheme
http://okmij.org/ftp/Scheme/enumerators-callcc.html#Generators

Generating Iterators
http://schemecookbook.org/view/Cookbook/IteratorGenerators



Thank you!
----------
Thanks to Guillaume Marceau, Dave Herman, Ryan Culpepper,
and Robby Findler for suggestions to improve this package.
And thanks to the PLT group in general for providing such
a pleasant language to play and learn with!