最初由Launchbury and Peyton Jones设计的ST monad允许Haskell程序员编写命令式代码(带有可变变量、数组等),同时获得该代码的纯接口。
更具体地,入口点函数的多态类型
runST :: (forall s. ST s a) -> a
确保包含ST
计算的所有副作用,并且结果值是纯值。
这一点曾经被严格地(甚至正式地)证明过吗?
最初由Launchbury and Peyton Jones设计的ST monad允许Haskell程序员编写命令式代码(带有可变变量、数组等),同时获得该代码的纯接口。
更具体地,入口点函数的多态类型
runST :: (forall s. ST s a) -> a
确保包含ST
计算的所有副作用,并且结果值是纯值。
这一点曾经被严格地(甚至正式地)证明过吗?
2条答案
按热度按时间igetnqfo1#
这里是Andrea Vezzosi的Agda formalization,它证明了
runST
对于一个具有可读/可写引用的单子是安全和全的。它依赖于假设的参数性,即所涉及定义的自由定理的真实性,这是可以预期的,因为参数性正是forall s.
技巧起作用的原因。然而,证明假设我们不能将值放入类型本身依赖于
ST s
的STRef s
中,在Haskell中,我们可以使用这种依赖来获得循环而不需要递归:可能这个版本的ST单子仍然是安全的,只是没有可证明的
writeSTRef
和readSTRef
的总和。3yhwsihp2#
碰巧的是,Amin Timany等人在POPL2018上发表了一篇论文,题目正是这个主题,
一元状态封装的逻辑关系
在runST存在的情况下证明上下文等效性
你可以找到文件here。充分披露:我自己还没有找到时间把它读透彻:)。