如何解释Haskell中的callCC？ [英] How to interpret callCC in Haskell?

问题描述

在Scheme中，执行从 call / cc 获得的延续有效地跳回到初始调用/ cc并恢复保存的调用堆栈。

我刚开始学习Haskell，并试图找出如何理解 callCC 。就理解Scheme的 call / cc 而言，试图理解 callCC 。 callCC 的实现是

  callCC f = cont $ \h - > runCont（f（\ a  - > cont $ \_-> ha））h 
  

据我所知，没有提到任何有关调用堆栈保存或恢复的内容。如何通过熟悉Scheme的 call / cc 来解释Haskell中的 callCC 。

编辑：也许如果有人可以将以下内容翻译成帮助我理解的Haskell。

 （define （返回）
（返回2）
 3）
 
（display（f（lambda（x）x）））;显示3 
 
（display（call-with-current-continuation f））;显示2 
  

解决方案

CC。您需要考虑它是否在Cont monad中。

实际功能是使用ContT定义的。 ContT是一个monad变换器，允许将延续添加到其他monad中，但让我们先看看它如何与Identity monad一起工作，并将自己限制为Cont。

  Cont ra = Cont {runCont ::（a-> r） - > r} 
  

这里， Cont ra 表示一个函数，它可以计算 a 类型的某个值，因为给定函数类型 a-> r ，它可以计算 r 类型的值。

显然是monad：

  return x = Cont $ \f  - > fx 
  

（一个类型 a

  ma>> = h = Cont $ \f  - > runCont ma $ \a  - > runCont（ha）f 
  

（here ma :: Cont ra 和 h :: a - > Cont rb ）

键入 a ，ma，可以变成类型为 b - runCont给定值 a ，知道如何产生一个 b 类型值的计算 - 可以用函数 f :: b - > r 来计算类型 r ）的值

实际上， h code>是 ma 和>> = 的延续绑定 ma 及其延续以产生函数组合的继续（在 ma 内的函数hidden code> a 和 h 中的函数hidden生成 b ）。这是您要查找的堆栈。

让我们从简化类型开始（不使用 ContT ） ：

  callCC ::（（a  - > Cont rb） - > Cont ra） - >在这里，callCC使用一个函数来构造延续的延续。
 
 $ b  

b
$ b

有一点很重要，你似乎也错过了。 callCC 只有在 callCC 之后有一个延续时才有意义 - 即有一个延续通过。让我们考虑它是 do -block的最后一行，这与使用>>指定它必须具有的东西是一样的; = ：

  callCC f>> = returnblah
  

会做。这里最重要的一点是，当你看到这个上下文，当你看到它在的左边时， callCC >> = 。

了解>> = 并考虑到>> = 的右关联性，您可以看到<$ c $中的 h c> callCC f = cont $ \h - > runCont（f（\ a-> cont $ \_-> ha））h 实际上是使用当前延续构建的 - 它使用 h 出现在>> = 右边 - 整个 do - 从line call following callCC to end：

 （callCC f）>> = h = 
 Cont $ \ g  - > runCont 
（cont $ \h-> runCont（f（\ a-> cont $ \_-> h a））h）
 \ a  - > runCont（h a）g = 
 
 [还原步骤：runCont（Cont x）=> x] 
 
 Cont $ \g  - > （\ h  - > runCont（f（\ a→> Cont $ \_→> h a））h）
 \ a  - > runCont（h a）g = 
 
 [（\ h→> f）（\ a  - > ...）=> f [h /（\ a  - > ...）]  - 用（\ a  - > ...）]替换
出现次数h 
 $ b Cont $ \\ \\ g  - > runCont（f（\ a→> Cont $ \_->（\ b  - > runCont（h b）g）a））
 \ a  - > runCont（h a）g = 
 
 [（\ b  - > runCont（h b）g）a => runCont（h a）g] 
 
 Cont $ \g  - > runCont（f（\ a→> Cont $ \_-> runCont（h a）g））$ 
 \ a  - > runCont（ha）g 
  

您可以在这里看到 \_ - > ; runCont（ha）g 本质上会忽略传递给 f 的函数和切换堆栈之后的延续，切换到code> callCC 被调用的地方的当前延续 h 。

（如果 callCC 是链中的最后一个，可以应用类似的推理，尽管这种情况下的当前延续是传递给 runCont ）

最后一点是 runCont（f ...）h 并不真正使用这最后一个 h ，如果实际调用 h 发生在如果发生这种情况，继续计算 f 。

In Scheme executing a continuation obtained from a call/cc effectively jumps back to that initial call/cc and reinstates the saved call stack.

I just started learning Haskell and I am trying to figure out how to comprehend callCC. That is try to comprehend callCC in terms of understanding of Scheme's call/cc. The implementation of callCC is

callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h

As far as I can tell there is nothing mentioned relating to call stacks saved or reinstated. How does one interpret callCC in Haskell coming from familiarity with Scheme's call/cc.

Edit: Maybe if someone could translate the following to Haskell that would help me understand.

(define (f return)
  (return 2)
  3)

(display (f (lambda (x) x))) ; displays 3

(display (call-with-current-continuation f)) ; displays 2

解决方案

It does work very much like Scheme's call/cc. You need to take into account that it is in Cont monad.

The actual function is defined using ContT. ContT is a monad transformer that allows to add continuations into other monads, but let's see how this works with Identity monad first, and limit ourselves to Cont.

Cont r a = Cont {runCont :: (a->r)->r}

Here, Cont r a represents a function that can compute some value of type a, since given a function of type a->r it can compute a value of type r.

It is clearly a monad:

return x = Cont $ \f -> f x

(a trivial "computation" of a value of type a)

ma >>= h = Cont $ \f -> runCont ma $ \a -> runCont (h a) f

(here ma :: Cont r a, and h :: a -> Cont r b)

(a computation of value of type a, ma, can turn into a computation of a value of type b - runCont ma is given h, which, given a value of type a, "knows" how to produce a computation of a value of type b - which can be supplied with function f :: b -> r to compute a value of type r)

In essence, h is the continuation of ma, and >>= binds ma and its continuation to produce the continuation of the function composition (the function "hidden" inside ma to produce a and the function "hidden" inside h to produce b). This is the "stack" you were looking for.

Let's start with the simplified type (not using ContT):

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

Here, callCC uses a function that constructs a continuation given a continuation.

There is a important point that you seem to be missing, too. callCC only makes sense if there is a continuation after callCC - i.e. there is a continuation to pass. Let's consider it is the last line of a do-block, which is the same as to say it must have something bound to it with >>=:

callCC f >>= return "blah"

will do. The important bit here is that the operation of callCC can be understood easier when you see this context, when you see it is on the left hand side of >>=.

Knowing how >>= works, and taking into account right-associativity of >>=, you can see that h in callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h is in fact built using current continuation - it is built using the h appearing on the right of >>= - the entire do-block from the line following callCC to the end:

(callCC f) >>= h =
Cont $ \g -> runCont
               (cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h) $ 
               \a -> runCont (h a) g =

[reduction step: runCont (Cont x) => x]

Cont $ \g -> (\h -> runCont (f (\a -> Cont $ \_ -> h a)) h) $
               \a -> runCont (h a) g =

[(\h -> f) (\a -> ...) => f [h/(\a -> ...)] -- replace
occurrences of h with (\a -> ...)]

Cont $ \g -> runCont (f (\a -> Cont $ \_ -> (\b -> runCont (h b) g) a)) $
               \a -> runCont (h a) g =

[(\b -> runCont (h b) g) a => runCont (h a) g]

Cont $ \g -> runCont (f (\a -> Cont $ \_ -> runCont (h a) g)) $
               \a -> runCont (h a) g

You can see here how \_ -> runCont (h a) g in essence will ignore the continuation following the invocation of the function passed to f - and "switch the stack", switch to the current continuation h of the place where callCC is invoked.

(Similar reasoning can be applied if callCC is the last in the chain, albeit it is less clear that the "current continuation" in that case is the function passed to runCont)

The last point is that runCont (f...) h does not really use this last h, if the actual invocation of h occurs from inside the continuation computed by f, if that ever happens.

这篇关于如何解释Haskell中的callCC？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！