前言
眾所周知，遞歸函數(shù)容易爆棧，究其原因，便是函數(shù)調(diào)用前需要先將參數(shù)、運(yùn)行狀態(tài)壓棧，而遞歸則會(huì)導(dǎo)致函數(shù)的多次無(wú)返回調(diào)用，參數(shù)、狀態(tài)積壓在棧上，最終耗盡棧空間。
一個(gè)解決的辦法是從算法上解決，把遞歸算法改良成只依賴(lài)于少數(shù)狀態(tài)的迭代算法，然而此事知易行難，線(xiàn)性遞歸還容易，樹(shù)狀遞歸就難以轉(zhuǎn)化了，而且并不是所有遞歸算法都有非遞歸實(shí)現(xiàn)。
在這里，我介紹一種方法，利用CPS變換，把任意遞歸函數(shù)改寫(xiě)成尾調(diào)用形式，以continuation鏈的形式，將遞歸占用的?？臻g轉(zhuǎn)移到堆上，避免爆棧的悲劇。
需要注意的是，這種方法并不能降低算法的時(shí)間復(fù)雜度，若是指望此法縮短運(yùn)行時(shí)間無(wú)異于白日做夢(mèng)
下文先引入尾調(diào)用、尾遞歸、CPS等概念，然后介紹Trampoline技法，將尾遞歸轉(zhuǎn)化為循環(huán)形式（無(wú)尾調(diào)用優(yōu)化語(yǔ)言的必需品），再以sum、Fibonacci為例子講解CPS變換過(guò)程（雖然這兩個(gè)例子可以輕易寫(xiě)成迭代算法，沒(méi)必要搞這么復(fù)雜，但是最為常見(jiàn)好懂，因此拿來(lái)做例子，免得說(shuō)題目都得說(shuō)半天），最后講通用的CPS變換法則
看完這篇文章，大家可以去看看Essentials of Programming Languages相關(guān)章節(jié)，可以有更深的認(rèn)識(shí)
文中代碼皆用JavaScript實(shí)現(xiàn)
尾調(diào)用 && 尾遞歸
先來(lái)探討下在什么情況下函數(shù)調(diào)用才需要保存狀態(tài)
像Add(1, 2)、MUL(1, 2)這種明顯不需要保存狀態(tài)，
像Add(1, MUL(1, 2))這種呢？計(jì)算完MUL(1, 2)后需要返回結(jié)果接著計(jì)算Add，因此計(jì)算MUL前需要保存狀態(tài)
由此，可以得到一個(gè)結(jié)論，只有函數(shù)調(diào)用處于參數(shù)位置上，調(diào)用后需要返回的，函數(shù)調(diào)用才需要保存狀態(tài)，上面的例子中，Add是不需要保存狀態(tài)，MUL需要保存
尾調(diào)用指的就是，無(wú)需返回的函數(shù)調(diào)用，即函數(shù)調(diào)用不處于參數(shù)位置上，上面的例子中，Add是尾調(diào)用，MUL則不是
寫(xiě)成尾調(diào)用形式有助于編譯器對(duì)函數(shù)調(diào)用進(jìn)行優(yōu)化，對(duì)于有尾調(diào)用優(yōu)化的語(yǔ)言，只要編譯器判斷為尾調(diào)用，就不會(huì)保存狀態(tài)
尾遞歸則是指，寫(xiě)成尾調(diào)用形式的遞歸函數(shù)，下面是一例
fact_iter = (x, r) => x == 1 ? 1 : fact_iter(x-1, x*r)
而下面的例子則不是尾遞歸，因?yàn)?code style="margin: 1px 5px; padding: 0px 5px !important; line-height: 1.8; vertical-align: middle; display: inline-block; font-family: 'Courier New', sans-serif !important; font-size: 12px !important; border: 1px solid rgb(204, 204, 204) !important; border-radius: 3px !important; background-color: rgb(245, 245, 245) !important;">fact_rec(x-1)處于*的第二個(gè)參數(shù)位置上
fact_rec = x => x == 1 ? 1 : x * fact_rec(x-1)
因?yàn)槲策f歸無(wú)需返回，結(jié)果只跟傳入?yún)?shù)有關(guān)，因此只需用少量變量記錄其參數(shù)變化，便能輕易改寫(xiě)成循環(huán)形式，因此尾遞歸和循環(huán)是等價(jià)的，下面把fact_iter改寫(xiě)成循環(huán)：
function fact_loop(x){
var r = 1
while(x >= 1) {
r *= x
x--;
}
return r;}CPS ( Continuation Passing Style )
要解釋CPS，便先要解釋continuation，continuation是程序控制流的抽象，表示后面將要進(jìn)行的計(jì)算步驟
比如下面這段階乘函數(shù)
fact_rec = x => x == 1 ? 1 : x * fact_rec(x-1)
顯然，計(jì)算fact_rec(4)之前要先計(jì)算fact_rec(3)，計(jì)算fact_rec(3)之前要先計(jì)算fact_rec(2)，...
于是，可以得到下面的計(jì)算鏈：
1 ---> fact_rec(1) ---> fact_rec(2) ---> fact_rec(3) ---> fact_rec(4) ---> print
展開(kāi)計(jì)算鏈后，再?gòu)那巴髨?zhí)行，就可以得到最終結(jié)果。
對(duì)于鏈上的任意一個(gè)步驟，在其之前的是歷史步驟，之后的是將要進(jìn)行的計(jì)算，因此之后的都是continuation
比如，對(duì)于fact_rec(3)，其continuation是fact_rec(4) ---> print
對(duì)于fact(1)，其continuation是fact_rec(2) ---> fact_rec(3) ---> fact_rec(4) ---> print
當(dāng)然，上面的計(jì)算鏈不需要我們手工展開(kāi)和運(yùn)行，程序的控制流已經(jīng)由語(yǔ)法規(guī)定好，我們只需要按語(yǔ)法寫(xiě)好程序，解釋器自動(dòng)會(huì)幫我們分解計(jì)算步驟并按部就班地計(jì)算
然而，當(dāng)現(xiàn)有語(yǔ)法無(wú)法滿(mǎn)足我們的控制流需求怎么辦？比如我們想從一個(gè)函數(shù)跳轉(zhuǎn)至另一個(gè)函數(shù)的某處執(zhí)行，語(yǔ)言并沒(méi)有提供這樣的跳轉(zhuǎn)機(jī)制，那便需要手工傳遞控制流了。
CPS是一種顯式地把continuation作為對(duì)象傳遞的coding風(fēng)格，以便能更自由地操控程序的控制流
既然是一種風(fēng)格，自然需要有約定，CPS約定：每個(gè)函數(shù)都需要有一個(gè)參數(shù)kont，kont是continuation的簡(jiǎn)寫(xiě)，表示對(duì)計(jì)算結(jié)果的后續(xù)處理
比如上面的fact_rec(x)就需要改寫(xiě)為fact_rec(x, kont)，讀作 “計(jì)算出x階乘后，用kont對(duì)階乘結(jié)果做處理”
kont同樣需要有約定，因?yàn)?code style="margin: 1px 5px; padding: 0px 5px !important; line-height: 1.8; vertical-align: middle; display: inline-block; font-family: 'Courier New', sans-serif !important; font-size: 12px !important; border: 1px solid rgb(204, 204, 204) !important; border-radius: 3px !important; background-color: rgb(245, 245, 245) !important;">continuation是對(duì)某計(jì)算階段結(jié)果做處理的，因此規(guī)定kont為一個(gè)單參數(shù)輸入，單參數(shù)輸出的函數(shù)，即kont的類(lèi)型是a->b
因此，按CPS約定改寫(xiě)后的fact_rec如下：
fact_rec = (x, kont) => x == 1 ? kont(1) : fact_rec(x-1, res => kont(x*res))
當(dāng)我們運(yùn)行fact_rec(4, r=>r)，就可以得到結(jié)果24
模擬一下fact_rec(3, r=>r)的執(zhí)行過(guò)程，就會(huì)發(fā)現(xiàn)，解釋器會(huì)先將計(jì)算鏈分解展開(kāi)：
fact_rec(3, r=>r)fact_rec(2, res => (r=>r)(3*res))fact_rec(1, res => (res => (r=>r)(3*res))(2*res)) (res => (res => (r=>r)(3*res))(2*res))(1)
當(dāng)然，這種風(fēng)格非常反人類(lèi)，因?yàn)?strong style="margin: 0px; padding: 0px;">內(nèi)層函數(shù)被外層函數(shù)的參數(shù)分在兩端包裹住，不符合人類(lèi)的線(xiàn)性思維
我們寫(xiě)成下面這種符合直覺(jué)的形式
1 ---> res => 2*res ---> res => 3*res ---> res => res
鏈上每一個(gè)步驟的輸出作為下一步驟的輸入
當(dāng)解釋器展開(kāi)成上面的計(jì)算鏈后，便開(kāi)始從左往右的計(jì)算，直到運(yùn)行完所有的計(jì)算步驟
需要注意到的是，因?yàn)?code style="margin: 1px 5px; padding: 0px 5px !important; line-height: 1.8; vertical-align: middle; display: inline-block; font-family: 'Courier New', sans-serif !important; font-size: 12px !important; border: 1px solid rgb(204, 204, 204) !important; border-radius: 3px !important; background-color: rgb(245, 245, 245) !important;">kont承擔(dān)了函數(shù)后續(xù)所有的計(jì)算流程，因此不需要返回，所以對(duì)kont的調(diào)用便是尾調(diào)用
當(dāng)我們把程序中所有的函數(shù)都按CPS約定改寫(xiě)以后，程序中所有的函數(shù)調(diào)用就都變成了尾調(diào)用了，而這正是本文的目的
這個(gè)改寫(xiě)的過(guò)程就稱(chēng)為CPS變換
CPS約定簡(jiǎn)約，卻可顯式地控制程序的執(zhí)行，程序里各種形式的控制流都可以用它來(lái)表達(dá)（比如協(xié)程、循環(huán)、選擇等），
所以很多函數(shù)式語(yǔ)言的實(shí)現(xiàn)都采用了CPS形式，將語(yǔ)句的執(zhí)行分解成一個(gè)小步驟一次執(zhí)行，
當(dāng)然，也因?yàn)镃PS形式過(guò)于簡(jiǎn)潔，表達(dá)起來(lái)過(guò)于繁瑣，可以看成一種高級(jí)的匯編語(yǔ)言
Trampoline技法
經(jīng)過(guò)CPS變換后，遞歸函數(shù)已經(jīng)轉(zhuǎn)化成一條長(zhǎng)長(zhǎng)的continuation鏈
尾調(diào)用函數(shù)層層嵌套，永不返回，然而在缺乏尾調(diào)用優(yōu)化的語(yǔ)言中，并不知曉函數(shù)不會(huì)返回，狀態(tài)、參數(shù)壓棧依舊會(huì)發(fā)生，因此需要手動(dòng)強(qiáng)制彈出下一層調(diào)用的函數(shù)，禁止解釋器的壓棧行為，這就是所謂的Trampoline
因?yàn)?code style="margin: 1px 5px; padding: 0px 5px !important; line-height: 1.8; vertical-align: middle; display: inline-block; font-family: 'Courier New', sans-serif !important; font-size: 12px !important; border: 1px solid rgb(204, 204, 204) !important; border-radius: 3px !important; background-color: rgb(245, 245, 245) !important;">continuation只接受一個(gè)結(jié)果參數(shù)，然后調(diào)用另一個(gè)continuation處理結(jié)果，因此我們需要顯式地用變量v、kont分別表示上一次的結(jié)果、下一個(gè)continuation，然后在一個(gè)循環(huán)里不斷地計(jì)算continuation，直到處理完整條continuation鏈，然后返回結(jié)果
function trampoline(kont_v) // kont_v = { kont: ..., v: ... }{
while(kont_v.kont)
kont_v = kont_v.kont(kont_v.v);
return kont_v.v;}kont_v.kont是一個(gè)bounce，每次執(zhí)行kont_v.kont(kont_v.v)時(shí)，都會(huì)根據(jù)上次結(jié)果計(jì)算出本次結(jié)果，然后彈出下一級(jí)continuation
具體應(yīng)用可看下面的例子
線(xiàn)性遞歸的CPS變換：求和
求和的遞歸實(shí)現(xiàn)：
sum = x => { if(x == 0) return 0; else return x + sum(x-1) }當(dāng)參數(shù)過(guò)大，比如sum(4000000)，提示Uncaught RangeError: Maximum call stack size exceeded，爆棧了！
現(xiàn)在，我們通過(guò)CPS變換，將上面的函數(shù)改寫(xiě)成尾遞歸形式：
首先，為sum多添加一個(gè)參數(shù)表示continuation，表示對(duì)計(jì)算結(jié)果進(jìn)行的后續(xù)處理，
sum = (x, kont) => ...
其中，kont是一個(gè)單參數(shù)函數(shù)，形如 res => ...，表示對(duì)結(jié)果res的后續(xù)處理
然后逐情況考慮：
當(dāng)x == 0時(shí)，計(jì)算結(jié)果直接為0，并將kont應(yīng)用到結(jié)果上,
sum = (x, kont) => { if(x == 0) return kont(0); else ... }當(dāng)x != 0時(shí)，需要先計(jì)算x-1的求和，然后將計(jì)算結(jié)果與x相加，然后把相加結(jié)果輸入kont中，
sum = (x, kont) => {
if(x == 0) return kont(0);
else return sum( x - 1, res => kont(res + x) ) };}好了，現(xiàn)在我們已經(jīng)完成了sum的CPS變換，大家仔細(xì)看看，上面的函數(shù)已經(jīng)是尾遞歸形式啦。
現(xiàn)在還有最后的問(wèn)題，怎么去調(diào)用？比如要算4的求和，sum(4, kont)，這里的kont應(yīng)該是什么呢？
可以這樣想，當(dāng)我們計(jì)算出結(jié)果，后續(xù)的處理就是把結(jié)果簡(jiǎn)單地輸出，因此kont應(yīng)為res => res
sum(4, res => res)
把上面的代碼復(fù)制到Console，運(yùn)行就能得到結(jié)果10
下面我們模擬一下sum(3, res => res)的運(yùn)作，以對(duì)其有個(gè)直觀(guān)的認(rèn)識(shí)
sum( 3, res => res )sum( 2, res => ( (res => res)(res+3) ) )sum( 1, res => ( res => ( (res => res)(res+3) ) )(res+2) ) )sum( 0, res => ( res => ( res => ( (res => res)(res+3) ) )(res+2) ) )(res+1) )// 展開(kāi)continuation鏈( res => ( res => ( res => ( (res => res)(res+3) ) )(res+2) ) )(res+1) )(0)// 收縮continuation鏈( res => ( res => ( (res => res)(res+3) ) )(res+2) )(0+1) ( res => ( (res => res)(res+3) ) )(0+1+2) (res => res)(0+1+2+3)6
從上面的展開(kāi)過(guò)程可以看到，sum(x, kont)分為兩個(gè)步驟：
展開(kāi)
continuation鏈，尾調(diào)用函數(shù)層層嵌套，先做的continuation在外層，后做的continuation放內(nèi)層，這也是CPS反人類(lèi)的原因，人類(lèi)思考閱讀都是線(xiàn)性的（從上往下，從左往右），而CPS則是從外到內(nèi)，而且外層函數(shù)和參數(shù)包裹著內(nèi)層，閱讀時(shí)還需要眼睛在左右兩端不斷游離收縮
continuation鏈，不斷將外層continuation計(jì)算的結(jié)果往內(nèi)層傳
當(dāng)然，現(xiàn)在運(yùn)行sum(4000000， res => res)，依然會(huì)爆棧，因?yàn)?code style="margin: 1px 5px; padding: 0px 5px !important; line-height: 1.8; vertical-align: middle; display: inline-block; font-family: 'Courier New', sans-serif !important; font-size: 12px !important; border: 1px solid rgb(204, 204, 204) !important; border-radius: 3px !important; background-color: rgb(245, 245, 245) !important;">js默認(rèn)并沒(méi)有對(duì)尾調(diào)用做優(yōu)化，我們需要利用上面的Trampoline技法將其改成循環(huán)形式（上文已經(jīng)提過(guò)，尾遞歸和循環(huán)等價(jià)）
可是等等，上面說(shuō)的Trampoline技法只針對(duì)于收縮continuation鏈過(guò)程，可是sum(x, kont)還包括展開(kāi)過(guò)程啊？別擔(dān)心，可以看到展開(kāi)過(guò)程也是尾遞歸形式，我們只需稍作修改，就可以將其改成continuation的形式：
( r => sum( x - 1, res => kont(res + x) )(null)
如此便可把continuation鏈的展開(kāi)和收縮過(guò)程統(tǒng)一起來(lái)，寫(xiě)成以下的循環(huán)形式：
function trampoline(kont_v){
while(kont_v.kont)
kont_v = kont_v.kont(kont_v.v);
return kont_v.v;}function sum_bounce(x, kont){
if(x == 0) return {kont: kont, v: 0};
else return { kont: r => sum_bounce(x - 1, res => {
return { kont: kont,
v: res + x }
} ),
v: null };}var sum = x => trampoline( sum_bounce(x, res =>
{return { kont: null,
v: res } }) )OK，以上便是改成循環(huán)形式的尾遞歸寫(xiě)法，
把sum(4000000)輸入Console，稍等片刻，便能得到答案8000002000000
樹(shù)狀遞歸的CPS變換：Fibonacci
因?yàn)?code style="margin: 1px 5px; padding: 0px 5px !important; line-height: 1.8; vertical-align: middle; display: inline-block; font-family: 'Courier New', sans-serif !important; font-size: 12px !important; border: 1px solid rgb(204, 204, 204) !important; border-radius: 3px !important; background-color: rgb(245, 245, 245) !important;">Fibonacci是樹(shù)狀遞歸，轉(zhuǎn)換起來(lái)要比線(xiàn)性遞歸的sum麻煩一些，先寫(xiě)出普通的遞歸算法：
fib = x => x == 0 ? 1 : ( x == 1 ? 1 : fib(x-1) + fib(x-2) )
同樣，當(dāng)參數(shù)過(guò)大，比如fib(40000)，就會(huì)爆棧
開(kāi)始做CPS變換，有前面例子鋪墊，下面只講關(guān)鍵點(diǎn)
添加kont參數(shù)，則fib = (x, kont) => ...
分情況考慮
當(dāng)x == 0 or 1，fib = (x, kont) => x == 0 ? kont(1) : ( x == 1 ? kont(1) ...
當(dāng)x != 1 or 1，需要先計(jì)算x-1的fib，再計(jì)算出x-2的fib，然后將兩個(gè)結(jié)果相加，然后將kont應(yīng)用到相加結(jié)果上
fib = (x, kont) => x == 0 ? kont(1) : x == 1 ? kont(1) : fib( x - 1, res1 => fib(x - 2, res2 => kont(res1 + res2) ) )
以上便是fib經(jīng)CPS變換后的尾遞歸形式，可見(jiàn)難點(diǎn)在于kont的轉(zhuǎn)化，這里需要好好揣摩
最后利用Trampoline技法將尾遞歸轉(zhuǎn)換成循環(huán)形式
function trampoline(kont_v){
while(kont_v.kont)
kont_v = kont_v.kont(kont_v.v);
return kont_v.v;}function fib_bounce(x, kont){
if(x == 0 || x == 1) return {kont: kont, v: 1};
else return {
kont: r => fib_bounce( x - 1,
res1 =>
{
return {
kont: r => fib_bounce(x - 2,
res2 =>
{
return {
kont: kont,
v: res1 + res2 }
}),
v: null
}
} ),
v: null
};}var fib = x => trampoline( fib_bounce(x, res =>
{return { kont: null,
v: res } }) )OK，以上便是改成循環(huán)形式的尾遞歸寫(xiě)法，
在console中輸入fib(5)、fib(6)、fib(7)可以驗(yàn)證其正確性，
當(dāng)然，當(dāng)你運(yùn)行fib(40000)時(shí)，發(fā)現(xiàn)的確沒(méi)有提示爆棧了，但是程序卻卡死了，何也？
正如我在前言說(shuō)過(guò)，這種方法并不會(huì)降低樹(shù)狀遞歸算法的時(shí)間復(fù)雜度，只是將占用的?？臻g以閉包鏈的形式轉(zhuǎn)移至堆上，免去爆棧的可能，但是當(dāng)參數(shù)過(guò)大時(shí)，運(yùn)行復(fù)雜度過(guò)高，continuation鏈過(guò)長(zhǎng)也導(dǎo)致大量?jī)?nèi)存被占用，因此，優(yōu)化算法才是王道
CPS變換法則
對(duì)于基本表達(dá)式如數(shù)字、變量、函數(shù)對(duì)象、參數(shù)是基本表達(dá)式的內(nèi)建函數(shù)(如四則運(yùn)算等)等，不需要進(jìn)行變換，
若是函數(shù)定義，則需要添加一個(gè)參數(shù)kont，然后對(duì)函數(shù)體做CPS變換
若是參數(shù)位置有函數(shù)調(diào)用的函數(shù)調(diào)用，fn(simpleExp1, exp2, ..., expn)，如exp2就是第一個(gè)是函數(shù)調(diào)用的參數(shù)
則過(guò)程比較復(fù)雜，用偽代碼表述如下：(<<...>>內(nèi)表示表達(dá)式， <<...@exp...>表示對(duì)exp求值后再代回<<...>>中)：
cpsOfExp(<< fn(simpleExp1, exp2, ..., expn) >>, kont)= cpsOfExp(exp2, << r2 => @cpsOfExp(<< fn(simpleExp1, r2, ..., expn) >>, kont) >>)
順序表達(dá)式的變換亦與上類(lèi)似
當(dāng)然這個(gè)問(wèn)題不是這么容易講清楚，首先你需要對(duì)你想要變換的語(yǔ)言了如指掌，知道其表達(dá)式類(lèi)型、求值策略等，JavaScript語(yǔ)法較為繁雜，解釋起來(lái)不太方便，
之前我用C++模板寫(xiě)過(guò)一個(gè)CPS風(fēng)格的Lisp解釋器，日后有時(shí)間以此為例詳細(xì)講講
延伸閱讀
- 最短路徑之Dijkstra算法和Floyd-Warshall算法 2017-07-26
- 基于Json序列化和反序列化通用的封裝 2017-07-25
- 游戲里的跨地圖尋路算法 2017-07-25
- webgl開(kāi)發(fā)第一道坎——矩陣與坐標(biāo)變換 2017-07-25
- 一篇文章搞懂柏林噪聲算法，附代碼講解 2017-07-24
- 第2章 rsync算法原理和工作流程分析 2017-07-24
- 基于Entity Framework的自定義分頁(yè)，增刪改的通用實(shí)現(xiàn) 2017-07-24
- Nancy基于JwtBearer認(rèn)證的使用與實(shí)現(xiàn) 2017-07-24
- 基于深度學(xué)習(xí)的圖像風(fēng)格轉(zhuǎn)換 2017-07-21
- 數(shù)據(jù)結(jié)構(gòu)與算法 2017-07-21
最短路徑之Dijkstra算法和Floyd-Warshall算法