Edsger Dijkstra：意識的なプログラミングへの「最短の方法」を求めて

abv24.comからの画像



シャーマニズムから科学へのプログラミングの変容に関連した名前を持つ人々の1人は、エドガーダイクストラです。 彼は、プログラミングは高度な芸術であり、知的創造性であると主張することに失敗しました。



彼のすべての研究において、ダイクストラは数学的推論の単純さと優雅さを非常に重視しています。 彼の作品を書くとき、彼は新しいスタイルの科学技術コミュニケーションを作成しました。



プログラミングは、パスや呪文のセットではなく、シャーマニズムではなく、タンバリンで踊るのではなく、数学的訓練です。 そして、外部の効果以上のものであると主張する分野は、強固な基盤の上に構築されるべきです。 ダイクストラのこのような基盤は、数学的論理、またはむしろ述語計算です。



今ではこれは珍しいことではありませんが、50年代には啓示のように聞こえました。 ダイクストラは、理論がどのように実践に役立つことができるか、またそうするべきかを理解し、説得力をもって示しました。

才能のために

Edsger Vyb Dijkstraは、1930年にロッテルダム（オランダ）で生まれました。 彼の両親は教育水準が高く、父親は化学者であり、母親は数学者でした。 1942年、ダイクストラは12歳で、ギリシア語、ラテン語、フランス語、ドイツ語、英語、生物学、数学、化学などのさまざまな科目が教えられている、特に才能のある子供向けの学校であるエラスミニウムジムナジウムに入学しました。





balto-slavica.comからの画像



1945年、ダイクストラは法律を勉強し、おそらく国連でオランダの代表として働くことができると考えました。 しかし、化学、数学、物理学の研究で成功したため、彼はライデン大学に入学し、そこで理論物理学を研究することにしました。 1951年、彼はケンブリッジ大学のプログラミングのサマースクールに参加しました。

ジレンマ

卒業する1年前、ダイクストラはジレンマに直面しました。主な専門分野である科学理論のキャリアを追求すること-理論物理学、またはプログラミングを続けること-

私は選択をしなければなりませんでした-プログラミングをやめて、立派な理論物理学者になるか、理論物理学の訓練を最小限の労力で正式に完了し、誰になるか... プログラマー？ しかし、これは立派な職業ですか？ 結局のところ、プログラミングとは何ですか？ プログラミングを科学の分野と見なすことを可能にする確かな知識は何でしょうか？

ある日、ダイクストラは監督のヴァン・ウェインガーデンの研究室をノックしました。 ダイクストラが懸念していることを辛抱強く聞いた後、ヴァン・ウィンガーデンはプログラミング分野に起因するものはそれほど多くないことに同意しましたが、自動機械計算は短期モードではなく、未来は彼らにあると静かに説明し続けました私たちは非常に始まりであり、誰が知っている？ -おそらく、Dijkstraは、プログラミングを名誉ある科学分野に変えるために呼び出されます。 これはエドガー・ダイクストラの人生のターニングポイントであり、できるだけ早く理論物理学の学位を取得するために必要なすべてのコースを通過し、プログラミングに従事し始めました。



ダイクストラは1952年3月1日に正式に「プログラマー」になり、自分の国でこれを始めた最初のオランダ人でした。 彼は、アムステルダムの数学センターでアルバイトとして働き始めました。

霧の未来

ダイクストラは、そのようなエキゾチックな職業を選ぶことを本当に危険にさらしたと言わなければなりません。 プログラマーはほとんどいませんでしたし、コンピューターは2つか3ダースで数えられていました。 科学としてのコンピューターサイエンスの未来はあいまいでした-多くのコンピューターサイエンスを応用数学の分野と見なしました（そして、理由なく認めなければなりません）。



しかし、次の数年は、ヴァン・ワインガーデンがミスを犯さず、才能のある学生、そして後に大学院生にプログラミングを選択することを示唆したことを示しました.50年代後半から、IBMはトランジスタコンピューターの製造を開始しました。これにより、エネルギー消費、重量、およびコストが大幅に削減されました。メモリとパフォーマンスを保持します。 他の企業は即座に撤退し、軍事研究所や科学研究所のコンピューターが銀行、製造業、教育機関、病院、公益事業で利用できるようになりました。

ダイクストラのアルゴリズム

ダイクストラは、1952年に彼が提案した「最短経路」アルゴリズムの作成者として多くのプログラマーに知られています。これは、Mathematical CenterにインストールされたARCMACコンピューターのパフォーマンスを評価するタスクに関する彼の仕事の結果として登場しました。 このアルゴリズムにより、2つのポイント間を移動する最適なパスを見つけることができます。



科学者はこのアルゴリズムを使用して、ARCMACの開発エンジニアが直面した「回路のすべての必須要素への電流伝送の最適経路を見つけ、銅の消費を最小限に抑える」という問題を解決しました。 彼はこのメソッドを「最短ブランチを持つツリーアルゴリズム」と呼びました。





urban-sanjoo.narod.ruからの画像



ダイクストラのアルゴリズムは、今日でも広く使用されています（たとえば、自動車や飛行機のルートを計画するとき、電子ボードを配線するとき、ルーティングプロトコルで）。 これは「貪欲な」アルゴリズムを指します。つまり、比較的小さなグラフでパスを検索するのに十分効果的です。

ALGOL-60

プログラミングのキャリアの初めに、マシンコードと、同じアルゴリズムを異なるコンピューターモデルのためにゼロから書き直さなければならないという事実で決心したため、Edsger Dijkstraは、高レベルのプログラミング言語を理解せずにはいられませんでした。



1950年代後半に登場したFORTRANは、ダイクストラにとってあまり魅力的ではありませんでした。FOTRANでは、高レベル言語を実装し、バイナリコードの「呪い」からプログラマを救うために、多くの犠牲が主な目標に犠牲になりました。 FORTRANが今日登場した場合、それを保持するチャンスは非常に疑わしいと思います。 しかし、もちろん、FORTRANは大きな前進でした。 しかし、ダイクストラはとにかくFORTRANが好きではありませんでした。この言語では、ダイクストラが数学や論理で見ていた構造の優美さと論理が欠けていたようです。



ALGOL-60言語は、調和のとれた非常に厳格な表記法（いわゆる「バッカスナウア形式」）によって記述され、その開発は、明快さ、明快さ、および証明可能性という固有の要件を備えたほとんど学術環境で行われました。 基準は厳しく、したがって言語はエレガントであることが判明しました（PL / 1、PASCAL、ADAなどのプログラミング言語がALGOLの影響の明らかな痕跡を持っていることは偶然ではありません）。



ためらうことなく、ダイクストラはコンパイラの実装を開始し、この方向での成功は彼の長年のアイデアを裏付けました。人間の心理学に可能な限り適応した「通常の」言語でプログラミングする必要があります。 そしてマシンコード-それなしではまだどこにも行けないので-マシンに任せることができますし、そうすべきです。



当時のプログラミング言語の翻訳で最も困難なタスクの1つは、演算と括弧の優先順位を考慮して算術式をコンパイルするタスクでした。 ダイクストラは、1957年にF. BrauerとK. Zamelzonがこの目的のために2つのスタックを使用することを提案したアルゴリズムを説得力のある方法で実証し、簡素化しました（通常、武器ストアとの類推で「ストア」と言いました）。 算術式は、オブジェクトコードの生成に非常に便利な逆（または「逆」）ポーランド表記法に効果的に変換されました。





逆ポーランド記法の例

ダイクストラによる過去の最大の発明

最大の発明の1つは、基本的な抽象概念の1つを具体化するクローズドルーチンであると彼は信じていました。



ダイクストラは、FORTRANの誕生をソフトウェアにおける2番目の大きな成果と呼びました。 これは非常に大胆なプロジェクトであり、成功するプログラミング手法として評価されるべきですが、基本概念をサポートする手段は非常に限られています。 最近では、この言語は時代遅れとみなされています。 FORTRANの悲劇的な運命は、その広まった認識の結果であり、何千ものプログラマーの考えを過去の過ちに結び付けてきました。



ダイクストラが言及している3番目のプロジェクトはLISPです。 LISPは、ある意味では、最も洗練されたソフトウェア製品の多くに基づいています。 冗談めかして、LISPは「コンピューターを悪用する最もインテリジェントな方法」と言われていました。 ダイクストラは、そのような特性は解放の完全さを伝えるため、大きな賛辞であると信じていました。LISPは、多くの才能のあるプログラマーの多くが、以前は考えられなかったものについて考えるのを助けます。



4番目のプロジェクトはALGOL-60でした。 LISPの定義は、言語の意味と動作の奇妙なミシュマッシュのままですが、有名なALGOL-60アルゴリズム言語メッセージは、次のレベルの抽象性に移行し、プログラミング言語を定義する真の努力の結果です実装とは独立しています。

5人の食事哲学者

ストレッチモードのオペレーティングシステムとも呼ばれる最初のオペレーティングシステムの開発者は、バッチモードで（すべてのコンピューターリソースが「完全に」1つのタスクに属していた場合）働いて、前世紀の60年代半ばまでに非常に重要になったタスクにほとんど遭遇しませんでした-共有リソースへの複数のプロセスのアクセスを提供し、プロセス間でこれらのリソースを共有します。 これがなければ、最も重要なタスクである1台のコンピューターでの複数のプロセスの同時実行を解決することは不可能でした。 これらのアルゴリズムを使用するオペレーティングシステムでは、互いのプロセスのブロックを避けられませんでした。



もちろん、メインプログラム（オペレーティングシステム）の動作のこのような不安定性と予測不能性は誰にも適合しませんでした。



ダイクストラは、このテーマに関する彼の考えを「逐次プロセスの相互作用」という記事で最も完全に表現しました。 この問題を解決するために、ダイクストラは「セマフォ」の概念を提案しました-特別な整数共通変数と2つのプリミティブ「P操作」および「V操作」。 ダイクストラ自身がこれらのプリミティブをどのように説明するかを以下に示します。

これらの最後の2つの操作は常にセマフォで実行され、同時に動作するプロセスからセマフォにアクセスする唯一の方法を表します。 セマフォは本質的に負ではない整数です。 相互排除問題の解決にのみ使用される場合、それらの値の範囲は「0」と「1」のみです。

V操作は、引数（セマフォ）の値を1増やすことで構成されます。このような増加は不可分な操作でなければなりません。 反対に、セマフォに適用されるP操作は、セマフォの値を1ずつ（不可分に）減らします。定義上、セマフォは負でない数なので、遅かれ早かれP操作はその値を0に減らします。P操作を開始したプロセス別のプロセスがこのセマフォの値を正の領域に「シフト」するまで待機する必要があります（つまり、実際には遅延実行モードになります）。 セマフォのロックを解除します。



これらの概念とそれらのさらなる開発（たとえば、ミューテックス）は、現在でもオペレーティングシステムの設計と実装に使用されています。



同じ年に、Edsger Dijkstraは、マルチタスクをサポートするTHEオペレーティングシステム（Technische Hogeschool Eindhovenから）の作成を主導しました。 オペレーティングシステムは、6レベルの階層で構築されました。 同時に、より低いレベル（0から開始）がより高いレベル（最大5）の基礎となりました。 初期レベルでは、割り込み処理システム、セマフォ、プロセスコンテキストの切り替え、メモリ管理システム、ディスパッチャが実装されていました。 中間レベルでは、コンソール、入力/出力、およびデバイスとの相互作用が実装されました。 最高レベルはユーザープログラムを対象としています。 その後、このようなオペレーティングシステムの組織モデルが広く採用されました。



リソースの共有/ブロックの問題とプロセスの相互作用を説明するために、ダイクストラはシンプルで機知に富んだモデルを提案しました。 後にこのモデルは「5人の食事哲学者の問題」と名付けられました。 Charles Hoareの声明では、次のように聞こえます。

古代、金持ちの慈善家の一人が首都を寄付して、5人の有名な哲学者に避難所を提供する寄宿舎を設立しました。 各哲学者は、自分が思考にふけることができる自分の部屋を持っていました。 また、丸いテーブルのある共通のダイニングルームがあり、その周りには5脚の椅子があり、それぞれに対象となる哲学者の名前がラベル付けされていました...

dic.academic.ruからの画像

哲学者はほとんどの時間を考えて過ごし、空腹を感じ、食堂に行き、椅子に座って、左にフォークを取り、食事を始めたと考えられていました。 しかし、これはスパゲッティの複雑な性質であり、2番目のフォークの助けがなければ口に持ってこられません。 したがって、哲学者はプラグを右に持って行かなければなりませんでした...別の哲学者がプラグを必要とする場合、彼はそれが解放されるまで待たなければなりませんでした。

構造プログラミング

産業、ビジネス、教育のすべてのセクターへのコンピューターの浸透、およびこの浸透に付随して開発されるソフトウェアの量の増加は、主要な専門家の間で懸念を引き起こしました：プログラムはますます複雑になり、ますます多様になりました。 これらすべてが品質に影響することはありませんでした-急速に低下していました。



エラーが給与計算プログラムにあった場合は迷惑ですが、これは最終的に修正可能なものです。 航空輸送制御システムでソフトウェアエラーが検出された場合、それは怖いです。 そして、原子炉の運転を制御するためのプログラムには絶対に壊滅的な間違いがあったでしょう。



ダイクストラは、プログラムの紛らわしい構造のエラーの原因を見ました。

プログラムはそれ自体で終わりではないと信じています。 プログラムは計算を呼び出すことを目的としており、計算の目的は目的の結果を取得することです...私たちの判断の容易さと柔軟性は、プログラムと計算の間の関係の単純さに実質的に依存することを確認します（大まかに言えば、望ましいと考えることができます）プログラムの構造が計算の構造に反映されるようにします。

彼はソフトウェア業界がより規律あるものになるのを助け、go toステートメントは有害であると主張しました。 つまり、プログラム内のステートメントに行くほど、プログラムのソースコードを理解することが難しくなりました。



示された容易さと柔軟性を確保するために、ダイクストラは、構造プログラミングと呼ばれる特定の分野に従ってプログラムを設計およびコーディングすることを提案しています。 （これはベーム・ヤコピニの定理として知られる数学的な事実です）任意のプログラムは、フォロー、ブランチ、ループの3つの構造を使用して構築できることが知られています。





itandlife.ruからの画像



ダイクストラは（同時に、 ニクラウスワースとは独立していますが）プログラムをブロックの階層構造として提示することを提案しました。各ブロックは、小さいながらも完了したタスクを実行します。 これは、手順と機能のメカニズムによって実現されます。



最初は不信に見舞われた構造プログラミングのアイデアがすぐに認知されました（特にNicklaus WirthがPASCALプログラミング言語を作成した後）。 さらに、この手法は現在でも重要です（一般的なプログラミング言語C、PASCAL、またはBASICを思い出してください）。

後藤の利点と害について

「Habr」に関する記事の1つがこの質問に当てられました。

に対して：

1. GOTOを使用すると音が悪くなります。

2.最悪のトーンは、マーク付きで戻ります。

3. GOTO-冗長演算子。 サイクルと条件に簡単に置き換えることができます。

4. WirthとDijkstraは、GOTOは悪いと言います。

5. GOTOは、制御構造を最適化するためのコンパイラの多くのオプションを無効にします。これにより、コードが遅くなり、ボリュームが大きくなります。

のために：

1.相互に排他的な条件のグループ。

2.普遍的な因果関係の原理-どこかにGOTOがあれば、そこに必要です。

3.複数のサイクルを同時に終了します。

4.有限状態マシン（コード例）。

記憶

ダイクストラは活発な作家であり、多くの本や記事が彼に属しています（彼はキーボードよりも万年筆を好んでいました）。 -構造プログラミングの理論に関する古典的な本。



ダイクストラは数学センターで働き続け、70年代初頭にアメリカのバローズコーポレーションの研究者として働くようになりました。 1972年、ACMはダイクストラチューリング賞を受賞しました。



1974年、AFIPSは彼にハリーグッドメモリアル賞を授与しました。 1980年代初頭、ダイクストラはテキサス州オースティンに移りました。 1984年に、彼はテキサス大学のコンピューターサイエンス学科の学部長に任命されました。



Edsger Vyb Dijkstraは、アメリカ人文科学アカデミーの名誉外国人会員です。 彼はまた、オランダ王立科学アカデミーの会員であり、英国コンピュータ協会の正会員であり、最終的にはクイーンズ大学ベルファストの博士号を取得しています。

abv24.comからの画像

この世界ではない

1957年に彼は結婚しました。 結婚の登録中に記入されることになっているアンケートの「職業」の列で、彼は「プログラマー」を書いた-彼はそのような職業が存在しないと述べて、文書を書き換えることを余儀なくされた。 その結果、ダイクストラは次のように書いています。「あなたが望むなら-信じるかどうか-しかし、私の結婚証明書の「職業」の欄には「理論物理学者」という面白いエントリがあります！」



ダイクストラは普通の生活では良い意味で「エキセントリック」でした。彼はコンピューターよりもシンプルなペンを好み、家にテレビがなく、携帯電話も映画も見ませんでした。 彼は音楽も愛し、優れたピアニストでした。



彼の同僚が60周年記念の特別なコレクションを準備し、公開したとき、ダイクストラはそれぞれに手で書かれた個人的な感謝の手紙で答えました（これはちなみに、61人の受信者）。 秘書は自分のレベルと地位の科学者であるはずでしたが、ダイクストラはこの特権を拒否し、自分ですべてを行うことを好みました。



2002年8月、Edsger Weebe Dijkstraはオランダの自宅で亡くなりました。