轉移控制權作為 effect：coroutine 與排程器

這是 effect 系列的第三篇，這篇要解釋怎麼用 effect 攔截 coroutines 的 yield 並重新排程。

所謂的 coroutines，就是一些互相約定好會主動讓出執行權利，互相「協作」的函數。是 continuation 極其常見的使用案例，首先我們先設定 abort 部分：

(define sched-tag (make-continuation-prompt-tag 'sched))

(define (yield)
  (call/cc
    (lambda (k)
      (abort/cc sched-tag k))))

可以看到 yield 就是預設外部會有一個 prompt (effect handler) 等著自己，於是它就把自己的 continuation 捕獲起來丟出去給 handler

我們需要一個地方存放還沒有做完的任務，所以定義了一個 queue tasks
spawn 單純就是把任務推入 queue 中排隊
continue 的目的是提供 handler 等待 thunk 的 yield 再次把執行權釋出

(define tasks (make-queue))

(define (spawn proc)
  (enqueue! tasks proc))

(define (continue thunk)
  (call/prompt
    thunk
    sched-tag
    (lambda (k)
      (enqueue! tasks k))))

最後就先把兩個 coroutines 推入 tasks，注意到兩個 tasks 只呼叫 spawn 並沒有意義，需要到下面的排程迴圈呼叫之後才會真的被執行

(spawn (lambda ()
         (for ([_n (range 5)])
           (displayln "A")
           (when (= 0 (random-natural 3))
             (yield)))))
(spawn (lambda ()
         (for ([_n (range 5)])
           (displayln "B")
           (when (= 0 (random-natural 3))
             (yield)))))

我們故意讓它隨機讓出執行權而不是每一步都讓出一次，在現實的使用情況中，我們通常是做了非常耗時的操作之後（比如各種 IO）才會讓出

不過在那種情況中我們這麼簡單的排程設計就有點問題了，我們會預期排程做更仔細的控制：handler 會在 coroutine 呼叫的資源準備好之後就把 coroutine 叫起來繼續，而不是直接把下一個 task 拿出來叫它繼續，確保 CPU 的利用率最大化

因為這只是單純教學，排程迴圈並不對 task 做出任何假設，也因此我們只用 queue 作為抽象結構，就像剛剛提到的一些策略，為了滿足那些策略，我們往往需要選擇合適的資料結構來滿足那些排程的需求。裡面放了一個 debug print 用來觀察排程過程剩餘的 tasks 的數量

(let loop ()
  (printf "How many tasks? ~a~n" (queue-length tasks))
  (cond
    [(queue-empty? tasks) (void)]
    [else
     (define t (dequeue! tasks))
     (continue t)
     (loop)]))

這樣的寫法當然有點樣板化，而且 effect handler 在這裏是不必要的，因為 yield 也能直接把自己的 continuation 推入 tasks，取出下一個任務跳轉：

注意到這裡 spawn 完還是需要自己記得從 tasks 中取一個出來執行才會開始執行
(spawn ...)
(spawn ...)
((dequeue! tasks))

(define (yield)
  (call/cc
    (lambda (k)
      (if (queue-empty? tasks)
        (k)
        (begin
          (enqueue! tasks k)
          (define t (dequeue! tasks))
          (t))))))

但這樣的話就需要每次都建立類似的樣板程式。用跳轉的方式解耦可以建立一個 macro 用來宣告區域，比如：

(with-scheduler
  (spawn ...)
  (spawn ...))

在該區域中的 spawn 不要直接壓入固定變數，而是從 macro 生成的 parameterize 取得要用的 tasks，這樣就可以把上面複雜排程迴圈就隱藏到 macro 中，使用者寫 coroutine，排程細節由 macro 負責

轉移控制權作為 effect：coroutine 與排程器 [Y7OR]