递归——CPS(一)

程序中为什么需要栈stack?

普通的程序中,接触到子程序和函数的概念,很直观地,调用子程序时,会首先停止当前做的事情,转而执行被调用的子程序,等子程序执行完成后,再捡起之前挂起的程序,这有可能会使用刚才子程序计算出的数据。但是在程序被挂起的地方重新捡起程序并继续执行需要一个机制,即,存储当前所做事情的相关信息和以后在哪里捡起这个程序(现场信息)。这时,栈自然而然就是满足这种需要的一个数据结构(为什么使用栈略过不提)。

如果情况发生改变,没有函数需要返回,函数要么终止程序,要么是调用另一个函数,那么该怎么做?

很明显,治疗比疾病更糟糕。这种情况下,不必保持当前所做事情的跟踪信息,因为永远不会返回,那每次调用一个过程,这个过程取得所有控制权并且不再返回,该如何让所有工作能完成?

首先,写一个函数,然后在这个函数的最后调用另一个函数(尾调用)。控制权不再返回,所以在调用函数后,还有任何代码都是没有意义的。

其次,假设在调用函数 foo 后你还有其他更多的事情要做。Foo 现在跟你同一个位置,根据上面所说,调用函数的最后一件事要么终止程序,要么调用其他函数,因此,你需要将额外的工作放入一个函数bar,并且希望这些工作在foo之后执行,也就是说,确保foo调用bar而不是终止程序。

但是你没有写出foo,怎么知道foo在它完成时即将调用bar?你需要告诉foo,让foo调用bar,并且你希望foo能合作。(废话。。。)

第三,如果某个人调用了你的函数,那么需要做的最后一件事就一样了,因为你的函数不会返回。你需要寻找某种方式,来允许函数的调用者告诉你,在完成你的工作后还应该该做些什么。

这种函数的理念是永远不会返回,调用者传入它们的函数信息(这个函数信息指示下一步该做什么),这有点奇怪,但确是很强大的编程风格,这就是传说中的 Continuation Passing Style。Continuation 就是指 “下一步该做什么”的信息,它从一个函数传到另一个函数,因此得名。

很多语言天然支持CPS——Scheme, Ruby 和Rhino等。CPS 使得在我们正常的递归程序中不需要使用栈(来存储现场信息)。

下面将写出混合CPS和常规程序两种风格的代码,用JScript语言。

假设有如下JScript程序代码片段

function foo(x)
{
var y = bar();
blah(x, y);
}
function bar()
{
return 10;
}
function blah(a, b)
{
print(a + b);
}
foo(1);

这段代码很直观。那如何写CPS风格呢?首先,每个函数需要增加一个额外的参数来保持continuation。我们的程序调用foo然后终止,所以调用foo的continuation就是“终止程序”。假设现在就有一个魔法函数用来终止程序,则

function foo(x, cfoo)
{
// undone: rewrite foo in cps
}
foo(1, terminate);

再来理一下,调用foo 确保以下三件事顺序被完成:

1. 运行bar

2. 运行blah

3. 运行foo的调用者提供的continuation

但是blah不会返回,所以我们需要让blah在完成它自己的任务后再来调用 foo 的 continuation,于是重写blah如下

function(x, cfoo)
{
var y = bar();
blah(x, y, cfoo);
}

现在看起来是可以确保foo的continuation可以被调用从而终止程序,可是,bar也是要被设计为不返回的,所以按上面这个方式写,那是无法调用blah的。

还有一个问题是,bar将返回一个值,这个值是在后面的任务中用到的,但是我们已经移除了函数的返回值。解决方法是,让bar有一个continuation参数,然后将bar的返回值(这里指原先bar的返回值)作为这个continuation的参数。之前,你将返回值返回到你即将继续运行程序的地方,现在,你将返回值传入你下一步将要做的事情中,道理是相同的。

但是foo将传什么continuation给bar?嗯,当bar调用foo传给它的continuation时(这个continuation将应用一个参数,这个参数就是之前bar的返回值),foo是想干嘛?

这么一想就简单了,foo想使用之前bar的返回值和自己的参数来调用blah,于是重写函数如下:

function foo(x, afterfoo)
{
function foocontinuation(y)
{
blah(x, y, afterfoo);
}
}
function bar(afterbar)
{
afterbar(10);
}
function blah(a, b, afterblah)
{
print(a+b, afterblah);
}
function print(a, afterprint) // overload print
{
print(a);
afterprint();
}
foo(1, terminate);

foocontinuation是一个闭包(closure),所以它封装了x的值和afterfoo的信息,然后传入给bar。

总结过程如下:

  1. 程序传给foo的参数为 1 和 terminate
  2. foo传给bar的参数为 foocontinuation
  3. bar传给 foocontinuation 的参数为 10
  4. foocontinuation 给出 blah 的参数为 1,10 和 terminate
  5. blah 将参数相加得到11,然后将 11 和 terminate 传给 print
  6. print 打印 11,然后调用terminate,结束程序

实际中,JScript不知道这些函数都不返回值。JScript也不能聪明地意识到即使这些函数返回了值,这些函数在子程序调用完成后,也不再做任何事情,因此保持堆栈中旧帧的信息是没有必要的。

原文:https://blogs.msdn.microsoft.com/ericlippert/2005/08/08/recursion-part-four-continuation-passing-style/

上一篇:jquery ajax中 php前台后台文件中编辑都是uft-8,返回数据还是乱码


下一篇:adapter(转自Devin Zhang)