sicp metacircular evaluator (4) - lambda

這次要實作的部份是 lambda, 在 functional programming 熱潮來息時, 最常出現的名詞是 lexical closure 和 lambda, 很多相關主題的聚會也會看到 λ 標誌。讓我想到 2000 年的顯學 - OO , 其三大特性也是讓人朗朗上口, 封裝、繼承、多型, OO 流派是否有時不我予之感。

喔! 還有那個 first-class function。

流行十多年了換人當主角也無不可, 不過 lambda 在 1958 年的 lisp 就已經出現, 經過這麼多年總算熬出頭。

其實我不知道 lambda 到底有多威, 現在的語言似乎一窩蜂要加入這個特性, c++11 也來湊熱鬧了, 用一般 function 遜, 來跑個 lambda 潮。不過在 scheme 裡頭, lambda 是唯一可以建立 function 的方法, 所以沒有 lambda, scheme 就沒有 function call 可以用了。所以得把 lambda 實作出來, 才會有 function call 可以用。

來看看 sicp 4.1.1 怎麼用 scheme 實作 lambda。

當 scheme evaluate 下面的 lambda 運算式時, 會發生什麼事情?

(lambda (x) (+ x 4))

lambda-res1

1 xx output: (procedure (x) ((+ x 4)) (((false true car cdr cons null? + *) #f #t (primitive #[compiled-procedure 2 (list #x1) #x3 #x4d655]) (primitive #[compiled-procedure 3 (list #x2) #x3 #x4d64e]) (primitive #[compiled-procedure 4 (list #x3) #x3 #x4d648]) (primitive #[compiled-procedure 5 (list #x5) #x3 #x4d639]) (primitive #[arity-dispatched-procedure 6]) (primitive #[arity-dispatched-procedure 7]))))

沒幹什麼事情, 很單純的把這個 procedure 加入到目前的環境中 (紅色部份是原本環境的內容)。會 append procedure 這個 symbol, 用來區別 lambda function 還是 primitive function。

這個運算式會建立一個 procedure object, 這是一個 pair, 一個代表 procedure 本身:

(x) (+ x 4)

另外一個東西就是環境指標, 上表的紅色部份就是它的環境指標, 指向 global environment。

handle lambda

143 (define (make-procedure parameters body env)
144 (list 'procedure parameters body env))

156 ((lambda? exp)
157 (make-procedure (lambda-parameters exp)
158 (lambda-body exp)
159 env))

lambda-parameters, lambda-body 兩個就是把 (x), (+ x 4) 分別抓出來, 傳給 make-procedure, 很容易理解。

下面的是 function call (會建立新環境), 以 lambda-exp L1 來說, 就是把 5 傳給 x, 然後計算 (+ x 4)。我知道語法很怪, lambda 就是這麼潮, 我也沒辦法。這就不是單純加入這個 procedure 就好, 還要能執行 + 的那個動作, 並把 x 換成 5, 這樣就能得到 9。

lambda-exp

1 ((lambda (x) (+ x 4)) 5)
2 ((lambda (x) (+ (* x 2) (* 3 x)))5)

lambda-exp L1 那個 expression 在 interpreter 會被怎麼處理? 直譯器會先處理這個 (lambda (x) (+ x 4)) expression, 知道要產生一個 function, 然後要把 5 當成變數 x 的值, 送進去給 (+ x 4), 透過 + 計算得到 9。說完了, 真簡單。

程式流程當然沒這麼簡單, 由於 (lambda (x) (+ x 4)) 是一個 function, 所以在呼叫 apply 時要執行一個 function 時, 會開一個新環境, 稱為 e0 好了, e0 的上層環境是 global 環境, 再把 x = 5 加入這個 e0 這個環境。當 eval x 的時候, 就會在 e0 這個新環境找到 x=5, 然後就是之前的故事了 - 四則運算。

那 lambda-exp L2 呢? 一樣阿! 在新環境找到 x=6 之後, 不就是 (+ (* 5 2) (* 3 5)), 四則運算式就提過了。

apply

  1 ; metacircular evaluator
 49 (define (apply procedure arguments)
 56   (cond ((primitive-procedure? procedure)
 57          (apply-primitive-procedure procedure arguments))
 58         ((compound-procedure? procedure)
 59          (eval-sequence
 60            (procedure-body procedure)
 61            (extend-environment
 62              (procedure-parameters procedure)
 63              arguments
 64              (procedure-environment procedure))))
 65         (else
 66          (error
 67           "Unknown procedure type -- APPLY" procedure))))

apply L58 ~ 64 是處理 lambda function, L61 的 extend-environment 就是用來開一個新環境, 將新的變數名稱變數值存入到那個新環境, 那個新環境會接在上層環境裡頭。

如下表的 L6 紅字部份。

test lambda

1 ((lambda (x) (+ x 4)) 5)
2
3 (procedure (x) ((+ x 4)) (((false true car cdr cons null? + *) #f #t (primitive #[compiled-procedure 11 (list #x1) #xf #x3218d3]) (primitive #[compiled-procedure 12 (list #x2) #xf #x321917]) (primitive #[compiled-procedure 13 (list #x3) #xc #x32195c]) (primitive #[compiled-procedure 14 (list #x5) #xc #x3219b8]) (primitive #[arity-dispatched-procedure 15]) (primitive #[arity-dispatched-procedure 16]))))
4
5
6 (((x) 5) ((false true car cdr cons null? + *) #f #t (primitive #[compiled-procedure 11 (list #x1) #xf #x3218d3]) (primitive #[compiled-procedure 12 (list #x2) #xf #x321917]) (primitive #[compiled-procedure 13 (list #x3) #xc #x32195c]) (primitive #[compiled-procedure 14 (list #x5) #xc #x3219b8]) (primitive #[arity-dispatched-procedure 15]) (primitive #[arity-dispatched-procedure 16])))