怎樣理解 Continuation-passing style?

01-06

呃, 這東西首先是用 Wiki 的... http://en.wikipedia.org/wiki/Continuation-passing_style
搜了一遍, 中文資源不是一般的少..

要理解CPS，首先要理解Continuation是什麼。

計算是有先後順序的，比如要在Racket里計算1+2+3:

(+ 1 (+ 2 3))

顯然需要首先計算（+ 2 3），再計算（+ 1 5），在得到（+ 2 3）的結果之前是無法計算(+ 1 ...)的。

我們把（+ 1 ...)這個表達式中缺少的部分叫做hole，一個帶有hole的表達式就是continuation，它需要另一個東西來填補這個hole才能進行進一步的計算（這個其實就是Evaluation Contexts的概念）。

Continuation是鏈式的，一個Continuation還鏈接著另一個Continuation。可以把Continuation理解為[e_w_hole, cont]的二元組，完成當前的e_w_hole的求值後，把結果填補給下一個cont的hole，直到cont是halt停機為止。比如

(+ 1 (+ 2 (+ 3 4)))

(+ 3 4)的continuation是 [(+ 2 ...), cont1]，而cont1則是[(+ 1 ...), halt]。

那麼CPS就是把continuation作為一個函數顯式地暴露出來，這個函數的參數就是hole，當我們apply這個continuation（函數）就是在填補這個hole，並進行進一步的計算。

上面的代碼很容易轉換為CPS（雖然加法操作是primitive的，但我們仍然可以自己編寫一個CPS版本的k+來模擬，同時我們還有一個identity continuation作為halt）：

(define k+ (lambda (x y k) (k (+ x y)))) (define id (lambda (x) x)) (k+ 2 3 (lambda (five) (k+ 1 five id)))

至於call/cc其實並不屬於pure CPS的一部分，call/cc是語言提供給程序員用以獲得當前continuation的機制。

上面的(+ 1 (+ 2 3))例子也可以用call/cc來實現:

(+ 1 (call/cc (lambda (k) (k (+ 2 3)))))

這時候k便是當前的continuation，也就是(+ 1 ...)。
通過獲取當前的continuation，實際上獲得了『此刻』以後所有的計算過程，於是便可以做一些有意思的事情，比如nont-deterministic的amb，比如coroutine等。

因為最少形式的純CPS的程序只需要有lambda和function application，因此CPS程序中所有的遞歸函數調用都是尾遞歸。

比如正常map函數可以這樣實現：

(define (map f xs) (if (empty? xs) "() (cons (f (first xs)) (map f (rest xs))))) (map (λ (x) (+ x 1)) "(1 2 3))

在這裡並不是尾遞歸，因為在第3行在(rest xs)上調用完map之後我們仍然有continuation要做，就是和(f (first xs))的結果cons起來。

而CPS版的map則是：

(define (map-k f xs k) (if (empty? xs) (k "()) (f (first xs) (λ (v) (map-k f (rest xs) (λ (rest-v) (k (cons v rest-v)))))))) (map-k (λ (x k) (k (+ x 1))) "(1 2 3) (λ (x) x))

可以看到，在map-k中，所有的函數調用都是尾遞歸，也就不存在由遞歸引起的stack空間的消耗（在支持tail-call opt的語言中）。

CPS在在過去是函數式語言常用的IR，在編譯和程序分析中有很多應用。當程序被轉換為CPS的時候，Continuation是直接在lexical scope中暴露出來的，而一切control flow的轉移都通過continuation來實現，這樣可以直接進行control flow analysis。在進行Partial Evaluation的時候CPS也可以獲得更好的特化效果。

但是CPS的可讀性太差了，後來direct style的A-Normal Form在編譯和程序分析中流行起來。而ANF和CPS是等價的，A-Normalize的過程等價於CPS convert-&>Beta normalize-&>un-CPS convert，請參考The Essence of Compiling with Continuation。

CPS同Static Single Assignment也是correspondence的，在CPS中每個變數都通過lambda來引入，變數的mutation也是通過新的continuation來引入；正對應於SSA中每個變數只被賦值一次，並dominate接下來的use，而Phi Node則在CPS中通過對於同一個cont傳入不同的值來實現。可參考A Correspondence between Continuation Passing Style and Static Single Assignment Form。

CPS同Monad也是等價的，理論上任何Monad都可以通過等價的CPS形式表達出來，這部分可以看The Essence of Functional Programming。

很久以前聽說CPS可以用來表達一切你能想到的控制流，所以我就嘗試了一下。我做了個小語言（tinymoe/StandardLibrary.txt at master · vczh/tinymoe · GitHub），在語法上支持CPS變換，然後除了select-case和地櫃之外什麼都不提供，最終用這兩個東西（見鏈接，這是我用這個語言寫的一個庫）做出了所有的if、for、try-catch、甚至是有些人莫名其妙的引以為豪的coroutine等基礎設施。然後我把CPS變換後的代碼編譯成了C#，在實際上做到了，凡是尾遞歸都會自動在stack上變成循環的這樣一個東西。

實現的時候我山寨了x86處理器做exception handling的小技巧，把很多continuation串成了一個鏈表，然後就可以在上面選擇你要jump到什麼地方去了。在看這段代碼的時候，不要通過debug，而要通過在紙上推導來看，不然是看不懂的（除非你原本就明白）。

經典的CPS定義就是說所有閉包都返回void，算出來的結果用調用一個參數指向的閉包返回，我的tinymoe作為一個教學項目也是這麼做的，概念都很直接。不過實際上這也只是一個概念，就跟說lambda-calculus跟圖靈機等價的這麼個說法差不多。你當然可以做，不過實際上沒什麼意義。真正在處理語言的時候，很少會出現真正的continuation，都是用很多奇怪的技巧，最後產生一些高度inline後的代碼，然後就什麼都看不出來了，就像C#的async-await和yield return一樣。

「CPS 就是把用於經典邏輯和直覺邏輯間命題轉換的 G?del–Gentzen 轉換，經 Curry–Howard correspondence 應用到證明過程表示的自然結果，有什麼難理解的？！」

EOPL 里有很好的解釋，看第五章Continuation-Passing Interpreters 和第六章 Continuation-passing Style。

ibm的開發者wiki看過嗎？那上面的continuation講的挺好的。

2014.3.1更新

====================

我又看了CPS方面的很多資料。

總結一下，

Dan Friedman的the little schemer第八章給出了一個continuation的簡單例子。真的很簡單。基本上沒有講引入continuation的目的，以及怎麼做CPS轉換。

接下來只需要看https://cgi.soic.indiana.edu/~c311/lib/exe/fetch.php?media=cps-notes.scm ，

這是我看過的最清晰最簡單的關於cps的文章了，indiana不愧是programming languages的研究重鎮。

再接下來可以看一下sicp第四章里利用continuation實現的amb。

之後其餘的文章應該都大同小異，推薦可以看看王垠的notes。

http://docs.huihoo.com/homepage/shredderyin/wiki/ContinuationNotes.html

https://cgi.soic.indiana.edu/~c311/lib/exe/fetch.php?media=cpslecture.scm

C311/B521/A596 Programming Languages [CPS Refresher]

@vczh 的感覺太高端了

摘自 @朴靈的書里的代碼

Continuation Passing Style

function foo(x, bar) { return bar(x); }

業務重點由返回值轉移到了回調函數中。

CPS是一種programming的方法／格式。一般這麼做是因為和recursive相比，它需要更少的memory/stack和更少的control context存儲，尤其是在call數字很大的時候會明顯。因為當用recursive function的時候，在沒完成之前要用多少memory，存多少control context是不確定的。

一般function做的事情僅僅只是把當前evaluate的結果pass給control context。CPS是會多一個argument，用來pass control context給function。這樣它就會知道在evaluate這一步之後下一步要做什麼。

不過每一種style，imperative/CPS/一般recursive，本身都是equivalent的。

http://blog.csdn.net/cnnzp/article/details/7832106

http://jasonwood1986.wordpress.com/2007/03/04/continuation-pass-style/

http://article.yeeyan.org/view/213582/179432

https://groups.google.com/forum/#!topic/scalacn/c_lZENqhrLY

http://stackoverflow.com/questions/8544127/why-continuation-passing-style

http://docs.huihoo.com/homepage/shredderyin/wiki/ContinuationPassingStyle.html

http://fillano.blog.ithome.com.tw/post/257/17737

http://www.newsmth.net/nForum/#!article/FuncProgram/1669

http://daweibalong.iteye.com/blog/1882795

認真看完這些不懂你再問

我們教授推薦的:

By example: Continuation-passing style in JavaScript

最簡單的例子之一 (Scheme):

(define (fact/k n k)

(cond

[(= n 1) (k 1)]

[else (fact/k (sub1 n)

(lambda (r)

(k (* n r))))]))

(fact/k 5 (lambda (r) r))

=&>120

Continuation passing style (CPS) is a style of writing programs in which the computation that happens after a function returns is packaged as a function and passed to that function instead where it is called directly.

In CPS, functions do not return. The computation that happens next is passed along as an argument in the form of a continuation function.

可以看我兩年前寫的一個模擬內核調用的程序 https://github.com/xudifsd/lab/blob/master/Schemelab/sched.scm