数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.2.1)
4/20: minghaiさんによる翻訳の更新を反映しました。
minghaiさんによるSICP全訳を読んでいます。
前回の記事にたくさんブックマークをいただき嬉しかったです！ありがとうございます。一人で5章まで続けられるか不安だったのですが、かなりモチベーションになりました。
あと翻訳を公開されたid:minghaiさんが前回の記事をブログでとりあげてくださり、ものすごくびっくりしました！とても嬉しかったとコメントをいただけて私もとてもとても嬉しくて飛び上がりました。（あと、はてなID記法というものを初めて知りました・・・。）
ありがとうございます！！がんばりたいと思います。
SICP、さっそく続きです。
と、その前に、そろそろ手続の展開順序を追う系の内容が増えてきたので、traceを導入しました。
slibを入れてtraceを見る
The SLIB Portable Scheme Libraryから。
以下はhomebrewでGaucheを入れている場合です。
cd /usr/local wget http://groups.csail.mit.edu/mac/ftpdir/scm/slib-3b4.zip unzip slib-3b4.zip cd slib sudo make infoz sudo make install
で、vimからGoshREPL起動して
(use slib) (require 'trace) (trace トレースしたい関数名)
でOK！
そのあとその関数使うとTraceを出力してくれます。なんて便利。
では続きいきたいと思います。
1.2 「手続とそれが生成するプロセス」
1.2の序文から引用。
エキスパートになるためには、数多くの種類の手続により生成されるプロセスを心に描けられるようにならなければなりません。そのようなスキルを開発した後に初めて望んだ挙動を示すプログラムを信頼できる形で構築する方法を学ぶことが可能になります。 この節では簡単な手続により生成されたプロセスのためのいくつかの共通 な “形” について検討してみます。またこれらのプロセスが時間と記憶域の重 要な計算資源をどの程度消費するかについても調査してみます。
よーしがんばろう。
前回は1.1(1.1.1〜1.1.8)を一気にやりましたが、1.2に入ってからますます手応えのある（そして重要な）内容になってきたように感じるので、小刻みに書いていきたいと思います。
今回は1.2.1「線形再帰と反復」です。
1.2.1 線形再帰と反復
この章、１回読んだだけではすっとわからなかったのでわかるまで何度も読み返しました。
で、加えて調べたりして、やっと整理がついた気がします。現時点での理解を図にしてみました。
ちょっとごちゃついてますが・・・
上から１段ずつ理解した内容を書いていくので、図も含め、もし間違えてる点あったら教えて下さい。
１段目：繰り返しが必要な処理
例として「nの階乗を求める」という内容が挙げられていました。
n! = n * (n-1)!
階乗の定義内で階乗を使っているので、!を「繰り返し」展開することが必要です。
繰り返しを行う手続に見られるパターンとして、「再帰」と「反復」があります。
２段目：構文上の「再帰手続」と「反復手続」
「再帰」とは、簡単に言うと自分の中で自分を参照していること。
「反復」とは、ループ、繰り返し。反復をループと言い換えると普段forとかeachとかwhileとか使っているので馴染みやすい。
で、１段目から２段目への矢印に再帰と反復の違いを書いていますが、この違いは構文上どっちの手続として記述されているか、という話です。
２段目を「再帰」「反復」と略して書いていますが、SICPでの言葉を借りて厳密に表すと「再帰手続」「反復手続」です。
そして本文内で注意があったのが、「手続」と「プロセス」は別物だということです。
再帰手続と再帰プロセスについての違いを引用します。
反復と再帰の対称性において、再帰プロセスの概念と再帰手続の概念を混同しないように注意せねばなりません。私達が手続を再帰だと説明する時、手続の定義が (直接、または間接的に) その手続自身を参照するという構文上の事実を参照します。しかし、プロセスがあるパターン、例えば、線形再帰に従うと説明する時、私達はプロセスがどのように展開するかについて話しており、手続がどのように書かれているかという構文については話していません。
なるほど。
- 「手続」とは、構文上の事実
- 「プロセス」とは、実際の処理がどのように展開されるかということ
図で言うと、手続→上から２段目、プロセス→上から４段目 になります。
この「手続とプロセスの違い」、あまり意識してみたことがなかったです。
構文上で再帰的な書き方になっていれば実際の処理も再帰的な内容になると思っていました。
そうではないケース「構文上は再帰手続なのに、実行されるプロセスは反復になる」というのはどういうことか？
本文内に「再帰プロセスで階乗を求める関数」と「反復プロセスで階乗を求める関数」の例が載っていましたので引用します。
まず構文的にもプロセスとしても再帰的になる例。
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
次に、構文は再帰的（fact-iter内でfact-iterを呼び出している）だけどプロセスが再帰ではなく反復になる例。
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
このふたつの構文内のどこが再帰プロセスと反復プロセスの分岐点になるのかなと考察して気づいたこと。
「自身を呼び出したあとに何らかの処理がある」場合、戻ってきてその処理をするために、自身が呼び出された文脈を毎回覚えておかないといけないですよね。（前者のプログラムでは(* n (factorial (- n 1)))の部分）
factorialの中でfactorialを呼び出してその結果をnに掛けるということは、呼び出したすべてのfactorialの結果を覚えておいて、それが全部揃ってから順々にかけていくことになるので、nが大きくなって再帰の深さが増すほど「覚えておかなければいけない情報」が増えていきます。
一方後者では「自身(fact-iter)を呼び出した結果」には何も計算を加えていなくて、そのままif文の結果になっているだけです。
だから最後に(> counter max-count)が真になったとき、productを返して即実行を終了できる。
その違いなのかなあと思いました。
と思ったのですが、やっぱり引っかかる。
自身の結果がそのまま戻り値になるからといって、自身を何度も呼び出した最下層で即終了なんてことができるのか？
自身の結果に計算を加えてなくても、最下層で計算し終えた最終的な値を最上層までReturnし続ける処理は行われるのではないかと思ったのです。
両方とも最初まで戻っていく必要があるのだとしたら、結局「自分がどこで呼び出されたか」という「覚えておかなければいけない情報」は一緒になる気がします。
うむむ。。。
後者は何が節約できるんだろう？
ここで悩んでいたのですが、解決の鍵は３段目の「末尾再帰」という言葉にありました。
３段目：「末尾再帰」そして「末尾再帰最適化」
ここが最初よく理解できなかったのですが、この「末尾再帰」と「末尾再帰最適化」の意味を調べてからやっと「再帰と反復」の章の理解に至りました。。
まず、末尾再帰とは何か。
末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。
末尾再帰 - Wikipedia
つまり上の２つの関数で言うと、後者が末尾再帰です。fact-iterの手続の最後のステップは自身、fact-iterの呼び出しだからです。
前者の関数は最後の行でfactorialを呼び出していますが、末尾再帰ではありません。そのあとに*nを実行しているので、最後のステップは*（乗算）です。
で、末尾再帰だと何が嬉しいの？ってことですが、、、
２段目の説明で前述したように、末尾再帰の形だと自身の戻り値に計算を加えないので
「最下層で自身が返す値と最上層で最終的に返す値が同じ」なんですよね。
それなのに同じ値をReturnし続けて最上層まで戻っていくのは無駄です。
でも言語の処理上、そういう動作になってしまう。
そこで！！
「末尾再帰の形になっている手続きは、不要なReturnの連鎖を省略し、最下層から最上層までジャンプして結果を返す形に書き換える」という最適化をコンパイル時に行ってくれるのが「末尾再帰最適化」なのです！！
そして、SICPで使用しているSchemeという言語は末尾再帰最適化を行うことが言語仕様に含まれているため、必ずそれを行ってくれるのです！！
呼び出し元へ戻る必要がなくなるということは、毎回自身を呼び出すたびに、その前に呼び出して実行していた自身の手続きを忘れられるということです。
同じ処理を繰り返すんだけど、前の処理を覚えている必要はなくて、決められた回数分実行されたら終了。
それはまさに「ループ」と同じです。
だから、Schemeでは手続を末尾再帰の形で記述すれば処理系によって最適化されて再帰プロセスではなく反復プロセスとして実行されるのです！！
つまり、２段目の説明の最後にもやもやしていた「後者でも結局最上層までReturnが必要なのでは？」という疑問は、「末尾再帰最適化を備えていない言語処理系ではそうなる」という答えになりますね。
たとえばCとか。Rubyもそうみたいです。
そういう言語の場合は、用意されている反復構造（forとかwhileとか色々）を使って構文レベルから手続を反復で書くことで反復プロセスとして実行するのですね。
実はこれSICP1.2.1本文内に言及があります。（ただ読んだ時点では事前知識が足りず理解できなかった。。。）
ちょっと長いけどまるごと引用します。
プロセスとプロシジャ (手続) の区別が混乱を招き易いのは、(Ada や Pascal、C 言語を含む) 多くの一般的言語の実装が、例えプロセスが本質的には反復で記述されていても、任意の再帰手続の逐次実行が手続呼出の回数に伴い多くのメモリ容量を消費するように設計されているためです。結果としてこれらの言語は反復プロセスのみを特別な目的の “ループ構成概念” である do, repeat,until, for, while のような物を用いて記述します。私達がChapter 5にて考える Scheme の実装はこの短所を共有しません。例え反復プロセスが再帰手続により記述されていても定量的な記憶域にて実行します。この属性を持つ実装はtail-recursive(末尾再帰) と呼ばれます。末尾再帰の実装を用いれば反復は一般的な手続呼出メカニズムを用いて表現可能であり、特別な反復構成概念は構文糖としてのみ実益のあるものとなります。
つまり、他の言語では反復プロセスは反復手続として記述しないといけない場合が多いけど、Schemeでは反復プロセスを再帰手続として記述できる。
だから前述した後者の関数は「構文としては確かに再帰手続だけどScheme処理系によって最適化されて反復プロセスと同様に実行される」。ということになりますかね。
図でいうと、再帰手続→末尾再帰→（末尾再帰最適化）→反復プロセス というルートになると思います。
あーすっきりしたーー。。
私はこういうの全然知らなかったので・・・
普段自分が書く言語（PHP、Ruby）で後者の手続きを書いたとしても最適化されずに再帰プロセスとして実行されるはずなので、直感的に納得できなかったんですね。
Schemeの特性を知る必要がありました。
あとちょっと頑張って、４段目についても考察してみようと思います。
４段目：再帰プロセスと反復プロセス
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 (* 4 6))) (* 6 (* 5 24)) (* 6 120) 720
遅延演算の連鎖として示されるこのタイプのプロセスはrecursive process(再帰プロセス) と呼ばれます。このプロセスの実行にはインタプリタが後の実行ために操作の過程を記録する必要があります。
自身を呼び出すたびに自身が展開され、戻っていくと同時に収縮していきます。
自身の呼び出し元へ戻っていくために、どういう文脈で呼び出されたのかをインタプリタが内部的に覚えておかないといけないわけですね。
次に反復プロセスの関数がたどるプロセスと解説。
(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
対照的に、2 つ目のプロセスは展開も収縮もしません。各ステップにおいて追跡が必要な物はどの n に対しても変数 product, counter, max-count の現在値です。これをiterative process(反復プロセス) と呼びます。一般的に、反復プロセスは限られた数のstate variables(状態変数) により状態が、集約されることが可能な物です。状態変数がプロセスが状態毎にどのように更新されるかという固定ルールとプロセスが停止する条件を指定する (任意の) 終了試験と一緒に用います。
「更新ルール・終了条件と一緒に用いる」という点はまさにループですね。
「限られた数の状態変数によって状態を集約できること」というのもポイントだなと思いました。
fact-iterでは自身を呼び出す際に「計算に必要な情報」をすべて引数として渡しているから、最後に自身を呼び出したときに最終的な720という答えにたどり着ける。
だから自身の返り値に計算を加える必要がないため、末尾再帰の形で記述できる、ということなのかなと思いました。
あと参考になる部分をもう一か所引用。
2 つのプロセスの対称性は他の見方もできます。反復の場合、プログラムの変数は任意のポイントにおいてプロセスの状態について完全な描写を提供します。もしステップの間で計算を停止した場合に、計算の再開を行うのに必要な全てはインタプリタに対し 3 つのプログラム変数の値を提供することです。再帰プロセスではそうはいきません。この場合、いくつかの追加の “隠された” 情報が存在し、インタプリタにより保持されており、プログラムの変数には保存されていません。その情報には遅延命令の連鎖を辿る中での “プロセスの現在地” が示されています。鎖が長い程、より多くの情報が保持される必要があります。
「線形」という言葉について
今回進めた1.2.1章の題目は「線形再帰と反復」です。
「線形」という言葉についても触れておきたいと思います。
「４段目：再帰プロセスと反復プロセス」で引用したふたつのプロセス（関数定義ではなく、展開されるプロセスのほうです）について、下記のような記述があります。
2 つのプロセスを比べてみて下さい。1 つの見方としては、これらはほとんど同じに見えます。両者は同じ数学の関数を同じ領域で計算し、それぞれが n! を求めるのに n に比例したステップ数を必要とします。
ここ、個人的に混同してしまいそうなので注意だなと思いました。
再帰プロセスのほうも反復プロセスのほうも、ステップ数はnに比例します。
再帰プロセスと反復プロセスで大きく異なるのはステップ数ではなく記憶域の消費量ということですかね。
で、両方ともプロセス数がnに比例して線形に増加するからそれぞれ線形再帰プロセス・線形反復プロセスと呼ぶのかなと思ったのですが、本文を読むと「線形再帰プロセス」と「線形反復プロセス」で「何が線形に増加するか」が少し異なるようです。
線形再帰プロセスの説明。
n! の演算では遅延乗算の連鎖の長さ、そしてそれに従う追跡の必要な情報の量が、 n に従い線形に ( n に比例して) ステップ数と同様に増加します。このようなプロセスはlinear recursive process(線形再帰プロセス) と呼ばれます。
線形反復プロセスのほうは。
n! の演算では n に従い必要なステップ数が線形に増加します。このようなプロセスはlinear iterative process(線形反復プロセス) と呼ばれます。
- ステップ数と必要な記憶域の両方が線形に増加するプロセスを、線形再帰プロセスと呼ぶ
- ステップ数が線形に増加するプロセスを、線形反復プロセスと呼ぶ
で、合ってますか？
課題
1.9 再帰？反復？
ex_1_9.scm
初めてtraceを使う。展開手順を書き出すの、traceを見ながらだとかなり楽。
inc（インクリメント）の中で+を使ってるので(inc 1)が循環してしまうように思ったが、ならなかった。incの中の+計算にはデフォルトの+が使われているみたい。
試しに+を定義したあとにincを同じ内容で定義しなおして実行したら予想通り無限ループに入ったので、関数の中で使う自由変数は、その関数が定義された時の内容で縛られているっぽい。クロージャを思い出す。
1.10 アッカーマン関数
ex_1_10.scm
アッカーマン関数ってなんだ・・・と思いつつ、あえて調べずにやってみる。
(A 0 n) (A 1 n) (A 2 n) それぞれの挙動について考察。展開順序を書き出してみることで理解できた。
そのあとアッカーマン関数をググってみたらWikipediaでの内容はSICP内での定義とちょっと違った。挙動を考察することを踏まえて、すこしわかりやすくしてあるのかも。
単純な処理に小さな値を与えているだけなのに計算量が爆発的に大きくなっていくとのことで、(A 2 5)でvimの画面が数字で埋まった。（ここには載せられない。）
1.2.1は以上です。
再帰と反復について、ここに書いたような理解へは週半ばぐらいになんとか至っていたのですが、それを言葉にして残そうと思うとまた大変で・・・
画像作ってみたりして、時間かかってしまいました。
でも結果的にブログを書かずに進めるよりも、アウトプットしたことでずっと理解が定着したと思います。
完全に一人旅なので、道間違えてたら教えてください・・・。
今後も考えたことは言葉にしながら進めていこうと思います。
間違えてたら教えてもらえそうだし、もしいつか忘れたとしても読み返せば近道して思い出せそうなのでｗ
次回は1.2.2 木再帰 です！
