haskell 有证据证明runST确实是纯的吗?

w8biq8rn  于 2023-01-26  发布在  其他
关注(0)|答案(2)|浏览(173)

最初由Launchbury and Peyton Jones设计的ST monad允许Haskell程序员编写命令式代码(带有可变变量、数组等),同时获得该代码的纯接口。
更具体地,入口点函数的多态类型

runST :: (forall s. ST s a) -> a

确保包含ST计算的所有副作用,并且结果值是纯值。
这一点曾经被严格地(甚至正式地)证明过吗?

igetnqfo

igetnqfo1#

这里是Andrea Vezzosi的Agda formalization,它证明了runST对于一个具有可读/可写引用的单子是安全和全的。它依赖于假设的参数性,即所涉及定义的自由定理的真实性,这是可以预期的,因为参数性正是forall s.技巧起作用的原因。
然而,证明假设我们不能将值放入类型本身依赖于ST sSTRef s中,在Haskell中,我们可以使用这种依赖来获得循环而不需要递归:

loop :: ()
loop = runST $ do
  x <- newSTRef (pure ())
  writeSTRef x $ do
    y <- readSTRef x
    y
  y <- readSTRef x
  y

可能这个版本的ST单子仍然是安全的,只是没有可证明的writeSTRefreadSTRef的总和。

3yhwsihp

3yhwsihp2#

碰巧的是,Amin Timany等人在POPL2018上发表了一篇论文,题目正是这个主题,

一元状态封装的逻辑关系

在runST存在的情况下证明上下文等效性
你可以找到文件here。充分披露:我自己还没有找到时间把它读透彻:)。

相关问题