今日はダイクストラの誕生日(1930)。
goto 不要論で有名な人。
…すいません。goto 不要論に関しては過去に書きたいこと書きましたし、ダイクストラの業績も実のところそれほど知らないのです。
余り書けることがなさそう。
通り一遍の説明になりますが、ダイクストラは電子計算機最初期の計算機数学者です。
初期のコンピューターには「スタック」構造がなく、つまりはサブルーチンコールもなく、そもそもプログラム言語もなく、アセンブラでプログラムを組んでいました。
これでもサブルーチンは作れました。
呼び出し元で、サブルーチンの最後にある「ジャンプ」のアドレスを書き変え、戻ってくるようにしてからサブルーチンにジャンプすればよいのです。
ただ、この方法は複雑極まりなく、プログラムは職人芸の世界でした。
あまりにも複雑で人間の手に負えない「プログラム」を、人間にできないのであればコンピューターにやらせたらどうか、というアイディアが出ます。
このアイディアは「自動プログラミング」と呼ばれますが、プログラムはそもそも創造的な行為だからコンピューターにできるわけがない、という懐疑派と、ある程度人間がわかるようにかかれた「詳細仕様」を、コンピューターが翻訳するのであれば可能ではないか、という推進派に別れます。
FORTRAN の登場(1957)により「翻訳は可能」とわかり、論争には終止符が打たれましたが、今度はより良い言語仕様とは何か、が議論に上ります。
また、PDP-6(1963)でCPUがスタック構造をサポートし、ルーチン呼び出しなど、基本的なプログラムの枠組みが整います。
ダイクストラはこの時代の人。ALGOL(1958)言語にほれ込んだ、強烈な支持者でした。
ただ、当初の ALGOL は言語仕様だけがあって処理系はありませんでした。
まさに絵に描いた餅。
＃実際には処理系はあったのだけど、とても実用にならなかった。
ALGOL は 1960 年に言語仕様を改定し、 ALGOL 60 となります。
最初の ALGOL (以下 ALGOL 58 と表記)に処理系がなかったのは、処理系が作りにくい仕様があったせいでもあります。
それを改め、実際に使える言語にしようと言うのがこの改定。
この際にダイクストラも参加し、ALGOL 60 の処理系を作成しています。
そして…ALGOL 60 の素晴らしさを広めようと、他の言語を攻撃し始めます。
自分の好きな言語だけがよくて他はダメ、という、いわゆる「言語厨」の状態。
BASIC を批判した、ということもよく言われるのですが、BASIC だけじゃなくて「ALGOL 以外全部認めない」だけですので、お間違えの無いよう。
あと、この批判は…どう見ても批判と言うより、冗談だよね。
言語の特徴を乱暴だけど短い（でも的確な）言い回しでとらえて、笑い飛ばしているだけ。
「FORTRAN は 20歳になるのに子供じみてる」とか、「COBOL は精神障害だ」とか、「BASIC を学んだものは、プログラマとして再起不能」とか。
多分、現在活躍する多くのプログラマが、最初は BASIC で学んだんじゃないかと思うんですけどね。
困るのは、ただの言語厨ではなく、高名な学者だと言うこと。
「言語厨乙」の一言で片づけるわけにいきません。
そして、有名な goto 不要論争。
以前に書いた通り、ダイクストラは goto が不要だとは思っていません。
話題になりすぎちゃって、本人の意図と違うことになってる。
ただし、当時の言語では goto が多すぎたのも事実です。
多くの goto は、処理を「開始」し、「終了」するために使われていました。
サブルーチンを呼び出し、復帰するとか、IF で実行されるべき流れにジャンプし、終わったから元の流れに戻るとか、そういう使われ方です。
ALGOL では、「開始」と「終了」に goto を使うのではなく、BEGIN と END という擬似命令を使うようにしています。
この方法では、人間にとってもプログラムがわかりやすくなりますし、ほとんどの goto を無くすことができました。
でも、「処理の打ち切り」などに goto が必要と言う認識はダイクストラも持っていたようです、というのも以前に書いた通り。
そして、今では ALGOL の影響を受けていないプログラム言語は無い、と言って過言ではありません。
FORTRAN や COBOL 、BASIC だって、その後「構造化」を取り入れているからね。
ダイクストラ自身は計算機科学の数学者であり、言語だけをやっていたわけではありません。
（さらに言えば、元々は理論物理学者です）
グラフ理論にも、ダイクストラ法と呼ばれる重要アルゴリズムを残しています。
これは、乗換案内やカーナビなどで使用される、「最短経路を求める」ためのアルゴリズムです。
わかる人にはわかると思うけど、カーナビとかって、「巡回サラリーマン問題」と類似だからね。
何の戦略もなく最短経路を求めようと思うと、組み合わせが爆発して計算できなくなってしまう。
でも、ダイクストラ法では、近傍探索を繰り返し、重複するルートを見つけた場合はより良い道のみを残す…ということを繰り返すことで、比較的短い時間に最適解を見つけ出してしまう。
今ではもっと改良されたアルゴリズムもあるけど、基本的には「改良」で、ダイクストラの考案した方法が元になっています。
逆ポーランド記法(RPN:Reverse Polish Notation)と、通常の数学記法を逆ポーランドに翻訳するためのアルゴリズムもダイクストラの考案だそうです。
…これ、大学の時に演習でプログラム作ったな。
説明すれば、普通の記法で
1 * (2 + 3)
と言う数式を、逆ポーランド記法で書くと
1 2 3 + *
となります。
逆ポーランドでは、演算記号が出てきた時点で「データの最後から２つ取り出して計算し、その結果を新たなデータとして残す」ように計算を進めます。
利点として、
・括弧がいらない
・数値データと、計算手順（記号）を分離できる
というものがあり…
…いや、あまり細かな話はいいや。これがどんなに便利か、興味ある人は自分で調べてください。
（このページから３ページ分を読むとよくわかるかと）
セマフォもダイクストラの考案らしいのだけど、これに至っては…
セマフォなしでプログラム書くなんてできないだろ、というくらい大切な概念。
いや、小さなプログラム書いている程度なら全然いらないのだけど、実用になる、ある程度のサイズのプログラムになると必須ですよ。
同じテーマの日記(最近の一覧)
別年同日の日記
15年 コンピューターが、チェスの世界チャンピオンに勝った日(1997)
申し訳ありませんが、現在意見投稿をできない状態にしています。 |