Generators

November 11, 2011

Although Scheme doesn’t provide generators natively, it is easy to add generators (note that old versions of Scheme, such as the one used at codepad.org, use the operator datum->syntax-object instead of datum->syntax):

(define-syntax define-generator
  (lambda (x)
    (syntax-case x (lambda)
      ((stx name (lambda formals e0 e1 ...))
         (with-syntax ((yield (datum->syntax (syntax stx) 'yield)))
           (syntax (define name
             (lambda formals
               (let ((resume #f) (return #f))
                 (define yield
                   (lambda args
                     (call-with-current-continuation
                      (lambda (cont)
                        (set! resume cont)
                        (apply return args)))))
                 (lambda ()
                   (call-with-current-continuation
                    (lambda (cont)
                      (set! return cont)
                      (cond (resume (resume))
                      (else (let () e0 e1 ...)
                            (error 'name "unexpected return"))))))))))))
        ((stx (name . formals) e0 e1 ...)
          (syntax (stx name (lambda formals e0 e1 ...)))))))

With that, it is relatively simple to build a generator:

> (define-generator (yield123)
    (yield 1) (yield 2) (yield 3))
> (define y (yield123))
> (y)
1
> (y)
2
> (y)
3
> (y)
Exception in yield123: unexpected return

Generators can take parameters:

> (define-generator (one-up n)
    (let loop ((n n)) (yield n) (loop (+ n 1))))
> (define from10 (one-up 10))
> (from10)
10
> (from10)
11
> (from10)
12

The prime generator is similar to the one in the prior exercise, but primes are yielded instead of added to a list, and there is no need for a variable to count the primes:

(define-generator (prime-generator)
  (yield 2) (yield 3)
  (let ((pq (pq-insert lt? (cons 9 6) pq-empty)))
    (let loop1 ((p 5) (pq pq))
      (cond ((< p (car (pq-first pq)))
              (yield p)
              (let* ((c (* p p)) (s (+ p p))
                     (pq (pq-insert lt? (cons c s) pq)))
                (loop1 (+ p 2) pq)))
      (else (let loop2 ((pq pq))
              (if (< p (car (pq-first pq)))
                  (loop1 (+ p 2) pq)
                  (let* ((c (car (pq-first pq)))
                         (s (cdr (pq-first pq)))
                         (pq (pq-rest lt? pq)))
                    (loop2 (pq-insert lt? (cons (+ c s) s) pq))))))))))

Then you can use the prime generator like this:

> (define p (prime-generator))
> (p)
2
> (p)
3
> (p)
5
> (p)
7
> (p)
11
> (p)
13
> (p)
17

Apologists for Scheme have long used generators as an argument against Python: It took nearly ten years from the 1.0 release of Python for BDFL Guido to add generators to the language in version 2.3. But it takes only 10 minutes for an ordinary Scheme programmer to add generators to Scheme. Isn’t Scheme wonderful!?

You can run the program at http://programmingpraxis.codepad.org/WNImfKrZ, where you will also find the declaration of the priority queue used by the prime generator.

About these ads

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: