王垠

王垠［yín］，四川大學(xué)97級本科畢業(yè)，保送到清華大學(xué)計算機(jī)系直博。期間曾在清華大學(xué)計算機(jī)系軟件工程專業(yè)就讀，主要進(jìn)行集成電路布線算法的研究。在此期間，他因《完全用GNU/Linux工作》一文和對TeX的推廣等“非研究成果的業(yè)余東西”而出名。 在只剩一年就要博士畢業(yè)的時候，他申請退學(xué)，并將1萬7千余字的“退學(xué)申請書”（題為清華夢的粉碎）公布在網(wǎng)上，引起輿論界一時對教育體制、理想主義等的熱議。

王垠的40行代碼

40行代碼專家解讀

1. 背景知識

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

簡單來講，CPS 是一種編程風(fēng)格：

Javascript：

（原味）

function foo（x） {

return x ;

}

（CPS）

function cps_foo（x， return_point） {

return return_point （x） ;

}

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

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

這段 40 多行代碼是給 Scheme 程序脫糖的程序，屬于解釋器的代碼，而不是應(yīng)用代碼。對其的客觀評價顯然只有設(shè)計解釋器的人才能給出。對應(yīng)用程序員的意義在于，發(fā)現(xiàn)每天上班時編寫的代碼多么無聊，此外并沒有任何實用價值。

2. 運行結(jié)果

‘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： 函數(shù)在執(zhí)行（apply）時候的上下文環(huán)境，可理解為 C 程序中運行時的棧。

整 個 cps 的（主要）過程就是 if 分支在不斷制造新的 ctx， 而 apply 分支（最后一個分支）不斷在新的 ctx 中 ‘計算’ （實際上是生成 cps 函數(shù)的代碼，而不是真的計算），并返回結(jié)果（到上一層 ctx）的過程。這個過程就是 scheme 的基本 eval-apply 過程。（參見SICP第四章）

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

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

5. 結(jié)論

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

網(wǎng)友評價：

看來網(wǎng)友們關(guān)注的重點，都在王垠說的話上，很多網(wǎng)友都認(rèn)為他在吹牛。但是也有網(wǎng)友為他說話的，覺得這40行代碼，確實很厲害，有些網(wǎng)友還悄悄的跑去運行了一下。

網(wǎng)友一：這40行代碼的價值，開始我是不以為然的。因為根本不懂它是干嘛用。直到自己水平的提升，又對這些代碼有研究，才發(fā)現(xiàn)，這40行代碼的價值。

網(wǎng)友二：這40行代碼的價值既然不在于實現(xiàn)了CPS的算法，也不在于這段代碼寫得有多么精簡和巧妙。而是：獨立思考。

網(wǎng)友三：這段代碼的功能是自動把普通遞歸轉(zhuǎn)換為尾遞歸。

網(wǎng)友四：不懂js的人，就算是簡單的js代碼也看不懂的。 很多人看不懂不代表沒有人看得懂。