limu
2013-03-03 19:34:44 +08:00
他自己以前说过:自动的CPS变换. 用伪C代码解释一个:
比如, 变换前的:
int sum(int* arr, int len){
if(len <= 0) return 0; else return arr[0] + sum(arr+1, len-1);
}
调用: print(sum([1,2,3,4], 4)) //输出 10;
变换后的:
void sum_cps(int sum, int* arr, int len, void (callback*)(int)){
if(len <= 0) callback(sum);
else sum_cps(sum + arr[0], arr+1, len-1, callback);
}
调用:(sum_cps, 0, [1,2,3,4], 4, print);
这样变换以后, 自动变成尾递归. sum 每次递归调用需要把arr[0] 压栈, len大时会堆栈溢出, 而sum_cps,需要的栈为0, 不会堆栈溢出.
递归调用是FP的根本, 所以自动实现这种变换意义很大.