この記事の著者であるダグラス・マキロイは、アメリカの数学者、エンジニア、プログラマーです。 彼は、Unix オペレーティング システムのパイプライン、コンポーネント指向プログラミングの原則、およびいくつかのオリジナル ユーティリティ (spell、diff、sort、join、speak、tr) の開発で最もよく知られています。

時々本当に素晴らしい番組に出会うことがあります。 記憶を調べた結果、長年にわたる実際の Unix の逸品のリストをまとめました。 基本的に、これらは非常にまれであり、それほど必要なプログラムではありません。 しかし、彼らを際立たせているのはそのオリジナリティです。 私自身がそれらのアイデアを思いついたとはさえ想像できません。

あなたもとても感銘を受けたプログラムを教えてください。

PDP-7 ユニックス

まず、PDP-7 Unix システム自体です。 そのシンプルさとパワーのおかげで、強力なメインフレームから小さなマシンに移行することができました。 これは、メインフレーム上の Multics が数百人年の開発を経て実現できなかった、典型的な階層ファイル システム、個別のシェル、およびユーザー レベルのプロセス制御です。 Unix の欠点 (ファイル システムのレコード構造など) は、その技術革新 (シェル I/O リダイレクトなど) と同じくらい有益で解放的でした。

dc

Robert Morris の Variable Precision Desktop Calculator Math Library では、逆誤差分析を使用して、ユーザー指定の結果精度を達成するために各ステップで必要な精度を決定しました。 1968 年の NATO ソフトウェア エンジニアリング会議で、ソフトウェア コンポーネントに関するレポートの中で、私は希望の精度を生み出すことができる参照手順を提案しましたが、それを実践する方法がわかりませんでした。 dc は、これを実行できる私が知る限りの唯一のプログラムです。

打ち間違え

Typo は、テキスト内の単語をテキストの残りの部分との類似性に基づいて配置します。 「hte」のようなスペルミスはリストの最後に来る傾向があります。 ロバート・モリス氏は、このプログラムはどの言語でも同様に機能すると誇らしげに語った。 タイプミスは発音上の間違いを見つけるのに役立ちませんが、これはすべての植字者にとって真の恩恵であり、あまり面白くはないがより正確な辞書のスペル チェッカーが登場する前には、多くの効果をもたらしました。

タイプミスは、外観と同様に内部でも予期せぬものです。 類似性測定アルゴリズムは、26×26×26 の配列でカウントされるトライグラムの出現頻度に基づいています。 小さなメモリには XNUMX バイト カウンタを格納するのに十分なスペースがほとんどなかったため、大きな数値を小さなカウンタに圧縮するスキームが実装されました。 オーバーフローを避けるために、カウンター値の対数の推定値を維持しながら、カウンターは確率論に基づいて更新されました。

式

写真植字の出現により、古典的な数学表記を印刷することが可能になりましたが、非常に面倒でした。 ロリンダ チェリーは高レベルの記述言語を開発することを決意し、すぐにブライアン カーニガンが彼女に加わりました。 彼らの素晴らしい行動は、口頭伝承を文字に置き換えることでした。そのため、eqn は驚くほど簡単に習得できました。 この種の最初の数式言語プリプロセッサである eqn は、それ以来あまり改良されていません。

構造

ブレンダ・ベイカーは、上司である私のアドバイスに反して、Fortan から Ratfor へのコンバーターの開発を開始しました。 これは原文の特別な並べ替えにつながるのではないかと思いました。 ステートメント番号はありませんが、それ以外の場合は、適切に構造化された Fortran コードと同じように読みやすくなります。 ブレンダは私が間違っていることを証明してくれました。 彼女は、すべての Fortran プログラムが標準的に構造化された形式を持っていることを発見しました。 プログラマは、自分たちが最初に書いたものよりも、正規の形式を好みました。

パスカル

バークレー校の Sue Graham のグループが作成したコンパイラの構文診断は、私がこれまで見た中で最も役立ちました。しかも自動的に実行されます。 構文エラーが発生した場合、コンパイラーは、解析を続行するためにトークンを挿入するように求めるプロンプトを表示します。 何が間違っているのか説明しようとはしません。 このコンパイラを使用すると、手元にマニュアルがなくても、一晩で Pascal を学習できました。

部品

WWB (Writer's Workbench) モジュール内に隠されています parts ロリンダ チェリーは、小さな辞書、スペル、文法規則のみに基づいて、英語テキスト内の単語の品詞を決定します。 この注釈に基づいて、WWB プログラムは、形容詞、従属節、複雑な文の出現率など、テキストのスタイロメトリー指標を表示します。 ロリンダが NBC の Today でインタビューを受け、WWB テキストの革新的な文法チェックについて話したとき、それがテレビで Unix について初めて言及されました。

egrep

Al Aho は、彼の決定論的正規表現リゾルバーが Ken の古典的な非決定論的リゾルバーを追い越すことを期待していました。 残念ながら、後者はすでに複雑な正規表現によるパスを完了していましたが、 egrep 彼は独自の決定論的自動化を構築しました。 この競争に勝ち続けるために、アル アホは、認識中に実際にアクセスされるテーブル内のエントリのみをオンザフライで構築する方法を発明することで、オートマトンの状態テーブルの指数関数的な増加の呪縛を回避しました。

カニ

Luca Cardelli の Blit ウィンドウ システム用の魅力的なメタ プログラムは、空の画面スペースを歩き回り、アクティブなウィンドウの端をどんどん噛み砕く仮想カニを解放しました。

一般的な考え

外側からは見えませんが、typo、dc、struct、pascal、egrep などのプログラムのほとんどの作成において、理論とアルゴリズムが決定的な役割を果たしました。 実際、最も驚くべきは、理論の珍しい応用です。

リストのほぼ半分 (パスカル、構造体、部品、eqn) はもともと女性によって書かれており、コンピューター サイエンスにおける女性の人口統計をはるかに上回っています。

ダグラス・マキロイ
3月、2020

出所： habr.com