JavaScript玩转Clojure大法之 - Trampoline
- JavaScript玩转Clojure大法之 - 并发编程
- JavaScript玩转Clojure大法之 - Transducer
- JavaScript玩转Clojure大法之 - Trampoline
- JavaScript玩转Clojure大法之 - Macro (1)
在函数式编程中, 递归可以说是最关健甚至唯一的循环手段
Clojure的recur可以保证得到 尾递归 优化, 而相互递归则不能用recur来保证得到优化, 因此 另一个大法出现了 – Trampoline

Trampoline 翻译成中文是蹦床, 蹦~蹦蹦蹦蹦 (自己脑补intel BGM)
如果你看过老友记这集(Friends: The One with Ross's New Girlfriend), 应该记得这个梗
Ross: you hang up first
Julie: No, you hang up first
Ross: No, you hang up first …
ok, 这就是相互递归(mutual recursion)
在继续解释trampoline是如何优化相互递归之前, 可能有些同学不太清楚什么是尾递归优化, 当然嫌我啰嗦的可以直接坐 电梯直达.
尾递归(tail recursion)
又要拿一个被举烂了的例子 - 求n的阶乘
很容易就可以写出来
function fact(n){ if(n==0)return 1; return n*fact(n-1); }
好吧, 这就是典型的非尾递归, 因为最后一个操作并不是调用自己, 而是 乘法
想想最后一行, 先算出 fact(n-1)
, 然后乘n, 返回
那么怎么才是尾递归, 当然是最后一个操作一定是调用自己.
function fact(n, acc){ if(n==0)return acc; return fact(n-1, acc*n) }
两个地方值得注意
- 看到
acc
了没有, 这就是典型的尾递归最常见的东西, 用来累计每次递归运算结果 - fact函数的最后一个操作是fact本身
由于tail recur非常容易改写成循环, 编译器容易对其进行优化
function fact(n){ var acc=1,i=n while(i!=0){ acc=acc*i; i-=1; } return acc }
有没有觉得尾递归和循环非常像, 唯一的区别是
- 尾递归用参数重新绑定递减的n
- 尾递归用参数重新绑定叠加值acc
- 循环直接改变变量i来进行递减
- 循环叠加变量acc
但思路是一模一样的
在clojure里, 尾递归是用
recur
来保证(scalar貌似是@tail annotation), 好处是
- 用recur的一定是尾递归, 直接优化
- 编译器可以检查recur出现的位置是否为tail
相互递归(mutual recursion)
相互递归由于是函数之间的互相调用, 则不能像尾递归一样直接优化成循环就完事.
DFA
举个最简单的例子, 相互递归经常用于状态机的实现, 比如自动贩卖机, 假设这台贩卖机非常简单, 只吃五块,只卖巧克力
那么输入集是 [五块, 选巧克力, 找零]
, 所以贩卖机正常的process是类似
5块 -> 巧克力 -> 找2块
好吧, 我们来实现一把
function eat_money(input_seq){ var input = input_seq.shift() if(input== '五块') console.log('收到呢,选个巧克力吧^_^') choose(input_seq) else eat_money(input_seq) } function choose(input_seq){ var input = input_seq.shift() if(input== '巧克力') console.log('选了巧克力, 按下找零按钮, 我还欠你两块钱哦') changes(input_seq) else choose(input_seq) } function changes(input_seq){ var input = input_seq.shift() if(input=='找零') console.log('欢迎再次光临') eat_money(input_seq) else changes(input_seq) }
假设我是个怪蜀黍QA,来到这个贩卖机上怒点这样以系列操作, 看我们的贩卖机有没有疯掉
['巧克力', '巧克力', '找钱', '五块', '找钱', '五块', '巧克力', '五块', '找钱']
很好
现在问题来了, 如果我的 input_seq
非常长, 比如
for(var n=15;n>0;n--){ input_seq=input_seq.concat(input_seq) } input_seq.length // => 294912
现在 input_seq
非常大, 再试试(请到node上试)
... 收到呢,选个巧克力吧^_^ RangeError: Maximum call stack size exceeded ...
爆栈了吧
Trampoline
Trampoline就是用来解决相互递归爆栈的问题, 等等, 什么是Trampoline
trampoline是一个函数:
- 接受一个函数, 一个或多个函数的参数
- 调用该函数
- 如果返回值是个函数, 继续调用
- 如果返回值不是函数, 停止
比如可以把贩卖机简单的改造一下, 让他返回函数, 而不是直接调用其他函数, 注意第6行
1: function eat_money(input_seq){ 2: if(input_seq.length==0)return 3: var input = input_seq.shift() 4: if(input== '五块'){ 5: console.log('收到呢,选个巧克力吧^_^') 6: return function(){ 7: return choose(input_seq) 8: } 9: }else{ 10: return function(){ 11: return eat_money(input_seq) 12: } 13: } 14: }
这样每次调用eat_money其实返回一个闭包, 需要再调用一下才能真的执行 choose
函数.
经过这样的改造以后(当然其他函数也要类似的加闭包), 就可以用 trampoline
来执行他们了
mori.trampoline(eat_money,input_seq)
由于eat_money返回一个闭包,也就是函数, trampoline会继续执行这个返回的闭包,直到返回的不是函数为止
而trampoline优化之前的 eat_money
, 其实就是把最后调用的函数压到调用栈里, 然后
压入调用栈的这个函数比如是 choose
又调用另一个函数比如 changes
, 然后一直压压压, 压到最后再从栈里弹出来一个一个执行.

function eat_money(input_seq){ return choose(input_seq){ return changes(input_seq){ return ... } } }
所以如果压入的函数个数超过栈的容量, 栈 菊花 就被爆了
而trampoline则是在函数最后返回一个闭包, 闭包内的递归调用并未被调用, 也就是未被压栈, 所以是这样的

var res = eat_money(input_seq) while(true){ if(typeof res =='function')res = res() else break }
优化成循环了不是.
完整代码, 如果uncomment 注释掉的代码浏览器会timeout, 请在node上跑, 反正不会爆栈
JS Bin