学习笔记：Continuation-passing Style

说来惭愧，虽然对于 CPS transform 这个概念略有耳闻（当时的理解是一种将普通递归调用变化为尾递归的方法），但是对于 CPS 这个概念还是在看轮子哥的文章 时才想起去详细了解。终究还是CS基础不牢。

Definition

In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which sets out the first version of the Scheme programming language.^[1][2] John C. Reynolds gives a detailed account of the numerous discoveries of continuations.^[3]

简单来说，就是一种程序调用方式，在每次函数调用时通过传参决定下一步执行的内容。

Wikipedia 上有一个直观的例子显示 CPS 方式与 Direct 方式的区别

Direct:

(define (pyth x y)
  (sqrt (+ (* x x) (* y y))))

CPS:

(define (pyth& x y k)
  (*& x x (lambda (x2)
            (*& y y (lambda (y2)
                      (+& x2 y2 (lambda (x2py2)
                                  (sqrt& x2py2 k))))))))

其中 +& *& 等表示对应operator的CPS版本，即接受第三个参数。Wikipedia上亦提供了一段 transformer：

(define (cps-prim f)
  (lambda args
    (let ((r (reverse args)))
      ((car r) (apply f
                 (reverse (cdr r)))))))
(define *& (cps-prim *))
(define +& (cps-prim +))

Use and implementation

群众喜闻乐见的语言JavaScript中臭名昭著的 callback hell 其实就有点CPS的味道（当然不算是full CPS）。

function fuckJson(url, callback) {
    makeAjax(url, (err, data) => err ? callback(err) : callback(null, data))
}

fuckJson("/holy-shit", (err, data) => {
    if(err) console.log("error!");
    addEntry(data);
})

CPS应用中最重要的地方当然不是引起开发者的怨念，而是在 functional programming 中进行控制流的优化（这个词是我乱说的，我也不知道准确的定义是啥……）

例如利用 CPS transform 实现将同步代码展开成回调地狱（2333333）continuation

例如 C# （包括现在的伪 EcmaScript 2016 实现）中的 await/async ，实质上也是一种形式的 CPS 变换（ES7是借助了Promise）

然后其它的黑魔法，以我的姿势水平也触及不到了……