2018-07-29

Scheme ê 延遲計算 (lazy evaluation) ê 例

目錄

1. 介紹
   1. 實作
   2. 參考
2. 註腳

（上尾更新 tī：2019-01-20）

介紹

佇電腦程式中，通常愛算一个運算式[ūn-suàn-sik] ê 結果，會 kā 逐个部份照算 ê 次序[tshù-sī]一改算予清，這種趁早算出來 ê 算法，號做「嚴格計算」 (strict evaluation; eager evaluation)。比論講：

(* 2 (+ 3 (/ 5 2)))

¹
Strict evaluation ê 作法，會代先共 (/ 5 2) 算出來，得著 2.5，了後 kā 這个結果下 kah (+ 3 ?) ê ?，上尾共 (+ 3 (/ 5 2)) 下佇 (* 2 ?) ê ?，一改 tiō 知結果，見若[kìnn-nā]有愛算 ê 所在，攏 buē-tàng 暫時 mài 算。

但是，有時仔咱無愛共運算 ê 結果做一改執行，tio̍h 共一部份先放 tī 邊仔，需要 ê 時 tsiah 執行，按呢叫做「貧惰計算」（延遲計算，lazy evaluation）。

Tī 介紹貧惰計算使用 ê 所在，咱代先看 Scheme ê 有關語法。通常 Scheme ê 逐个函數，kap Haskell 無仝，攏是嚴格計算 ê。Beh 予計算式「貧惰」，著用 (delay 計算式)，按呢 tiō 會產出 promise（欲算 ê 物件）。kàu 欲算 promise ê 時陣著用 (force promise)。以下是舉例，所有 ê 例攏佇 Racket ê Scheme R5RS 環境執行：

> (define a (delay (+ 2 1))) ; Tī 終端機輸入，kā (+ 2 1) ê promise 下佇 a
> a
#<promise> ; a 是 promise
> (force a)
3 ; 逼 a 算出來，得著 3
>

咱無法度共 promise kap 數值用 +、-、*、/ 直接算：

> (+ (- 12 6) (delay (+ 2 1)))
+: contract violation
  expected: number?
  given: #<promise>
  argument position: 2nd
  other arguments.: ; 現出錯誤
>

舉例：無限數列

毋過，讀者會問，到底這有 sím 物路用？貧惰計算 ê 一个好處，tiō 是 thang 表示一个「無限數列[bû-hān sòo-lia̍t]」(infinite sequence)。

汝[lí]想，設使咱 beh 做一个

f(x) = 2x, x = 0,1,2,…

ê 級數，beh 按怎表示 nih？咱人通觀察伊 ê recursion（遞迴[tuē-huê]、遞歸[tuē-kui]、再歸[tsài-kui]）表示：

咱通觀察，這个數列通表示做 (inf-series 20)，其中

(inf-series n) := (cons n (inf-series 2×n))

。

所以咱 kám 有可能 kā tse 用程式表示出來？巧 ê 讀者應該 ê 知影，因為無限級數內底有無限 ê 數，電腦無可能一改算出來，而且 iā 無可能儲存 hiah-ni̍h tse ê 數，所以準若有人好膽執行這个程式，系統會當[tǹg]掉抑是有錯誤資訊：

(define (inf-series n)
  (cons n (inf-series (* 2 n))))

(inf-series (expt 2 0)) ; (expt 2 0) = 2^0

所以嚴格計算無法度表示。是講，咱人無愛 kā 無限級數 ê 所有項攏展示，只要算 kàu 咱愛 ê 項 tiō 可以。所以，tse ē-tàng 用貧惰計算來表示囉，ná án-ne：

; (delay ...) 是咱 buài tsit-má 算 ê 所在。
(inf-series x_1) = (cons x_1 (delay (inf-series 2*x_1)))

假使咱 beh 第二項 x₂，tiō 愛共包佇 delay 內底 ê promise 強制執行，若：

; 第二項出來矣，毋過生出別个 promise。
(cons x_1 (force (delay (inf-series 2*x_1)))
=> (cons x_1 (cons x_2 (delay (inf-series 2*x_2))))

咱人 tiō 通實做：

; 定義無限級數
; (inf-series 1)
; -> (1  #<promise>)
(define (inf-series n)
  ; 注意 (delay ...) 是慢且算的所在，會變做 promise。
  (cons n `(,(delay (inf-series (* 2 n))))))

; 提第 n 項（對 0 開始）ê 數值
; (inf-series-ref 3) -> 8
(define (inf-series-ref n)
  (inf-series-ref-iter n (inf-series (expt 2 0)))
)

; 協助 inf-series-ref ê 函數
(define (inf-series-ref-iter i inf-series-part)
  (if (= i 0)
     ; 若是 i == 0,提數列已經算 ê 尾兩項（含 promise，
     ; tiō 是 inf-series-part）ê 頭，有咱愛 ê 結果。
     (car inf-series-part)
     ; 若是 n != 0，閣用 force 拆開 promise，得著新 ê 一項。
     (inf-series-ref-iter (- i 1) (force (cadr inf-series-part)))))

; 提著包 inf-series 第 0 - n 項 ê 數列。
; 例：(inf-series-head 10)
; -> (1 2 4 8 16 32 64 128 256 512 1024)
(define (inf-series-head n)
  (inf-series-head-iter n (inf-series (expt 2 0)) '()))

; 協助 inf-series-head ê 函數。
(define (inf-series-head-iter i inf-series-part prev-result)
  ; 定義可能 ê 結果
  (let ((result (append prev-result `(,(car inf-series-part)))))
    (if (= i 0)
       result ; i == 0 ê 時，得著結果
       (inf-series-head-iter (- i 1) (force (cadr inf-series-part)) result))))

試驗：

> (inf-series 1)
(1 #<promise>)
> (inf-series-ref 3)
8
> (inf-series-head 10)
(1 2 4 8 16 32 64 128 256 512 1024)
> 

實作

欲做這真簡單，delay tiō 是 kā 函數用無任何引數 ê lambda 包起來。force tiō 是 kā 予 lambda 包起來 ê 執行。毋過準若用 define 定義，因為會代先嚴格計算 beh khah 慢算 ê 表達式，致 kàu 無合咱所愛 ê，所以定著愛用 macro ê 方式來寫：

(define-syntax my-delay
  (syntax-rules ()
    ((_ expr) (lambda () expr))))

force tiō 是：

(define (my-force my-promise)
  (my-promise))

以下是使用 ê 例：

> (define delayed-procedure (my-delay (+ 1 2)))
> delayed-procedure
#<procedure:delayed-procedure> ; 注意毋是 promise，是 procedure
> (my-force delayed-procedure)
3
> 

參考

* [(Scheme) 17. Lazy evaluation](http://www.shido.info/lisp/scheme_lazy_e.html) of Yet Another Scheme Tutorial by Takafumi Shido * [21. Delayed evaluation and infinite lists in Scheme](http://people.cs.aau.dk/~normark/prog3-03/html/notes/eval-order_themes-delay-stream-section.html) of Functional Programming in Scheme : With Web Programming Examples by Kurt Nørmark, Department of Computer Science, Aalborg University, Denmark

註腳

¹ 這是 Scheme ê 寫法，共算數[suàn-sòo]符號抑是函數 ê 名 khǹg 頭前，一般是 2 * (3 + 5 / 4)

Blog

資訊, Holo話, Scheme