« Home

racket 中的有界續延如何實作 effect system 的功能？ [cs-000G]

一個 effect system 大概做了什麼，我們從 effekt 語言 (https://effekt-lang.org/) 這個案例著手

  • 一個簽名 effect yield(v : Int) : Bool
  • 一個 handler try { ... } with yield { n => ...; resume(n < 10) }
  • 在 try 區塊中調用的函數 f 可以用 do yield(k) 來調用 handler
  • 當 f 執行到 do yield(k)，就會跳轉到 with yield 中繼續進行，並且 n = k
  • 當程式執行到 resume 就會跳回去 f 之後的 do yield(k) 的續延繼續執行

因此 exception 系統也可以被視為，沒有調用 resume 的 effect handler，讀者或許也想出數種使用方法了吧？這正是 effect system 的價值。而 racket 擁有比 effect handler 更複雜的機制（continuation with marks），不過 effect handler 機制具有保障使用者不容易出錯的好處，因此在 racket 中模擬一套 effect system 依然有意義，也是有趣的挑戰。

call/prompt [rkt-0000]

  • 2024-08-27

call/prompt 的主要功能，就如其名稱，是為被呼叫的函數提示一個標記，這個標記在 abort/cc 會被使用。完整的 call/prompt 調用是

(call/prompt f tag handler args ...)

f 是被調用的函數，中間的 tag 是標記，handler 是處理標記的函數，剩下的都是 f 的參數。讀者可以想像成

(with-handler [tag handler]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              (f args ...))

abort/cc [rkt-0001]

  • 2024-08-27

abort/cc 的調用是

(abort/cc tag vs ...)

tag 當然就是先前 prompt 寫進去的 tag，而 vs ... 則作為呼叫 handler 的引數

(handler vs ...)

Continuation prompt tag 的產生方式 [rkt-0002]

  • 2024-08-27

調用 (make-continuation-prompt-tag) 產出，這個函數還可以接受一個 symbol 產生可讀的識別碼，並且每次調用這個函數，產生的 tag 都算是不同的 tag，勿必要儲存好這個實體。

要想實現 exception 目前的程式已經完全充分了，只要寫下

(define (f params ...)
  (abort/cc tag "cannot read file ..."))
(call/prompt f
             tag
             (λ (err)
               (printf "got err ~a~n" err))
             args ...)

即可。事實上 racket 自身的的 exception 也是這樣實作的，要考慮的問題是，前面我們看過 resume 可以跳回去被呼叫的函數！這是如何做到的？

call/cc [rkt-0003]

  • 2024-08-27

call/cc 這個函數是 call with current continuation 的意思，比如說在下面的程式碼中

(* 2 1)

1 的 continuation 就是把 1 挖掉留下的 (* 2 hole)，故下列程式碼

(* 2 (call/cc (λ (k) (k 1))))

的結果是 2。讀者可以想像 k = λ (hole) (* 2 hole)，這在實作上不太正確，但對理解很有幫助。

一般來說，racket 的函數會簡單的寫成

(define (f params ...)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              stmt1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              ...
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              stmtn)

如果我在其中安放一個 call/cc 會發生什麼事呢？

(define (f params ...)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              ...
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              (call/cc (λ (k) ...))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              stmtk
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              ...)

答案是 k = λ () (begin stmtk ... stmtn)。由於 racket 自動把

stmt1 ... stmtn

包裝成 (begin stmt1 ... stmtn)，而

(begin stmt1 stmt2 ...)

中 stmt1 的 continuation 是 (begin stmt2 ...)，以此類推就很容易理解 k 等於什麼了。

我們正是需要使用 call/cc 來做出 resume 的效果。

實現 resume [cs-000H]

  • 2024-08-27

在 f 中我們寫下

(define (f params ...)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             (call/cc (λ (k) (abort/cc tag k ...))))

在 call/prompt 的 handler 中新增一個 resume 參數，這樣就完成了。讀者可以填補下面的程式中的空白來檢驗結果，也充當練習

(define (f params ...)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             (call/cc (λ (k) (abort/cc tag k ...)))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             ...)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           (call/prompt f
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        tag
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        (λ (resume ...)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ...
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ; 跳回 f 繼續
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          (resume))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        args ...)

到這裡我們已經有了運行的基礎，要改善有幾個方向可以參考

  1. 用 macro 包裝語法
  2. 放到 typed/racket 中加上 effect 類型檢查確保使用者沒有漏掉 handler：typed/racket eff
  3. 支持 finally handler，保證任何退出行為都會被這個 handler 攔截（考慮 racket 的函數 dynamic-wind）