懶惰的力量

（今天我在舊金山參加了Erlang factory 2015大會，增長了很多見識。參會的總結我過兩天再寫，很多思想需要時間沉澱。）

前段時間寫了篇「永恆不變的魅力」，介紹了immutability，很多讀者表示喜歡這樣的文章。這篇文章繼續走標題黨路線，給大家奉上的不是雞湯，而是正兒八經的技術文章，講的是Lazy evaluation。

在大家熟悉的編程語言中，調用一個函數，系統會老老實實返回調用的結果。這非常正常且直觀 —— 計算機不就該這麼運作么？如果你恰巧是個c語言開發者，objdump一下生成的目標文件，可以看到所有的計算過程。

lazy evaluation，顧名思義，就是調用函數，函數並不進行運算，而是返回一個數據結構，這個數據結構說：「嗯，你要調用這個函數，我知道了，你該幹嘛幹嘛吧。」如果接下來程序需要使用這個函數的返回值，那麼計算才真正開始。

聽上去似乎沒太多好處。別急，考慮一下這樣的代碼（以Elixir為例）：

awesome_listn|> Enum.filter(data_wash_fun)n|> Enum.map(do_some_cool_stuff_fun)n|> Enum.reduce(reduce_fun)n

這種pattern的代碼在日常生活中會經常遇到：一個數據集，清洗一下，然後map/reduce。這代碼效率不高，循環三遍，O(3n)。要想提高效率到O(n)，可以寫一個for循環，把wash/map/reduce的動作都塞進去。不過，這樣的代碼非常醜陋，不利於復用，也不利於日後擴展（不符合open/close principle）。這時候，立即計算的劣勢就顯現出來。如果我們把代碼稍作修改：

awesome_listn|> Stream.filter(data_wash_fun)n|> Stream.map(do_some_cool_stuff_fun)n|> Enum.reduce(reduce_fun)n

這裡，你可以簡單認為 Stream 是 Enum 的延遲計算。我們看看調用 Stream.filter，繼而調用 Stream.map 都發生了什麼：

iex(4)> alist |> Stream.filter(&(&1 > 2))n#Stream<[enum: [1, 2, 3, 4],n funs: [#Function<39.29647706/1 in Stream.filter/2>]]>n iex(5)> alist |> Stream.filter(&(&1 > 2)) |> Stream.map(&(&1 / 2))n#Stream<[enum: [1, 2, 3, 4],n funs: [#Function<39.29647706/1 in Stream.filter/2>,n #Function<45.29647706/1 in Stream.map/2>]]>n

沒有任何循環，執行完這兩句後，只是把整個計算的細節包裝了一下。當上述代碼運行到 Enum.reduce 時，才開始真正觸發求值。而求值的過程是：從 [1, 2, 3, 4] 里取出 1，依次調用 funs 列表裡的函數，得到的返回值，再送給 Enum.reduce 進行計算。

Lazy evaluation在代碼乾淨漂亮的前提下，在這段代碼下達到了我們優化的目標：只有一遍循環。

當然這只是其一個顯而易見的好處：避免不必要的循環。從更廣泛的意義上講：Lazy evaluation能避免不必要的計算，提高效率。比如說在某些情況下，代碼根本沒有使用某次計算的返回值，這樣就可以節省運算。

Lazy evaluation的另一個極大的好處是很容易並發。既然計算的細節被包裹起來，那麼，計算本身還被限定在當前的上下文，或者當前的vCPU完成么？

顯然不必。在Elixir里，我們可以這樣做：

awesome_listn|> Stream.filter(data_wash_fun)n|> Stream.map(do_some_cool_stuff_fun)n|> Stream.async() <--------n|> Enum.reduce(reduce_fun)n

Stream.async() [1] 之前的 lazy evaluation 都可以放在另一個 process 處理了。每計算完一個值，就會返回給 reduce 處理，假設 reduce 是個耗時的操作，這樣就不會block前面的運算。

這代碼太美，和之前的描述方式幾乎一樣，但同步的動作就變成了非同步。最爽的是，程序員不用糾結任何細節。如果相同的非同步處理要自己實現，可能需要一頁紙的代碼。

再進一步：

awesome_listn|> Stream.Op1(...)n|> Stream.Op2(...)n|> Stream.async() # rp1 (rendevous point)n|> Stream.Op3(...)n|> ...n|> Stream.async() # rp2n|> ...n|> Stream.async() # rp3n|> Enum.reduce(reduce_fun) # rp4n

看著這段代碼，我想起了兒時讀過的一個故事。說美國南北戰爭時期，槍支短缺，政府需要短期內生產幾萬支槍，可當時最好的毛瑟槍工匠一天只能造一支槍。政府的訂單一直沒人敢接，後來有個大膽的商人接了。他把槍械生產的過程拆解開，每個人只負責其中一個部件。有些簡單的部件，普通人就能勝任，不需要毛瑟槍工匠。故事到這我想用不著繼續講了，大家都知道我想講什麼了。

這裡，一條run to complete的流水線被分成了四條子流水線，一個數據現在要經過四道互不影響的工序，才最終處理完畢。嗯，如果某條流水線處理速度慢怎麼辦？繼續上代碼（假設運行效率：rp4 = 2倍rp3 = 4倍rp2 = 6倍rp1）：

awesome_listn|> Stream.Op1(...)n|> Stream.Op2(...)n|> Stream.async(6) # rp1n|> Stream.Op3(...)n|> ...n|> Stream.async(4) # rp2n|> ...n|> Stream.async(2) # rp3n|> Enum.reduce(reduce_fun) # rp4n

hmm…perfect。這裡的數字是個比例，rp4如果是1個process的話，rp3就是2個，以此類推。

有時候我們希望每個process都是毛瑟槍工匠，或者，整個過程的每一步都可以細粒度控制並發，那麼，可以使用這些方法：

Stream.farmnStream.pmapnStream.chunked_pmapn

這就是lazy evaluation的威力，幾乎同樣的代碼，卻能夠以你需要的方式漂亮地並發跑在多核場景下。

小結一下，lazy evaluation：

1. 把計算和計算髮生的時間decouple，避免了不要要的計算

2. 把計算和計算髮生的空間decouple，提供了並發的可能

回過頭來我們再好好想想這裡處理問題的思路，發現什麼了么？indirection！Computer science最重要的思想：

Every problem could be solved by adding another layer of indrection.

（PS: 本文撰於今天坐Caltrain從SF回SV的路上。來美有近一個季度了，總共坐過兩次Caltrain。兩周前，同樣從SF回SV，在Mountain View附近，一哥們卧軌自殺，我花了3小時，才輾轉回到家；今天第二次做坐Caltrain，還是SF回SV，又有一哥們把車扔到了鐵軌上，害的列車停了一個半小時，7點半發車，到家10點半。唉，Caltrain，我跟你什麼冤什麼仇啊）

如果您覺得這篇文章不錯，請點贊。多謝！

歡迎訂閱公眾號『程序人生』（搜索微信號 programmer_life）。每篇文章都力求原汁原味，北京時間中午12點左右，美西時間下午8點左右與您相會。