Cps变换

Table of Contents

什么是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

参考资料

Date: 2022-06-21 Tue 14:58

Author: yangk

Created: 2023-01-03 Tue 12:43

hello-world