IteratorGenerators - Cookbook - s c h e m a t i c s : c o o k b o o k

Generating Iterators

Problem

Python programmers may be familiar with Python's yield keyword and generator functions. Python has built-in language support specifically for generator functions, whereas PLT Scheme does not. Can we invent our own then?

Solution

Yes. We will first need an iterator class:

(require (lib "class.ss"))

(define iterator%
   (class object%
     (init-field initial-k)
     (define k initial-k)
     (define set-k! (lambda (c) (set! k c)))
     
     (define/public (next)
       (let/cc cc
         (raise (let/cc raise-cc
           (cc (k (list set-k! cc raise-cc)))))))

     (define/public (reset)
        (set! k initial-k))
        
     (super-new)))

Next, let's define an exception to be raised at the end of iteration:

(define-struct (exn:stop-iteration exn) ())

Now we define the define-gen syntax for defining generators:

(define-syntax (define-gen stx)
  (syntax-case stx ()
    [(_ (id args ...) bodies ...)
     (with-syntax ([yield (datum->syntax-object stx 'yield)]
                   [return (datum->syntax-object stx 'return)])
     #`(define (id args ...)
         (make-object iterator%
           (lambda (set-k!&ec&raise)
             (define-values (set-k! ec raise) (values #f #f #f))
             (define (set-values the-set-k! the-ec the-raise)
               (set! set-k! the-set-k!)
               (set! ec the-ec)
               (set! raise the-raise))
             (define (return)
               (raise (make-exn:stop-iteration "StopIteration"
                                               (current-continuation-marks))))
             (define (yield x)
               (apply set-values
                      (let/cc k
                        (set-k! k)
                        (ec x))))
             (apply set-values set-k!&ec&raise)
             (with-handlers ([void raise])
               (begin bodies ...)
               (return))))))]))

Finally, we can define a generator:

(define-gen (iter lst)
  (for-each yield
            lst))

and use it:

> (define i (iter '(1 2 3)))
> (send i next)
1
> (send i next)
2
> (send i next)
3
> (send i next)
StopIteration

Discussion

Comments about this recipe

Ruby Garden has an entry on IterationStyles that has a comparison between Ruby and Python, which makes an interesting reference. I've classified this one under DataStructureRecipes until we can come up with a better place. Maybe there should be a whole chapter on how to emulate idioms from other programming languages?

-- GordonWeakliem - 10 Sep 2004

The following Web page "Generators in Icon, Python, and Scheme" http://pobox.com/~oleg/ftp/Scheme/enumerators-callcc.html#Generators describes a different -- and a portable -- way of emulating generators in Scheme. Syntax-case macros are not required. The other sections of that page argue that enumerators provide generally a better interface for iterating over a (virtual) collection than generators do. One should also mention delimited continuations (such as prompt/control or shift/reset -- which again seem superior to generators).

-- OlegK - 14 Sep 2004

Contributors

-- DanielSilva - 10 Sep 2004

CookbookForm
TopicType:	Recipe
ParentTopic:	DataStructureRecipes
TopicOrder:	999

PLT Scheme	SISC
Scheme48	SCM
MIT Scheme	scsh
JScheme	Kawa
Chicken	Guile
Bigloo	Tiny
Gambit	LispMe
Gauche	Chez