为什么在函数定义中进行自调用是合法的，但对于值是非法的？

Question

Structure and Interpretation of Computer Programs (SICP) 3.5.2 引入无限流：

(define ones
  (cons-stream 1 ones))

此代码在 DrRacket 中无效，错误为：

ones: undefined; cannot reference an identifier before its definition

像这样的其他代码：

(define (integers-starting-from n)
  (cons-stream n
               (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

产生错误：

Interactions disabled

（陷入死循环？）

据我阅读（SICP），实现无限流的关键点是延迟评估：

(define (delay exp)
  (lambda () exp))

(define (cons-stream a b)
  (cons a
        (delay b)))

在cons-stream中使用这个，无限流仍然是非法的。

这样的数据结构让我想起了递归函数，在其定义中自调用在实际退出或没有实际退出时都是合法的（在编译中）。

为什么值引用自身是非法的？连引用都延迟了？

其他编程语言可以支持无限流吗？

如果不是，是关于处理器处理汇编语言的方式吗？数据栈的东西？

Answer 1

这是因为define 中的表达式在名称绑定到一个值之前被求值。它尝试在定义 ones 之前评估 (cons-stream 1 ones)，从而导致错误。

这对函数工作良好的原因是 函数的主体没有被计算 函数被计算时。也就是说，要评估 (lambda (x) (f x))，语言 returns 一个函数而不看它的主体。自

(define (f x) (f x))

是定义lambda的语法糖，逻辑相同。

你自己定义cons-stream了吗？如果您将 cons-stream 设为普通函数，它将无法正常工作。由于 Scheme 在默认情况下是严格的，因此在调用函数之前 评估参数。如果 cons-stream 是一个普通函数，b 将在传递给 delay 之前得到完整的计算，使你陷入无限循环。

cons-stream 在 SICP 中是一个 "special form" 而不是函数，这意味着它可以控制如何计算其参数。

如果您使用 Racket 中内置的 stream-cons 和其他 stream- 操作，您将获得所需的行为。

最后，其他一些语言允许值引用自身。一个很好的例子是 Haskell，因为默认情况下一切都是 惰性的 。这是一个 Haskell 片段，将 ones 定义为无限列表。（因为一切都是惰性的，Haskell 列表的行为就像 Scheme 流）：

ones = 1 : ones

Answer 2

此定义适用于 Racket：

(define ones
  (cons-stream 1 ones))

…只要您提供 cons-stream 的延迟实现作为特殊形式，这就是 SICP 中第 3.5 节的全部要点：

(define-syntax cons-stream
  (syntax-rules ()
    ((_ head tail)
     (cons head (delay tail)))))

Answer 3

当您创建一个过程时，当您启动该过程的主体时，参数已经被评估。因此 delay 不会做任何事情，因为它已经在那个时候计算过了。 cons-stream 需要是一个宏。

DrRacket 不是一种语言实现。这是一个支持多种语言的 IDE。其中之一是 SICP 兼容语言。我在 DrRacket 中使用这段代码运行你的代码没有错误:

#!planet neil/sicp

(define ones
  (cons-stream 1 ones))

(define (integers-starting-from n)
  (cons-stream n
               (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

它就像一个魅力。 DrRacket中的默认语言，#!racket，has streams too，只是名字不同：

#!racket 

(define ones
  (stream-cons 1 ones))

(define (integers-starting-from n)
  (stream-cons n
               (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

然而，对于 Scheme，您应该使用 SRFI-41，您可以从 #!racket（使用 (require srfi/41)）和 #!r6rs（完成后使用 R7RS-large）

(import (rnrs)
        (srfi :41))

(define ones
  (stream-cons 1 ones))

(define (integers-starting-from n)
  (stream-cons n
               (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

要在 #!racket 和 #!r6rs 中滚动您自己的 SICP 流，您可以使用 define-syntax

(define-syntax stream-cons 
  (syntax-rules ()
    ((_ a d) (cons a (delay d)))))

请注意，RSFI-41 和球拍拥有 #!racket 的流库会延迟 stream-cons 中的两个值，而不仅仅是此处 SICP 版本中的尾部。

Answer 4

除了上面的答案之外，为了确保代码运行，您还应该像这样定义 delay：

(define-syntax delay
  (syntax-rules ()
    ((_ exp)
     (lambda () exp))))

delay 以及 cons-stream 必须定义为宏。

在另一种选择中，您可以只调用 Racket 中预定义的 delay 而不是构建新的。

但不要这样做：

(define (delay exp)
  (lambda () exp))

编译器会采用您的定义，因此程序在求值时崩溃：

Interactions disabled

为什么在函数定义中进行自调用是合法的，但对于值是非法的？

Why is it legal in a function definition to make self-call but illegal for a value?

functional-programming

scheme

racket

sicp