Delimited Continuation 实现 State Monad

发表于更新于阅读时长 1 分钟

可能标题看起来有点像乱码.

最近看了一篇讲 delimited continuation 的教程, 不过里面的运行时比较难搞到, 所以我就想能不能用最能直击函数式编程本质的 scheme 来写. 结果在安装最广泛的 Guile (因为是 make 的依赖)里找到了 ice-9 control 这个模组.

ice-9和 call/cc 相比, 提供了两个原语, shift 和 reset. 两者的语法分别是

reset body1 body2

shift cont body1 body2

简单地说来, shift 就是获取当前直到最近的 reset 的 continuation, 把它绑定到 cont 上, 然后执行body.

然后来实现 get 和 set

(define (get) (shift k (λ (v) ((k v) v))))

(define (set v) (shift k (λ (_) ((k v) v))))

这里比较 trick 的一点是((k v) v), 第一个 v 是当前函数返回的值, 第二个则是后续的 state.

还需要实现 run

(define (run thunk) (reset (let ([result (thunk)]) (λ (state) result))))

使用 let 让 thunk 先求值.

跑一下试试

(define (calc)
  (set (* (get) (get)))
  (+ 1 (* 10 (get)))
)

(display ((run calc) 5))

会输出 251.

好吧, 但是这有什么用? 首先, 这里没有一个变量却仍然实现了可变状态, 这很酷. 此外, ocaml-multicore也用这个技术实现 Algebraic Effect, 说不定过几年就能在普通版的 ocaml 里用上.

© 2016 - 2022Austaras Devas