How `set!` works in Racket when working with continuations?

Question

I have this code working code based on an example from wikipedia

(define (foo5)
  (define (control-state return)
    (define-syntax-rule
      (yield x) 
      (set! return (call/cc
                    (lambda (resume-here)
                      (set! control-state resume-here)
                      (return x)))))
    (yield 'foo)
    (yield 'bar)
    (yield 'tar)
    (return 'end))
  (thunk (call/cc control-state)))

I would never achieve this code by my self because the use of set! goes against every intuition there exists inside me.

First, control-state is local to foo5, okay, then I do (define g (foo5)) in the top level, at this point, in my head g points to the same reference that control-state points, a closure somewhere in the memory.

Then I call g as (g) it evaluates up to (set! control-state resume-here) at this point is where my intuition breaks. In my head this will set the internal control-state symbol to resume-here, BUT IT CHANGES THE OUTER g ALSO?. How this is even possible?

Answer 1

This is simpler than it looks.

First of all let's rewrite it, giving it a more obvious name and replacing the local macro with a function, to remove any confusion that a macro might be needed:

(define (yielder)
  (define (control-state return)
    (define (yield x)
      (set! return (call/cc (? (resume-here)
                              (set! control-state resume-here)
                              (return x)))))
    (yield 1)
    (yield 2)
    (yield 3)
    (return 'end))
  (thunk (call/cc control-state)))

OK, so first of all notice that the top-level thing is (define (yielder) ...), and not (define yielder ...), so yielder is a function which, when called will return (thunk ...): a function of no arguments. That means that this:

(define g (yielder)

causes g to be bound to that function of no arguments. In particular g is not the same thing as control-state, and neither is it a suspended continuation. Nothing has happened yet as the function has not yet been called. Further g is never changed by any assignment: the control-state binding it closes over is mutated, but the binding of g itself is nt.

So, when g is called then it immediately calls the current value of control-state with the current continuation: a function which, when called, will immediately return from the call/cc and hence from g: that function is bound to return inside control-state.

control-state then calls (yield 1) which starts to evaluate

(set! return (call/cc (? (resume-here)
                        (set! control-state resume-here)
                        (return x)))))

So this then involves calling

(? (resume-here)
  (set! control-state resume-here)
  (return x))

With resume-here bound to a continuation which, if invoked, will cause the value it's invoked with to be assigned to return. It stashes this continuation into control-state, and then invokes the current value of return with the value of x which is 1. return then returns from that value from g: the assignment is not (yet) completed.

The next time g is called it does the same thing, creating a new return continuation and calling the current value of control-state with it as argument. But that value is now the continuation that was stashed there on the last call. So this now returns from the call/cc that was suspended by the invokation of the old value of return and completes the assignment before carrying on ... to the next yield call which does the same dance again except this time returning 2 from g. And so on.

Essentially the two continuations perform this little interleaved dance where you're for each call of g you're making a new continuation which says how to return from that call, and then invoking a continuation which restarts the body, stashing a new continuation for the next step before returning from g.

This is fiddly to understand but not impossible if you pore over it a bit.