CPS冥想

这篇文章是在阅读Eric Lippert大神的MSDN Blog文章时同步写成的,其中主要是各种翻译,同时还混杂自己阅读文章的笔记和感想。

原博文地址 http://blogs.msdn.com/b/ericlippert/archive/2010/10/21/continuation-passing-style-revisited-part-one.aspx

CPSContinuation Passing Style的缩写,关于这种风格,E.L.大神和通常的程序风格做了一个对比:

通常的程序:

  记录下程序当前的状态,比如本地变量的值等,一般保存在栈里面

  把程序的控制权交给“子过程”,直到其返回

  恢复到调用前的状态,此时已经知道了子过程的返回值

CPS是一种没有“子过程”和“返回”的风格。取而代之的是,当前函数执行的最后一条指令是调用下一个函数,因为没有函数会返回,你也就不需要保存调用之前的值,现在程序在什么地方也没有什么意义,因为程序永远不会回来。

显然从这里看,结合以前的知识,CPS变换也就是所谓的尾递归形式,因为是尾调用,所以前面栈上的东西也就没有存在意义了,于是优化的时候栈空间可以重复利用,也就是所谓的尾递归优化。

为了确保事情按我们想要的顺序发生,调用新的函数的时候给他传一个continuationcontinuation本身也是一个函数,它负责执行后面所有的东西。

 

E.L.大神用C#写的例子,幸好我看得懂:(毕竟人家是C#的爹们之一)

我们有以下四个函数 string M(int); bool B(); int C(); int D(); 

假定C#没有?:三目运算符,那么该如何实现 M(B() ? C() : D()); 

忽略废话,我们有

T Conditional<T>(bool b, Func<T> consequence, Func<T> alternative)
{
  if (b) return consequence(); else return alternative();
}

直接调用 M(Conditional(B(), ()=>C(), ()=>D()); 就好

C#lambda写起来真是爽)

好了下面要强行把Conditional写成CPS风格的,怎么办,这么分析:

  M调用结束后应该调用一些东西(用来继续控制流),姑且叫它currentContinuation,先不管它到底是什么样

  需要重写B使得B接受一个接受boolcontinuation,姑且用Action<bool>代替“一个接受boolcontinuation”,现在有了void B(Action<bool>)

  Bcontinuation,也就是在B之后发生的事情是什么?

    先跳步:形式是 B(b=>M(Conditional(b, ()=>C(), ()=>D()))) ,B接受的lambda接受一个bool,然后把它传给Conditional

  现在BCPS了,但是传给Blambda不是CPS的,为了让lambda也变成CPS的,我们重复对B的分析:

    M需要接受一个Action<string>CD需要接受Action<int>

    至于Conditional,仍然需要对他的参数有惰性求值的特性,但是调用的那些lambda已经没有返回值了,所以,那个lambda也要接受一个continuation

  所以有: B(b=>Conditional(b, c=>C(c), c=>D(c), t=>M(t, currentContinuation))) 

Conditional现在是这样的:

void Conditional<T> (bool condition, Action<Action<T>> consequence, Action<Action<T>> alternative, Action<T> continuation)
{
  if (condition)
    consequence(continuation) ;
  else
    alternative(continuation);
}

总之:B执行然后把bool结果传给参数lambda,这个lambda用这个bool和其他三个lambda调用ConditionalConditional决定把第三个lambda传给前两个中的哪个,假设它选择了传给alternative,那么,D执行然后把他的结果传给continuation,也就是t=>M(currentContinuation, t) ,然后M用这个整数t做一些事情,再调用之前说过的currentContinuation,然后就OK了。

没有返回,每个方法都是void的,每个委托(匿名函数,lambda)都是一个Action,函数最后做的事情就是调用其他函数,调用的时候前面的调用栈已经没用了,因此编译器可以优化之前的代码,使得没有任何函数会消耗调用栈的空间,值全都临时存储在寄存器之类的临时位置。

也许你会觉得这TM是什么烂代码?但是你看,我们已经做出了一个CPS版本的?:运算符啊,行为完全与之相同,有用lambda实现的惰性求值,控制流由继续向最后面的continuation传合适的方法得以继续。

然而该用continuation解决的事我们一个都没干。

Continuation是控制流的异化,目前我们只讨论了一个单continuation传来传去的系统,因为continuation只是一个委托(lambda),所以我们没有理由只在系统里面用一个continuation

下一节:一些关于更复杂的控制流的冥想。

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