Programming Praxis

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.

Pages: 1 2