Hatena::Groupsicp

SICP読書記

 | 

2009-11-22

問題3.9

問題3.9 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.9 - SICP読書記

再帰

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 6)

呼び出しのスタックトレースは以下の通り。それぞれの環境に名前をつける。

(factorial 6) [E1]

→(factorial 5) [E2]

→(factorial 4) [E3]

→(factorial 3) [E4]

→(factorial 2) [E5]

→(factorial 1) [E6]

環境の構成としては

大域環境

|

    • E6
    • E5
    • E4
    • E3
    • E2
    • E1

になる。

反復版

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product count max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

(factorial 6)

呼び出しは

(factorial 6) [E1]

→(fact-iter 1 1 6) [E2]

→(fact-iter 1 2 6) [E3]

→(fact-iter 2 3 6) [E4]

→(fact-iter 6 4 6) [E5]

→(fact-iter 24 5 6) [E6]

→(fact-iter 120 6 6) [E7]

→(fact-iter 720 7 6) [E8]

環境の構成は

大域環境

    • E1
    • E2
    • E3
    • E4
    • E5
    • E6
    • E7
    • E8

結局どっちも大域環境下に直接全ての手続きが束縛されているので、環境も大域環境の一段階下にぶらさがる。

問題3.12

問題3.12 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.12 - SICP読書記

(define x (list 'a 'b))

(define y (list 'c 'd))

(define z (append x y))



(cdr x)
;;-> (b)

(define w (append! x y))

(cdr x)
;; -> (b c d)

問題3.13

問題3.13 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.13 - SICP読書記

(18088)> rlwrap gosh

gosh> (define (make-cycle x)

(set-cdr! (last-pair x) x) x)

make-cycle

gosh> (define z (make-cycle (list 'a 'b 'c)))

z

gosh> (last-pair z)

かえってこない〜

cycleを回り続けているはずですね。

append!も、set-car!やset-cdr!も、理解はできるが気持ちが悪い。。。

schemeは以外と普通のプログラミング言語だったと言うことで納得しよう。

問題3.14

問題3.14 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.14 - SICP読書記

(use slib)
(require 'trace)

(define (mystery x)
  (define (loop x y)
	(if (null? x)
		y
		(let ((temp (cdr x)))
		  (set-cdr! x y)
		  (loop temp x))))
  (trace loop)
  (loop x '()))

(define v (list 'a 'b 'c 'd))

(define w (mystery v))

(print w)

(trace loop)を入れてみた。

(mystery v)を評価したときのtraceは以下の通り

CALL loop (a b c d) ()
 CALL loop (b c d) (a)
  CALL loop (c d) (b a)
   CALL loop (d) (c b a)
    CALL loop () (d c b a)
    RETN loop (d c b a)
   RETN loop (d c b a)
  RETN loop (d c b a)
 RETN loop (d c b a)
RETN loop (d c b a)

つまり、最終的にreverseと同じ値を返す。

(set-cdr! x y)ってのは、要するにyの先頭にxをつけちゃってxとするっていう操作。それを末尾再帰でループしているのはreverse以外の何者でもない。

違うのは、最終的にmysteryの引数を壊しちゃうってこと。

最後で(print v)すると

(a)

になっちゃう。

 |