やろーじだい

ブログです

Aizu-SICP 第三回

2016/5/22 に Aizu-SICP 第三回 (SICP読む会) を行った。時間が空いたこともあり、復習に時間を使わせて頂いた。

タイムテーブル

  • 19:00 ~ 19:40: これまでの簡単な復習と練習問題の確認
  • 19:40 ~ 19:55: 読書 p32~p36 「1.2 手続きとそれが生成するプロセス」~「1.2.1 線形再帰と反復」練習問題前まで
  • 19:55 ~ 20:25: 質疑

今回の内容

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

 手続きは、計算プロセスの局所展開 (local evolution) のためのパターンです。それは、プロセスの各段階が、どのように前の段階の上に構築されるかを記述するものです。プロセスの局所展開は手続きによって記述されるものですが、できればプロセスの全体的なふるまい、別の言い方をするとグローバル (global) なふるまいについても何か言えるようになりたいところです。これは、一般的にはとても難しいことです。しかし、プロセスの展開のよくあるパターンについての説明を試みるぐらいはできるでしょう。 P32

今一理解できないが、あるプロセス (関数) がどのような形 (一般的に見たふるまい) を持っているかを明かにしたいと理解した。例として以下の章では、再帰関数を二つの形に分けたり、計算時間などを計算することにより、そのプロセスのふるまいを一般的に説明することを試みている。

1.2.1 線形再帰と反復

 ここでは様々な概念に対して名前を付けている。概念としては知っていても何と呼ぶかが明確でないものが多かったが、名前が付くことで話をすることがしやすくなった。例として以下に挙げる。

遅延演算の連鎖

 P33 図 1.3 のような再帰関数において、展開後に行われる演算の連鎖こと。 (図 1.3 における *)

再帰プロセス

 遅延演算が行われる再帰関数の性質。また例による n! の計算は記録するための情報量や計算ステップ数が n に対して線形に増加するため、線形再帰プロセスと呼ばれる。

反復プロセス

 図 1.4 のように、関数の結果を引数として変数に保存することにより遅延演算が行われない再帰関数の性質。毎回の再帰が独立して計算を反復しており、またステップ数は n に対して線形に増加するため線形反復プロセスと呼ばれる。再帰プロセスと反復プロセスについては今まで、末尾再帰最適化できない方・できる方のように呼んでいた。
 反復プロセスが末尾再帰最適化できることの理由として、本文中の

反復プロセスの場合、プログラムの変数はどの時点でもプロセスの状態を完全に記述しています。 P35

というのが重要な点だとわかった。

状態変数

 反復プロセスにおいて、関数の状態 (繰返しの数やそれまでの反復の結果) を保存しておくための変数。関数 fact-iter における productcountermax-countを指す。

再帰プロセスと再帰手続きの違い

 再帰プロセスは上記のような、再帰関数ふるまいを一般化した場合のひとつを指しているが、再帰手続きとは自分自身を参照しているような関数 (手続き) を指す。今回の例では図 1.3・図 1.4 の関数は共に再帰手続きであるが、再帰プロセスであるのは図 1.4 のみである。