_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. New to (= major 2): > (generator-next generator [finished-f] [resume-value]) FUNCTION We allow cross communication back to the generator at the point of resumption by passing an additional resume-value. See some of the examples in test-generator.ss for example usage. > (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!