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

私の実装と教授のコードの両方のコードは、同じ結果に達します。しかし、それらが同じ性質を持っているかどうかはわかりません。

したがって、私は自問し始めました: 私の実装は本当に不可欠でしたか? 「セット！」を使用するだけです。それを保証しますか？

教授の補助反復関数には引数がまったくありませんが、私はまだ補助反復手順でパラメーターを使用しています。これは私の質問に答える核となるものですか？

ありがとう！SOユーザーは私を大いに助けてくれました!

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と引数の唯一の理由は、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)))

OK、まあ、これで、副作用がなく終了する限り、形式の式(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)))

OK、これで次のような形(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: 「見事に狂った」は侮辱を意味するものではありませんでした。そのように解釈されないことを願っています。

于 2016-10-20T19:19:15.840 に答える