Coroutines in Scheme (R5RS)

Question

So I first came across the concept of coroutines in lua and lua's implementation was more or less understandable.. I'm learning scheme now and I understand that the same functionality is implemented with call/cc, but I'm having a bit of trouble wrapping my head around how exactly one would go about achieving this. Anyone know an easy tutorial or something on the subject?

Answer 1

Matt Might's link is fine which I visited that last time when visiting Amb implementation in rosettacode wiki. But for coroutine, it only shows

1. "cooperative multi-threading" (i.e. coroutine) is possible with Continuations (IMHO coroutine means communicating routine to differentiate from generator which can also "be suspended and resumed")
2. The yield behavior for cooperative multithreading
3. APIs

That APIs seem to a bit symmetric due to thread queue while lua uses yield, resume which should be asymmetric due to the caller/callee relation. Symmetric vs asymmetric is shown well in this QA "Symmetric coroutines" link.

So IMHO Matt Might's link has no additional help for OP based on OP's background.

---

(coroutine routine) in c2 wiki is helpful which is asymmetric (as the above QA link shows, asymmetric version can be symmetric with one additional dispatcher).

That asymmetric version doesn't allow pass data between coroutines to be used in the coroutine itself, but we can do that with some modifications by adding clauses in cond and pass value using call/cc. (See the following (current passed-arg) context.)

(define (coroutine routine)
   (let ((current routine)
         (status 'suspended))
     (lambda args
       (cond ((null? args) 
              (if (eq? status 'dead)
                  (error 'dead-coroutine)
                  (let ((continuation-and-value
                         (call/cc (lambda (return)
                                    (let ((returner
                                           (lambda (value)
                                             (call/cc (lambda (next)
                                                        (return (cons next value)))))))
                                      (current returner)
                                      (set! status 'dead))))))
                    (if (pair? continuation-and-value)
                        (begin (set! current (car continuation-and-value))
                               (cdr continuation-and-value))
                        continuation-and-value))))
             ((eq? (car args) 'status?) status)
             ((eq? (car args) 'dead?) (eq? status 'dead))
             ((eq? (car args) 'alive?) (not (eq? status 'dead)))
             ((eq? (car args) 'kill!) (set! status 'dead))
             (true nil)))))
(define test-coroutine-1
     (coroutine (lambda (yield)
                  (print "HELLO!")
                  (yield 1)
                  (print "WORLD!")
                  (yield 2)
                  (print "SORRY, I'M OUT"))))

;; added
(define print write-line)

(test-coroutine-1 'status?)
; suspended
(test-coroutine-1 'dead?)
; #f
(test-coroutine-1 'alive?)
; #t
(test-coroutine-1)
; "HELLO!"
; 1
(test-coroutine-1)
; "WORLD!"
; 2
(test-coroutine-1)
; "SORRY, I'M OUT"
(test-coroutine-1 'status?)
; dead
(test-coroutine-1 'dead?)
; #t
(test-coroutine-1)
; . error: dead-coroutine

Here it uses 2 call/ccs, return is to drop out of the coroutine with yield and then return to the other coroutine (i.e. interaction program here) after doing something. next is to store the former suspension location after using one value.

Then when (test-coroutine-1) is called later again, we will continue to run from the location where the previous value is used, e.g. (yield 1) is assigned returner due to (current returner) where current is assigned next before.

yield behavior implies we can add one cond clause with (current passed-arg) so that (yield foo) is assigned passed-arg expectedly which achieves communication.

So the "fundamental characteristics of a coroutine" (i.e. keeping both data and control history) are implemented due to call/cc.

Answer 2

Matt Might has written a good introduction to continuations, including a section on coroutines:

http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/