【連載】第5回:ソフトウェアテストそもそも話～三角形問題の歴史（前編）： 誰が「マイヤーズの三角形問題」を作ったのか～

筆者は、2009年に出版された『ソフトウェアテストPRESS Vol.8』[2]に、テスト技術の歴史を調査した結果を「ソフトウェアテスト・ヒストリー」として寄稿しました。その際、技術的な変遷だけでなく、テストにまつわるさまざまな話題の来歴も調べました。三角形問題の歴史もその一つです。

三角形問題は、前述のMyersによる1979年の書籍[1]によって広く知られるようになりましたが、これが初出ではありませんでした。Myers自身、すでに1976年に出版された『Software Reliability（ソフトウェアの信頼性）』[3]の中で三角形問題を取り上げています。

さらに調査を進めると、1972年6月に米国ノースカロライナで開催された、世界で初めてテストを主題にしたシンポジウム"Computer Program Test Methods Symposium"で発表された、Fred Gruenberger（以下、Gruenberger）の論文『Program testing: The historical perspective（プログラムテスト:歴史的展望）』[4]に次のように三角形問題のことが書かれているのが見つかりました。

Richard Hamming博士は彼のComputers and Society（計算機と社会）の著書の中で、ちょっと気のきいた問題を述べている。それぞれ三つの数字をもつ入力カードが与えられる。その数字は、三角形の三辺の長さで、各カードにつき、各辺の長さをプリントし、その三角形が正三角形か二等辺三角形か、不等辺三角形かを示すことである。これは、初心者のクラスにとって、論理およびフローチャートの作成という点でいきな問題である。

そこで、1972年2月に出版されたRichard Hamming（以下、Hamming）の著書『Computers and Society』[5]を入手して確認してみました。確かに、第5章「Examples from Geometry（幾何学からの例題）」に "Classifying Triangles（三角形の分類）" という例題が載っていました。

ただし、Hammingはこの三角形問題を使って、プログラムの論理やフローチャートを作る過程を説明しているだけで、テストケースの作成についてまでは触れていませんでした。ちなみに、このHammingは、データの誤りを検出・訂正できる「ハミング符号」を考案したことでも知られる、アメリカの数学者であり計算機科学者です。

「リチャード・ハミング」（2005年9月19日 (金) 9:00　JSTの版）『ウィキペディア日本語版』。
https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%81%E3%83%A3%E3%83%BC%E3%83%89%E3%83%BB%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0

Gruenbergerの論文に話を戻すと、そこには次のように、テストケース作成の例題としても適していると書かれていました。まさに「マイヤーズの三角形問題」の先駆けと言えそうです。

これはまた、プログラム・テストの良い練習問題でもある。プログラムを十分に確認するには、何枚のテスト用入力カードが要るか。よくできる学生でも、完全なテストをするには7個以上の場合が必要で、(3,4,7)の組が不等辺三角形と呼ぶべきでないことを見いだして驚く。

テスト技術に関する論文で三角形問題を例題として用いた最も早期のものは、私が調べた限りでは、TRW社のJohn Brown（以下、Brown）が1972年9月のWESCONで発表した論文[6]です。その中には、Gruenbergerの論文[4]で紹介された例題であることが明記されていました。なお、このBrownの論文は、第4回後編で紹介したように、初めてテストカバレッジの基準TER（Test Effectiveness Ratio）を提案したものでもあります。

以上の調査結果から、2009年時点の筆者の結論は、三角形問題を最初に作ったのはHamming、テストケース作成の例題として使ったのはGruenberger、そしてテストに関する論文で取り上げたのはBrownが最初、ということになりました。

ところが、最初の調査から2年ほどたった2011年の初め、何かの調べものをしていたときに、偶然「Weinberg's Triangle Problem」と書かれたWebサイトを目にしたのです。「うーん? なぜMyersじゃないんだろう」と不思議に思い、改めて調査を始めました。

さらに調べてみると、米国のテスト界の著名人たちが、Gerald Weinberg（以下、Weinberg）が三角形問題を作ったと書いていることが分かってきました。

・Cem Kaner （「基本から学ぶソフトウェアテスト」の著者）

Weinbergの三角形問題は、1969年ころから使用されている。Myersは、1979年にソフトウェアテストに関する最初の書籍『The Art of Software Testing』でこれを掲載している。

・Bj Rollison （当時Microsoftのテストアーキテクト、JaSST'12 Tokyoの基調講演者）

Weinbergの有名な三角形問題は1966年からあり、Myersの著書『The Art of Software Testing』で広く知られるようになった。

・Michael Bolton （カナダのテストコンサルタント、JaSST'15 Tokyoの基調講演者）

このテスト自体は、当時IBMで働いていたWeinberg、Myers、あるいは (おそらく) Harlan Millsによって開発されたものである。

どうも、Weinbergが1966年か1969年辺りに、三角形問題を使った何らかの記述をしていたようです。Hammingの三角形問題は1972年出版の書籍に書かれたものなので、それをさかのぼることになります。

これは何としても調べなければという思いで、さらに調査を続けた結果、ついに決定的な記事を見つけました!

それは、Danny R. Faught（以下、Faught）が2001年10月に発行したTejas Software Consulting Newsletterに書かれていました。彼が立ち上げた会社のニュースレターです。

Faughtといえば、1993年に始まったインターネットのメーリングリスト comp.software.testing ニュースグループで、テストに関するFAQ[7] をまとめていたことで知られています。

その年の9月号でFaughtは『The Art of Software Testing』を改めて読み直した書評を掲載しました。すると、それに対してWeinbergからコメントが寄せられ、その内容を10月号で次のように紹介しています（筆者訳）。

Glenford Myers著『The Art of Software Testing』の書評に、いくつかコメントをいただきました。Jerry Weinberg氏はこう書いています：

「素晴らしい号ですね。とても役に立ちました。

ところで、ご存知かもしれませんが、Myersが用いた三角形の問題の考案者は私です。（BTW, you may or may not know that I was the originator of the triangle problem that Myers used.）」

何と、Weinbergさん自ら「私が三角形問題の考案者だよ」と言っているではないですか! ニュースレターは続きます。

Jerryは、三角形の問題を『PL/I Programming - A Manual of Style (1970)』か『PL/I Programming Primer (1966)』に載せたと思う、と述べたうえで、さらにこう続けました。

「私はそれより前から、Glenがのちに私の後を継いで教えることになるIBM Systems Research Instituteで、長年この問題を使っていました。おそらくGlenは、そこで見たのか、この本から得たのか、あるいは自分で再発明したのかもしれません。」

Faughtは、このニュースレターの中で「Weinbergが三角形問題を載せたというPL/Iの本を探してみよう」と書いていましたが、その後に続報らしきものは見つかりませんでした。

私はどうしても1966年なのか1970年なのか決着を付けたく、何とか2冊の書籍[8][9]を入手しました。

2冊の書籍を隅から隅まで調べたところ、三角形問題は1970年出版の『PL/I Programming: A Manual of Style』[9]に書かれていることが分かりました。三角形の種類を分類するプログラムを例にして、PL/Iの配列の使い方を説明しています。そして、テストの章では、このプログラムに対するテストケースを考えさせる設問がありました。

以上のことが分かりましたので、これからは「マイヤーズの三角形問題」ではなく、「ワインバーグの三角形問題」あるいは「ワインバーグ・マイヤーズの三角形問題」と呼ぶのが良いかもしれません（笑）。

最後に、三角形問題のバリエーションについて整理しておきます。

Myersの三角形問題は、与えられた三辺の長さから、不等辺三角形・二等辺三角形・正三角形のいずれかを判別して表示するものでした。これに対し、考案者のWeinbergは辺だけでなく角度にも着目し、直角三角形・鋭角三角形・鈍角三角形の判別も行う問題としていました。HammingのバージョンもWeinbergと同様に辺と角を扱っていましたが、同時期のBrownの論文では辺の判別のみにとどまっています。

要するに、どちらでなければならないという決まりがあるわけではなく、三角形問題を使って何を説明したいかによって、「辺だけにするか」「角も含めるか」が選ばれてきたのでしょう。そして一般に「マイヤーズの三角形問題」と呼ばれる場合は、辺だけを判別対象とするものを指すと考えてよいと思います。

三角形問題の使われ方は、「外部仕様の例題」として使う場合と、「プログラム解析の題材」として使う場合の二つに大別できそうです。

後者には、外部仕様そのものは多くの人が理解しているため、すぐに内部処理やコード解析の話に入れるという利点があります。前述のBrownの論文はその典型で、テストカバレッジ測定の題材として取り上げられています。一方、前者の「外部仕様の例題」として使ったのがHammingです。

Hammingは、(1)三角形の定義（3辺の関係）に基づく判別、(2)ピタゴラスの定理による角度の判別、という論理ブロックの流れを示し、それをさらに詳細なフローチャートへ展開するプロセスを解説しています。そしてこの展開を説明する前に、この問題には「隠れた前提（hidden assumption）」があることを指摘しました。すなわち「三角形の二辺の和は、残りの一辺より長くなければならない」という暗黙の条件です。

Hammingはこれを通じて、現実の仕様書も十分に書き尽くされているとは限らず、見落としが含まれる可能性があることを示したのです。実際、Myersの三角形問題でも、このケースを見落とす人は少なくないと思います。Gruenbergerが「いきな問題」と賞したのも、このような見落としがあることに気付かせるための良い例題だったからではないでしょうか。

以上、前編では、三角形問題の考案の歴史を解説しました。後編では、テストプロフェッショナルたちの三角形問題に対する解答や考え方を紹介します。

<参考文献>

[1] G. J. Myers, “The Art of Software Testing,” John Wiley & Sons, 1979（松尾正信（訳），長尾真（監訳）, ソフトウェア・テストの技法, 近代科学社, 1980）
[2] ソフトウェア・テストPRESS Vol.8, 技術評論社, 2009
　https://gihyo.jp/book/2009/978-4-7741-3749-0
[3] G. J. Myers, “Software Reliability Principles and Practices,” Wiley, 1976（有澤誠(訳)，ソフトウェアの信頼性 ソフトウェア・エンジニアリング概説, 近代科学社, 1977）
[4] F. Gruenberger, "Program testing: The historical perspective," in Program Test Methods, Prentice-Hall, 1973"(鳥居 宏次(訳)，プログラムテスト:歴史的展望，プログラム・テスト法，近代科学社，1974)
[5] R. W. Hamming, "Computers and society," McGraw-Hill, 1972
[6] J. R. Brown, "Practical applications of automated software tools," WESCON 1972, Session 21 and TRW Software Series SS-72-05, September 1972
[7] comp.software.testing Frequently Asked Questions (FAQ)
　http://www.faqs.org/faqs/software-eng/testing-faq/
[8] G. M. Weinberg, "PL/I Programming Primer," McGraw-Hill, New York, 1966
[9] G. M. Weinberg, "PL/I Programming: A Manual of Style," McGraw-Hill, New York, 1970