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 行代码」
;; 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 (lambda (exp) (letrec ([trivial? (lambda (x) (memq x '(zero? add1 sub1)))] [id (lambda (v) v)] [ctx0 (lambda (v) `(k ,v))] ; tail context [fv (let ([n -1]) (lambda () (set! n (+ 1 n)) (string->symbol (string-append "v" (number->string n)))))] [cps1 (lambda (exp ctx) (pmatch exp [,x (guard (not (pair? x))) (ctx x)] [(if ,test ,conseq ,alt) (cps1 test (lambda (t) (cond [(memq ctx (list ctx0 id)) `(if ,t ,(cps1 conseq ctx) ,(cps1 alt ctx))] [else (let ([u (fv)]) `(let ([k (lambda (,u) ,(ctx u))]) (if ,t ,(cps1 conseq ctx0) ,(cps1 alt ctx0))))])))] [(lambda (,x) ,body) (ctx `(lambda (,x k) ,(cps1 body ctx0)))] [(,op ,a ,b) (cps1 a (lambda (v1) (cps1 b (lambda (v2) (ctx `(,op ,v1 ,v2))))))] [(,rator ,rand) (cps1 rator (lambda (r) (cps1 rand (lambda (d) (cond [(trivial? r) (ctx `(,r ,d))] [(eq? ctx ctx0) `(,r ,d k)] ; tail call [else (let ([u (fv)]) `(,r ,d (lambda (,u) ,(ctx u))))])))))]))]) (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 (cps '(lambda (n) ((lambda (fact) ((fact fact) n)) (lambda (fact) (lambda (n) (if (zero? n) 1 (* 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