话题由来

参加了不少IT公司的笔试，有些题目遇到的次数还是比较多的，例如给一系列字符和一个空栈，询问你选项中的哪一个是不可能出现的出栈顺序这样的问题。另外一道题目，就是我这里要拿来讲的，不过我讲的和题目本身不直接相关，只是恰好和题目所要完成的任务有重合罢了。这道题目就是“给出一颗二叉树的先序遍历和中序遍历的输出结果，请给出这个二叉树的后序遍历的输出结果”。

这道题目其实非常简单，尽管我一开始遇到的时候仍然是手足无措的（谁没有年少无知过呢对不），不过一两次之后就轻车熟路了，知道了这样的题目的行之有效的解法。举个例子，先序的序列和中序的序列分别是”abfce”和”bface”，那么这棵二叉树就是这样子的

可以知道，后序遍历的输出结果为”fbeca”。怎么得到这棵二叉树呢？其实很简单，首先根据先序遍历的定义，所以在先序遍历结果中的第一个元素一定是整棵二叉树的根结点，也就是a，那么根据中序遍历的定义，在a左边出现的序列就是左子树的中序遍历结果，在a的右边的就是右子树的中序遍历结果，它们分别是”bf”和”ce”。并且可以知道，在先序遍历中与它们对应的片段应该也是”bf”和”ce”。在对”bf”做同样的处理，就可以知道b是根结点，而左子树为空且右子树为单节点f，另一棵子树的根结点为c且左子树为空，右子树为单节点e。

那么，怎么用程序来自动化呢？

C语言的递归版本

以文字来描述根据先序和中序来构造二叉树的算法还是很好理解的。为了描述方便，取几个名字。把先序遍历的结果叫做preseq，中序遍历的输出结果叫做inseq，并且把它们当作C语言中的数组那样来取出元素（例如preseq[0]表示第一个元素），再给它们一个方便取出片段的语法糖，例如preseq[0..2]表示取出下标从0到2的三个元素组成一个新的输出序列。

首先，取出preseq的第一个元素preseq[0]，可以知道它肯定是目前正在处理的整棵二叉树的根结点，接着在inseq中寻找这个根结点，于是就可以把inseq分成三段，第一段是左子树的中序输出结果inseq1，第二段是根结点本身inseq2，第三段则是右子树的中序输出结果inseq3。同样的，preseq也可以分成三部分：第一个元素就是根结点，记为preseq1，然后是和inseq1等长的一个子串，也就是左子树的先序遍历的输出结果，剩下的，就是和inseq3等长的子串，即右子树的先序遍历输出结果了。既然有得到了先序和中序遍历的输出结果各一对，那么接下来只要对对应的一对输出结果递归调用原来的功能就可以了。递归的base case，就是输出结果只有一个元素的情况。这时候只需要生成一个没有左右子树的节点即可。

我写了两个版本，第一个是很简单很直接的实现，就是完全按照上面所说的思路来做的，因此其中充满了字符串的复制操作，详见代码（其中的make_tree_by_prein函数就是实现了上面的算法的代码）

第二个版本避免了字符串的复制操作，不过没有第一个版本的make_tree_by_prein函数那么好理解了。这里只有修改后的make_tree_by_prein函数的代码

CommonLisp和Java的版本

C语言中的第二个版本在CommonLisp和Java里面可以改得更好一点，这多亏了CommonLisp的闭包特性和Java的OO方式。在C实现的第二个版本中，make_tree_by_prein函数有两个参数，而辅助函数make_tree_aux则需要两个参数。其中参数preseq和inseq是两个在传递过程中完成不会被修改的参数，它们之所以被作为参数，仅仅是因为C语言中只有两种方式在函数间共享一些信息：

• 函数参数
• 全局变量

因为不想使用全局变量，所以只好在参数列表中动手脚了，不过在CommonLisp和Java的实现，就有办法可以在函数之间以受控的方式共享信息。例如下面用CommonLisp实现的make-tree-by-prein函数

函数make-tree-by-prein利用labels在函数体内部定义了一个闭包aux，preseq和inseq则是在词法范围内可见的变量，因为在aux内部依然可以访问到它们，这样就不需要将它们作为aux的两个参数来进行传递了。而Java的实现也是类似的，在Java中方法从属于类，并且它们可以共享同一个类的实例中的所有变量，因此直接使用这些变量即可，代码如下（因为Java同样没有办法定义内部函数的关系，所以只好定义一个用private修饰的方法makeTreeAux了。）

不是有人说吗？OO是穷人的闭包；闭包是穷人的OO;-)

后记

总算把讲思路贴代码的东西弄完了，可以好好扯淡一番了=。=话说上课的时候有个考研的同学找我讲话（班里的一名胖子，在算法方面有很厉害的嗅觉），就是问我对于用算法来实现“根据先序和中序输出结果如何构造二叉树”有没有思路。递归的方法其实很容易就可以想出来了，加之我之前已经想过这类题目要怎么系统地解决，所以很快就说出来了。然后我就觉得用C语言可以像上面那样写出一个高效（即没什么字符串复制操作）的版本，接着又想到这个可以用Lisp（或者其它带闭包的语言）来实现得更好，又想到了用Java也可以实现闭包的那类效果，再接着又觉得可以发篇文章来讨论讨论，于是就有这样的一篇东西了。

对于具体实现某个功能的技术，我貌似没有特别地挑剔，甚至可以说，对于加入到编程语言中的任何特性，我都没有太挑剔的，只要好用，那么我就很可能会接纳——当然了，我也无法保证自己在找到一个反例之后不会把这句话给改掉当作自己没有这么说过，不过暂时没有想到这种情况，所以就先当作我是这样的人吧。举个例子，对于Haskell我很喜欢，也很喜欢纯函数语言的说法，即“纯函数是非常有利于程序编写的”。不过对于副作用我也没有持完全拒绝的态度，即使我在编程的过程中也会尽量遵循函数式编程的规矩（尽量避免副作用）。可是副作用实际上避无可避，倒不如拥抱它们。或许正是因为这个原因，我才会喜欢OCaml更甚于Haskell吧——至少目前是这样的。

我也喜欢惰性计算，尤其是其带来的效果——无限长的列表推到看起来实在是帅得不行，并且还可以使得编写的程序拥有了函数式的外观和命令式的效率（例如《SICP》中举的例子，用惰性计算结合map、filter和reduce）。拥有惰性计算有利无害，何乐而不为呢～或许也正是因为自己对特性的需求是多多益善，所以才喜欢Common Lisp吧。

链子涂色问题的动态规划解法

话说大四已经开始了一个半月了，自己自从开学以来也一直在找工作，相继投了很多家IT公司。可悲的是，笔试过后就完全没有回音了——参加了多益网络的笔试两天后倒是有回音，只是收到的是拒绝的邮件QAQ。说实话，现在对于自己能不能够顺利地找到工作还是很担忧的，所以最近开始了紧张的复习。不过自己实在是懒，所以也没有像别人考研那么地拼命，只是在刷完微博读完邮件逛完豆瓣后开始看一些讲数据结构和算法的书罢了。至于是否真的有效，我也不清楚，毕竟笔试题目也不一定就完全考察这些内容的。不过按照目前的几次经验来讲，考察数据结构和算法的擦边球也有不少，可以说也是为了日后的面试准备一下吧，如果有面试的话……QAQ。

问题来源与描述

前面跑题还真严重，算是个人风格吧……话说室友去了一家名为CVT的公司参加笔试和面试，尽管最后第二轮被刷了，不过可以说还是挺厉害的。他在参加了笔试之后回来和我说了一道题目，大意是“给一串红绿珠子并存的链子，要求通过涂色把红色的珠子全部放到绿色的珠子的左边去，要求涂色的次数尽可能地少”。刚开始的时候没有认真听，于是就觉得这是编辑距离的变体罢了，那天晚上就把这个思路脱口而出，结果他第二天去面试面试官又拿这道题问他有没有新思路，结果估计被我害得够呛吧，惭愧。

题目其实有蹊跷，因为编辑距离是有前提的，那就是做变换的过程中要可以使用插入和删除操作，而那道题只允许涂色，那么也就是编辑距离中的替换操作罢了。还有另外一个和编辑距离不同的地方，那就是最终的变换目标不是唯一的，因为完全可以把链子里的珠子全部涂成一个颜色，那样就不会有红色在绿色的右边的情形了。所以，这道题目不是编辑距离的变体。唉，都怪自己太骄傲了，没有读懂题目。

动态规划的解法

前天上计算智能的课的时候，因为室友（去笔试的那位）想到了正确的线性时间的解法，所以我也不甘落后，开始在课堂上捣鼓起这道题目来。我的预感是，一般笔试题应该都可以用动态规划来做的，于是就从动态规划的角度来思考，结果也确实想到了一个办法。尽管不知道网上是不是已经有这道题的解法了，不过还是拿出来分享一下吧。

既然要使用动态规划，那么当然要按部就班地来思考。首先，就是要描述最优解的结构，也就是要找出问题解的最优子结构。为了便于描述，先约定一些记法。对于珠子和链子这种东西，可以把它们适当地抽象为元素和数组，用R代表红色而用G代表绿色，同时用S表示整个数组。数组的长度记为S.len，数组的第n个元素记为S[n]，而把最后一个元素拿掉之后的数组记为S[1..(S.len-1)]（类似于Python中的数组slice的写法）。对具体的数组实施变换，即涂色操作的功能就命名为F，它是一个二元函数，第一个参数是数组，第二个参数是位于数组之后的元素。为什么要这样子定义，而不是定义为一元函数呢？

不一样的最优子结构

对于数组的最后一个元素S[S.len]，它只有两种可能：

• S[S.len]为R；
• S[S.len]为G。

并且如果本来是红色R的，那么可以涂成绿色G的；本来是绿色G的，可以涂成红色R。可是对于一个珠子，是不是真的可以随意地对它涂色的呢？显然不是的。例如，如果已经确定了整个数组S的下一个元素是红色R的，那么S[S.len]就无论如何也不能涂成绿色，因为这样一来就绝对无法得到红色全在绿色右边的链子了。所以，如果操作F是最优的，即F对于一个数组S以及给定的下一个元素a，它的涂色次数最少，那么：

• 如果a为R，那么F肯定是把前缀S[1..(S.len-1)]也给全部涂成了红色；
• 如果a为G，那么F对于数组S的前缀S[1..(S.len-1)]的涂色次数肯定也是最少的。

上述的第二条，正是解的最优子结构。

递归定义最优解的值

显然，最优解的值也就是最优解的衡量标准，即需要对原来的数组进行的涂色的次数。既然要递归定义，那么就要考虑递归的一般情形（也就是需要递归的情形）以及基准的情形。对于下一个元素a为红色的情况，只能继续选择把目前处理的数组的最后一个元素也涂成红色，因此如果原来的数组最后一个元素S[S.len]不是红色，那么就需要一次涂色操作，如果是那么就不需要；对于下一个元素为绿色的情况，需要分别考虑要不要涂改最后一个元素的问题。如果涂，那么就增加一次操作，不涂就不需要。在a为绿色的两个分支中，涂成（或者保留）红色末尾元素的情形，和a为红色的情况的递归是一样，因此这里确实存在重叠子问题——动态规划的另一个要求。至于基准情况，则是当数组只有两个元素时的情况。此时，只能是GG、GR、RG、GG这四种，除了GR需要进行一次涂色之外，其它的均不需要涂色。

用数学公式来表示递归的情形可能更清楚：

其中diff函数判断两个参数是否相等。如果相等，那么就返回0，否则返回1。也就是在从第一个参数变换到第二个参数时所需要的涂色次数。

按自底向上的方式计算最优解的值

在思考如何自底向上的时候，我采用的办法是先自顶向下地演示一遍。如下图所示，其中入口功能的名字为G，例子所使用的数组为RGRG：

显然这里需要构造一个表格来对F过程的中间结果进行存储，因为F是一个二元的函数。尽管F的第一个参数是一个数组，可是原来的数组是不会变的，所以只需要记住当前处理的数组是由原来的数组的前多少个元素组成的前缀即可，因此F的第一个参数可以用数字来代替。因此，在处理过程中需要的是这样的一张表：

（不好意思，图中的空格没有对齐>_<）

那么如何自底向上呢？首先对于参数为1而下一个元素为R的情况，因为是递归函数的基准情况，所以可以直接得到F(1, R)=F([R], R)为0，于是填入0；同样第二行的第一个空格的值也为0。当需要填写第一行的第二个空格的时候，可以知道因为下一个元素为R，所以此处的值只与之前的末尾元素亦为红色R的情形有关，所以这个值只与第一行的前一个值有关，并且此时的元素S[2]为G与R不同，因此需要变换，故增加一；而第二行的第二个空格的值取决于前一列的两个格子的值。此时即计算G([RGG])的值，所以取F([RG], G)和F([RG], R)+1的较小值，即1。其它空格以此类推，最终结果为：

由计算出的结果构造一个最优解

显然，最后一列的结果就是所要的值，例如上面的数组[RGRG]的最少涂色次数是1，并且操作是将第二个位置上的G涂成R。这样的操作反映在中间结果中，就是先找出最后一列的元素的值最小的那一行，例如上面就是第二行。然后就是在所有的列中找出所有与下一列的值不一样的列，将其对应的珠子的颜色翻转。例如在上面的表格中，就是将第二列的G涂成R，因为G对应的数字0不同于下一列的数字1。好吧，这一次，我就不给代码了，因为我还没有写出来;)

问题一：50个瓶子的故事

一个青年走进了一家便利店买了，爽快地购买了50瓶饮料，并且跟老板扬言说他可以一口气全部喝完。老板听了笑了觉得起来，因为这实在是太不可思议了，并且跟青年保证可以用三个空的瓶子换得一瓶新的饮料继续喝。青年微微一笑，随手拿起了一瓶并且一口气喝下了第一瓶，然后用神情的眼眸望向老板，问到：“呵呵，老板，你猜一下，我最后总共可以喝到多少瓶饮料呢？”而此刻的你，就是那个双眼中充满了疑惑的老板……

threebodies：三种思考方式

思路一：一遍又一遍地计算！

老板想，这个年轻人可能会采用这样的策略来喝饮料：首先把50瓶饮料全部喝掉，这样就可以得到50个空瓶子，然后用50个空瓶子来和自己进行交换，可以换得16瓶新的饮料，并且还剩下了2个原有的空瓶。接下来再把16瓶新装的饮料喝完，这样就得到了18个空瓶子，那么就可以继续和自己进行交换了。然后可以用全部的18个瓶子换得6瓶新饮料，并且再喝掉。再用6个空瓶子换得2瓶饮料继续喝掉，那么就会剩下2个空瓶，也就没办法再继续换下去了，所以最后的结果应该是74瓶！

在α世界线中的你，也就是老板就是这样子想的，他得出的结果是74瓶。可惜的是，青年技高一筹，他向你伸出手说：“老板，可以不可以借一瓶给我，这样我喝完之后就有3个空瓶了，还给了就相当于一瓶新的饮料，你也不亏啊。”你想了想，觉得倒也合情合理，于是答应了。所以最终的结果是，青年一共喝了75瓶饮料。

思路二：找出递推公式！

老板是个函数式语言程序员，他发现了要计算这样的过程的结果，可以利用递归！他假设了有一个函数叫做F，这个函数接受一个正整数作为参数，并且可以计算出这个正整数所对应的总共可以额外获得的饮料的数量。如果用50作为参数，那么就是在计算这个青年所提出的问题了。那么怎么递归呢？从一个特殊的情况考虑就是50瓶拿出3瓶来喝掉，并且换得一瓶新饮料，那么也就是说现在得到了一瓶新饮料，并且还剩下48瓶，所以关系应该是：F(50)=1+F(48)，以此类推，F(48)=1+F(46)，F(46)=1+F(44)等等。那么递推公式就是

F(n)=1+F(n-2)。

而最终的基础情形是n为1（当一开始的n为奇数时）或者n为2（当一开始的n为偶数时），它们对应的值分别为0和1（因为对于下降到n为2的情况，可以和老板借一瓶来凑数），所以如果一开始的参数为50，那么最后的计算结果将是F(50)=24+F(2)，即25。那么将可以额外获得的25瓶加上原来的50瓶，青年总共可以喝到75瓶饮料。这一次，β世界线中的你终于得到了正确的答案。

思路三：列方程！

老板是个数学家，他首先意识到了青年可能会向自己借饮料，于是他开始列方程了：假设青年向自己借了x瓶饮料，那么他必须在喝完所有的饮料之后偿还这x瓶，为了能够正好喝完所有饮料而又不需要多还空瓶或者多买几瓶，那么他所借的饮料的数量应该满足这个方程

50+x=3x。

解方程，得到结果为75。在γ世界线中，老板几乎在听到了青年的问题后的瞬间回答了这个问题，青年先是吃了一惊，然后发出了爽朗的笑声……

问题二：圆与弦的故事

很久之前在学校里面的一家书店里面买了一本书，连我自己也觉得不可思议的是，这本书既不是轻小说也不是计算机类的书，它的名字叫做《悖论简史》，副标题还很唬人，叫做“哲学和心灵的迷宫”。这本书里面提到了很多有趣的故事，其中一个是由约瑟夫·路易斯·伯特兰在1889年提出的一个问题：在一个圆内任意拉一条弦，这条弦的长度比圆的内接等边三角形的边长还要长的概率是多少？这个问题在维基百科上也有收录，叫伯特兰悖论)。

至于这个问题的三种解答方法，我就不一一赘述了，反正我也不觉得自己能够把故事再用青年人和老板来重演一遍，各位读者就自己看维基百科上面的说明好了。不过我觉得这个题目很有意思，非常的有意思。首先它和问题一一样，可以从三个不同的角度来进行解答，问题在于，问题一的三个答案在同样的前提下是一样的（即允许青年向老板借一瓶饮料，而实际上即使不能借，前两个思路算出来的结果也是正确的），可是对于伯特兰悖论而言，三种方法算出来的结果截然不同！不过现实和数学毕竟是不一样的，答案终究只有一个，这个是用实践就可以证明的。

后记

从不同的角度看待不同的问题，除了会得到不同的解法之外，不同的解法甚至还可能得出不同的答案，但是这样的答案尽管互相之间是矛盾的，却无法从推理过程中看出问题，不得不承认，数学有时候真的是一种很神奇的东西，尽管不少时候我都会觉得，数学就是符号和规则的游戏，只是碰巧现实世界的模型和数学所使用的模型一致罢了。算了，我对数学的理解也不深刻，就不继续民科下去了。总之，以后多尝试从不同的角度看问题，或许真的会有不同的收获。啊，怎么感觉这文章虎头蛇尾的？！

先跑跑题

自从辞掉了那份实习，我仿佛失去了什么东西，以致于在后来的两天里面都有一种无所事事的感觉，做什么事情都不在状态的样子。可能现在的我看起来还是那样子，不过我的自我感觉还可以，虽然看动画占了一天当中不少的时间份额，不过也总算是值得的。当然了，还有阅读小说的时间。最近买了不少小说（同时也不小心错手买了两本漫画），读了大部分，现在还剩下一本《奋斗吧！系统工程师》的第三卷没有打开来读。说到学习方面的话，最近确实是松懈了很多，丝毫没有按照自己在日程安排当中写的那样去做（回家没有网络也算一个原因吧），例如没有看《算法导论》，倒是看了不少和OCaml有关的内容，也掌握了不少OCaml的知识，感觉如果要实际使用的话，只要再努力学习一点库和领域特定的知识就足够了吧——大概是的……

入正题

ProjectEuler的第18题所需要的答案就是从三角形的最上层，到达三角形的最下层的路径中，哪一条路径上数字的和最大，计算出这个最大值就可以了。如果对动态规划的思想有点感觉的话，那么这个问题其实就是可以运用动态规划来解决的一个比较典型的例子了。按照《算法导论》一书中的描述，动态规划算法的设计可以分为下面的四个步骤：

• 描述最优解的结构
• 递归定义最优解的值
• 按自底向上的方式计算最优解的值
• 由计算出的结构构成一个最优解

要想描述这里的最优解的结构，不妨自己定义一些名词以方便描述。首先给三角形中的每个元素设定一个位置，它们各自的位置由行和列来决定，最上面是第一行，而最下面是最后一行，也就是第十五行。而最上面的那个元素，就是传说中的第一行第一列，给位置取个符号，叫做P(i,j)好了，其中i代表行号，j代表列号。给路径取名为p，那么如果找到了一条从位置P(i,j)到底层的路径p，它上面的数字的和是所有从P(i,j)出发的路径中最大的，那么称这条路径p为所谓的“最大和路径”。

描述最优解的结构

如果从位置P(i,j)开始的路径p是其对应的最大和路径，那么p必然包含了从位置P(i+1,j)或者P(i+1,j+1)开始的最大和路径。要证明这样的东西，可以用反证法（《算法导论》中都是这样的思路）。假设这条路径没有包含通过位置P(i+1,j)的最大和路径作为其一部分，那么就是说存在从位置P(i+1,j)开始到达底层的另一条路径p’，其上面的数字之和比p的对应的那一部分要大。如果真的是这样的话，那么只需要在原来的路径p中，将从位置P(i+1,j)开始的那一部分替换成这条新的路径p’，那么就可以构造出一条新的、从位置P(i,j)开始到达底层的最大和路径p2，并且p2包含的数字之和比p的要大。这与原来的假设，即p是最大和路径相矛盾，所以假设不成立，p包含了通过其上面每一个子位置的最大和路径。同理可以证明对于位置P(i+1,j+1)这样的关系也是成立的。

这就是最优解的结构，也就是最大和路径的构成是怎样的。一个问题的最优解包含了子问题的一个最优解，这就是所谓的最优子结构性质，是运用动态规划来设计算法的一个重要的要求。现在最优解的结构已经找出来了，可是这个东西似乎不是可以拿来计算的东西，毕竟它不是一个量化的东西，所以接下来就要……

递归定义最优解的值

那么应该用怎样的数量来作为可以代表最优解的值呢？其实PE的这个问题本身就提供了非常好的入手点，也就是从某个位置出发，到达底层的路径上的数字的和。因为要从最优解的方面来考虑，所以可以把这个代表最优解的值设定成“从位置P(i,j)开始的最大和路径p所经过的数字的和”。不过这个定义也只是解决了最优解的值从那个方面入手的问题而已，更重要的是，这个最优解的值可以通过怎样的方法计算得来呢？显然，最大和依赖于下面一层中和位置P(i,j)相邻的两个位置所能够得到的最大和，这两个位置分别是P(i+1,j)和P(i+1,j+1)。假设在一个位置中存储的数字为a(i,j)，与一个位置相关的最大和记为S(i,j)，那么对于一般的i和j而言，S(i,j)=max{S(i+1,j), S(i+1,j+1)}+a(i,j)，其中要求j<=i。有两个临界情况，它们分别是当i等于1和15时的情况，一个是处于最上层，另一个则是处于最下层。对于i=1的情况，S(1,1)就是题目所需要的答案，而对于所有i=15的情况，S(15,j)=a(15,j)。（如果可以用LaTeX来排版公式的话表意一定会更加地明确）

按自底向上的方式计算最优解的值

现在的问题就是，要怎么自底向上地计算出这个最优解的值呢？其实很简单，只要从第14层开始一层一层地往上处理就可以了。假设有一个三角形S记录着对应于每一个位置的最大和，那么对于遇到的每一层中的每一个位置P(i,j)，只需要在S(i+1,j)和S(i+1,j+1)中选择一个较大的值，然后与a(i,j)相加并且放入表S的对应位置中就可以了。这样当处理完了所有的元素后，也就是遍历到了第一层之后，表S的(1,1)位置就是最终的答案了。不过这里稍微有个可以优化的地方，就是在处理第i层的时候，每一个元素在处理完之后，原先存放的值就没有用处了，因此其实完全可以不需要再使用一个三角形S，而是直接将求和得到的阶段性的那个值放入P(i,j)中。这样下次计算上一层时也不需要三角形S了，而是直接使用下一层的数据就可以了。

由计算出的结构构成一个最优解

第三阶段的计算实际上已经完成了这里的工作，所以可以直接编码了。代码在这里，是用OCaml来写的。

之前在新浪博客上已经发表了一篇同样主题的文章了，不过心血来潮想重写一份发到这边的博客上来，顺便看看自己能不能够在自己重写这篇的东西的过程中再发掘出一些有价值的东西，充实一下内容。

什么是CPS

首先双手奉上来自维基百科的Continuation-passing-style条目。CPS一般译作续延传递风格，这里最不好理解的词语莫过于续延了。维基百科上关于续延也有详细的介绍，不过我也可以简单地介绍一下。续延是一种表示接下来所要进行的计算的对象，也就是你在计算了这一步之后需要继续做的事情的一个描述。举个例子，对于Common Lisp代码(+ (+ 1 2) 3)而言，最左边的参数首先会被计算，也就是Lisp实现先计算的是(+ 1 2)这个表达式，于是可以得到返回值为3。那么计算完了最左边的参数之后，Lisp实现接下来要做什么呢？显然，接下来会计算作为直接值的3得到3本身，然后再将第一次计算得到的3和第二次求值得到的3进行相加。而上面的这两个步骤，其实可以用Lisp中的对象进行描述，只需要用一个匿名函数就可以了，写成

(lambda (v) (+ v 3))。

那么我们就可以思考，在这一个匿名函数被计算之后，再一次的接下来的计算又是什么呢？对于在REPL中输入的代码而言，Lisp实现会把表达式最终计算得到的返回值打印在终端上，所以我们可以认为上面的匿名函数，也就是一个计算过程，所对应的续延是

(lambda (u) (print u))。

那么原来的表达式(+ (+ 1 2) 3)就可以写成下面这样的风格的代码：

(+& 1 2 (lambda (v)
          (+& v 3 (lambda (u)
                    (print u)))))

你或许会感到奇怪：这里的+&是个什么东西啊？+&是一个和加法类似的函数，只是它除了会把前两个参数相加之外，还会将这个参数传递给作为第三个参数传入的匿名函数，并进行函数调用。按照维基百科上的说明，CPS代码有两个规范：

1. 每一个函数都要接受一个续延作为额外的参数；
2. 每一个函数调用中的参数都只能是一个变量或者λ表达式。

可以说，+&这样的函数是为了将代码变换成CPS才创造出来的。当然了，除了+函数需要进行变换之外，其它的普通函数（regular function）也是需要进行变换的。例如对代码(\ (+ 1 2) 3)进行变换的话，就需要为\函数提供相应的变体，结果应该是：

(+& 1 2 (lambda (v)
          (*& v 3 (lambda (u)
                    (print u)))))。

上面的代码中有个可以稍微琢磨的地方：为什么在两个不同的匿名函数的参数列表中偏偏要使用不同的参数名呢？事实上，在上面的两个变换出来的结果中，完全可以统一使用v或者u来作为参数名，那是因为参数v不需要在第二层嵌套的匿名函数中被使用。可是有时候一开始就进行求值的表达式不一定是马上就被使用的，例如代码(- (+ 1 2) (\ 3 4))*的变换结果就是

(+& 1 2 (lambda (v)
          (*& 3 4 (lambda (u)
                    (-& v u)))))。

可以说，当参数列表表达式中不止一个复杂表达式时，就需要至少两个不重名的参数了。讲了这么多手动变换的事情，现在可以讨论最重要的问题了：

如何对Lisp代码进行CPS变换

如果我们可以对一类简单的代码进行CPS变换了，那么如何在这个基础上对复杂的代码进行CPS变换呢？例如我们有一段简单的代码(op3 (op2 (op1 a b) c) d)，并且我们已经有了一个通用的功能F可以对其中的嵌套的表达式(op2 (op1 a b) c)进行变换，那么要如何将其和外层的对op3函数的调用结合在一起呢？显然，我们可以先把(op2 (op1 a b) c)换掉，换成一个普通的符号v，以表示一个变量。那么接下来我们的处理对象就是一个稍微简单的表达式(op3 v c)了，对于这种参数列表均由变量所构成的表达式，要将其变换成CPS代码只需要修改其函数为加&的形式，并且添上一个额外的参数——续延就可以了。至于这个续延应该是由调用者提供，而又可以使用默认的(lambda (XXX) (print XXX))的。所以，上面的代码最终会变成

(经过F处理的代码 (lambda (v)
                (op3& v c (lambda (XXX)
                            (print XXX)))))。

对内层的表达式应用F处理完之后还要再计算外层表达式的续延，而计算续延正是函数F所做的事情，所以实际上对一个复杂的表达式做CPS变换，是一个递归的过程。用两段代码进行变换可以有更直观的体验：假设我们有一个正确实现的变换函数F，它接受一个代码和一个续延，并产生出对代码进行CPS变换所得到的结果。那么如果应用在代码(+ (+ 1 1) 3)上，就是

(F (+ (+ 1 1) 3) (lambda (v) (print v)))。

显然，这段代码应该和下面的这段代码是等价的：

(F (+ 1 1) (lambda (u)
             (+& u 3 (lambda (v)
                       (print v)))))。

并且上面这段代码的续延参数部分，和下面的这段代码是等价的：

(F (+ u 3) (lambda (v) (print v)))。

是不是就是说，对于一个复杂的表达式expr0，如果想要在提供一个额外续延cont0的情况下，将其正确变换成CPS形式，那么可以先提取出它的第一个被求值的子表达式expr1，将原来子表达式出现的地方替换为一个变量，那么原本的表达式就变成了expr1对应的续延cont1。此时先将cont1和cont0传入函数F进行CPS变换，得到的结果cont将会成为和expr1一起传入函数F进行变换，并最终得到对expr0和cont0进行变换的正确结果呢？显然这是对的，因为cont0紧随expr0求值，而expr0可以拆分为两部分：expr1以及紧随其求值的cont1。那么显然cont0紧随cont1求值，所以cont0是cont1的续延，同样需要进行CPS变换，然后得到新的代码作为expr1的续延继续进行变换，那么最终就会得到代码，它反映的求值顺序正是expr1 -> cont1 -> expr0。

那么重点就在于怎么把原本的expr0给拆分成expr1和cont1，以及具体结合代码和续延的技术细节了。假设实现拆分功能的函数叫做split-funcall，那么它需要在什么情况下做什么事情呢？一般而言，split-funcall处理的是有复杂的子表达式的代码，那么它需要能够在整个表达式expr0中找出尽量左的一个复杂子表达式，也就是expr1。如果找到这样的expr1了，那么就需要同时找出对应的续延cont1并将两者都返回；如果没有这样的expr1，那么直接返回逻辑假和整个expr0就可以了。说到需要返回多个值的情况，正是Common Lisp的values函数派上大用场的时候了。

对于含有复杂子表达式的情况，split-funcall函数会返回提取到的子表达式和对应的续延，那么这里的续延应该用什么样的形式来表示呢？为了方便使用从split-funcall内部所gensym出来的符号，所以直接返回一个经过构造的lambda表达式就可以了，但是在递归调用函数F时，不能直接对其进行变换处理，因为lambda表达式不是一个会对参数求值的操作符，所以真正需要变换的是lambda表达式的函数体。因此必须先拆开lambda表达式，对其函数体进行变换并再次构造成lambda表达式，以传递给函数F使用。

最后，贴一下自己放在Gist上的代码: