｢裏｣勉強会その２メモ

本日第4回目が開かれるのですが...2回目のメモでございます.
maoeの日記 SICP勉強会

ifはなんで特殊形式?

特殊形式とは, あらかじめプログラムに定義されている関数などのこと.
C言語で言えばマクロみたいなもの(正確には違うとか)

では, ifはなんで特殊形式なんでしょうか?
次のように条件式を作成するcondで表すことができるよね?

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

実際使えば,

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

とつかえるはず.

しかしこいつには問題があるのです.
例として次の関数を考える.

(define (test a)
  (new-if (= a 0)
          0
          (test a)))

こう定義して

(test 0)

を評価する. すると

((lambda (test a)
    (new-if (= a 0)
            0
            (test a)))
 0)

ここで展開するとき, 条件文の中の引数をやっつける
作用的順序であることを忘れてはいけない.
つまり先に条件式内の(test a)を展開するのだ.

((lambda (test a)
    (new-if (= a 0)
            0
            (lambda (test a)
               (new-if (= a 0)
                       0
                       (test a))))
 0)

おっと. こいつはやばいまた条件式にtest関数がでてきたぞ!

((lambda (test a)
    (new-if (= a 0)
            0
            (lambda (test a)
               (new-if (= a 0)
                       0
                       (lambda (test a)
                          (new-if (= a 0)
                                  0
                                  (test a)))))
 0)

終わらない. このような感じで条件式のなかを展開し続けて
無限ループに陥ってしまうのだ.

こうしないために特殊形式のifがある.
これは条件に合致する方の｢式を抜き出して」計算してくれる.
だから無限展開地獄に陥ることがないのです!

((lambda (test a)
    (if (= a 0)
        0
        (test a)))
 0)
 
(if (= 0 0)
    0
    (test a))

(if #t 0 (test a))

0

よし, 解決!
このように作用的順序では不都合な場合があるため,
あらかじめ特殊形式でifを定義しておいてあるのだ.
無駄に特殊形式があるわけではないのだよ.

再帰的プロセスと反復的プロセス

まず階乗( n! = n(n-1)(n-2)…2・1 )を求める関数を作ってみよう.

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

できた!
この関数の流れをおっかけてみよう. nに6を代入してみると,

(fact 6))
(* 6 (fact 5)))
(* 6 (* 5 (fact 4))))
(* 6 (* 5 (* 4 (fact 3)))))
(* 6 (* 5 (* 4 (* 3 (fact 2))))))
(* 6 (* 5 (* 4 (* 3 (* 2 (fact 1)))))))
(* 6 (* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))))
(* 6 (* 5 (* 4 (* 3 (* 2 (* 1 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

なんじゃこりゃ?? どんどん膨らんでいくぞ.
数が大きくなればなるほどこの計算に必要なメモリの量が増えますな.
線形オーダってやつ.

そこで次の階乗の計算を次の関数で表してみる.

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

ちょっと一瞬では判断ができないような関数.
また6いれて追っかけてみよ!

(fact-iter 1   1 6)
(fact-iter 1   1 6)
(fact-iter 2   1 6)
(fact-iter 3   2 6)
(fact-iter 4   6 6)
(fact-iter 5  24 6)
(fact-iter 6 120 6)
720

お!解がでましたな〓!
しかも覚えておく数は3つのままだぞ.
資源が無駄に使われることがなさそうですな.

この2つの関数は｢再帰的プロセス｣と｢反復的プロセス｣の特徴があります.
どっちも再帰のプログラムを使用してはいるんです.
この2つの大きな違いは再帰をおこなうタイミング.

再帰的プロセスとは...
条件式の中で最後の計算が四則演算などの演算子である場合.
再帰していくたびに覚えておかなくてはいけない引数・演算子が増えるのです.

一方反復的プロセスとは...
条件式の中で再帰を最後におこなう場合.
演算後に再帰をおこなうので引数・演算子を覚えておく必要がないのです.

もちろん反復的プロセスのほうがマシンにやさしいのです.
ただ, 人間の脳みそ的には再帰的プロセスのほうが直感的に書きやすい.
こいつは悩ましい...