如何在 Guile 方案中使用 Lazy Evaluation？

Question

我写了一个代码，它使用惰性求值来产生无限数据结构，但是有一个错误。

代码如下：

#!/usr/bin/guile \
-e main -s
!#
(define ints-f 
    (lambda (n) 
        (let ((n1 (delay (ints-f (+ n 1)))))
        (cons n (force n1)))))
(define (main args)
    (display (car (ints-f 3) ))
    (newline)
    )

这给出了一个错误，指出堆栈溢出。这意味着即使没有调用，也会执行力。如何纠正？

#!/usr/bin/guile \
-e main -s
!#
(define ints-f 
    (lambda (n) 
        (let ((n1 (delay (ints-f (+ n 1)))))
        (cons n n1))))
(define (main args)
    (display (car (ints-f 3) ))
    (newline)
    )

上面的代码给出了 3 的预期输出，但是如果我在下面的代码中使用 cdr

#!/usr/bin/guile \
-e main -s
!#
(define ints-f 
    (lambda (n) 
        (let ((n1 (delay (ints-f (+ n 1)))))
        (cons n n1))))
(define (main args)
    (display (cdr (ints-f 3) ))
    (newline)
    )

它打印一个 promise 对象。

如何在 guile scheme 中使用惰性求值？

Answer 1

第一个片段不正确，您在构建序列时强制使用该值，因此违背了惰性求值的全部目的。另一方面，第二个片段看起来是正确的——尽管它可以稍微简化一下：

(define (ints-f n)
  (cons n (delay (ints-f (+ n 1)))))

调用cdr时得到一个promise是正常的，它是一个用delay构建的thunk，只有在[=16=时才会产生它的值]d。事实上，如果你想窥视无限序列的元素，你将不得不使用一个过程来遍历你感兴趣的部分：

(define (take seq n)
  (if (= n 0)
      '()
      (cons (car seq)
            (take (force (cdr seq)) (- n 1)))))

同样：

(define (get seq idx)
  (if (= idx 0)
      (car seq)
      (get (force (cdr seq)) (- idx 1))))

例如：

(take (ints-f 5) 5)
=> '(5 6 7 8 9)

(get (ints-f 5) 5)
=> 10

Answer 2

您要创建流吗？您不妨参考(srfi srfi-41) module for an implementation of that. (Disclosure: I wrote the Guile-specific parts of the module code; everything else was ported from the reference implementation.)

(use-modules (srfi srfi-41))
(define-stream (ints-f n)
  (stream-cons n (ints-f (1+ n))))

请注意，define-stream 和 stream-cons 是在幕后共同构建（SRFI 45 风格）delay/force 的宏。 ^†

用法示例：

> (stream->list 10 (ints-f 100))
(100 101 102 103 104 105 106 107 108 109)

^† 特别是，您的函数扩展为：

(define (ints-f n)
  (lazy (eager (cons (delay n)
                     (lazy (ints-f (1+ n)))))))

您可以使用：

> (define x (ints-f 100))
> (force (car (force x)))
100
> (force (car (force (cdr (force x)))))
101

如何在 Guile 方案中使用 Lazy Evaluation？

How to use Lazy Evaluation in Guile scheme?

scheme

lazy-evaluation

guile