破棄されたブログ

このブログは破棄されました。

計算機プログラムの構造と解釈 問題 1.6 について

ぼちぼち「計算機プログラムの構造と解釈 (SICP) 」 を読んでいて、問題 1.6 でつまずいたので考え方について。

問題 1.6 のコードを実際の処理系で処理させると、スタックオーバーフローを起こして落ちる。 これは、実際の処理系が作用的順序で処理を行うため、 new-if 手続きにおいて predicate の評価に依らず、 then-clauseelse-clause が常に評価されることが原因。

GNU Guile などを使って、 then-clause, else-clause で文字出力をしてみるとわかりやすい。

(use-modules (ice-9 pretty-print))

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(new-if (= 1 0)
        (pretty-print "then-clause")
        (pretty-print "else-clause"))

このコードを実行すると

"then-clause"
"else-clause"

と出力され、 predicate 評価結果に依らず then-clauseelse-clause が評価されることがわかる。

では、通常の if を使うとどうなるのか。

(use-modules (ice-9 pretty-print))


(if (= 1 0)
        (pretty-print "then-clause")
        (pretty-print "else-clause"))

new-if ではなく、通常の if を使うと predicate に基づいて then-clause は評価されないため、 以下の通り、 else-clause のみが評価される。

"else-clause"

次に、問題 1.6 のコードについても考えてみる。問題のコードは次の通り。

(define (average x y)
    (/ (+ x y) 2))

(define (improve guess x)
    (average guess (/ x guess)))

(define (square x) (* x x))

(define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (sqrt-iter guess x)
    (new-if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x)
                    x)))

(define (sqrt x)
    (sqrt-iter 1.0 x))

(sqrt 5)

この処理を作用的順序で追う。

(sqrt 5)

(sqrt-iter 1.0 5)

(new-if (good-enough? 1.0 5)
    1.0
    (sqrt-iter (improve 1.0 5)
                5)))

(new-if #f
    1.0
    (sqrt-iter 3.0 5))

(new-if #f
    1.0
    (new-if (good-enough? 3.0 5)
        guess
        (sqrt-iter (improve 3.0 5)
                     5)))

(new-if #f
    1.0
    (new-if #f
        3.0
        (sqrt-iter 2.33333333333333 5)))

(new-if #f
    1.0
    (new-if #f
        3.0
        (new-if #f
            2.33333333333333
            (sqrt-iter (improve 2.33333333333333 5)
                        5)))

(new-if #f
    1.0
    (new-if #f
        3.0
        (new-if #f
            2.33333333333333
            (sqrt-iter 2.238095238 5)))

以上でわかるように、 sqrt-iter が無限に再帰呼び出しされるので、スタックオーバーフローして死ぬ。

Backtrace:
In /path/to/1.1.7.scm:
  21: 19 [sqrt-iter 2.23606797749979 5]
  21: 18 [sqrt-iter 2.23606797749979 5]
  21: 17 [sqrt-iter 2.23606797749979 5]
  21: 16 [sqrt-iter 2.23606797749979 5]
  21: 15 [sqrt-iter 2.23606797749979 5]
  21: 14 [sqrt-iter 2.23606797749979 5]
  21: 13 [sqrt-iter 2.23606797749979 5]
  21: 12 [sqrt-iter 2.23606797749979 5]
  21: 11 [sqrt-iter 2.23606797749979 5]
  21: 10 [sqrt-iter 2.23606797749979 5]
  21: 9 [sqrt-iter 2.23606797749979 5]
  21: 8 [sqrt-iter 2.23606797749979 5]
  21: 7 [sqrt-iter 2.23606797749979 5]
  21: 6 [sqrt-iter 2.23606797749979 5]
  21: 5 [sqrt-iter 2.23606797749979 5]
  21: 4 [sqrt-iter 2.23606797749979 5]
  21: 3 [sqrt-iter 2.23606797749979 5]
  21: 2 [sqrt-iter 2.23606797749979 5]
  19: 1 [sqrt-iter 2.23606797749979 5]
  12: 0 [good-enough? 2.23606797749979 5]

/path/to/1.1.7.scm:12:15: In procedure good-enough?:
/path/to/1.1.7.scm:12:15: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'.

実際に実行するとこういう感じのバックトレースを吐いたりする。

MIT の学生っていつ寝てんだ。

参考資料

更新履歴

  • 2014-05-25 参考資料を整理
広告を非表示にする