函數式語言 Racket 學習記錄

來自專欄東嶽網路工作室團隊4 人贊了文章

PS：文章寫於 2015 年 6 月 20 日，重新發在知乎上以表示東嶽是一個非常活躍的組織。

今天在複習程序語言基礎的考試，偶有所獲，記錄下來~

延遲求值相關

Thunk

首先，先看看函數式裡面延遲求值的方式之一，Thunk。這裡有一個函數，他的作用是用來取代原本的If判斷，代碼是這樣的~

(define (my-if-bad x y z) (if x y z))

初步看上去，代碼很不錯，簡單易懂，但，如果我們以這樣的方式進行調用，就會出問題~

(define (factorial-wrong x) (my-if-bad (= x 0) 1 (* x (factorial-wrong (- x 1)))))

這裡會出什麼問題呢~程序會陷入無盡的遞歸中。這是因為以Racket為代表的大部分函數式編程語言的設定造成的，對於函數的參數，會在執行函數之前先進行求值。所以，my-if-bad的第三個參數，會先進行求值。而在求值的時候，就陷入了無限的遞歸求值當中。

那既然會有問題，該如何解決呢~方法也很簡單，只需要修改下my-if-bad的定義~

(define (my-if x y z) (if x (y) (z)))(define (factorial x)(my-if (= x 0) (lambda () 1) (lambda () (* x (factorial (- x 1))))))

這裡利用的是以Racket為代表的大部分函數式編程語言的另一設定，直到函數被調用的時候才對函數體進行求值。所以這樣將原本的參數變成一個沒有參數的匿名函數後，就不會在把它們作為參數傳入函數的時候就進行求值，而是在使用到它的時候才進行求值。這樣程序就可以正常工作了。所以這種方法就叫做Thunk，在這裡我們把參數y和z給Thunk了。

Delay and Force

上面的Thunk，在某些情況下，不太能滿足要求。比如，Thunk是將參數寫成匿名函數，如果參數需要大量計算，那Thunk會使得每次調用的時候都要求值一次，會比較浪費資源，於是有了另外一種方式，利用Delay和Force，這種方法又被叫做Call by need，因為它既做到了延遲求值，有Call by name的性質，又只需要求值一次，有Call by value的性質。

(define (my-delay f) (mcons #f f))(define (my-force th) (if (mcar th) (mcdr th) (begin (set-mcar! th #t) (set-mcdr! th ((mcdr th))) (mcdr th))))

這裡用了Racket相比於SML的動態特性，其List中的元素不需要是同一類型。所以在delay函數中，把原本的Thunk與一個布爾變數構成一個List，或者說Pair更好一點，(False, Thunk)然後，在force的時候，如果該布爾變數取值為false，那就意味著Thunk還沒有被求值，那就對其求值，並把這一對Pair的值變為(True, Evaluated value)，這樣以後調用，就可以直接返回已經被求值過一次的值。

Stream

一個流是一個有無數個數值的序列，不知道翻譯的對不對。Racket可以通過自己來實現按需生成的流，之所以能做到按需，還是用到了之前的Thunk。流的實現，基本是通過(Item in the stream, Thunk of the function which is responsible for generating new item)的方式來實現的。舉個例子~

(define nats (letrec ([f (lambda (x) (cons x (lambda () (f (+ x 1)))))]) (lambda () (f 1))))

這裡f是一個接受參數x的函數，然後其產生一個形如(x, Thunk{f(x + 1)})的Pair。所以Nats就會產生(1, Thunk{f(2)}))，當繼續展開這個Stream，((cdr (nats)))，就會產生(2, Thunk{f(3)})，通過這樣的方式就可以假裝產生了一個有無數個元素的序列。

Memo

Memo想做的事情，是對於那些，給定一樣的參數，函數的返回值也是固定的這一些函數，緩存它們的(參數，結果)，然後在之後有同樣參數的調用，那直接返回結果就可以了。實現這一點，需要對於每一個函數維護一個Pair類型的List，其實就是拿來模擬Map。然後每當調用函數的時候，都會先去列表中查看是否能找到之前的調用產生的Pair，有的話就直接返回Pair中的結果，沒有的話就進行計算，然後把參數和結果組成一個Pair存入List中。看看示例代碼~

(define fibonacci (letrec([memo null] [f (lambda (x) (let ([ans (assoc x memo)]) (if ans (cdr ans) (let ([new-ans (if (or (= x 1) (= x 2)) 1 (+ (f (- x 1)) (f (- x 2))))]) (begin (set! memo (cons (cons x new-ans) memo)) newans)))))]) f))

這段代碼中用到了一個庫函數，assoc。它接受一個參數，從一個Pair類型的List中找到第一個Pair的Key與傳入的參數相等的Pair，正好用來查找是否已經緩存結果在Memo中。如果有，就直接返回這個Pair的cdr，否則就去計算答案，然後把答案存入Memo。

Macros

關於Racket的宏，讓人印象最深的一點，就是它不會擴展宏到variable definitions中，比如說~

(let ([hd 0] [car 1]) hd) ; evaluates to 0(let* ([hd 0] [car 1]) hd) ; evaluates to 0

如果有一個宏是把替換car為hd，同時宏定義可以擴展到variable definitions中，那第一條語句會報錯，let: duplicate identifier in: hd。所以為了解決類似的問題，Racket的宏定義不會擴展到variable definitions中。variable definitions中的與宏定義中一樣的欄位會shadow住所有關於它的宏定義。

但是，需要注意的一點就是，不要把所有的函數都妄圖寫成宏定義。因為兩者概念上的區別會導致一些情況下兩者功能不是完全一樣的。比方說，之前的Force函數，

(define-syntax my-force (syntax-rules () [(my-force e) (if (mcar e) (mcdr e) (begin (set-mcar! e #t) (set-mcdr! e ((mcdr e))) (mcdr e)))]))

總之，我覺得如果函數可以實現，就不要用充滿了謎的Macros。

推薦閱讀：