« Home

以 effect 為合約：用 effect system 解耦遍歷演算法與存取點 [4Z05]

我以前寫過一篇文章介紹 effect system，看過之後的回饋基本上有兩種

  1. 哇靠這也太抽象了，到底在說什麼
  2. 那 effect system 到底對我們日常的程式開發有什麼用？

所以我打算利用零碎的時間寫寫各種應用範例，而這篇就是關於如何用 effect system 將遍歷演算法與 visit 處理分離。我想不重複 racket 中的有界續延如何實作 effect system 的功能？已經介紹過的各個 racket API，所以直接用程式案例說明。比如今天我們想要走訪 binary tree，以 inorder 走訪可以寫成

(define (dfs t)
  (match t
    [(list v L R)
     (dfs L)
     (visit v)
     (dfs R)]
    [v (visit v)]))

我們單純認定 (list root-value L-tree R-tree) 這樣的格式是 binary tree，這很可能不是最好的寫法，不過以這裡要講的概念來說，重點在 visit 是什麼，所以我們先看一下實現

要記得用 (require racket/control) 引入 racket/control
(define visit-tag (make-continuation-prompt-tag 'visit))
(define (visit v)
  (call/cc
   (lambda (k)
     (abort/cc visit-tag k v))))

這段程式大致上就是說，abort/cc 會去找 visit-tag 的 handler 處理（這部分跟 try/catch 與 raise 是完全一樣的，raise 就是 abort/cc）。而 call/cc 提供了 k 這個 continuation，而且我們也把它傳給 handler，讓 handler 知道怎麼跳回來，最後把 v 傳給 handler。

調用 dfs 的程式需要準備好 handler。call/prompt 的格式是：函數、prompt tag、handler、函數的參數。以下範例把節點的值印出來

(call/prompt
  dfs
  visit-tag (lambda (resume v)
              (println v)
              (resume))
  '(4 (2 1 3) 5))

換一個 handler，完全不需要動 dfs 的程式，就能改成計算節點數量

(define counter 0)
(call/prompt
  dfs
  visit-tag (lambda (resume v)
              (set! counter (add1 counter))
              (resume))
  '(4 (2 1 3) 5))
(println counter)
這裡用全域變數 counter 是為了簡化範例

如果不用 effect system，遍歷演算法就得有 visitor 這個 callback 參數，或是直接 hardcode 每個存取點的操作。後者很容易發生：開發者順手寫死，等到要改的時候才發現需要四處找出調用點、改寫成 callback 形式。

callback 法還有另一個深層問題：決定 callback 行為的地方，有時候在呼叫遍歷演算法的好幾層 frame 之上。這樣一來，中間穿過的每一個函數都得多帶一個參數，純粹為了傳遞這個 callback。effect system 找 handler 的方式是從執行期的 call stack 往上翻，所以 handler 可以放在任何外層 frame，完全不需要靠參數傳遞。

使用 effect system 之後，遍歷演算法不需要知道實際上 visit 會進行什麼操作，只需要相信 visit 會去找某個 handler 做事；而 visit 的 handler 也不用知道遍歷演算法是怎麼實現的，只需要相信遍歷演算法會把結構的每個節點的值傳給自己。兩方完全依賴 visit 為合約！