dikini.net

control resumed inspired me to take a small exercise.

"Code a minimal approximation of the python yield operator based generators"
Here follow the results I managed to get with help from Matthias Felleisen, via the plt mailing list. You can see the non-edited exchange via the mailing list archives and control and macors. All control&prompt are forms specific to plt scheme's control.ss module. The first attempt looks something like this:

(require (lib "control.ss"))

(define (make-step)
  (define (control-state)
    (yield 1)
    (yield 2)
    (yield 3)
    'finished)
  (define (yield value) (control resume-here (set! control-state resume-here) value))
  (define (generator) (prompt (control-state)))
  generator)

(define step (make-step))

(step) (step) 

It does the job. Kind of. For me the interesting bit is how the interplay of prompt and control achieve maintaining the current state of execution before the return and allowing to continue from that interruption. It can be done with call/cc but it looks a helluva a lot more complicated and is far more unreadable.

There is a problem with the code above though. As Matthias notes in his email:

LESSON: never 'test' by running things at the top-level prompt. It IS a prompt. -- Matthias

So comes version 2:

(require (lib "control.ss"))

(define (make-step)
  (define (control-state)
    (yield 1)
    (yield 2)
    (yield 3)
    'finished)
  (define (yield value) 
    (control resume-here 
             (set! control-state 
                   (lambda () (prompt (resume-here)))) 
             value))
  (define (generator) (prompt (control-state)))
  generator)

(define step (make-step))

(equal? '(1 2 3) (list (step) (step) (step)))

control-state is a variable holding a reference to a function with no arguments, doing what the python function would do. yield is a variable holding a reference to a function which does the interrupt magic. generator is a variable holding a reference to a (sugary) function which does the initial step.

The logic of the above algorithm is roughly as follows - mark thy state, do what you need to do, when you encounter control stop, remember your state by wrapping it in a function (resume-here), remember where do you what to continue from ( the set! control-state ...). Notice that the value of control-state is replaced. This is possible since the resume-here continuation is a function and a first class value.

So what next. Boilerplate code is tedious to write. And there is a lot of boilerplate code there. And every function, which needs to follow this recipe, will need to duplicate it.

So scheme macros to the rescue. It is not a trivial problem. A 'generator' function can look something like this:

(define/y (make-step)
          (yield 1)
          (yield 2)
          (yield 3)
          'finished)

While it could be better, it does resemble the normal define syntax for function definitions. Attempt 3...

(require (lib "control.ss"))

(define-syntax define/y
  (syntax-rules ()
    [(_ yield-name (name arg ...) body ...)
     (define (name arg ...)
       (define (control-state) body ...)
       (define (yield-name value) 
         (control resume-here 
                 (set! control-state (lambda () (prompt (resume-here 'dummy))))
                  value))
       (lambda () (prompt (control-state))))
       ]))
       
(define/y yield (make-step)
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(define step (make-step))

(equal? '(1 2 3) (list (step) (step) (step)))

There are a few problems with this code... Firstly it is annoying to specify yield every time. Second... It migh not be convenient to make a factory, and then make the 'generator'.... The harder issue at hand is How to eliminate the yield from the define/y line. The problem stems from the hygiene enforced by syntax-rules and syntax-case macros. It guarantees that the naive use of yield in the macro definition below doesn't override any other definition of yield. Usually that would be an error. In this case it does cause problems:

(define-syntax define/y
  (syntax-rules ()
    [(_ (name arg ...) body ...)
     (define (name arg ...)
       (define (control-state) body ...)
       (define (yield value) 
         (control resume-here 
                 (set! control-state (lambda () (prompt (resume-here 'dummy))))
                  value))
       (lambda () (prompt (control-state))))
       ]))

So this won't work. To acheive the goal, yield needs to be introduced into the macro scope. It can be done using the datum->syntax-object form. It helps us to introduce the yield identifier into the syntax macro scope:

(require (lib "control.ss"))

(define-syntax (define/y stx)
  (syntax-case stx ()
    [(mkg (name arg ...) body ...)
     (syntax-case (datum->syntax-object (syntax mkg) 'yield) ()
       [yield (syntax
               (define (name arg ...)
                 (define (control-state) body ...)
                 (define (yield value) 
                   (control resume-here 
                             (set! name (lambda () (prompt (resume-here 'dummy))))
                            value))
                 (prompt (control-state))))])]))

(define/y (step)
          (yield 1)
          (yield 2)
          (yield 3)
          'finished)

(equal? '(1 2 3 finished) (list (step) (step) (step) (step)))

Well nearly over. The last variant was suggested by Matthias, and is somewhat more elegant:
(require (lib "control.ss"))

(define-syntax (define/y stx)
  (syntax-case stx ()
    [(_ (name arg ...) body ...)
     (with-syntax ((yield-name (datum->syntax-object stx 'yield)))
       (syntax
        (define (name arg ...)
          (define (yield-name x)
            (control resume-here
             (set! name (lambda () (prompt (resume-here 'dummy))))
             x))
          (prompt body ...))))]))

(define/y (step)
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(equal? '(1 2 3) (list (step) (step) (step)))

As a footnote a traditional call/cc based implementation of the first macro, which formulated the tricky macro questions (by Matthias):

(define-syntax define/y
  (syntax-rules ()
    [(_ yield-name (name arg ...) body ...)
     (define (name arg ...)
       (define (yield-name x)
         (call/cc
          (lambda (resume-here)
            (set! name (lambda () (resume-here 'dummy)))
            (exit-with x))))
       (define exit-with #f)
       (call/cc
        (lambda (k)
          (set! exit-with k)
           body
          ...)))]))

(define/y yield (step)
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)