Webを何となく見ていたら、 ネット家電のOSとしてLINUXか TRONを採用することを 経済産業省と電機業界が検討しているというニュースが出ていた。 なぜLINUXかというと、 安全性が高いというのだ。 やっと安全とは何かユーザーが分かる時代になったかと思えば感無量である。 マイクロソフトは「Windowsは安全だ」とビルゲイツ自らアピールしたりして、 売り込みに力を入れているらしいが、 Windowsは安全ですという宣言の数日後に 「重大なセキュリティの問題が発見されました」 みたいなことを言われたりして、訳が分からない。 Windows Updateを実行したらWindowsが起動しなくなった経験が何回かある私としては、 セキュリティの問題というリスクを抱えて現状のまま運用するか、 それとも、 Windowsが起動しなくなってsafe modeであれこれ作業するというリスクを選択するか、 という、 さらに、ある意味究極の選択を強いられるのである。

まあそれはそうとして、 びっくりしたのは、ここでTRONが出てきたということだ。 今時の人達だと「TRONって何?」という方も多いのではないか。 TRONプロジェクトは確か1984年に始まったはずだから、 もうすぐ20年になる。

プログラマーズフォーラムでは1989年にTRONをテーマにした会議があった。 そこでプログラマー的に関心が集まったのが、 TRON作法なのである。 TRON作法とは?　これが、Webで調べてみても、埒があかない。 確かに何件かヒットするが、 何件というレベルなのである。 しかも、私が見たページは全て、 「操作体系がTRON作法として標準化されている」としか出ていなかった。 一体その作法はどんな作法なのか、というのが分からないのだ。

多分、TRON支持者に言わせれば、 これがTRONの一番面白い所なのでは、と言ってもいいほど面白い内容なのだが、 その実体があまり話題になっていないというのがどうも不思議である。 FPROGには、思想レベルのTRON作法と、 設計方針レベルのTRON作法が紹介されているのだが、 その中から、思想レベルのTRON作法を紹介してみよう。

-- 表1 思想レベルのTRON作法 --

思想1 できる限りモードに入らない。

思想2 コンピュータで判断が付くことをユーザーに行なわせてはならない。

思想3 初心者の時の操作法と、熟練してからの操作法を設け、スムーズに移行できるようにする。

思想4 ユーザーの操作には常に即座になんらかの反応を返し、見捨ててはならない。

思想5 ユーザーが指示することが可能でありながら、行なってはならない操作があってはならない。

-- 表1 end --

思想レベルのTRON作法は、後で追加されていなければ、これだけである。 書き方がロボット3原則みたいな感じなのが素晴らしい。 もっとも、TRONがコンセプトに終わるのではなく、 実装して動かすという前提で作られていたから、 「できる限り」のような妥協を許す表現は仕方ないし、 今風に考えると、 条件次第で例外も許すというのはかえって時代を先取りしたことになるか。

よく槍玉に上がったのが、思想2の 「コンピュータで判断が付くことをユーザーに行わせてはならない」 だった。 当時、電脳住宅というモデルハウスがあって、 中の植物にはコンピュータが自動的に水をやることができるというのだが、 当時、坂村氏がよくネタにしていたのが、 「わしは花に水をやるのが生き甲斐だから、 コンピュータが水をやるなんてもってのほかだ」 という頑固な人がいるという話だ。 もちろん、 「ユーザーに行なわせてはならない」は「ユーザーが行ってはならない」ではない。 水をやりたい人は、いつでもやることができます。 ところで、あなたが病気になって入院したり、長期間家を留守にする時はどうするのですか、という話だったと思う。 もっとも、実際にそのようなシステムを作るのは結構大変かもしれない。 ユーザーが水をやったかどうかをセンサーで判断した上で、 コンピューターが水をやりすぎないように設計しなければならないからだ。

§

ある週刊マンガ誌に面白い問題が出ていた。 興味がある方は、 Webで「文句数」というキーワードで検索すると出てくるので、 調べてみて欲しい。 実は、この問題、問題文が極めてよく出来ている。 数学的に問題を表現するのが結構面倒なのだ。あえて表現してみる。

1からnまでの整数を任意の順序で並べる。 ある桁の数に対して、自分より右に位置する桁に、 自分よりも大きな数がいくつあるかを数える。 これを全桁に対して行った結果の合計をmとする。 1から6までの整数を並べたときに、mが7となるような並べ方が何通りあるか、 というのが問題である。

例えば、435216と並べると、4と3に対しては自分より右に5と6があるから2、 5と2と1に対しては、自分より右に6があるから1、ということで、 2+2+1+1+1 で m が 7になる。 このような並べ方が何通りあるのか、という話だ。 マンガではこれを手計算で解くのだが、 ちなみにプログラムで解くとどうなるか。

演習問題としては、 この種の問題は、 再帰呼び出しで解くのが定番である。 1からnまでの整数に対して、前述のような並べ方が何通りあるかを求める関数を

c(n,m)

と書くことにすると、定義より、

c(n, 0) = 1　…(1)

である。また、n > 1 に対して明らかに、

c(n, m) = c(n-1, m) + c(n-1, m-1) + ... + c(n-1, m-n+1)　…(2)

が成り立つ。 どこが明らかなのかサッパリ分からないような気もするが、 とりあえず明らかだとして話を進める。 m の範囲がちょっと気になるので、

c(n, m) = 0   (m < 0 の場合)　…(3)

としておく。 これを perl で解こうとしたのが List 1。

-- List 1 (m を求める) --

sub get_c {
  my $n = shift;
  my $m = shift;

  return 1 if ($m == 0);
  return 0 if ($m < 0);

  my $result = 0;
  my $i;
  for ($i = 0; $i < $n; $i++) {
    $result += &get_c($n - 1, $m - $i);
  }

  return $result;
}

-- List 1 end --

このように、割と簡単に書ける。 再帰呼び出しを perl で書く時には、 my を使い忘れないように気をつけよう。 perl は定義していない変数をいきなり使うことのできる、 ある意味お気楽言語なのだが、 そういう書き方の変数は、グローバルに値を保持することになる。 再帰呼び出しのように、 自分自身を呼び出すコードを書くと、 そのような変数の値が全部共有されてしまう。 ヘタすると、ループカウンタが書き換えられて、 いつまでたっても戻ってこない。 my をつけておくと、 呼び出し毎に変数が別途作られるから、 戻ってきても呼び出した時の値が残っていて安心である。

実は、最初にこのコードを書いた時に、 ちょっとだけズルをして List 2 のように書いた。 ズルというのは、 last if ($m < $i); というのがソレだ。 $m < $i の場合は (3) により get_c($n - 1, $m - $1) の値が0になる。 値が0であると分かっていれば、わざわざ足しこむ必要はないので、 そこでループを打ち切るのだ。

-- List 2 (m を求める…一工夫版) --

sub get_c {
  my $n = shift;
  my $m = shift;

  return 1 if ($m == 0);

  my $result = 0;
  my $i;
  for ($i = 0; $i < $n; $i++) {
    last if ($m < $i);
    $result += &get_c($n - 1, $m - $i);
  }

  return $result;
}

-- List 2 end --

一般に、関数を呼び出すという処理は、 かなりのコストがかかるものと思ってよい。 List 1とList 2を比べると、 条件成立時に関数呼び出しが省略されるのだから、 効率がいいのはList 2に決まっている。 それをなぜわざわざ List 1 のように書き直したのかというと、 前回のコラムを読んでください。

但し、再帰呼び出しには、もう一つの原則がある。 再帰呼び出しを使うと、 一見コードは簡単でも、膨大な数の呼び出しが発生する場合がある。 ちょっとしたコストが積み重なると、 膨大なコストになってしまうかもしれない。 そういう場合なら、 ある程度の可読性を犠牲にしてでも、 効率を優先するという選択も考えるべきだ。 つまり、再帰呼び出しは極力効率よく書くべし、というのも原則なのである。

では、どうやって効率化するか。 List 2のように処理に依存した小技を使う手もあるが、 結果を覚えておき、1度しか計算しないという技法がよく使われる。 Webなんかで、一度見たページをキャッシュしておいて、 同じページを参照しようとした時には見に行かずに手元のデータで済ませる、 というのと同じことだ。

-- List 3 (計算結果を覚えておく) --

sub get_c {
  my $n = shift;
  my $m = shift;

  return $cached_value if defined($cached_value = $result_table{$n, $m});
  return $result_table{$n, $m} = calc_c($n, $m);
}

sub calc_c {
  my $n = shift;
  my $m = shift;

  return 1 if ($m == 0);
  return 0 if ($m < 0);

  my $result = 0;
  my $i;
  for ($i = 0; $i < $n; $i++) {
    $result += &get_c($n - 1, $m - $i);
  }

  return $result;
}

-- List 3 end --

get_c は、計算結果が保存されていれば、それを使ってただちに値を返す。 保存されていないなら、calc_c で計算して、それを保存しながら値を返す。 Java なら、get_c を public、calc_c は private にするところだろう。

もちろん、この原則にも例外はある。 テーブルを参照する方が時間がかかってしまうとか、 同じ値で呼ばれることがあまりないとか。 最近の環境ではあまり気にしなくていいような場合が増えているのかもしれないが、 テーブルのサイズが膨大になり、メモリ効率の問題が生じるとか。 それが心配なら、 実際にコードを実行してプロファイルを取ってみるのがよい。 何回呼ばれたとか、 テーブルのサイズがどの程度で、 実行時にハッシュの処理にどの程度かかっているとか、 実測値から判断するというのも手である。 もっとも、今回の程度の問題だと、どれも誤差の範囲内という感じもするが。

§

ところで、この問題、こうやってコンピュータに計算させるのもアリだが、 もちろん、人間が自力で判断するのも作法としてはアリのはずである。 では、人間が解くにはどうするのが正解なのでしょうか?

※ 2003年4月のアレ、 の中で、4月10日にこれを解いている。 ところが、今パッと見たら何をやっているのか皆目分からん。 ボケたか?