はむはむエンジニアぶろぐ

このブログのコンセプトは"ハッキングの為なら愛する家族を傷つけることをいとわない" 自分にとってエンジニアリングは "手段ではなく生きる目的" である

SICP 1.2.1 線形再帰と反復

f:id:secret_hamuhamu:20150524211758j:plain
SICPの1.2.1 線形再帰と反復を読んだので自分の言葉で内容をまとめます。
再帰的手続きと反復プロセスがややこしかったですが、理解できれば難しい話ではないと思います。
改めて手続きとプロセスは異なるものだなと実感しました。

問題1.9と問題1.10も解いたので回答を記載します。

1.2 手続きとその生成するプロセス

1.1節で、合成手続きとして抽象化するやり方を学んできた。
この状態では、どのようなケースにどのような手続き(アルゴリズム)が有効かわからない。
何故なら、どのように手続きが実行されるか予測することを学んでいないから。


手続きの生成するプロセスは、どのように実行されるのか?
我々は、手続きの生成するプロセスを視覚化して、説明できるようにならなければならない。


1.2節で確認すること

  • 生成するプロセス共通の「形」
  • プロセスが時間とスペースという計算資源を消費する速度


1.2.1 線形再帰と反復

n! = n * (n -1) * (n -2 ) ・・・ * 3 * 2 * 1 で定義する階乗関数から始める。

階乗を計算する方法は多い。

線形再帰的プロセス

まず、一つ目は任意の正の整数nに対し、n!はnに(n - 1)!を掛けたものとの考える。
n! = n * [(n - 1) * (n - 2)・・・ * 3 * 2 * 1] = n * (n - 1)!
つまり、n!は、(n - 1)!を計算し、その結果にnを掛けて計算できる。
1!は、1に等しいという規約を追加すれば、手続きに変換できる。

(define (factorial n)
  (print "n=" + n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))


この手続き(factorial)で、6!を計算する。

gosh> (factorial 6)
n = #<subr +>6
n = #<subr +>5
n = #<subr +>4
n = #<subr +>3
n = #<subr +>2
n = #<subr +>1
720


6!を計算する線形再帰プロセスを置換えモデルで表す。

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


線形反復的プロセス

次に、n!の計算の規則を、まず1に2を掛け、結果に3を掛け、4を掛け、nになるまで続けるとの規定で記述できる。
1からnまでを数えるカウンタと共に部分積を保持する。
計算は、カウンタと積を規則に従って同時に変化させ、n!はカウンタがnを超えた時の積の値であるということを記述できる。

規約

積 ← カウンタ * 積
カウンタ ← カウンタ + 1

この記述を階乗計算の手続きとして書き直す。


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

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


この手続き(factorial)で、6!を計算する。

gosh> (factorial 6)
product=#<subr +>1#<subr +>counter=#<subr +>1#<subr +>max-count=#<subr +>6
product=#<subr +>1#<subr +>counter=#<subr +>2#<subr +>max-count=#<subr +>6
product=#<subr +>2#<subr +>counter=#<subr +>3#<subr +>max-count=#<subr +>6
product=#<subr +>6#<subr +>counter=#<subr +>4#<subr +>max-count=#<subr +>6
product=#<subr +>24#<subr +>counter=#<subr +>5#<subr +>max-count=#<subr +>6
product=#<subr +>120#<subr +>counter=#<subr +>6#<subr +>max-count=#<subr +>6
product=#<subr +>720#<subr +>counter=#<subr +>7#<subr +>max-count=#<subr +>6
720


6!を計算する線形反復プロセスを置換えモデルで表す。

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


線形反復的プロセスは、再帰的手続きの実装でfor文やwhile文を使わずに反復処理を行っているものである。

線形再帰的プロセスと線形反復的プロセスを比較

2つのプロセスを比較する。
どちらもn!を計算するのにnに比例したステップを必要とする。
どちらも同じ部分積の列を作りながら、同じ乗算の列を実行する。

しかし、2つのプロセスの「形」を考える時、それらは全く異なる展開をとる。

線形再帰プロセスの置換えモデルを見て分かるように膨張とそれに続く縮小の形をとる。

線形再帰的プロセス

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


膨張は、プロセスが遅延演算の列(この場合は乗算の列)を作るときに起きる。
縮小は、演算が実際に実行される時に起きる。

遅延演算の列で特徴づけられる、この形を 再帰的プロセス という。
再帰的プロセスの実行には、解釈系は後に実行する 演算を覚えている必要 がある。
n!の計算では、遅延乗算の列の長さ分、覚えておく必要がある。
従ってそれを覚えておくのに必要な情報の量は、ステップ数のように、nに線形(nに比例して)的に成長する。
こういうプロセスを 線形再帰的プロセス という。


線形反復的プロセス

線形再帰的プロセスと対照的に、線形反復的プロセスは伸び縮みしない。
各ステップで、任意のnに対して覚えておくのは変数product, counter, max-countの現在の値である。
これを 反復的プロセス という。
反復的プロセスの状態は、一定個数の 状態変数 と、状態が移った時、状態変数をどう更新するのか?という一定した規則とプロセスを停止させる条件式で成立させる。
n!の計算に必要なステップ数はnに線形的に成長するが、こういうプロセスを 線形反復的プロセス という。


線形再帰的プロセスと線形反復的プロセスを比較②

2つのプロセスの違いは、別の見方も出来る。
反復的の方ではどの時点においてもプログラム変数がプロセスの状態の完全な記述を持っている。
計算のステップを途中で止めたら、計算再開に必要な物は3つのプログラム変数だけである。

どういうことかというと、 (factorial 6) の実行を途中で止めたとする。

(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
; 実行ストップ

実行ストップされた場所から、計算再開するにはproduct, counter, max-countの値である6, 4, 6のみでよい。
3つのプログラム変数の値さえ分かれば、 (factorial 6) から計算をやり直す必要はない。

しかし、再帰的プロセスではそうはならない。
再帰的プロセスは、解釈系が保持し、プログラム変数に含まれない「隠れた」情報がある。
それが遅延演算の列での「プロセスのいる場所」を示している。
遅延演算の列が長くなると当然、多くの情報を保持しなければならなくなる。

プロセスと手続きの違い

再帰と反復を比べる際、 再帰的プロセス(process)再帰的手続き(procedure) を混同してはいけない。
プロセスと手続きは異なる。

再帰的手続きとは、再帰的に自身である手続きを呼び出す手順のことを指す。
再帰的プロセスとは、プロセスが再帰的に展開されることを指す。

fact-iterのような再帰的手続きが反復的プロセスを生成するというのは、紛らわしい。
しかし、プロセスは反復的である。
実行中の状態は、3つの変数で完全に維持され、解釈系はプロセスを実行するのに、3つの変数を覚えておくだけでよい。

反復的プロセスというのは、for文やwhile文のような状態を持った「ループ構造」の処理のことである。

問題1.9

次の二つの手続きはどちらも, 引数を1増やす手続きincと, 引数を1減らす手続きdecを使って, 二つの正の整数を足す方法を定義している.

(define (inc x)
    (+ x 1))

(define (dec x)
    (- x 1))

; パターン1
(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

; パターン2
(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

置換えモデルを使い, それぞれの手続きが(+ 4 5)を評価する時に生成するプロセスを示せ. そのプロセスは反復的か再帰的か.

回答

まずは、 パターン1 から置換えモデルで展開をする。

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

再帰的プロセス である。

次に パターン2

(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9

反復的プロセス である。

問題1.10

まずは、問題を回答するにあたり必要な手続きを定義する。

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

次の式の値は何か.

(A 1 10)

(A 2 4)

(A 3 3)
gosh> (A 1 10)
1024
gosh> (A 2 4)
65536
gosh> (A 3 3)
65536

では、本題に入る。
問題1.10は、数学的定義を答える問題。
数学的定義ってなんだよと思いましたが、問題文中にヒントが書かれてました。
(define (k n) (* 5 n n)) の定義があるとして、(k n)の数学的定義は、 5n^2 である。
5 * n * n は、5n^2 といえる。

正の整数nに対して手続きf, gおよびhが計算する関数の簡潔な数学的定義を述べよ.

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

回答

(f n)

gosh> (f 0)
0
gosh> (f 1)
2
gosh> (f 2)
4
gosh> (f 3)
6
gosh> (f 4)
8

数学的定義

(f n) の実行結果が、 n * 2 となっている。
f(n) = 2n


(g n)

gosh> (g 0)
0
gosh> (g 1)
2  ; 2^1
gosh> (g 2)
4  ; 2^2
gosh> (g 3)
8  ; 2^3
gosh> (g 4)
16 ; 2^4

数学的定義

(g n) に実行結果が、 2のべき乗となっている。
ただし、Wikipediaのべき乗の指数の拡張と指数法則によれば 2^0 = 1 である。
それを踏まえると、数学定義はこうなる。
g(n) = 2^n ただし、n = 0であれば g(0) = 0

(h n)

gosh> (h 0)
0
gosh> (h 1)
2
gosh> (h 2)
4
gosh> (h 3)
16
gosh> (h 4)
65536

数学的定義

結構この問題は難しかったです。

まず、 A(1, n) = g(n) である。
ということは、 A(1, n) = 2^n と置換えられる。

(h 3)(h 4) を途中まで、置換えモデルで展開してみる。

(define (h n) (A 2 n))
(h 3)
(A 2 3)
(A 1 (A 2 2))
(A 1 (A 1 (A 2 1)))
(A 1 (A 1 2))
(A 1 (A 0 (A 1 1)))
(A 1 4)
(A 1 4)
(define (h n) (A 2 n))
(h 4)
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)


(h 3) は、 2^(2 * 2)
(h 4) は、 2^(2 * 2 * 2 * 2)
222^・・・とn回計算することになる。

h(n)  =  2^h(n-1)     n > 1 の時
h(1)  =  2            n = 1の時
h(0)  =  0            n = 0の時

となる。
ちょっと (h n) の数学的定理は、あっているか自信なし。

最近読んだ本

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで

Short Coding ~職人達の技法~

Short Coding ~職人達の技法~