CPS冥想

原博客链接: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 0; // 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(0), 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.


下一节:向协程挥手

原文地址:https://www.cnblogs.com/pointer-smq/p/4818760.html