深入理解運算原理｜從簡單的機器到無所不能的程式

206

|

第 6 章

實作 Lambda 演算

我們的 FizzBuzz 實驗讓我們意識到以無型別 lambda 演算編寫程式的感覺。這些限制強

迫我們要從零開始實作大量的基本功能，而不是依賴語言的功能，但我們最終的確設法

建置了諸多的資料結構和演算法；要解決我們所提出的問題，需要這些資料結構和演算

法。

我們當然並沒有真的編寫 lambda 演算程式，因為我們沒有 lambda 演算直釋器；我們

只是以 lambda 演算的風格編寫了 Ruby 程式，去體會多小的語言可以運作。但是，

我們已經擁有構建 lambda 演算直釋器所需要的所有知識，並且使用它來估算實際的

lambda 演算運算式，所以讓我們進一步的試試這些。

語法

無型別的 lambda 演算是一種僅具有 3 種運算式的程式語言：變數、函式定義、呼叫。

我們並不為 lambda 演算運算式引進新的具體語法，而是堅持使用 Ruby 的慣例（變數

看起來像

x

、函式看起來像

-> x {x}

、呼叫看起來像

x[y]

），並且試著不混淆兩種語言。

為什麼是『

lambda

演算』

?

這種情況的

演算

（

calculus

）一詞是指用來操縱符號字串的規則系統

7

。

lambda 演算的原生語法使用希臘字母 lambda（

λ

）代替 Ruby 的

->

符

號；舉例來說，

ONE

要寫成

λ

p.

λ

x.p x

。

我們可以依照平常的方式實作

LCVariable

、

LCFunction

和

LCCall

語法類別：

class LCVariable < Struct.new(:name)

def to_s ...