Pub*_*bby 27 scheme continuations haskell callcc
我试图找到如何实现call/cc.我发现的最好的是这个Haskell片段:
callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k
虽然这不是那么简单,我想由于Cont和runCont.我也找到了它的功能描述,尽管从未像实际代码那样清晰.
那么它是如何以最简单的形式实现的呢？我用Scheme和Haskell标记它,因为这是我喜欢的两种语言.
ehi*_*ird 82
"实施call/cc"在您工作的层面上并没有真正意义; 如果你能用call/cc一种语言实现,那就意味着它有一个至少和它一样强大的内置结构call/cc.在语言本身的层面上,call/cc基本上是一个原始的控制流操作符,就像某种形式的分支必须一样.
当然,你可以用call/cc没有它的语言实现一种语言; 这是因为它处于较低的水平.您正在以特定方式翻译语言的结构,并安排此翻译以便您可以实施call/cc; 也就是说,通常是连续传递样式(尽管对于C中的非可移植实现,您也可以直接复制堆栈;稍后我将更深入地介绍延续传递样式).这并没有给call/cc 自己带来任何深刻的洞察力- 洞察力就是你可以实现的模型.最重要的是,call/cc它只是一个包装器.
现在,Haskell没有揭示延续的概念; 它会破坏参考透明度,并限制可能的实施策略.Cont在Haskell中实现,就像所有其他monad一样,你可以把它想象成一种使用延续传递风格的延续语言的模型,就像列表monad模型nondeterminism一样.
从技术上讲,那定义callCC并键入如果你只是删除的应用程序Cont和runCont.但这不会帮助你理解它在Contmonad 的上下文中是如何工作的,所以让我们来看看它的定义.(这个定义不是当前Monad Transformer Library中使用的定义,因为它中的所有monad都是基于它们的变换器版本构建的,但它匹配了代码片段的使用Cont(仅适用于旧版本),并且大大简化了事情.)
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
好的,Cont r a就是这样(a -> r) -> r,runCont让我们从一个Cont r a值中获取这个功能.很简单.但是这是什么意思？
Cont r a是一个带有最终结果r和结果的连续传递计算a.最终结果意味着什么？好吧,让我们runCont更明确地写出类型:
runCont :: Cont r a -> (a -> r) -> r
因此,正如我们所看到的,"最终结果"是我们最终得出的价值runCont.现在,我们如何建立计算Cont？monad实例具有启发性:
instance Monad (Cont r) where
return a = Cont (\k -> k a)
m >>= f = Cont (\k -> runCont m (\result -> runCont (f result) k))
嗯,好吧,如果你已经知道这意味着什么,那就很有启发性.关键的一点是,当你写Cont (\k -> ...),k是计算的其余部分 -它希望你给它的值a,然后会给你计算的最终结果(类型的r,记不清了)回来了,然后你就可以作为使用您自己的返回值,因为您的返回类型也是r如此.呼!当我们运行Cont计算时runCont,我们只是指定最终结果k- 产生最终结果的计算的"最高级别".
什么是"剩下的计算"？一个延续,因为它的持续计算的!
(>>=)实际上非常简单:我们在左边运行计算,给它我们自己的计算余量.这种计算的剩余部分只是将值输入f,从而产生自己的计算.我们运行该计算,将其提供给我们已经给出组合动作的剩余计算.通过这种方式,我们可以将计算线程组合在一起Cont:
computeFirst >>= \a ->
computeSecond >>= \b ->
return (a + b)
或者,用更熟悉的do表示法:
do a <- computeFirst
b <- computeSecond
return (a + b)
然后我们可以运行这些计算runCont- 大多数时候,类似的runCont foo id工作会很好,将foo结果和最终结果类型转换为结果.
到现在为止还挺好.现在让我们让事情变得混乱.
wtf :: Cont String Int
wtf = Cont (\k -> "eek!")
aargh :: Cont String Int
aargh = do
a <- return 1
b <- wtf
c <- return 2
return (a + b + c)
这里发生了什么？!wtf是Cont最终结果String和结果的计算Int,但是没有Int看到.
当我们运行时会发生什么aargh,runCont aargh show比如运行计算,并将show其Int结果作为a String来产生最终结果？
我们"eek!"回来了.
还记得k"其余的计算"是怎么回事？我们所做的wtf就是狡猾地不称之为,而是提供我们自己的最终结果 - 然后,最终成为!
这只是延续可以做的第一件事.像Cont (\k -> k 1 + k 2)运行其余的计算一样运行,就好像它返回1一样,再次将它返回2,并将两个最终结果一起添加!Continuations基本上允许表达任意复杂的非本地控制流,使它们像混乱一样强大.实际上,延续是如此普遍,从某种意义上说,每个单子都是一个特例Cont.实际上,您(>>=)通常可以将其视为使用一种延续传递方式:
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
第二个参数是继续获取第一个计算的结果并返回要运行的其余计算.
但我仍然没有回答这个问题:那是怎么回事callCC？好吧,它调用你给当前延续的函数.但是,坚持一秒,是不是我们已经做了Cont什么？是的,但比较类型:
Cont :: ((a -> r) -> r) -> Cont r a
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
呵呵.你看,问题Cont在于我们不能从我们传递的函数内部对动作进行排序- 我们只是r以纯粹的方式生成结果.callCC让继续被访问,传递,并且通常只是从内部 Cont计算中弄乱.当我们有
do a <- callCC (\cc -> ...)
foo ...
您可以想象,cc作为一个函数,我们可以使用函数内部的任何值调用它来使callCC (\cc -> ...)计算本身的返回值.或者,当然,我们可以正常返回一个值,但是然后调用callCC首先会有点毫无意义:)
至于b那里的神秘,它只是因为你可以用来cc foo计算你想要的任何类型,因为它逃脱了正常的控制流程,就像我说的那样,立即使用它作为整体的结果callCC (\cc -> ...).因此,由于它永远不必实际生成一个值,因此可以返回它想要的任何类型的值.偷偷摸摸的!
这将我们带到实际的实施:
callCC f = Cont (\k -> runCont (f (\a -> Cont (\_ -> k a))) k)
首先,我们得到整个计算的其余部分,然后调用它k.但这f (\a -> Cont (\_ -> k a))部分是关于什么的？嗯,我们知道f取一个类型的值(a -> Cont r b),这就是lambda是一个函数,它接受一个值作为结果使用callCC f,并返回一个Cont忽略其延续的计算,只返回该值k- "休息计算的"从...的角度来看callCC f.好的,所以该f调用的结果是另一个Cont计算,我们需要提供延续才能运行.我们只是再次传递相同的延续,因为如果一切正常,我们希望计算返回的是我们的返回值并继续正常.(事实上,传递另一个值是没有意义的 - 它是"用当前延续进行调用",而不是"用你实际运行的那个之外的延续来调用".)
总而言之,我希望你发现这很有启发性.延续非常强大,但是可能需要花费大量时间来确定它们的工作方式.我建议玩Cont(你必须打电话cont来使用当前的mtl工作)并弄清楚如何获得你做的结果以了解控制流程.
建议继续阅读续篇:
bdo*_*lan 12
call/cc实施是微不足道的.困难的部分是建立可以实施的环境.
我们必须首先定义一个延续传递样式(CPS)执行环境.在这种环境中,你的函数(或类似函数的东西)不会直接返回值; 相反,它们被传递一个函数来表示计算中的"下一步" - "延续" - 并将它们的结果传递给那里.在Haskell中,这看起来像这样:
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
正如你所看到的,Contmonad动作实际上是一个函数,它接受一个延续(a -> r),将结果传递a给continuation,并获得最终结果r,它只是传递给它的调用者(即,Contmonad动作应该调用到延续).runCont只是将它从newtype包装器中取出 - 您也可以将其视为调用具有某种特定延续的动作,如runCont someAction someContinuation.
然后我们可以把它变成一个monad:
instance Monad (Cont r) where
return x = Cont $ \cc -> cc x
(Cont f) (>>=) g = Cont $ \cc -> f (\r -> runCont (g r) cc)
正如您所看到的,return只是得到一个延续cc,并将其值传递给延续.(>>=)它有点棘手,它必须调用f继续然后调用g,获取操作,然后将外部延续传递给这个新操作.
所以给定这个框架,继续进行是很简单的.我们只想调用一个连续两次的函数.棘手的部分是我们需要在一个新的monadic动作中重新包装这个延续,抛出现有的延续.所以让我们分解一下:
-- Invoke a raw continuation with a given argument, throwing away our normal
-- continuation
gotoContinuation :: (a -> r) -> a -> Cont r x
gotoContinuation continuation argument = Cont $ \_ -> continuation argument
-- Duplicate the current continuation; wrap one up in an easy-to-use action, and
-- the other stays the normal continuation for f
callCC f = Cont $ \cc -> runCont (f (gotoContinuation cc)) cc
简单,不是吗？
在像Scheme这样的其他语言中,原理是相同的,尽管它可以实现为编译器原语; 我们在Haskell中可以做到这一点的原因是因为继续传递是我们在Haskell中定义的,而不是在运行时的较低级别.但原理是一样的 - 你需要首先使用CPS,然后call/cc才是这个执行模型的一个简单应用.