ガベージ・イン／ガベージ・アウト：
善き人々が悪しきプログラムに手を染める時

Henry G. Baker

hbaker@netcom.com
http://linux.rice.edu/~rahul/hbaker/home.html

Copyright (c) 1997 by Henry Baker. All rights reserved.

日本語訳：Shiro Kawai (shiro@acm.org)

プロジェクト杉田玄白協賛参加テキスト

これは、ACM SIGPLAN Noticesに掲載されたコラム Henry G Baker： "Garbage In Garbage Out: When Bad Programs Happen To Good People" を、原著者の許可を得て翻訳・公開するものです。原文は下記のURLから入手可能です。 原文の転載は原著者の許可を得て下さい。翻訳文の転載・利用条件については、 現在Baker氏の意向を確認中です。

ユーモラスで所々にパンチの効いた原文のリズムは訳しきれていません。 この話題に興味を持たれましたら、できれば原文を読んでみて下さい。 もちろん、翻訳の不備の指摘や改善意見は大歓迎です。

原文URL: http://home.pipeline.com/~hbaker1/sigplannotices/gigo-1997-03.html

2000/7/4 翻訳公開
2000/7/6 木村 巌さんからの訳文への指摘を反映しました。多謝
2001/2/4 阿部 洋志さんから "EboMIX" に関する情報を頂き、 本文および訳註1に反映させました。ありがとうございます。
2001/5/4 原文のURL移動を反映
2003/9/22 ふたたび原文のURL移動を反映 (Thanks to HIROO Yamagata)

優秀な研究者、数学者、教授あるいは学生が、へたくそなプログラムを書いてしまうことが しばしばあるのは、何故なのだろう。表現や証明の単純さと優雅さを以て最高のものと考える 数学者達が、アルゴリズムを表記するのにプログラムの形式を使うことはただの必要悪と考え、 その表記をも優雅にしようと考えないのは何故なんだろう。

数学者よりは技術者の方が、コードの読みやすさや優雅さに無頓着でありそうなものだ。 しかしそれは間違いかもしれない。技術者が実装の細かいところをいじくりまわすのに対し、 数学者はアルゴリズム全体が正確でそこそこの効率が出ていれば良しとしそうなものだが、 クヌースのような極めて優秀な数学者でさえ、 「奇怪」語(訳註1)を教えているのだ。

こんなことになってしまった理由を、私は想像することしかできない。 最先端をゆく数学者達は、新しい結果がうまく証明できたらそれで良しとして、 その証明を後世のために綺麗に書き直して単純に直すのは、もう少しレベルの低い人達の することだと思っているのかもしれない。そういう仕事は「明らかなことを 誰にでもわかるようにする」だけのことで、真剣に考えるに値しないと思っているの かもしれない。

極めて高い知能を持っている人は、大きな短期記憶を持っていて、たくさんの 概念に同時に思いをめぐらすことが容易なのかもしれない。だから、単なる凡人のために それらの概念をかみくだいてやる必要性に気付かないだけなのかもしれない。

研究者はふつう、コードを書く立場におり、読む立場 にはいない。だから、他の人の創作物を読む際の問題というのを認識しないだけなのかもしれない。

教授達は、読みやすく解りやすいコードを書くためにはどうしたらよいかと言う問題が 大いに考察される時代より前に学校を卒業してしまった。きっと、 BASICやら機械語やらにあまり幼いうちに晒されると、 脳に取り返しのつかない損傷を受けるのだ。彼等の言葉を読み解こうとする人々は、 今は亡き太古のマシンやコンパイラの亡霊と闘い続けなければならない。 彼等のプログラムは滅びたコンピュータ言語の古き地方の強いなまりに彩られている。

計算理論家達は、機械語以外の言語で「ステップ数」を数えることができない。 チューリングでさえラムダ算法を愛したというのに。

それに、編集者と評論家も、本や記事に出版されてしまった悪しきプログラムに対して 責を負うべきだ。

それとも、我々のようなプログラムの質を気にする人々が、十分に声を上げて 来なかったからなのかもしれない。 「良いプログラマの沈黙こそが、悪しきプログラムの勝利の条件」なのだから。 このような無抵抗性を、私は「λたちの沈黙」と呼ぼう。

我々は既に、コンピュータプログラム達が、そのプログラムをいびつにした制約を もたらしたマシンやコンパイラが死に絶えた後でさえ、何十年もの長きにわたって生き残るのを 恐怖をもって目の当たりにしてきた。我々はハッカー的熱意が作り出した錬獄に 住んでいるのだ。

だが、ハードウェア／コンパイラの最適化とソフトウェアに関する文献との極めて強固な フィードバック機構が、悪しきプログラミングスタイルを今後も生き残らせてゆきそうだ (悪しきプログラミングスタイルのために最適化されたハードウェア上では、 そういうプログラムが「効率良く」走るからだ)。 そんな世界では、より良いスタイルのためにハードウェアを最適化してくれることは期待できない。

我々は、傑出したプログラムを書くことでこの悪循環を打ち破ることに、全力を傾けなければ ならない。コンパイラやハードウェアが、優れたプログラムを効率良く走らせるように 合わせるべきで、ハードウェアを効率良く使うためにプログラミングスタイルを合わせるようでは だめなのだ。優れたプログラムはたまたま出来てしまうようなものではなく、 非常な努力を必要とする。我々は進んで優雅さを追求しなければならない。 優雅さはむこうから自然と歩いて来てはくれない。

悪しきプログラムとはどういったものだろうか。たいてい、それは必要以上に長く、 目の前に屹立するプログラムの分量だけでも読む者をおびえさせる。当然そういったプログラムには、 的外れや意味をなさない名前と、鼠の巣のように入り組んだ二進分岐が溢れかえっているのだ。

定義

悪しきプログラムとは、 そのスタイルがあまりにひどく見通しが悪いために、 それを読む人をして、そのプログラムを理解しもしくはデバッグしようとするくらいなら 初めから書き直すことを強要させるようなプログラムである。 (コメントは良く書けたプログラムにおいては有用であるが、 もしプログラムを理解するのにコメントが必要だというのなら、 それは通常悪しきプログラム(または、悪しきプログラミング言語)である。)

では、優れた著者による出版された本の中から、いくつかのコード例を見てみよう。 (ここではスペースの都合で 小さなコード例を見ることしかできないので、「小さなプログラムの例は現実的でない」 というような批判を招くかもしれないが、私のコメントの多くは大きなプログラムにも 適用できるものである)。 断わっておくが、私はこれらの著者に最大限の尊敬の念を抱いている。 だからこそ、彼等が悪しきプログラムを書いて、それが次世代のコンピュータ科学者達に インスピレーションを与えてゆくことが、どうしようもなく耐え難いのだ。 

FUNCTION Euclid(a,b : INTEGER) : INTEGER;
{ユークリッド法でGCD(a,b)を計算する}
VAR m,n,r : INTEGER;
BEGIN m:=a; n:=b;
  WHILE n <> 0 DO BEGIN r:=m MOD n; m:=n; n:=r END;
  Euclid:=m
END {Euclid};

図 1: リーゼルのEuclidプログラム ([Riesel85], p. 242より)

ハンス・リーゼル(Hans Riesel)は数論の問題の解決にコンピュータを用いたパイオニアの 一人であり、 「Prime Numbers and Computer Methods for Factorization」という優れた本は既に 第2版となっている。図1は彼のEuclidプログラムで、 ユークリッド法で最大公約数(gcd)を求めるアルゴリズムである。

私なら、リーゼルの Euclid プログラムには "B" をつける。 真に悪しきプログラムというわけではないが、こんなに簡単なアルゴリズムはもっと明確に 記述されてしかるべきだ。リーゼルは再帰的なアルゴリズムをむりやり「繰り返し」スタイルに 変えた。彼のために一言沿えておけば、彼は確かにPascalの「構造化」機能を、繰り返しを 表記するために使っている。しかし、図2に示す、[Jensen74]にあるヴィルトのエレガントな gcd コード以上にわかりやすいものはあるだろうか？ (私は常に非負の結果を返すようにabs()を挿入した。 残念ながら、同じ本の後のほうにあるヴィルトの「拡張された」GCD プログラム(157ページ)は信じられない程に醜い)。 

FUNCTION gcd(m,n : INTEGER) : INTEGER;
  BEGIN
    IF n=0 THEN gcd:=abs(m)
           ELSE gcd:=gcd(n,m MOD n)
  END;

図 2: ヴィルトのgcdプログラム ([Jensen74], p. 82より).

ヴィルトのgcdプログラムはより小さく、より少ない名前を使い、 そして解りやすい---GCDを計算する数学上の規則とほぼ一対一に対応している。 余分な名前を導入して外部の名前空間をごちゃごちゃにしたりもしていないし、 無限多倍長整数("bignum")を使っているために、たとえ再帰のオーバーヘッドがわずかでも あるとしたって、MODを無限多倍長で計算するコストに比べて無視できる。 もし値を返すためのPascalの構文がこんなに愚かでなかったら、直接読み下すことさえ 可能だったかもしれない！ (十分にパワフルな言語なら何でも、それによって 良いプログラムも悪いプログラムも書ける、というのは確かだが、だからと言って プログラミング言語の選択に意味は無いと言うつもりは無い。例えば、 Pascalのぶきっちょな構文、弱いオペレータの優先順、そして欠陥だらけの基本算術関数の 定義は、そのプログラムを必要以上に読みにくく、また最適化しにくくしている)。

よく、「再帰は繰り返しより効率が悪い」とぶーぶー言う輩がいる。 中でも、再帰は O(log(max(|m|,|n|)))のスタックフレームを 積んだり戻したりする必要があるからというのだ。 だが、このGCDアルゴリズムは末尾再帰である--- つまり、再帰的に呼ばれた関数の戻り値がそのままその関数の戻り値となっている--- ので、スタックフレームを積む必要は全く無い。 このプログラムは繰り返しプログラムである。 このプログラムをループに展開出来ないコンパイラがあるとすれば、 それはコンパイラがぶっ壊れているのだ。

図3はやはりリーゼルの本にある、もう一つのとりわけひどい例で、 「Jacobi シンボル」関数 (m/p) を計算するコードJacobi である。この関数は 奇数の素数pのモジュロにおいて、 数mが平方剰余(訳註2)になるかどうかを返す。 この関数は、よくある「確率的」素数テストの内部ループに使われる。 (Jacobi symbol関数は[Knuth81]の練習問題4.5.4#23aで議論されている)。 

FUNCTION Jacobi(d,n : INTEGER) : INTEGER;
{奇数nに対してJacobiの symbol (d/n)を計算する}
LABEL 1,2,3,4;
VAR d1,n1,i2,m,n8,u,z,u4 : INTEGER;
BEGIN
  d1:=d; n1:=abs(n); m:=0; n8:=n1 MOD 8;
  IF odd(n8+1) THEN
    BEGIN writeln(tty,'(d/n)においてnが偶数であってはならない');
      GOTO 3 END;
  IF d1<0 THEN
    BEGIN d1:=-d1; IF (n8=3) OR (n8=7) THEN m:=m+1 END;
1: IF d1=0 THEN
    BEGIN writeln(tty,'(d/n)において GCD(d,n)>1 であってはならない');
      GOTO 3 END;
  i2:=0;
2: u:=d1 DIV 2; IF d1=u*2 THEN
    BEGIN i2:=i2+1; d1:=u; GOTO 2 END;
  IF odd(i2) THEN m:=m+(n8*n8-1) DIV 8;
  u4:=d1 MOD 4; m:=m+(n8-1)*(u4-1) DIV 4; z:=n1 MOD d1;
  n1:=d1; d1:=z; n8:=n1 MOD 8; IF n1>1 THEN GOTO 1;
  m:=m MOD 2; IF m=0 THEN Jacobi:=1 ELSE Jacobi:=-1;
  GOTO 4;
3: Jacobi:=0;
4: END {Jacobi};

図 3: リーゼルのJacobiプログラム ([Riesel85], p. 286 より).

この醜いJacobiプログラムは書かれてから多分13年経っている (上の二つの例は1994年版のリーゼルの本にも変更無しで出ていた)。しかし、この プログラムか書かれた時点で、ダイクストラの有名な論文「Goto文は有害だ」[Dijkstra68] は書かれてから16年の歳月が流れていたのだ。 もしこのプログラムが今日のプログラミングコースの宿題の結果として提出されたとしたら、 きっと非常に低い点数しかもらえないだろう。

私が何故このJacobiの例にこんなに苦悩しているかって?

1. この例は高度な教育を受けた非凡な天才 (コンピュータのパイオニアだ) であり、 傑出した数学的スキルを持っている人物 (Erdosと共著がある(訳註3)) によって書かれた。

2. この例は、16年もの長きにわたる、最高にして最も才能のある コンピュータ科学者達の十分に裏付けのある叫びが、 「コンピュータ科学」という狭い枠の外に全く影響を与えていないという ことを示している。これはつまり、プログラミングまたは数学のどちらか 一方を知っている学生を雇うことは出来るが、両方を知っている学生はほとんど見つけられない、 ということだ。

3. 今日(1997年)の時点で教えられ、使われているプログラミングスタイルが ここに上げたものより良くなっているとは全然思えない (Barnes & Nobleのコンピュータ関連書籍の棚をざっと眺めるか、 あるいはもっと悪いが、マイクロソフト出版の本に出て来る「例」を見たまえ。)

リーゼルのJacobiプログラムの最も悪い点は ループ構文の存在を---Pascalの主要な存在価値はそこにあるのに---全く無視している点であるが、 あまりにひどいので、これをWHILEやREPEATで 簡単に書き直すということはできない。

リーゼルの無価値／無構造(訳註4)のプログラムを徐々に改善してゆくよりは、 Jacobiシンボルのルール[Riesel85/94] [Knuth81]から直接プログラムを 書き下してしまおう。 

(0/n) = 0, except (0/1) = 1

(1/n) = 1

            (n^2-1)/8
(2/n) = (-1)

(ab/n) = (a/n)(b/n)

(m/n) = ((m mod n)/n)

            (m-1)(n-1)/4
(m/n) = (-1)             (n/m),   (m,n odd)

(m/n)を計算するための方針は極めて単純だ： 境界条件に当たる場合を調べ、その場合は正しい結果を返す。そうでなければ 再帰を用いてパラメータを単純なものに変換してゆく。 

FUNCTION Jacobi(m,n : INTEGER) : INTEGER;
{m>=0, 奇数n>0 に対してJacobiシンボル (m/n) を計算する}
  BEGIN
    IF n=0 THEN Jacobi:=1
    ELSE IF m=0 THEN Jacobi:=0
    ELSE IF odd(m) THEN
           IF (m MOD 4=3) AND (n MOD 4=3)
           THEN Jacobi:=-Jacobi(n MOD m,m)
           ELSE Jacobi:= Jacobi(n MOD m,m)
    ELSE IF (n MOD 8=3) OR (n MOD 8=5)   {コンパイラがCSE(訳註5)をしてくれるよね}
         THEN Jacobi:=-Jacobi(m DIV 2,n)
         ELSE Jacobi:= Jacobi(m DIV 2,n)
  END {Jacobi};

図 4: 改善されたJacobiプログラム

図4のプログラムは素直に書かれていて、しかもとても良く動く (我々はm < 0 の場合を無視した。呼び出し側は 5番目のルールによってこの場合を m >= 0の場合に簡単にマップできる)。 とりわけ、このコードはリーゼルの提案した最適化を取り入れているからだ。例えば、 mとnの低位の数ビットのみが結果の符号を決めるのに 働いている。 但し、このプログラムは「末尾再帰」ではない。 再帰的に呼び出した関数の結果を待って、符号を反転させなければならない箇所があるからだ。

ところで、Jacobiシンボルは本質的にGCDの計算と同じ手順を踏んでいるが、 通常のJacobi計算では最後にgcdの情報を捨ててしまっていて、勿体無い。 そこで、図5に示す"Jcd" アルゴリズムというのを考えてみる。 これは gcd(m,n)=1の場合に (m/n) を返し、 そうでなければ+-gcd(m,n)を返す。 Jcd(m,n)はJacobi(m,n)と 全く同じ負荷で計算できて、Jacobiの情報はJcd(m,n)の結果から 簡単に導ける。 

FUNCTION Jcd(m,n : INTEGER) : INTEGER; {m>=0, odd n>0.}
  BEGIN
    IF m=0 THEN Jcd:=n
    ELSE IF odd(m) THEN
           IF (m MOD 4=3) AND (n MOD 4=3)
           THEN Jcd:=-Jcd(n MOD m,m)
           ELSE Jcd:= Jcd(n MOD m,m)
    ELSE IF (n MOD 8=3) OR (n MOD 8=5)
         THEN Jcd:=-Jcd(m DIV 2,n)
         ELSE Jcd:= Jcd(m DIV 2,n)
  END {Jcd};
FUNCTION Jacobi(m,n : INTEGER) : INTEGER; {odd n>0.}
  BEGIN Jacobi:=1 DIV Jcd(n+(m MOD n),n) END;

図 5: gcdとJacobiを同時に計算するプログラム

ここで、コードの一部をミラーすることにより、 末尾再帰版のJcdは簡単に作れる。この版では 結果の符号の情報は謂わばプログラムカウンターの中に隠されている(訳註6)。 良いコンパイラなら、この関数にはスタックフレームを一つだけ割り当てて、 残りの情報はレジスタとプログラムカウンターに置いておくだろう。 我々はここで、見通しの良さと効率の高さを一つのプログラム内で実現できたわけだ。 

FUNCTION Jcd(m,n : INTEGER) : INTEGER; {m>=0, odd n>0.}
  FUNCTION negJcd(m,n : INTEGER) : INTEGER; {m>=0, odd n>0.}
    BEGIN
      IF m=0 THEN negJcd:=-n
      ELSE IF odd(m) THEN
             IF (m MOD 4=3) AND (n MOD 4=3)
             THEN negJcd:=   Jcd(n MOD m,m)
             ELSE negJcd:=negJcd(n MOD m,m)
      ELSE IF (n MOD 8=3) OR (n MOD 8=5)
           THEN negJcd:=   Jcd(m DIV 2,n)
           ELSE negJcd:=negJcd(m DIV 2,n)
    END {negJcd};
  BEGIN
    IF m=0 THEN Jcd:=n
    ELSE IF odd(m) THEN
           IF (m MOD 4=3) AND (n MOD 4=3)
           THEN Jcd:=negJcd(n MOD m,m)
           ELSE Jcd:=   Jcd(n MOD m,m)
    ELSE IF (n MOD 8=3) OR (n MOD 8=5)
         THEN Jcd:=negJcd(m DIV 2,n)
         ELSE Jcd:=   Jcd(m DIV 2,n)
  END {Jcd};

図 6: 末尾再帰型Jcd プログラム

より効率の良いgcdとJacobiのアルゴリズムは知られており[Meyer96]、 ここの例はJacobiアルゴリズムのベストの実装を示すものではない。だが、 どうやってわかりやすくエレガントなプログラムを書いたら良いか、という 発想の助けにはなったのではないかと思う。

References

Dijkstra, E.W. "Go To Statement Considered Harmful." Comm. of the ACM 11, 3 (March 1968), 147-148. Reprinted in October 1995 Communications of the ACM.

Jensen, K., and Wirth, N. PASCAL User Manual and Report, 2nd Ed. Springer-Verlag, New York, 1974, ISBN 0-387-90144-2.

Knuth, D.E. Seminumerical Algorithms, Second Edition. Addison-Wesley, Reading, MA, 1981, ISBN 0-201-03822-6. Problem 4.5.4#23a.

Meyer, S.M., and Sorenson, J.P. "Efficient Algorithms for Computing the Jacobi Symbol". Cohen H. (ed.) Proc. ANTS-II, 2nd Intl. Symp. Alg. Num. Th., Springer LNCS 1122, 1996, pp. 225-239, http://www.butler.edu/~sorenson/.

Riesel, Hans. Prime Numbers and Computer Methods for Factorization. Birkhauser, Boston, 1985, ISBN 0-8176-3291-3. Code is online at ftp://ftp.nada.kth.se/Num/riesel-comp.tar.

訳者註

訳註1) 「奇怪」語：原文 "EboMIX"。 MIXはKnuthがアルゴリズムを解説するために導入した仮想プロセッサのアセンブリ言語。 ここは当初わからなかったのですが、 阿部 洋志さんより "ebonics" と掛けているのではないかとの御教示がありました。 (「奇怪語」の表現も阿部 洋志さんのメイルより頂きました)。 "ebonics" はなまりの強い黒人英語で、 よくラップミュージックや黒人霊歌の歌詞に出て来るやつ…なんじゃないかなあ、と思います。 ここで 普通の英語をebonicsに変換してくれます。

(実はここの意味がわからなくてBaker氏に質問したのですが、返事が無かったのです。 洒落がわからないヤツと思われたのかも…)。

訳註2) 平方剰余：整数x, m, nが

x2 ≡ m (mod n)
を満たす時、m はモジュロnにおける平方剰余quadratic residueであると言う。 参考： Quadratic Residue

訳註3) Paul Erdos (1913-1996)： ハンガリー出身の数学者。極めて多数 (千数百本)の優れた論文を著した。ある科学者の論文の、共著者の論文の、 その共著者の…と辿っていって何ステップでErdosに辿り着けるか、は Erdos Number と呼ばれており、多数のフィールズ賞受賞者やノーベル賞受賞者は小さいErdos Numberを 持つことが知られている。Erdos本人と共著のあるリーゼルはErdos Number 1である。

訳註4) 無価値／無構造：原文 wirth-less。 worthless(価値の無い)と、Wirth-less (ヴィルトWirthはPascalの創始者) をかけたのだと思う。

訳註5) CSE： Common Subexpression Elimination 共通部分式の簡略化。 コンパイラの最適化技法の一つ。この例だと、 同じnに対してn MOD 8がプログラム上では2回現われるが、 これらは2回計算する必要は無い。CSEはそれを認識して、中間変数を導入して 一回しか計算しないようにすること。

訳註6) プログラムカウンタに置いておく： 符号が負の場合と正の場合を、内部関数negJcdと関数の本体のブロックとで 別々に計算している。内部の関数negJcdはコンパイラによってただのブロックに展開 されるので、現在扱っている符号は「現在どちらのブロックを実行しているか」という情報 ＝プログラムカウンタの中に示されている。

[Practical Scheme]