北京
八年前，Jane Street開源了一個(gè)叫Incremental的庫。它做的事情聽起來很抽象：讓程序像Excel表格那樣"聰明地"只重算變化的部分，但比Excel更靈活——計(jì)算圖的結(jié)構(gòu)本身也能隨數(shù)據(jù)變化。
Excel的優(yōu)化邏輯很簡(jiǎn)單。每個(gè)單元格存數(shù)據(jù)或公式，公式引用其他單元格，形成一張計(jì)算圖。關(guān)鍵優(yōu)化是：當(dāng)某些單元格變了，Excel只重算依賴這些單元格的部分。Incremental把這個(gè)思路搬到通用編程里，但加了一個(gè)Excel沒有的能力：運(yùn)行時(shí)動(dòng)態(tài)改圖結(jié)構(gòu)。
這個(gè)動(dòng)態(tài)性打開了幾個(gè)應(yīng)用場(chǎng)景。
第一是在線組合算法。Incremental基于Umut Acar等人的自調(diào)整計(jì)算研究。他們的核心發(fā)現(xiàn)是：很多離線算法簡(jiǎn)單改造后，能達(dá)到專門設(shè)計(jì)的在線算法的漸進(jìn)復(fù)雜度。不用從頭寫復(fù)雜的在線版本，增量化改造就行。
第二是GUI構(gòu)建。把界面看成"從數(shù)據(jù)模型生成視圖"的函數(shù)，每次都從頭生成太慢。寫成增量計(jì)算，既保持代碼簡(jiǎn)潔，又獲得性能。Jane Street自己在多個(gè)UI里用過這個(gè)技術(shù)。
這和Elm等語言里的函數(shù)式響應(yīng)編程（FRP）有點(diǎn)像，但語義不同。FRP關(guān)注時(shí)間流，SAC優(yōu)化有向無環(huán)圖計(jì)算。實(shí)現(xiàn)層面倒是密切相關(guān)。
第三是配置化計(jì)算。Jane Street自己的例子是風(fēng)險(xiǎn)計(jì)算。投資組合的風(fēng)險(xiǎn)度量要組合大量互相關(guān)聯(lián)的模型，每個(gè)模型依賴市場(chǎng)實(shí)時(shí)數(shù)據(jù)和用戶配置。配置變化可能只是調(diào)個(gè)系數(shù)，也可能改變計(jì)算結(jié)構(gòu)——比如換一組因子。Incremental能同時(shí)高效處理這兩種更新。
庫的接口設(shè)計(jì)圍繞幾個(gè)核心抽象：可變的輸入節(jié)點(diǎn)、能構(gòu)建和組合計(jì)算的算子、以及觸發(fā)和傳播變化的機(jī)制。mli文件里的注釋詳細(xì)說明了每個(gè)部分的契約和性能特征。
一個(gè)值得注意的設(shè)計(jì)選擇是顯式區(qū)分"穩(wěn)定"和"不穩(wěn)定"階段。變化批量收集，然后在穩(wěn)定階段統(tǒng)一傳播，避免中間狀態(tài)的冗余計(jì)算。這對(duì)高頻更新的場(chǎng)景很關(guān)鍵。
開源八年，Incremental在OCaml生態(tài)里成了一個(gè)基礎(chǔ)設(shè)施級(jí)的存在。它的價(jià)值不在于某個(gè)具體算法，而在于提供了一種組織計(jì)算的通用模式：聲明式描述依賴關(guān)系，運(yùn)行時(shí)自動(dòng)處理增量更新。對(duì)于數(shù)據(jù)流復(fù)雜、更新頻繁的系統(tǒng)，這個(gè)模式能顯著降低心智負(fù)擔(dān)。
特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺(tái)“網(wǎng)易號(hào)”用戶上傳并發(fā)布，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
