王垠的「40 行代碼」真如他說的那麼厲害嗎？

12-27

"我有什麼資格說話呢？如果你要了解我的本事，真的很簡單：我最精要的代碼都放在 GitHub 上了。但是除非接受過專門的訓練，你絕對不會理解它們的價值。你會很難想像，這樣一片普通人看起來像是玩具的 40 行 cps.ss 代碼，融入了我一個星期的日日夜夜的心血，數以幾十計的推翻重寫。這段代碼，曾經耗費了一些頂尖專家十多年的研究。一個教授告訴我，光是想看懂他們的論文就需要不止一個月。而它卻被我在一個星期之內悶頭寫出來了。我是在說大話嗎？代碼就擺在那裡，自己去看看不就知道了。當我死後，如果有人想要知道什麼是我上半生最重要的「傑作」，也就是這 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

王垠 cps.ss explained:

1. 背景知識

CPS: Continuation-Passing Style. 有一篇介紹 CPS 通俗易懂的文章（中文翻譯）。

簡單來講，CPS 是一種編程風格：

Javascript:

（原味）

function foo(x) {

return x ;

}

（CPS）

function cps_foo(x, return_point) {

return return_point (x) ;

}

CPS 多了一個參數 return_point，return_point 來自 caller ，是 caller 所在的「世界」，caller 將這個「世界」傳遞給 callee (cps_foo)，這樣 cps_foo 就無須利用額外的工具（比如堆棧）去查詢 caller 的世界在哪裡，以便返回，而是直接進入這個世界：return_point (x)。
這便是 CPS 的初衷 —— 去掉層層嵌套的世界。行話講就是 desugar（脫糖）。Syntax sugar
是為了方便人類的表達和理解，給編程語言的核心套上的一層好吃好看的外衣，而對機器對程序的解釋，需要將其還原到最本質的結構，以便機械化處理和優化，這
就是脫糖的意義。

以函數式編程的觀點來看，return_point 是一個函數，以 C 觀點來看，你可以把它理解為程序地址，或者，以 Matrix 來看，它是 key-maker 打開門進入新世界的那把鑰匙。「世界」上只有一個巨大的程序（比如，你的程序不過是在 chrome 裡面運行的一個小程序，而 chrome 又是在 OS 裡面的一個小程序），return_point 將各種小程序竄連起來了。恩，差不多就是這個意思。只不過，在函數式程序裡面（比如Scheme）裡面，return_point 是函數，而在過程式程序（比如C）裡面它更像是 0x4f36a0c4。

這段 40 多行代碼是給 Scheme 程序脫糖的程序，屬於解釋器的代碼，而不是應用代碼。對其的客觀評價顯然只有設計解釋器的人才能給出。對應用程序員的意義在於，發現每天上班時編寫的代碼多麼無聊，此外並沒有任何實用價值。

2. 運行結果

"x
"(lambda (x k) (k x))
"(lambda (x k) (x 1 k))
"(f x (lambda (v0) (if v0 a b)))
"(if x (f a (lambda (v0) v0)) b)
"(lambda (x k) (f x (lambda (v0) (if v0 (k a) (k b)))))
"(lambda (x k) (let ((k (lambda (v0) (if v0 (k c) (k d))))) (if x (f a k) (k b))))
"(lambda (x k) (let ((k (lambda (v0) (if v0 (k c) (k d))))) (if x (k (zero? a)) (k b))))
"(lambda (x k) (if t (if x (f a k) (k b)) (k c)))
"(lambda (x k) (let ((k (lambda (v0) (if v0 (k e) (k w))))) (if t (if x (f a k) (k b)) (k c))))
"(lambda (x k) (let ((k (lambda (v0) (h v0 k)))) (if x (f a k) (k b))))
"(lambda (x k) (let ((k (lambda (v0) (v0 c k)))) (if x (f g k) (k h))))
"(f
a (lambda (v0) (g b (lambda (v1) (v0 v1 (lambda (v2) (f c (lambda (v3)
(g d (lambda (v4) (v3 v4 (lambda (v5) (v2 v5 (lambda (v6)
v6))))))))))))))
"(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))
120

原代碼中最後一句 ((eval fact-cps ) 5 (lambda (v) v)) 在 racket 中要修改為：
((eval fact-cps (make-base-namespace)) 5 (lambda (v) v)) 才能通過算得 120。

3. 注釋

4. 要點

ctx: 函數在執行(apply)時候的上下文環境，可理解為 C 程序中運行時的棧。

整
個 cps 的（主要）過程就是 if 分支在不斷製造新的 ctx, 而 apply 分支（最後一個分支）不斷在新的 ctx 中 "計算"
（實際上是生成 cps 函數的代碼，而不是真的計算），並返回結果（到上一層 ctx）的過程。這個過程就是 scheme 的基本
eval-apply 過程。（參見SICP第四章）

這是一個解釋器（解釋成為 CPS 風格的代碼），同時也是一個CPS轉換器，正所謂 Compiling with Continuations. 另外，Scheme 這種代碼即數據（字元串列表）的特性，使得編寫生成代碼的代碼相對容易和簡潔。

至於代碼為何有 k 這個命名。呵呵，你可以叫它 kontinuation 或者 klosure.

5. 結論

以自然語言寫作比喻，編寫自解釋器級別的代碼，就像你在寫一本小說，而小說的主角也在寫一本小說，這位主角在描寫你，對你的刻畫會影響到你，你受到影響之後又會改變小說中的主角，從而影響到他對你的描寫。你倆要相安無事，情節合符邏輯地發展，直到最後圓滿的結尾。這比寫一本普通小說可難多了。

Amazing Fun ！

謝謝邀請。我不算很熟悉Scheme，只能勉力為之。我知道我的解讀也許有錯，我也邀請了我熟悉的朋友來回答。他比我懂得更全，應該有幫助。

=== 07/29/2013 更新 ===
當事人到場了。我畢竟是個業餘搞函數式編程的。大家還是不要看我這裡，看@王垠的原版解釋吧。
===================

我大概讀過這段代碼：https://github.com/yinwang0/gems/blob/master/cps.ss。簡單地說，這段代碼做了兩件事，一件事是CPS，也就是自動尾遞歸，第二件事則是用Scheme語言寫了一個Scheme的解釋器。通過他給出的cps函數，我可以用Scheme這個語言的符號系統重新定義所有Scheme的關鍵字，並執行正確的程序語義。換言之，它可以讓這個語言自己解釋自己。本質上，他的代碼是在模仿當初 John McCarthy 發明 Lisp 語言時給出的代碼，但用了Scheme風格重寫了一遍。

這段代碼里有一些相當有技巧性的部分。主要是那個cps1函數。我承認我也沒有完全看懂，但大概能理解它在保持語義的同時基本做到了語言元素的最小化。他的代嗎的31行和37行就是最關鍵的部分，實現了條件分支和遞歸調用。基本的原理並不複雜，主要是利用了Scheme的列表解構拆解元素，最終落實到條件分支和函數調用。如果說得更Scheme風格一點，這個cps函數就是一個自己實現的eval函數。當然是簡化了一些，沒有實現一些更誇張的功能，比如call-with-current-continuation。

註：這個cps的實現中只包含了很少的幾個語言特性：定義常量，定義函數，分支（if）和遞歸。這是滿足一個有意義的最小化描述必需的。如果任意引入語言元素，比如while，循環，則可能就會出現語言元素爆炸的情況，陷入無限自證的邏輯怪圈裡去。

對這段代碼，我自己的建議是，大家可以不必太在乎王垠的宣言。能寫出這段代碼的人，無疑非常熟悉符號推理的一般規則，也具備相當深厚的數學功底，一般人確實是寫不出來。這也符合我對王垠學識的印象。但我也得說，這段代碼對多數工程師而言並沒有實際價值。不懂也無妨。

======
對不熟悉編譯原理和符號推理的朋友們來說，這裡可能需要一些額外的說明。請參見下方。

在編譯原理的世界裡，自舉是一個很重要的話題。一個很經典的例子：GCC語言的編譯器是C語言寫的，但第一個GCC編譯器是用另一個編譯器編譯的；那麼順著這個根源向下跟蹤，我們遲早必須回答這個問題，即世界上第一個編譯器是什麼語言寫的——答案是彙編。那麼這樣下去，我們最終發現，任何程序設計語言都不能完全用自己描述自己。

從工程角度上說，這個問題倒不影響什麼。但是從數學角度上看，這個缺陷則讓很多人頭疼不已，因為它破壞了所謂數學的「美」的原則。這裡的「美」，實際的含義是自解釋。很多符號邏輯研究者都熱衷於找到一種符號體系，能夠使用有限的符號系統描述自身。只要找到了這一點，整個解釋器的設計可以成為一個自己證明自己的，封閉的體系。

喜歡浪漫的文科朋友們可能會記得希臘神話中的烏洛波洛斯，一條首尾相連象徵無窮無盡的蛇。是的，所謂自舉就是符號推演世界的烏洛波洛斯，一種純粹的數學上的和諧和優雅。

可惜對我這個哥德爾定理的信徒而言，這種數學上的美是毫無價值的東西。因為在我的邏輯體系里，這個世界裡沒有可以自證自身的公理體系。

大概就是這樣。

這40行代碼的價值，開始我是不以為然的。
因為根本不懂它是幹嘛用。
直到...
...

對scheme稍微懂點皮毛後，知道了CPS。在此期間看了《Lisp in Small Piece》，還讀了一些優秀的博客http://matt.might.net/articles/cps-conversion/，自己也擼過一些scheme的toy。終於知道這是一個很複雜的東西，被實現得如此精簡，巧妙。
但我還是不以為然的：王垠所做的事情，無非是把前人發現過的東西重新發明了一遍。
直到...
...

讀王垠的yscheme，自己fork出來GitHub - tiancaiamao/yscheme: a compiler from a subset of Scheme into X64做過一番研究。
發現它把40行代碼中用到的一些技巧性的東西，用到了其它很多地方。
一個人可以讀懂CPS的論文，也可以照著裡面實現出代碼。但是經歷這種過程的人，永遠無法掌握將裡面的技巧用到其它地方，因為只有自己思考出來，才懂得觸類旁通，才有可能如此靈活！

我於是完全相信了這40行代碼的價值。自己思考出來，和從它處學到，完全不同。
這40行代碼的價值既然不在於實現了CPS的演算法，也不在於這段代碼寫得有多麼精簡和巧妙。而是：獨立思考。

這一段代碼和 Danvy Filinski 那篇文（Representing Control: A Stydy of the CPS Transformation，doi=10.1.1.46.84）里的如出一轍。你去把論文讀完，就能看懂了。論文可不是單丟一段代碼就跑的，裡面有詳盡的說明，以及最重要的，思考的過程。

ps. 後來 Danvy 又寫了一篇文叫 Back to Direct Style，然後 Sabry 把他兩篇文的技術組合到了一起，發明了 A Normal Form……
pps. 在「理解技術最好去看原始論文」這點上，我是認同王某人的。

王垠這個人挺不錯的，樓主何不鑽研他的代碼，而不是鑽研他說話的語氣與用詞

別邀請了，也別贊同，這代碼不是一般人看的，本身他用的語言就是極客向的語言，而且這搞的又是很專業的東西，主要是與解釋器相關的領域。CPS的功能是很明確的，但其價值只有對編譯器解釋器很有研究的人才能判定。

王垠明確說了：

除非接受過專門的訓練，你絕對不會理解它們的價值

我沒有接受過他那個專門的訓練，但光看代碼的話，美感與精巧是存在的。

至於他是不是在說大話，這個不重要，因為每個人都可以有自己的最得意的傑作，如果這是他自己最得意的傑作，代表了這是他自己的最高水平。——很多男人同樣說過類似的話：我兒子是我這半輩子最得意的傑作。——所以，傑作這東西，人人都可以有，而且我相信每個人都是真心認同自己的傑作的，這就夠了。

我不想談cps本身，只想談談理解這段代碼需要的「專門的訓練」。

我目前發現最容易理解continuation, cps, cps轉換的材料是 brown university的programming languages課程。

課程主頁在此

On-Line Offering

有在線教材，視頻，作業。

第14章手把手教你寫cps轉換。（當然課上的版本沒有王垠的屌，會引入很多administrative lambdas，但至少可以去讀王垠的代碼了）

課程大作業教你實現一個python。上完課你也可以自豪的在簡歷上寫上 I wrote a toy python

這些東西有沒有用呢？

我個人覺得是很有用的，我平時喜歡讀讀programming languages theory的東西，最大的好處就是看待語言的方式發生了變化。我不再關注語言的新特性，因為所謂新的特性早就被發明了一百次了。比如generator coroutine這些東西，懂了continuation就發現沒什麼稀奇的。

語言已經不是語言，而是plt裡面一些常見東西的取捨而已。不同的語言除了syntax上的差異，無非是把plt里的那些東西當成樂高積木拼一拼。然後就能從一個更高的脫離了具體編程語言的高度思考編程，很爽！

另外，其實高票的答案或多或少都有些扯淡。把上面那門課上完，就明白他們哪裡扯淡了。

如果要科普，
請先看這裡：什麼是遞歸？
然後指出，在編程里，遞歸很容易帶來副作用，即結果依賴於再次對自身的調用，這需要等待，等待需要額外空間。也就是棧。太多的數據在棧上就會溢出。
一種好的方法是，尾遞歸。所謂尾遞歸就是把對自身的調用放到方法的最後面。這意味著調用變成了一個類似鏈表的形式，每次調用的結果立刻用作下次調用的參數，而不會「等待」，從而節省棧上的空間。
最後，這段代碼的功能是自動把普通遞歸轉換為尾遞歸。

別贊同。

------

貼篇簡單容易懂的東東：尾遞歸與Continuation

之前從來沒有聽說過他，今天百度的時候無意間看到，特地去github看到了這段代碼。
大概研究了一下，發現是在嘗試自舉。
代碼的作用很簡單，能夠自動尾遞歸，簡單來講就是自動加上回調函數。
主要用於代碼解釋器，對一般的程序員無任何意義，除非你的工作是開發一門新的語言，或者用js寫一個js的解釋器。
而這段代碼本身的邏輯非常巧妙，非常非常的巧妙（不要覺得我low啦，這是發自內心的感嘆。)看懂和創造是兩個完全不同的概念，再次發表感慨。
我本來以為我就是世界上最牛逼的存在了，奈何人外有人啊！！！！
希望3年後我能超越他兩年前的水平!!!!

王垠前幾天在 blog 里關於 P != NP 問題的一些觀點：

我早期對演算法的研究告訴我一個經驗，如果花了很多功夫，仍然找不到一個簡單而快速的多項式演算法，那麼快速的多項式演算法往往不存在。當然，你可以花更多功夫，經過長篇累牘的證明各種上限下限，找到很複雜的多項式演算法，但是這些演算法的實際效率，往往還不如很簡單的指數時間演算法。

同樣，作為非 researcher 但是已經以 coding 為生這麼多年的人來說。如果有一個計算機領域的東西，別人還告訴你必須經過「很特殊的訓練」才能體會（而且僅僅是體會，還談不上完全理解或者批評）它的價值，那麼它的價值 …… 往往 ……

隔行如隔山，除非是在那個領域有點造詣的人。不懂js的人，就算是簡單的js代碼也看不懂的。
很多人看不懂不代表沒有人看得懂。

回答嘛字裡行間都有那種，有什麼了不起的酸

40行代碼怎麼樣我不知道，作為一個python程序員我暫時也看不懂他寫了什麼

但很有意思的是什麼阿貓阿狗都能來踩王垠兩腳，包括代碼也不用會寫的門外漢

王垠說自己一周搞定從前學術圈花了十年的問題；這一點都不算什麼。我上高中的時候就獨自發現了好些定理
比如牛頓萊布尼茲定理，只用一天提出了人類花了幾千年才提出的定理；夠牛逼吧！

----------------------------------------- 分割線 ------------------------------------------------------------
其實只是老師提前講了導數，積分等一些概念，有了這些定義，牛頓萊布尼茲定理就是自然而然的事了；同理，王垠解決問題的時候間接的借用前人的很多思路和發現，只是他自己沒意識到而已

我承認王垠是個牛逼的程序員，不過離天才的距離還有點遠
世界上未解決的難題很多，什麼時候王垠能首先解決其中一個，那就是真天才

隔行如隔山，我也看不懂他寫的程序到底有多牛，但是我有99.9%的把握說，以下2本書中任意挑出一個40行的結論，都比王垠的這40行代碼要牛上10倍。我看懂了以下2本書中的大部分，（我相信在這裡回答問題的人也能看懂），但絕沒有看到寫這些結論的人有多少自我誇耀的地方。

再回復：
不少人質疑我是否能看懂。說是看懂再說。
我看不懂，因為我沒學過。我也可以列出一大堆大家看不懂內容。
做的事情多了，你就會發現:大道至簡，真正的積澱都是初看易懂，細想有深度。
再宏大再複雜的項目，都必須一句話能講明白。
阿里這麼大的帝國，他也必須歸約成一句：讓天下沒有難做的生意。
谷歌這麼大的帝國，你也能夠整理成一句：整合信息，讓人人皆可訪問並受益。
你去理他們的每一個核心點，都能夠整出一句直達要點的話。
谷歌的核心技術rank，可以歸為一句：」引用數為王「。
阿里的核心商業模式，可以歸為一句：」生態搭台，流量唱戲「

我們所創造的一切都是為了他人，需要容易理解，並有明顯的受益點。
不講功效，以複雜不容易理解為賣點，除了炫技的幼稚者和有企圖的騙子還有別的嗎?

============================================================
真佩服他這種忽悠能力。
在同花順的時候，我也寫過一個壓縮演算法，這個演算法作為核心技術寫在同花順上市的招股書上。
性能和效率都遠超之前使用的國際壓縮演算法。演算法反覆重構之後，最後的核心的代碼只有三行。
這些東西研究出來的過程很精彩，但說破了，有時候和魔術一樣，馬上就引不起大家興趣了。
------------------------------------------------------------------------------------------------------------------------
招投書中的內容：鏈接來源廣發證券
3、核心技術的主要內容及應用
1、壓縮：以15年行業經
驗為基礎，依據金融數據
專用壓縮演算法實現的高
效壓縮；
比普通壓縮演算法提高2-3倍的壓縮率；（這個有點吹牛了）
鏈接出處
廣發證券上面說的七項核心技術，四項和我相關。
1、高性能大並發中，排第一的壓縮及相關的通訊協議是我一個人做的。
2、三網合一中兩網是我帶隊做的
3、認證體系最早是我下面的成員做的，後移交出去的。
4、手機那塊。全部是我帶隊做的，其中架構都是我設計的，代碼也有近半是我做的。

如果你看不到這裡的美，你為什麼還要留在這裡？

單從7天轉換到10年創造這個時間差距完成源代碼轉換！這也是不小的工作量，天才般的頭腦勝過大多數人，但還是要佐證開創性的工作！

這個東西的確要那麼一些訓練才能看懂和體會。至少首先要看一本叫sicp的課程洗洗腦，然後到wiki了解下continuation和cps這東西是什麼…難的在於訓練一般計算機學生的思維方式（以sicp作教材的某國外名校cs畢業生或許可以除外）…其實我沒仔細看過這段……不過我相信搞這個的人是會牛逼的，因為他們真的熱愛編程。反正我暫時沒耐心搞懂過。慚愧……

說說我的理解哈，首先寫一個操作內存的還是函數假設是f1，然後定義一套語法並用函數實現語法解析功能的函數f2，f2通過遞歸解析語法，f2調用f1操作內存完成業務。最後注意保護f1和f2所在內存不被寫掉。