「有害なgoto」「時期尚早な最適化」、そしてプログラミングにまつわる神話は諸悪の根源である

以下のプレゼンテーションは、私がPapers We Love Madridの初会議で発表したものです。講演のテーマは、Donald Knuthの論文「Structured Programming with Go To Statements」(goto文を用いた構造化プログラミング)でした。

我々が人間として抱える最大の問題は、信念と現実を混同することである。 – Alan Kay

それ(goto)を禁止するか、それとも使わない方向へ教育するかが問題だ。 – Donald Knuth

この記事では、神話についてお話ししたいと思います。Googleで神話(myth)の定義を検索してみると「広く信じられているが誤った信念や観念」とあり、dictionary.comを見ると「立証されていないか誤った共通的信念であり、社会制度を正当化するために用いられる」と説明されています。ここで問いたいのは、21世紀の人々が神話を信用しているかということです。

Umberto Ecoは著書『The Book of Legendary Lands』(伝説の地の本)において、「神話の中には社会で広く信じられているため、真実ではないことを話しているとさえ気づかれないものもある」ということを示すべく、簡単なテストを提案しています。それは、誰かに「コロンブスが西へ航海してインドを目指した時に証明しようとしていたことは何か?」、また「当時サラマンカの学者たちに広く信じられていた説は何か?」と尋ねてみることです。多くの人は、コロンブスが、地球は平らであるという当時一般的に信じられていた説に反して、地球は丸いことを証明したかったと答えるでしょう。しかし実は、Ecoが著書の中で説明しているように、中世の人たちは、地球が平らではないことをよく知っていました。コロンブスのインドまでの航海日数を確認するために、地球の直径さえ算出されていたのです。学者たちがコロンブスの計画に反対した真の理由は、距離が長いため物資があまりにも多く必要となるのを懸念していたからでした。

では、なぜそんな神話が広がったのでしょうか? Washington Irvingが書いた『A History of the Life and Voyages of Christopher Columbus』(クリストファー・コロンブスの生涯と航海の歴史)という本は、コロンブスの歩みについて書き留めつつ、楽しめる作品とするため、話にスパイスを加えたものでした。Irvingの書籍が普及しつつあった頃、科学界では創造論に反対して進化論を広めようとする動きがありました。もし教父が地球の形状を誤って認識していたとすれば、このような19世紀の一般思想家は教会の創造論が誤りだったことも示せた、ということなのでしょう。彼らは、地球は平らであるとの主張を3世紀に展開していたラクタンティウスやコスマス・インディコプレウステスの理論を引き合いに出しました。こうして、一方では文筆家が著書の中で事実をあちこちに散りばめて内容の向上を図り、他方では一般思想家が進化論を広めようと試みたことで、地球平面説という神話が作り出され、あるいは広まっていったのです。

A History of the Life and Voyages of Christopher Columbus

事実に反するながらも広く信じられていた神話がいまだに残っている一例ですね。根拠を示そうとする人たちによって広められた神話であり、嘘も方便のようなケースです。疑似事実が書籍に掲載され、その真実性が検証されることもなく学者たちに用いられ、加速度的に肥大化して現在に至っている流れは興味深いものです。コロンブスの航海から400年以上を経た今、地球平面説という神話が現代人を惑わせることはもはやなさそうですが、問題は、コンピュータサイエンス分野の状況はどうなのかということです。ソフトウェアエンジニアリングでも似たようなケースはあるのでしょうか? 現在にも存続している神話のうち、生み出された起源や背景を知られることもなく、真実性が実は見過ごされているようなものは? きっとあると思いますが、むしろ誰もが必ず従うべき格言のような形で存在するのではないでしょうか。そこで注目したいのが、今回検証するDonald Knuthの論文「Structured Programming with Go To Statements」です。

Structured Programming with Go To Statements

この論文に興味を持ったきっかけは、あるPHPライブラリのGitHub issueとして投稿された、次の簡単な質問でした。

関数の再帰ではなくgotoを使っている理由を教えてください。

質問者が指しているのは、以下のプログラムの17行目にあるgoto文です。

<?php

namespace igorw;

class FailingTooHardException extends \Exception {}

function retry($retries, callable $fn)
{
    beginning:
    try {
        return $fn();
    } catch (\Exception $e) {
        if (!$retries) {
            throw new FailingTooHardException('', 0, $e);
        }
        $retries--;
        goto beginning;
    }
}

このライブラリの作成者は、PHPインタプリタの動作を詳しく説明し、質問者の示唆した再帰ではなくgotoを選択した理由を答えています。インターネットですから案の定、激しいやり合いが始まりました。あるユーザはgoto文の使用に反対しただけでなく、Dijkstraの有名な論文「Go To Statement Considered Harmful」(goto文は有害である)へのリンクを張っています。この問題に関して非常に様々な意見があることが分かり、もっと詳しく知りたいと思うようになりました。

flamewar dot gif

Googleで単純に検索してみると、Stack Overflowで交わされている議論「goto文有害論は健在?」が見つかりました。その中ではDijkstraの論文が前述のDonald Knuthの論文と対比されており、これが今回お話しするメインテーマとなります。

Dijkstraの論文は、goto文があるとそのプログラムを理解しにくくなるという理由で、goto文をなくすことを提唱しています。この論文を巡っては注目すべき話があります。Dijkstraは”A case against the goto statement“(goto文を使うべきでないケース)というタイトルで投稿したのですが、出版を急いだ編集者が「編集者への手紙」の欄に、より興味を引きそうなタイトルを新たにつけて掲載したのです。その編集者とは、Pascalの創始者Niklaus Wirthでした。

A Case against the Go To Statement

この論文は当時、多くの議論を呼んだようです。批判の矛先は、gotoを誤用している人だけでなく、優れた構造化プログラムを書きながらたまたまgotoを使ったという人にも向けられます。そのような人たちは、下手なプログラマとまで言われるようになりました。

Knuthの論文「Structured Programming with Go To Statements」に出会う前の私は、コロンブスが地球は平らであることを証明しようとしていたと思っていました。つまり、Dijkstraがgoto文のあらゆる使用に反対していると考えていたのです。Knuthの論文を何段落か読んでいくと、KnuthとDijkstraの私的なやり取りから重要なことが見えてきました。Knuthによれば、Dijkstraは以下のように述べたそうです。

私が(goto文に対して)ひどく独断的な考えを持っていると誤解しないでほしい。このプログラミング上の概念的問題が、たった一つの仕掛け、一つの単純なコーディング規則で解決できるかのような宗教が作り出されているのは不愉快だ。

興味深い言葉が使われていますが、特に注目したいのは「宗教」と「たった一つの仕掛け」です。どういうわけか、私たち開発者はいつも、あらゆる問題を解決できる理想的手段を探し求めています。例えば、CAP定理を破ったと主張するブログ記事をよく見かけますよね。数学的な定理を……破ったとは。しかし、Frederick Brooks Jr.が論文「No Silver Bullet」(銀の弾丸は存在しない)で述べているように、ソフトウェア開発における万能の解決策は存在しません。

技術の面でも管理手法の面でも、以下に述べるような開発というものは1つとして存在しない。それは、生産性、信頼性、簡潔性が10年以内に1桁(10倍)も向上することを請け合うような開発のことだ。

いろいろ証拠をつきつけられても、私たちはいまだに、自分を助けてくれる銀の弾丸を探し求めています。

Knuthの論文に戻りましょう。Knuthは前置きに続いて徹底的な歴史的見直しを行います。プログラミングの歴史上、gotoに反対の立場を取っていた人物を調べ上げており、古くは1959年の話にまでさかのぼると言及しています。

そして、論文は最初のメインセクション「goto文の除去」に突入します。ここでKnuthは、goto文を使ったforループやwhileループが含まれている様々なアルゴリズムをあちこちで示し、そのgoto文を除去する方法を論じています。ここでプログラム自体の他に興味深いのは、それらがforwhileといった最も基本的なプログラム構造だけで出来ており、例えばクラスどころかプロシージャさえ使われていないということです。そこで疑問が湧いてきました。この論文を読むに当たって、プログラミングのどんな時代背景を考慮すべきなのでしょうか?

Knuthの論文が出版されたのは1974年です。ここで2つ目のコード例「Example 1a」をご覧ください。

Example 1a

上記で興味深いのは、アルゴリズム自体ではなく、その次の部分です。

ここで用いられているand演算は、McCarthyの逐次的な論理積演算を表している。

つまりKnuthは話を中断し、現在は大抵のプログラミング言語を使う際に当然のことと見なされているAND短絡演算子について説明しているのです。ではちょっと脇道に入って、この論文が出版された当時のコンピューティング業界の状況を見てみましょう。

先ほど、Knuthの論文に掲載されている例について、ifforwhileといった基本的なプログラミング構造が使われていると述べました。論文の出版年は1974年で、ちょうどBarbara Liskovの重要な論文「Programming with Abstract Data Types」(抽象データ型を用いたプログラミング)が発表されたところでした。LiskovはInfoQで行った最近の講演の中で、当時は抽象化を行う手段といえばプロシージャであり、モジュールとは何であるかさえ知られていなかったと述べています。

Programming with Abstract Data Types

論理プログラミングはになり始めたばかりでした。PLANNERは1969年に設計され、Prologは1972年に欧州で誕生しました。

The Birth of Prolog

それ以前の1964年にBASICが開発され、1968年にはALGOLが登場しています。ALGOLは、beginendをブロックデリミタとして導入した言語です。

BASIC

1973年にはUNIXが発表され、イーサネットも考案されました。また、Carl Hewittによるアクターモデルもこの年に開発されています。

Ethernet

Knuthの論文でもう一つ特徴的なのは、演算数を数えることでアルゴリズムの計算量を算出するという古い手法を取っていることです。1976年になって初めて、Knuthがアルゴリズム計算量の解析手法としてプログラミング界にビッグオー記法を導入したのです。ビッグオー記法とは、1894年から数学の分野で用いられていた概念です。背景をさらにご紹介すると、1976年はApple Iが発表された年でもありました。

Big Omicron Knuth

Big Oh Notation in Die analytische Zahlentheorie

セキュリティの分野では、1977年にRSA暗号アルゴリズムが発明されています。

RSA Original Scheme

翌1978年には、Robin Milnerが「A Theory of Type Polymorphism in Programming」(プログラミングにおける型多相性の理論)を発表しました。また同年、Leslie Lamportは分散システムに関する重要な論文「Time, Clocks, and the Ordering of Events in a Distributed System」(訳注:リンク切れ)(分散システムにおける時間、クロック、およびイベントの順序づけ)を発表しています。

RSA Original Scheme

つまり当時は、PCが一般に普及するには程遠く、今日知られている公開鍵暗号法が登場しつつあり、抽象データ型のような今日一般的に使われているプログラミング手法が学術界で議論され始めたという時代だったのです。そうした背景を踏まえて考えてみると、なぜKnuthの論文に掲載されている例が、for文やgotoを使うループをいかに改善するかということに終始しているのか、あるいはなぜKnuthがif節内のANDの意味を説明する必要があったのかが見えてきます。

コンピュータリソースが乏しかった背景を考慮すれば、Knuthがプログラムから最大限のパフォーマンスを引き出すことに関心を持っていた理由も理解できます。Knuthは「I/Oバウンドでないプログラムにおける実行時間の大部分は、ソーステキストの約3%に集中している」こと、そしてある「内側のループ」の速度を10%上げればプログラム全体も同じだけ速くなるようなケースがしょっちゅうあるということを述べています。

Knuthが問題視しているのは、彼がチューリング賞受賞講演「Computer Programming as an Art」(芸術としてのコンピュータプログラミング)で述べたように、プログラマがプログラムの見当違いの部分を速くしようと取り組んでいることです。

経験からいえば、ほとんど誰もが、プログラムにおける真のボトルネックを誤って捉えている

Knuthは、「例えば97%ぐらいの時間は、ささいな効率のことは忘れるべきだ」と述べ、有名な下記の言葉を続けています。

時期尚早な最適化は諸悪の根源である

この最後の文は文脈から切り離されて引用されるケースが多く、この言葉自体が神話を生み出してきました。つまり、プログラムの最適化に際し何をすべきで何をすべきでないかについての、完全なる宗教のように捉えられているのです。最適化の議論におけるゴドウィンの法則のような状況です。問題なのは、論文では次に続いている下記の内容が、引用時には大抵省略されてしまうことです。

けれども、そのクリティカルな3%の機会を見過ごすべきではない。優れたプログラマは、そんな論法を使って自己満足に陥ることなく、クリティカルコードを慎重に調べる。ただし、そのコードが認識されたあとに限った話である。

この文章の鍵となるのは、「そのコード(クリティカルコード)が認識されたあとに限った話である」という部分です。それからKnuthは次のように注意しています。

測定ツールを使用しているプログラマが共通して経験しているのは、直観的な推測は外れるということだ。

Knuthが最適化の実行を禁じているわけではないことは明らかです。最適化は行うのですが、それが有効であると分かっている場合に限って行うべきなのです。そしてもちろん、有効か否かを知る唯一の方法は、プログラムのベンチマークを測定、実行することです。

格言「諸悪の根源」が文脈から切り離されて引用されている状況で問題なのは、これがあらゆる種類の最適化を禁じるために使われているようだということです。まるでダモクレスの剣によって、コードを改善しようと試みることさえ妨げられているような状況なのです。

Knuthは論文の中で、gotoを除去できるプログラムの例を繰り返し示しています。ただし除去後のプログラムはどれも、元のプログラムと同じか非常に近いパフォーマンス指標しか示していません。けれども、プログラムに何らかのリファクタリングが必要か判断する際、プログラムの読みやすさと分かりやすさはKnuthにとって鍵となる要素です。なぜKnuthはプログラムの効率をそんなに気にかけているのかと不思議に思われるかもしれません。もちろんそれには理由があります。

私が著書で効率を強調している理由は、著書で扱っているアルゴリズムが、多様なアプリケーションの基本要素として繰り返し用いられているものだからである

Knuthの論文に示されている情報の背景がつかめてきました。そう考えてみると、ひょっとしたら今日使われている基本的アルゴリズムの大部分は、Knuthが書籍『The Art of Computer Programming』(コンピュータプログラミングの芸術)シリーズで述べていることに何らかの影響を受けているのかもしれません。

Knuthはこの論文で、追って以下のように述べています。

そうした方が今風だからという理由でgoto文を単に取り除くべきではない。goto文があるかないかは、真の問題ではないのだ。

「我々が人間として抱える最大の問題は、信念と現実を混同することである」 – Alan Kay(「Programming and Scaling」<プログラミングとスケーリング>)

本来の文脈から脱して元々発表された論文よりも目立つようになった文章や論文名という、2つのケースしか示していませんが、プログラミング界の神話の例としてはこれで十分ではないでしょうか。

Alan Kayはインタビューの中で、なぜ他の言語より技術上のメリットが多いと思われながら注目を失っていく言語があったり、一方で他の言語より普及するプログラミング言語があったりすると思うかについて語っています。Kayは、我々自身がプログラマとして受けた教育に問題があると理解しているようです。

(1970年代、)知識を持っていない人たちに教育が行き届くよりもずっと急速に、コンピューティングが普及しました

Kayは、上記の状況からプログラミングが大衆文化であるかのような風潮が生み出され、この分野の基礎が無視されるようになったといい、こう付け加えています。

今日、真のコンピュータサイエンスと真のソフトウェアエンジニアリングが欠如していることは、この大衆文化に原因の一端があると考えています。

これは、今日のプログラミング文化に見られる2つの現象につながっています。TwitterとHacker Newsです。両サイトで起こる議論を見ていると、記事のタイトルを読んだだけで意見を出している人が多いように思えます。現在はクリックベイトがあまりにもはびこっているため、そういった誘惑的なタイトルをなくすことだけを目的とするTwitterアカウントさえあります。

私は以前、ふざけて「140文字に収まらない考えは、取るに足りない考えだ」と言ったことがあります。すると同僚が、140文字以内の論文を募集しているコンピュータサイエンス研究のグループがあるよ、と教えてくれました。それが下記のサイトです。

Tiny TOCS

この傾向によって、私たちのコンピュータサイエンス離れは進んでいるのではないでしょうか。過去に何があったかはもはや知られていません。再考案された手法には、アジャイルテスト駆動開発(TDD)オフラインファースト(訳注:リンク切れ)といった新たな名前が与えられています。

Dijkstraはこの問題を十分認識していました。

1968年、『Communications of the ACM』(米国コンピュータ学会誌)は私の論文を「The goto statement considered harmful」というタイトルで出版した。このタイトルが後に、非常によく引用されこととなったのだが、残念なことに、タイトルしか知らずに引用されているケースが多い。

Dijkstraの論文は、数え切れないほどの議論の場で”ゴドウィンの法則化”している最たるものです。多くの場合は、タイトルしか言及されず、文脈や後にDijkstra自身がこの件について述べた内容は完全に無視されているのです。

知識がこのように扱われている状況を見ていると、『Fahrenheit 451』(邦訳書『華氏451度』)の一節を思い出します。消防隊長がモンターグに、本の禁じられている理由を説明する場面です。

古典は15分のラジオ番組に編集され、2分で読める書評にまたまとめられる。しまいには辞書の10行ぐらいの説明に収まるんだ。

なぜ私たちは、過去の優れた論文や考えのこうした要約だけを広め、神話を作り上げてしまうのでしょうか? それには単純な答えと、より複雑で関連の強い答えがあるように思います。単純な理由は、無精なため、そして気の利いた感じに見せたいためでしょう。議論が沸騰してきたら、相手の主張に屈するよりも論文のタイトルを持ち込んだ方がいいですよね。これはもちろん皮肉です。

複雑な方の理由は、Richard Dawkinsが著書『The Selfish Gene』(邦訳書『利己的な遺伝子』)で説明しているように、ミームに関係があるのではないでしょうか。ご紹介したようなプログラミングにまつわる一文の格言は、実際にその方法論の全容を学ぶことよりも、伝えたり従ったりする方が簡単です。Knuthも論文の中で次のように述べています。

(前略)真に重要な問題の代わりにgotoの除去があまりにも強調されすぎている。人間は元々、優れたプログラム構造のような質的目標を直接目指すよりも、ジャンプの廃止のような、いとも簡単に理解できる量的目標を掲げる傾向があるのだ。

プログラマの書いたコードの質を評価するよりも、コードを何行書いたかを数える方が簡単ですから。

結局のところ、私たちは重要なことに注意を向けるべきであり、自分が常に様々なトレードオフに直面し選択を行っているということを認識すべきなのです。なお、プログラミングの場合は、複雑なプログラムより分かりやすいプログラムの方が成功するでしょう。

特に努力すべきは、プログラムを分かりやすくし、ほぼ確実に動作するようにすることである

最後に、この分野に関するDijkstraの言葉を引用して締めくくりたいと思います。

「コンピュータ産業がコンピューティングサイエンスを駄目にすることのないよう注意しなければならない」 – Dijkstra(「Computing Science: Achievements and Challenges」<コンピューティングサイエンス:業績と挑戦>)

謝辞

Papers We Love Madridでの発表の機会を与えてくれたMiguel PastorFélix Lópezに感謝を述べたいと思います。

同時に、本記事の草稿を校正してくれたLeif Walshに感謝を述べたいと思います。この記事に間違いや誤植が残っていた場合は、全て私の責任です。

参考資料