我試圖在 Scheme 中用代數資料型別編碼一個小的 lambda 演算。我希望它使用惰性求值，為此我嘗試使用原語delay和force. 但是，這對評估性能有很大的負面影響：小型測驗用例的執行時間增加了 20 倍。
雖然我沒想到懶惰會加速這個特定的測驗用例，但我也沒想到會大幅放緩。我的問題是：是什么導致了延遲評估的巨大開銷，以及如何在仍然獲得延遲評估的同時避免這個問題？我已經很高興將嚴格版本的執行時間縮短 2 倍，但當然更快總是更好。
下面是我使用的測驗用例的嚴格和惰性版本。該測驗以一元表示法處理自然數：它構造一個2^24 sucs 后跟a 的序列，zero然后再次破壞結果。懶惰版本是從嚴格版本構建的，通過在適當的位置添加delay和force，并添加let-bindings 以避免多次強制引數。（我還嘗試了一個版本，其中zero和suc是嚴格的，但其他函式是惰性的，但這比完全惰性的版本還要慢，所以我在這里省略了它。）
我使用compile-fileChez Scheme 9.5編譯了這兩個程式，并.so使用petite --program. 嚴格版的執行時間（僅限用戶）為 0.578 秒，而懶惰版的執行時間為 11,891 秒，幾乎慢了 20 倍。
嚴格版
(define zero 'zero)
(define (suc x) (cons 'suc x))
(define one (suc zero))
(define two (suc one))
(define three (suc two))
(define (twice m)
(if (eq? m zero)
zero
(suc (suc (twice (cdr m))))))
(define (pow2 m)
(if (eq? m zero)
one
(twice (pow2 (cdr m)))))
(define (consume m)
(if (eq? m zero)
zero
(consume (cdr m))))
(consume (pow2 (twice (twice (twice three)))))
懶人版
(define zero (delay 'zero))
(define (suc x) (delay (cons 'suc x)))
(define one (suc zero))
(define two (suc one))
(define three (suc two))
(define (twice m)
(delay
(let ((mv (force m)))
(if (eq? mv 'zero)
(force zero)
(force (suc (suc (twice (cdr mv)))))))))
(define (pow2 m)
(delay
(let ((mv (force m)))
(if (eq? mv 'zero)
(force one)
(force (twice (pow2 (cdr mv))))))))
(define (consume m)
(delay
(let ((mv (force m)))
(if (eq? mv 'zero)
(force zero)
(force (consume (cdr mv)))))))
(force (consume (pow2 (twice (twice (twice three))))))
uj5u.com熱心網友回復：
可以使用 ChezScheme 的(time ...)程式查看測驗程式兩個階段的統計資料：
$ scheme
Chez Scheme Version 9.5.2
> (load-program "strict.ss")
(time (pow2 (twice (...))))
21 collections
0.695561822s elapsed cpu time, including 0.521065634s collecting
0.695607000s elapsed real time, including 0.521191000s collecting
672586992 bytes allocated, including 236483824 bytes reclaimed
(time (consume u2^24))
no collections
0.037766347s elapsed cpu time
0.037762000s elapsed real time
0 bytes allocated
對于懶惰版本：
$ scheme
> (load-program "lazy.ss")
(time (pow2 (twice (...))))
no collections
0.000000000s elapsed cpu time
0.000000000s elapsed real time
400 bytes allocated
(time (force (consume u2^24)))
572 collections
11.997971385s elapsed cpu time, including 10.798406971s collecting
12.012723000s elapsed real time, including 10.813517000s collecting
4832215216 bytes allocated, including 4460306000 bytes reclaimed
所以90%的時間都在收集。調整收集器引數可能會改善這一點，例如：
(collect-trip-bytes 1000000)
(collect-generation-radix (greatest-fixnum))
(heap-reserve-ratio 2.0)
（這些值使懶惰時間 OMM 減半）
也可以用精簡版替換 ChezScheme 的delay和force：
(import (except (chezscheme) delay force))
(define (make-promise p)
(let ([value (box p)])
(lambda ()
(when (box? value)
(let ([x ((unbox value))])
(when (box? value)
(set! value x))))
value)))
(define-syntax delay
(syntax-rules ()
[(_ expr) (make-promise (lambda () expr))]))
(define (force promise)
(promise))
（在lazy.ss開頭添加上面）
注意這些沒有錯誤檢查，并且不處理多個值或惰性框。
（ChezScheme 實作在這里）
通過這些更改，惰性版本比嚴格版本慢約 4 倍：
$ scheme
> (load-program "lazy.ss")
(time (pow2 (twice (...))))
no collections
0.000000000s elapsed cpu time
0.000000000s elapsed real time
336 bytes allocated
(time (force (consume u2^24)))
3813 collections
2.977003428s elapsed cpu time, including 2.175818398s collecting
2.977292000s elapsed real time, including 2.179504000s collecting
4029652320 bytes allocated, including 2414247968 bytes reclaimed
uj5u.com熱心網友回復：
這聽起來很像一個在 Haskell 中不時出現的問題。問題是垃圾收集之一。
這有兩種方式。首先，惰性串列可以在使用時被消耗，從而限制消耗的記憶體量。或者，其次，惰性串列可以以一種始終保留在記憶體中的方式進行評估，串列的一端固定在適當的位置，因為它仍在使用中 - 垃圾收集器對此表示反對并花費大量是時候嘗試處理這種情況了。
Haskell 可以和 C 一樣快，但需要嚴格的計算才能做到這一點。
我不完全理解代碼，但它似乎遞回地創建一個越來越長的串列，然后對其進行評估。您是否有工具來測量垃圾收集器必須處理的記憶體量以及垃圾收集器運行的時間？
uj5u.com熱心網友回復：
您要做的不是encode a small lambda calculus with algebraic datatypes嘗試對 Peano 算術進行編碼，這是邁向“小 lambda”的第一步。
我試圖給你寫一些代碼，以“更快的方式”完成它。因為我不使用特殊形式force，所以delay在我的代碼中我使用了 thunk 來編碼它們的邏輯。
(define succ
(lambda (x)
(lambda ()
(cons 'succ x))))
(define zero (lambda () 'zero))
(define one (succ zero))
(define two (succ one))
(define three (succ two))
(define twice
(lambda (n)
(define twice
(lambda (k)
(if (eq? 'zero k)
n
(succ (twice ((cdr k)))))))
(twice (n))))
(define pow2
(lambda (n)
(if (eq? 'zero n)
one
(twice (pow2 ((cdr n)))))))
(define print10
(lambda (n)
(define toten
(lambda (n)
(if (eq? n 'zero)
0
( 1 (toten ((cdr n)))))))
(display (toten (n)))
(newline))))
(print10 zero)
(print10 one)
(print10 two)
(print10 three)
(print10 (twice three))
(print10 (pow2 (zero)))
(print10 (pow2 (one)))
(print10 (pow2 (two)))
(print10 (pow2 (three)))
測驗會話應該如下所示：
% mit-scheme --silent <peano.scm
0
1
2
3
6
1
2
4
8
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/399410.html