Haskell中使用callCC实现协程时输出不符合预期的问题排查

我尝试用Haskell的callCC实现简单协程，对callCC :: ((a -> m b) -> m a) -> m a的理解是：编写example :: Cont Int Int这类代码时，callCC会把后续延续绑定到k；如果在callCC函数体内调用k，就会用传入值执行该延续，没调用k的话就用return的值作为延续的输入。通过把k存入数据结构，就能恢复callCC之后的函数执行。

实现代码 #

{-#LANGUAGE GeneralisedNewtypeDeriving #-}

module Cont where

import Control.Monad.Cont
import Control.Monad.IO.Class(liftIO)
import Control.Monad.State(put, get, runStateT, evalStateT, StateT, MonadState, MonadIO, execStateT)

newtype CoroutineT r m a = CoroutineT {runCoroutineT :: ContT r (StateT [CoroutineT r m ()] m) a}
    deriving (Functor,Applicative,Monad,MonadCont,MonadIO, MonadState [CoroutineT r m ()])


schedule :: CoroutineT () IO ()
schedule = do
    cs <- get
    case cs of
        (c:cs) -> do
            put cs
            c
            schedule
        [] -> return ()

yield :: CoroutineT () IO ()
yield = callCC $ \k1 -> do
            cs <- get
            put (cs ++ [k1 ()])
            schedule

test1 :: CoroutineT () IO ()
test1 = do
    liftIO $ print "HelloTest1"
    yield
    liftIO $ print "HelloTest1_2"

test2 :: CoroutineT () IO ()
test2 = do
    liftIO $ print "HelloTest2"
    yield
    liftIO $ print "HelloTest2_2"

test_cont :: IO ()
test_cont = do 
    runStateT (evalContT (runCoroutineT schedule)) [test1,test2]
    return ()

问题现象 #

yield会将延续存入状态，由schedule恢复执行。我预期每个延续执行两次，预期输出：

"HelloTest1"
"HelloTest2"
"HelloTest1_2"
"HelloTest2_2"
"HelloTest2_2"
"HelloTest1_2"

但实际输出是：

"HelloTest1"
"HelloTest2"
"HelloTest1_2"
"HelloTest2_2"
"HelloTest1_2"

问题原因 #

核心问题是对callCC中k的行为理解不完整：调用k后会直接使用callCC之后的延续，并且忽略调用k时的后续延续。从callCC的定义可以明确这一点：

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = Cont $ \k1 -> let a2b = \x -> Cont $ \_ -> k1 x in
                         runCont $ (f a2b) k1

当调用callCC $ \k -> ...时，k绑定到a2b，在callCC外部调用k时，k会变成\x -> Cont $ \_ -> k1 x——其中k1是callCC之后的延续（也就是yield之后的代码），而调用k后的延续（比如schedule中执行完任务后的后续调度逻辑）会被直接忽略。

结合代码执行流程来看：

1. test1执行到yield，将自身后续延续（print "HelloTest1_2"）加入队列，调用schedule调度test2。
2. test2执行到yield，将自身后续延续（print "HelloTest2_2"）加入队列，调用schedule调度test1的延续。
3. 执行test1的延续：调用k1直接跳转到yield之后的代码，打印"HelloTest1_2"，执行完毕后回到schedule继续调度test2的延续。
4. 执行test2的延续：调用k2直接跳转到yield之后的代码，打印"HelloTest2_2"，执行完毕后直接结束，不会回到schedule的后续调度。
5. 此时test1的yield中调用的schedule已经执行完所有队列任务，返回后callCC函数体执行完毕（未调用k1），因此callCC正常返回，yield执行完毕，test1再次执行yield之后的代码，打印最后一个"HelloTest1_2"。
6. 而test2的yield中调用的schedule在执行完自身延续后直接结束，没有回到callCC函数体，因此test2不会再次执行后续代码。

这就是实际输出与预期不符的根本原因：callCC的k调用会截断当前流程，只有未触发k的协程会在schedule执行完后继续执行后续代码。

内容的提问来源于stack exchange，提问作者Aleksei