如何有效地在 Scheme 中使用惰性？
How to use of laziness in Scheme efficiently?
我正在尝试在 Scheme 中使用代数数据类型对一个小的 lambda 演算进行编码。我希望它使用惰性求值，为此我尝试使用原语 delay 和 force。然而，这对评估性能有很大的负面影响：小型测试用例的执行时间增加了 20 倍。
虽然我没想到懒惰会加速这个特定的测试用例，但我也没想到会出现巨大的减速。因此，我的问题是：是什么导致惰性求值的巨大开销，我如何在仍然进行惰性求值的同时避免这个问题？我已经很乐意将执行时间缩短到 2 倍以内严格版本，但当然越快越好。
以下是我使用的测试用例的严格版本和惰性版本。该测试以一元表示法处理自然数：它构造一个 2^24 suc 后跟 zero 的序列，然后再次破坏结果。惰性版本是通过在适当的位置添加 delay 和 force 并添加 let-bindings 以避免多次强制参数来构建的。 （我也尝试了一个 zero 和 suc 是严格的但其他函数是惰性的版本，但这比完全惰性的版本还要慢，所以我在这里省略它。）
我在 Chez Scheme 9.5 中使用 compile-file 编译了这两个程序，并使用 petite --program 执行生成的 .so 文件。严格版本的执行时间（仅限用户）为 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))))))
这听起来很像是 Haskell 中不时出现的问题。问题是垃圾回收之一。
这有两种方法。首先，lazy list可以随用随用，这样消耗的内存量是有限的。或者，其次，惰性列表可以以一种始终保留在内存中的方式进行评估，列表的一端固定在适当的位置，因为它仍在使用 - 垃圾收集器反对这一点并花费了很多是时候尝试处理这种情况了。
Haskell 可以和 C 一样快，但要求计算严格才能做到这一点。
我不完全理解代码，但它似乎在递归地创建一个越来越长的列表，然后对其进行评估。您是否有工具来测量垃圾收集器必须处理的内存量，以及垃圾收集器运行的时间？
您尝试做的不是 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
可以使用 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% 的时间都在收集。调整 collector parameters 可能会改善这一点，例如：
(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 实现是 here）
通过这些更改，惰性版本比严格版本慢 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
我正在尝试在 Scheme 中使用代数数据类型对一个小的 lambda 演算进行编码。我希望它使用惰性求值，为此我尝试使用原语 delay 和 force。然而，这对评估性能有很大的负面影响：小型测试用例的执行时间增加了 20 倍。
虽然我没想到懒惰会加速这个特定的测试用例，但我也没想到会出现巨大的减速。因此，我的问题是：是什么导致惰性求值的巨大开销，我如何在仍然进行惰性求值的同时避免这个问题？我已经很乐意将执行时间缩短到 2 倍以内严格版本，但当然越快越好。
以下是我使用的测试用例的严格版本和惰性版本。该测试以一元表示法处理自然数：它构造一个 2^24 suc 后跟 zero 的序列，然后再次破坏结果。惰性版本是通过在适当的位置添加 delay 和 force 并添加 let-bindings 以避免多次强制参数来构建的。 （我也尝试了一个 zero 和 suc 是严格的但其他函数是惰性的版本，但这比完全惰性的版本还要慢，所以我在这里省略它。）
我在 Chez Scheme 9.5 中使用 compile-file 编译了这两个程序，并使用 petite --program 执行生成的 .so 文件。严格版本的执行时间（仅限用户）为 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))))))
这听起来很像是 Haskell 中不时出现的问题。问题是垃圾回收之一。
这有两种方法。首先，lazy list可以随用随用，这样消耗的内存量是有限的。或者，其次，惰性列表可以以一种始终保留在内存中的方式进行评估，列表的一端固定在适当的位置，因为它仍在使用 - 垃圾收集器反对这一点并花费了很多是时候尝试处理这种情况了。
Haskell 可以和 C 一样快，但要求计算严格才能做到这一点。
我不完全理解代码，但它似乎在递归地创建一个越来越长的列表，然后对其进行评估。您是否有工具来测量垃圾收集器必须处理的内存量，以及垃圾收集器运行的时间？
您尝试做的不是 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
可以使用 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% 的时间都在收集。调整 collector parameters 可能会改善这一点，例如：
(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 实现是 here）
通过这些更改，惰性版本比严格版本慢 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