Cps变换
什么是CPS呢？
- Continuation-Passing Style, 有道翻译：连续传球风格编程，说的简单点，其实就是函数通过回调传递结果
例1:js版本
原味
function foo(x) {
return x ;
}
CPS
function cps_foo(x, return_point) {
return return_point (x) ;
}
CPS 多了一个参数 return_point，return_point 来自function的调用者 ，是调用者所在的context，调用者将这个context 传递给cps，这样cps 就无须利用额外的工具（比如堆栈）去查询调用者的环境在哪里(调用位置)，以便返回，而是直接进入这个环境：return_point (x)。
这便是 CPS 的初衷 —— 去掉层层嵌套的世界。行话讲就是 desugar（脱糖）。
Syntax sugar 是为了方便人类的表达和理解，给编程语言的核心套上的一层好吃好看的外衣，而对机器对程序的解释，需要将其还原到最本质的结构，以便机械化处理和优化，这 就是脱糖的意义。
例2:java版本
原味
public class Demo {
public static long plus(int i1, int i2) {
return i1 + i2;
}
public static void main(String[] args) {
System.out.println(plus(1, 2));
}
}
CPS
public class CpsDemo {
interface Continuation {
void next(int result);
}
public static void plus(int i1, int i2, Continuation continuation){
continuation.next(i1 + i2);
}
public static void main(String[] args){
plus(1, 2, result -> System.out.println(result));
}
}
王垠的「40 行代码」
1: ;; A simple CPS transformer which does proper tail-call and does not;; duplicate contexts for if-expressions.;; author: Yin Wang (yw21@cs.indiana.edu)(load "pmatch.scm")(define cps 2: (lambda (exp) 3: (letrec 4: ([trivial? (lambda (x) (memq x '(zero? add1 sub1)))] 5: [id (lambda (v) v)] 6: [ctx0 (lambda (v) `(k ,v))] ; tail context 7: [fv (let ([n -1]) 8: (lambda () 9: (set! n (+ 1 n)) 10: (string->symbol (string-append "v" (number->string n)))))] 11: [cps1 12: (lambda (exp ctx) 13: (pmatch exp 14: [,x (guard (not (pair? x))) (ctx x)] 15: [(if ,test ,conseq ,alt) 16: (cps1 test 17: (lambda (t) 18: (cond 19: [(memq ctx (list ctx0 id)) 20: `(if ,t ,(cps1 conseq ctx) ,(cps1 alt ctx))] 21: [else 22: (let ([u (fv)]) 23: `(let ([k (lambda (,u) ,(ctx u))]) 24: (if ,t ,(cps1 conseq ctx0) ,(cps1 alt ctx0))))])))] 25: [(lambda (,x) ,body) 26: (ctx `(lambda (,x k) ,(cps1 body ctx0)))] 27: [(,op ,a ,b) 28: (cps1 a (lambda (v1) 29: (cps1 b (lambda (v2) 30: (ctx `(,op ,v1 ,v2))))))] 31: [(,rator ,rand) 32: (cps1 rator 33: (lambda (r) 34: (cps1 rand 35: (lambda (d) 36: (cond 37: [(trivial? r) (ctx `(,r ,d))] 38: [(eq? ctx ctx0) `(,r ,d k)] ; tail call 39: [else 40: (let ([u (fv)]) 41: `(,r ,d (lambda (,u) ,(ctx u))))])))))]))]) 42: (cps1 exp id))));;; tests;; var(cps 'x)(cps '(lambda (x) x))(cps '(lambda (x) (x 1)));; no lambda (will generate identity functions to return to the toplevel)(cps '(if (f x) a b))(cps '(if x (f a) b));; if stand-alone (tail)(cps '(lambda (x) (if (f x) a b)));; if inside if-test (non-tail)(cps '(lambda (x) (if (if x (f a) b) c d)));; both branches are trivial, should do some more optimizations(cps '(lambda (x) (if (if x (zero? a) b) c d)));; if inside if-branch (tail)(cps '(lambda (x) (if t (if x (f a) b) c)));; if inside if-branch, but again inside another if-test (non-tail)(cps '(lambda (x) (if (if t (if x (f a) b) c) e w)));; if as operand (non-tail)(cps '(lambda (x) (h (if x (f a) b))));; if as operator (non-tail)(cps '(lambda (x) ((if x (f g) h) c)));; why we need more than two names(cps '(((f a) (g b)) ((f c) (g d))));; factorial(define fact-cps 43: (cps 44: '(lambda (n) 45: ((lambda (fact) 46: ((fact fact) n)) 47: (lambda (fact) 48: (lambda (n) 49: (if (zero? n) 50: 1 51: (* n ((fact fact) (sub1 n))))))))));; print out CPSed function(pretty-print fact-cps);; =>;; '(lambda (n k);; ((lambda (fact k) (fact fact (lambda (v0) (v0 n k))));; (lambda (fact k);; (k;; (lambda (n k);; (if (zero? n);; (k 1);; (fact;; fact;; (lambda (v1) (v1 (sub1 n) (lambda (v2) (k (* n v2))))))))));; k))((eval fact-cps) 5 (lambda (v) v));; => 120