CPS冥想 - 2 手撸控制流

时间:2023-03-08 21:52:17

原博客链接:http://blogs.msdn.com/b/ericlippert/archive/2010/10/22/continuation-passing-style-revisited-part-two-handwaving-about-control-flow.aspx

上一节说到:我们可以通过跟踪不同的continuation并决定下一步执行哪个来构造任意复杂的控制流。

来看一个比条件跳转更复杂的:考虑最简单版本的try-catch,throw后面不跟表达式,也就是一个goto,goto到最近的catch,代码是这样的:

void Q()
{
  try
  {
    B(A());
  }
  catch
  {
    C();
  }
  D();
} int A()
{
    throw;
    return ; // unreachable, but let's ignore that
}
void B(int x) { whatever }
void C() { whatever }
void D() { whatever }

传统方法理解这段代码,是我们知道这附近有一个catch语句块,保存上下文,调用A,如果正常返回,那么保存上下文然后用A的返回值调用B,如果B正常返回,调用D.如果A或B没有正常返回,寻找之前说过的catch块,然后调用C,调用D。

E.L.大神说真正的CLR里面throw的实现“疯狂地复杂”,假定一个语言没有内置try-catch,那么我们没办法把一些“疯狂地复杂”的东西实现为库函数,所以,我们能否用一个支持CPS的语言实现一个Try()和Throw()函数呢?

我们可以通过给每个可能throw的函数传两个continuation,一个正常情况,一个错误情况。不妨设A会throw,把所有东西翻译成CPS的,有:

void A(Action<int> normal, Action error)
{
Throw(()=>normal(), error);
}

这样就明了了,A干了什么?调用Throw,然后把0传给了它的normal continuation,这个Throw的continuation再调用A的continuation,也就是normal(0)。(我们这里仅仅把Throw看成一个函数调用)

void B(int x, Action normal, Action error) { whatever }
void C(Action normal, Action error) { whatever }
void D(Action normal, Action error) { whatever }

所以Throw的实现是什么呢?很简单,Throw调用error continuation然后放弃normal continuation。

void Throw(Action normal, Action error)
{
error()
}

Try的实现比较难,try-catch做了些什么?他为try块创建了一个新的error continuation,但没有给catch创建,这要怎么去做呢,直接给实现

void Try(Action<Action, Action> tryBody,
Action<Action, Action> catchBody,
Action outerNormal,
Action outerError)
{
tryBody(outerNormal, ()=>catchBody(outerNormal, outerError));
}

调用是这样的

void Q(Action qNormal, Action qError)
{
Try (
/* tryBody */ (bodyNormal, bodyError)=>A(
/* normal for A */ x=>B(x, bodyNormal, bodyError),
/* error for A */ bodyError),
/* catchBody */ C,
/* outerNormal */ ()=>D(qNormal, qError),
/* outerError */ qError );
}

首先,这是CPS的,每个函数都返回void,每个lambda都返回void,每个函数或lambda都在最后调用了其他函数。

它正确吗,我们来脑补debug一遍:

调用Try,Try调用tryBody,tryBody接受两个continuation,Try把outerNormal,也就是一个()=>D(qNormal, qError) ,作为一个normal continuation传给tryBody。
把()=>catchBody(outerNormal, outerError) 作为函数体的error continuation,catch body是C,因此tryBody的参数error continuation就会被求值为()=>C(()=>D(qNormal, qError), qError) 
再来看tryBody,他是一个(bodyNormal, bodyError)=>A(x=>B(x, bodyNormal, bodyError), bodyError) ,我们知道bodyNormal和bodyError是什么了,所以把他们展开,最后变成了这样

A(
x=>B( // A's normal continuation
x, // B's argument
()=>D( // B's normal continuation
qNormal, // D's normal continuation
qError), // D's error continuation
()=>C( // B's error continuation
()=>D( // C's normal continuation
qNormal, // D's normal continuation
qError), // D's error continuation
qError)), // C's error continuation
()=>C( // A's error continuation
()=>D( // C's normal continuation
qNormal, // D's normal continuation
qError), // D's error continuation
qError)) // C's error continuation

所以调用tryBody就是调用A,A立即调用Throw,传一些复杂的东西作为normal continuation并且把()=>C(()=>D(qNormal, qError), qError) 作为error continuation.

A内部的Throw忽略它的normal Continuation,直接调用()=>C(()=>D(qNormal, qError), qError) 。
那么C干了什么,如果C throw,那么控制流立即转向qError(catch里面又throw,异常处理还要往上走一层)。如果C正常结束,那么执行的是normal continuation,也就是()=>D(qNormal, qError) ,D怎么做就不管它了。
以上假定每个函数都有可能throw,所以每个函数都有一个normal continuation和error continuation。

再回来,如果A不throw会怎样?如果他只是用0去调用它的normal continuation呢,上面写的很清楚,A的normal continuation是去调用B,所以他把0传给B,如你所见,如果B throw,那么控制流传给C,否则传给D。

所以这样就OK了,我们已经把try-catch实现为了函数,而且只用了1行(误),这一点也不复杂嘛(大神原话逃

如你所见CPS就是控制流的异化,continuation是一个代表了即将发生什么的对象。控制流是什么?控制流是决定即将发生什么。任何可以想象的控制流都能用CPS表示。

然和可以想象的控制流真的有很多,这么做可行的原因是任何控制流都是围绕条件goto的,if是goto,循环是goto,子调用时goto,返回是goto,异常是goto,都是goto,有了continuation,任何各种口味的goto以及非本地分支都完全无关紧要,你可以用CPS实现一些十分具有“异国情调”的控制流,可返回的异常,并行求值两个分支的条件表达式,yield return,协程。更Hack的,你可以写一个正着运行过去然后又倒着运行回来的程序。

If it's a kind of control flow, then you can do it with CPS.

下一节:向协程挥手