4

我正在与 Racket 和 Dr. Racket 一起研究 SICP 书。我也在看以下讲座：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/5a-assignment-状态和副作用/

在第 3 章，作者介绍了命令式编程的概念。

为了说明含义，他们将使用函数式编程的阶乘过程的实现与使用命令式编程的实现进行了对比。

下面你有一个使用函数式编程的迭代过程的递归定义：

(define (factorial-iter n)
  (define (iter n accu)
    (if (= n 0)
        accu
        (iter (- n 1) (* accu n))))
  ; (trace iter)
  (iter n 1))

在教授要介绍一个命令式实现之前，我尝试了自己。

我使用命令“set！”到达了这段代码：

(define (factorial-imp n count product)
  (set! product 1)
  (set! count 1)
  (define (iter count product)
    (if (> count n)
        product
        (iter (add1 count) (* product count))))
  (iter count product))

但是，教授的实现与我的命令式实现完全不同：

(define (factorial-imp-sicp n)
  (let ((count 1) (i 1))
    (define (loop)
      (cond ((> count n) i)
            (else (set! i (* count i))
                  (set! count (add1 count))
                  (loop))))
    (loop)))

两个代码，我的实现和教授的代码，都达到了相同的结果。但我不确定它们是否具有相同的性质。

因此，我开始问自己：我的实施真的势在必行吗？只需使用“设置！” 保证？

我仍然在我的辅助迭代过程中使用参数，而教授的辅助迭代函数根本没有任何参数。这是回答我问题的核心吗？

谢谢！所以用户一直在帮助我很多！

4

2 回答 2

3

您的解决方案非常疯狂，因为它看起来势在必行，但实际上并非如此。（下面的一些内容是特定于球拍的，但并不重要。）

从您的实施开始：

(define (factorial-imp n count product)
  (set! product 1)
  (set! count 1)
  (define (iter count product)
    (if (> count n)
        product
        (iter (add1 count) (* product count))))
  (iter count product))

count好吧，使用and参数的唯一原因product是为这些变量创建绑定：从不使用参数的值。所以让我们明确地用 来做这件事，let我最初会将它们绑定到一个未定义的对象，因此很明显从未使用过绑定（我还重命名了内部函数的参数，因此很明显这些是不同的绑定）：

(require racket/undefined)

(define (factorial-imp n)
  (let ([product undefined]
        [count undefined])
    (set! product 1)
    (set! count 1)
    (define (iter c p)
      (if (> c n)
          p
          (iter (add1 c) (* p c))))
    (iter count product)))

好的，现在很明显，只要是没有副作用并终止的任何形式的表达式都(let ([x <y>]) (set! x <z>) ...)可以立即替换为。这里就是这样，所以我们可以将上面的内容改写如下：(let ([x <z>]) ...)<y>

(define (factorial-imp n)
  (let ([product 1]
        [count 1])
    (define (iter c p)
      (if (> c n)
          p
          (iter (add1 c) (* p c))))
    (iter count product)))

好的，所以现在我们有了以下形式(let ([x <y>]) (f x))：这可以简单地替换为(f <y>)：

(define (factorial-imp n)
  (define (iter c p)
    (if (> c n)
        p
        (iter (add1 c) (* p c))))
  (iter 1 1))

现在很明显，您的实现实际上并不是以任何有用的方式强制执行的。它确实会改变绑定，但它只会改变一次，并且在突变之前从不使用原始绑定。我认为这本质上是编译器编写者称之为“静态单一分配”的东西：每个变量都被分配一次，并且在分配之前不使用。

PS：'splendidly mad'并不是侮辱，我希望它没有被这样理解，我很高兴回答这个问题！

于 2016-10-20T19:19:15.840 回答
1

Usingset!通过更改绑定引入了副作用，但是您将其从传递的值更改为1不使用传递的值，并且之后您永远不会更改该值，人们可能会将其视为传递给助手的常量，如下所示1：1

(define (factorial-imp n ignored-1 ignored-2)
  (define (iter count product)
    (if (> count n)
        product
        (iter (add1 count) (* product count))))
  (iter 1 1))

助手通过递归更新它count，product因此是 100% 功能的。

如果你用命令式语言做同样的事情，你会在循环外创建一个变量，你会在循环中的每一步更新它，就像教授的实现一样。

在您的版本中，您更改了合同。用户需要传递两个不用于任何事情的参数。我通过调用它们ignored-1和来说明这一点ignored-2。

于 2016-10-21T08:17:27.410 回答