Why this generator implementation does not work in Racket?

user_652528 0
Viewed 61

I'm trying to implement generators in racket using call/cc, I have this code so far

(define (foo2)
  (define (g abort)
    (define-syntax-rule
      (yield x)
      (call/cc (lambda (k)
                 (set! g k)
                 (abort x))))
    (yield 'foo)
    (yield 'bar)
    (yield 'tar)
    (abort 'end))
  (thunk (call/cc g)))

If I play with this in the REPL it seems to be working correctly

foo.rkt> (define g (foo2))
foo.rkt> (g)
'foo
foo.rkt> (g)
'bar
foo.rkt> (g)
'tar
foo.rkt> (g)
'end
foo.rkt> (g)
'end
foo.rkt>

But if I try to call g inside a list, it hangs and I have no idea what is happening

foo.rkt> (define g (foo2))
foo.rkt> (list (g) (g) (g))
;; prompt is not released

What is going on? Where my generator implementation is wrong?

racket continuations
1 Answers

What is (list (g) (g) (g))? Well it is basically this in CPS:

(g& (lambda (g1) ; continuation g1 
     (g& (lambda (g2)
          (g& (lambda (g3)
               (list& g1 g2 g3 halt))))

You are replacing g&, but all of you yield share the same initial abort which is continuation g1 and you will never ever reach continuation g2 since every time abort is called you run continuation g1. If you step through you'll notice that this continuation gets fed all the yield values but eventually it calls abort. Even if you remove the last call it will always call the second (g) in your expression.

It helps to know call/cc& is this:

(define (call/cc& f cc)
  (f (lambda (v ignored-cc) 
       (cc v)) 
     cc))

Now g in CPS would look something like this. Notice the abort are free variables in there and they will be the same even if you replace g&

(define (g& abort cont)
  (call/cc& (lambda (k cc)
              (set!& g& 
                     k 
                     (lambda (undefined) 
                       (abort 'foo cc))))
            (lambda (ignored1)
              (call/cc& (lambda (k cc)
                          (set!& g& 
                                 k 
                                 (lambda (undefined) 
                                   (abort 'bar cc))))
                        (lambda (ignored2)
                          (call/cc& (lambda (k cc)
                                      (set!& g& 
                                             k 
                                             (lambda (undefined) 
                                               (abort 'tar cc))))
                                    (lambda (ignored3)
                                      (abort 'end cont)))))))))

As a fix I guess you need to control what you set as g. Eg. instead of (set! g k) something like this perhaps:

(set! g (lambda (new-abort)
          (set! abort new-abort)
          (k 'ignored)))

Then the list expression works as expected. Why it worked in the REPL is due to continuation prompts.

user_15656980
Related