SICP 1.2 Procedures and the Processes They Generate

前回のアップロードが5月27日なので約3ヶ月ぶりとなります。この間本業が大変忙しかったのですが漸く帰って来ました。暫くペースは上げられませんが地道に頑張ります。

ノート

手続きとそれが生成するプロセス。

Our situation is analogous to that of someone who has learned the rules for how the pieces move in chess but knows nothing of typical openings, tactics, or strategy. Like the novice chess player, we don't yet know the common patterns of usage in the domain.

どうやって基本的な関数を組み合わせて新しい関数を作るのかを学んだが、まだチェスで言えば駒の動かし方を覚えたに過ぎない。序盤戦、定石、戦略と言ったものを学んだ訳ではない。

The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer,

エキスパートになるにはプロセスの挙動をイメージ（可視化）出来る様になる必要がある。

1.2.1 Linear Recursion and Iteration

線形再帰（？）と繰り返し。

まずは普通の階乗の定義

> (factorial 6)
720
>

与えられたnに比例して、保留されたかけ算の数（deferred operations）が膨れ上がり、計算しながら収縮する。
linear recursive processと呼ばれる。

次に、引数としてx!、x、n（n!を求める）の３つの値を取る関数で、x=1から始めてx=nとなるまで再帰する関数

> (factorial 6)
720
>

同じく再帰はしているが保留した演算はないので膨れ上がらない。iterative processと呼ぶ。
ここでの引数をstate variableと呼んでいる模様。

iterative processでは計算の途中経過が常に変数に保存されているので、計算を一旦中断してもこれらの値さえ分かれば再開する事は簡単*1。一方recursive processの場合は保留された演算はインタープリタの内部で保存されているものなので状況は異なる。

ここでrecursive processとrecursive procedureを混同してはいけない。procedureがrecursiveだと言った場合は、その手続きが自分自身を呼び出す事を意味している。一方recursive processは保留された計算が膨れ上がる様な状況を指している。recursive procedureでも保留された計算が無ければiterative processと言える。

processとprocedureが混同されるひとつの理由はAda、Pascal、Cと言った言語は例えprocessがiterativeでもrecursive procedureだと必ずrecursive processの様にスタックが膨れ上がる様に設計されている事による。なのでこれらの言語でiterarive processを表現するには何らかのループ構文が必要になる。
5章で実装する事となるSchemeにはこの欠点が無い。例えrecursive procedureであってもiterarive processであれば一定のスタック消費量で計算される。このような実装を末尾再帰（tail-recusive）と呼ぶ。

Exercise 1.9

(+ 4 5)を二つの実装について計算過程を検証する。

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

recursive processと言える。

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

iterative processと言える。

を再帰的に呼び出す時に、+の戻り値を更に別の演算に使う場合はその演算が保留されるためrecursive processとなる。前者の場合はincが保留される。後者は+の再帰呼び出しが最後で+の戻り値がそのまま自身の戻り値となるので保留される演算が無い。

Exercise 1.10

『Scheme手習い』でも登場するAckermann関数が早くも登場。
実行してみる。

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

トレースすると：

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024

次は

(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)
(A 0 (A 1 15))
…ここまで来ると、yが1になるまで展開される事が分かっている。
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1))))))))))))))
…で、この後は2の冪乗が並ぶ事も分かっている。(A 1 16)まで来れば2^16と分かる。
65536

次は

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1))
(A 2 (A 0 2))
(A 2 4)
…ここで上の問題と同じになる。
65536