SICP

Question

我正在和 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-state-and-side-effects/

在第 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)))

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

因此，我开始问自己：我的实施真的是势在必行吗？仅使用 "set!" 就可以保证吗？

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

谢谢！ SO 用户一直在帮助我！

Answer 1

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

从您的实施开始：

(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 和 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))

现在很明显，您的实施实际上在任何有用方面都不是命令式的。它确实会改变绑定，但只会改变一次，并且从不使用改变前的原始绑定。这本质上就是编译器作者所说的东西 'static single assignment' 我认为：每个变量都被赋值一次并且在赋值之前未被使用。

PS：'splendidly mad' 不是侮辱，我希望这不是侮辱，我很高兴回答这个问题！

Answer 2

使用 set! 通过更改绑定引入副作用，但是您将它从传递的值更改为 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.

来说明这一点

SICP - 阶乘的命令式与功能式实现

SICP - Imperative versus Functional implementation of factorial

lisp

functional-programming

imperative-programming

racket