megrxu

SICP 讀後

Apr 18, 2020  「PL」  

暑假讀了一下 SICP。

函式式和抽象

最前面的一小沓許多都是常規函數語言程式設計中老生常談的部分。但是跟著作者的腳步,能夠很明顯地發現他們把「抽象」放在了一個非常高的角度。從小的,一般的情況開始玩弄,最後推廣;後來發現推廣的一般式是一個更一般式的特殊形式,從而使得最初的幾例亦可以用這種推廣進行實現。

另外,一些例子還「強迫」讀者不再使用過程式的思維,考慮任何的「暫存器」了。將值在程式呼叫時進行傳遞(例如大量的把遞迴改為迭代的練習題),從而使得純函式能夠做大量以前以為需要改變臨時變數的值才能做到的事情,並且也沒有引入可見的時間或空間冗餘。這些是書中所謂的「過程抽象」。

除了程式本身,下層對上層的抽象屏障還使得「介面」這種東西變得異常清晰。只要一些宣告,就可以開發不同層次的程式,而無需考慮底層的設計細節。就我理解來看,這是抽象在設計模式方面的一個簡單應用,但是在 SICP 中顯得非常自然。進一步,有了介面,以及對於大量不同物件的類似操作,則必然就需要有通用性系統進行「分發」:根據物件的型別和操作名,分發給他對應的函式。到後期開始實現「型別塔」和型別之間的轉化,也顯得不是那麼難了(如果讓我直接去想怎麼實現,我感覺我很快就會把問題變得非常複雜)。

再談副作用 – 以及模擬世界的另一種方式

和純函式打了一段時間交道,接下來就得看看環境模型了。這個模型下,變數的值並不是每時每刻都一樣的,因為存在了有副作用的函式。副作用使得函式(或者說物件)本身帶有了狀態,從而可以做到很多以前做不到的事情。例如銀行的賬單。直觀來看,似乎幾乎不可能透過純的函式進行實現,畢竟賬戶的值是一個變動的值,無法使用一個函式來進行記錄。函式的副作用引來了好處,也當然引來了痛點:我們必須小心地維護這些狀態,以便他們按照我們意圖的方式工作;函式執行的先後順序,也可能需要特別考慮。

更驚人的是,實際上透過「流」,一種延遲(按需)計算的,可以用純函式實現的資料結構,可以實現無狀態的銀行賬戶,從而在另一個角度來模擬這個物理世界。這樣定義出來的函式本身是無狀態的,但是使用者的互動賦予了它狀態,使得不同時刻它具有了不同的值。更巧妙的結合是,雖然可以使用純函式來實現這樣的「流」,但是如果同時在內部輔以「狀態」,例如求值一次之後就將其標記為「已求值的」,則又將會減少一大堆的計算冗餘(將來不需要再計算了)。

更進一步:新的語言

其實有了之前的資料抽象,以及對於環境模型的認識,已經可以使用 lisp 構建一個 lisp 的求值器了。但是,這當然是不夠的,我們需要更多的可能性,而不是實現已經有的:

  • 對「流」的實現表現了一種「按需計算」的可能性,而這個可能性可以更深層次地嵌入到求值器中去,這便是惰性求值。
  • 開發一個不確定的過程,它可以根據一些約束,來逐漸減小自己的搜尋空間。從而使得破解謎題成為可能。即 amb 求值器。
  • 根據邏輯查詢語句,搜尋模式匹配下的語句,並返回這些滿足要求的條目。