３月５日に、トニー・ホーア氏が亡くなったらしい。
…いや、すみません。正直自分でも誰だったかわかってませんでした。
チャールズ・アントニー・リチャード・ホーア 享年92歳。
クイックソートの発明者だそうです。
大学の時にソートアルゴリズムいろいろ習ったのを思い出します。
ソートって、プログラマには当たり前すぎる概念なのだけど、何らかの基準に従って「並べる」ことを意味します。
エクセルなんかでも、特定の列の値に従って、行を並び替えたりできますね。あれがソート。
ソートって、「比較」と「データの移動」が非常に多いので、どうしても遅くなる傾向にある。
コンピューターって、メモリのアクセスが遅いのね。仕組み上、計算よりずっと遅い。
クイックソートでは、比較と移動のやり方を工夫していて、非常に速いです。
でも、実はこの工夫が「ちょっとしたズル」になっていて、事前のデータの並びによって、必要な計算量が激しく変わる。
プログラムの種類にもよりますが、「最悪の時の速度」を確保するのが必要な場合があります。
そういう場合には、クイックソートは余り使えない。
もっとも、クイックソートと、別のソートアルゴリズムをうまく組み合わせると、この最悪を避けられることも知られている。
こうした「組み合わせ」アルゴリズムはいろいろと考案されていて、別の名前がついていたりもする。
その意味では、クイックソートは「ソートの基本アルゴリズム」の中では最速で、これを考案したのはすごい人だと思う。
ホーア氏は計算機科学者で、クイックソートは「わかりやすく有名なもの」の一つに過ぎない。
特に「ホーア論理」で知られるそうです。
ごめんなさい。こちらも僕は認識していなかった。
ただ、「そういうものがある」というのは聞いていました。実際使うのは非常に難しいのだけど…
ホーア論理、プログラムが「バグがない」と証明するための、数学的な定義です。
バグがないプログラムというのは理想だし、僕もプログラマとして目指している所ではあるのだけど、人がやることはどうしても間違いを含んでしまう。
ホーア論理は、プログラムにとはなにか、ということを「数学的に」定めたものです。
数学的なので、いろいろと記号に置き換えて論じているからややこしく見えるけど、別にその記号じゃなきゃいけない、というわけではない。
具体的には、プログラムを６つの機能の組み合わせと見て、それらが正し組み合わされることで目的通りの動作をするのであれば、バグがないプログラムと見なす。
実際のプログラム言語をホーア論理を使用してチェックするようなシステムもあるんだそうです。
僕は使ったことないですが。一般に広まってない、ということは、チェックできるようにプログラムの書き方に制約があるとか、どんなプログラムにでも適用できるようなものではないのでしょう。
ただ、ホーア自身が、1995 年には、この方法で「バグがない」ことが確認できるのは非常に小さなプログラムだけで、現在の（1995年時点での）プログラムでは役に立たない、というようなことを言っています。
null 参照、という概念も、ホーア氏が「発明」したものだそうです。
コンピューターのメモリは、アドレス（番地）で区別されます。
プログラム内で、いろいろなデータは「変数」に入れられて保存されますが、この変数の正体は、アドレスで示されたメモリ。
ここで、「アドレス自体が存在しない変数」というのが null 参照です。
変数と書いてしまったけど、アドレスが示すメモリが変数だと考えると、「変数ですらないもの」です。
プログラム馴れしていない人には奇妙に思えるかもしれませんが、これはこれで便利なんですよ…
でも、ホーア自身は、null 参照の発明を悔いていました。
「プログラム馴れ」した人なら使いこなせても、プログラム初心者には使いこなせない。
概念すら理解しづらい。
そして、概念もわからずに使っているものは、必ずバグの温床になるのです。
ホーアが残した言葉。（うけうり）
ソフトウェアを設計するには、2通りの方法がある。
1つは、とてもシンプルに設計して、明らかに欠陥がないようにすること。
もう1つは、とても複雑に設計して、明らかな欠陥がないようにすることだ。
前者の方がはるかに困難である。
「明らかに」と「明らかな」なのが大事。
「明らかに」は、バグがないことを保証している。
「明らかな」は、目立つようなバグは無い、というだけで、保証はできていない。
でも、プログラムって、コンピューターの力を借りたいほど問題が複雑だから作られるの。
バグがないほどシンプルなプログラムで、役に立つような動作ができるなんてことは、多くない。
だから、「前者の方がはるかに困難」。
…DJB なんかは、この困難を実現した例ですかね。
メールサーバーが有名だけど、動作を分割して別々のプログラムにしてしまった。
一つ一つのプログラムはシンプルで、「明らかに」バグが無いようにしてある。
全体としてはそれなりに複雑なことをしているのですが、実際長年バグが見つからないままです。
（全く見つからないわけではないが、他のソフトに比べると非常に少ない）
同じテーマの日記(最近の一覧)
別年同日の日記
申し訳ありませんが、現在意見投稿をできない状態にしています。 |