a sample generator API for Scheme, implemented using continuations

readme.md

Generator functions

This is an implementation of Generators in Scheme, using continuations. Generators allow you to:

• Write consumer code as if you're pulling values out of the producer
• Write producer code as if you're pushing values onto the consumer

Each side gets to pretend they own the control-flow: they each decide when the other gets called. Pulling values allows you to terminate early, for example (but not pulling any more).

Pushing values on the producer side makes it easier to keep track of how far you've reached in your data-structure traversing. Quoting Wikipedia:

However, Java does not have generators built into the language. This means that creating iterators is often much trickier than in languages with built-in generators, especially when the generation logic is complex. Because all state must be saved and restored every time an item is to be yielded from an iterator, it is not possible to store state in local variables or use built-in looping routines, as when generators are available; instead, all of this must be manually simulated, using object fields to hold local state and loop counters.

Below is an example of generators in Scheme. We can use continuations to implement them. Seegenerators.scm.

generators.scm

;;; generator function example, inspired by this post:
;;; http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/
;;;
;;; Kristian Lein-Mathisen 2017

(import (scheme small))

; current-continuation : -> continuation
(define (current-continuation) 
  (call-with-current-continuation
   (lambda (cc)
     (cc cc))))

; void : -> void
(define (void)
  (if #f #t))

; tree-iterator : tree -> generator
;
; example iterator. we don't have to explicitly "save" and "restore" our
; temporary `tree` variable anywhere!
(define (tree-iterator tree)
  (lambda (yield)

    ;; Walk the tree, yielding the leaves.
    
    (define (walk tree)
      (if (pair? tree)
          (begin
            (walk (car tree))
            (walk (cdr tree)))
          (yield tree)))
    
    (walk tree)))

;; generator : ((-> anything) -> anything) (-> anything) -> void
;; iterator: procedure that takes in a yield procedure and calls this
;; for every element.
;; eof: procedure that called when iterator is done
(define (generator iterator eof)
  (letrec
      ((continue #f) ;; continuation of caller

       ;; allow resuming our iterator function. wrap value in case
       ;; it's a procedure?.
       (yield*
        (lambda (value)
          (let ((cc (current-continuation)))
            (if (procedure? cc)
                (begin (set! body (lambda () (cc #f)))
                       (continue (cons value '())))
                (void)))))

       ;; body is continuation (or start) of iterator function
       (body (lambda ()
               (iterator yield*)
               ;; iterator is done, so next (body) call should just
               ;; return dummies (must call continue!)
               (set! body
                     (lambda () (continue (cons (eof) '()))))
               (body))))
    (lambda ()
      (let ((cc (current-continuation)))
        (if (procedure? cc)
            (begin (set! continue cc)
                   (body))
            (car cc))))))

;; this prints:
;; 3
;; 4
;; 5
;; 6
;; eof
(let ((next (generator (tree-iterator '(3 . ( ( 4 . 5 ) . 6 ) ))
                       (lambda () 'eof))))

  (newline) (display (next))
  (newline) (display (next))
  (newline) (display (next))
  (newline) (display (next))
  (newline) (display (next))
  (newline))