Autor článku Douglas McIlroy je americký matematik, inžinier a programátor. Je známy najmä vývojom pipeline v operačnom systéme Unix, princípmi komponentovo orientovaného programovania a niekoľkými originálnymi utilitami: spell, diff, sort, join, speak, tr.

Niekedy narazíte na naozaj skvelé programy. Potom, čo som sa prehrabal v pamäti, zostavil som zoznam niektorých skutočných unixových skvostov v priebehu rokov. V zásade ide o pomerne zriedkavé a nie také potrebné programy. Čo ich však odlišuje, je ich originalita. Neviem si ani predstaviť, že by som s nápadom na niektorú z nich prišiel sám.

Zdieľajte, aké programy na vás tiež tak zapôsobili?

PDP-7 Unix

Pre začiatok samotný Unixový systém PDP-7. Jeho jednoduchosť a sila ma prinútili prejsť z výkonného mainframu na malý stroj. Je to základný hierarchický súborový systém, samostatný shell a riadenie procesov na užívateľskej úrovni, ktoré Multics na sálových počítačoch nedokázal implementovať po stovkách človek-rokov vývoja. Nedostatky Unixu (napríklad záznamová štruktúra súborového systému) boli rovnako poučné a oslobodzujúce ako jeho inovácie (napríklad presmerovanie I/O shellu).

dc

Matematická knižnica stolnej kalkulačky Roberta Morrisa s premenlivou presnosťou používala inverznú analýzu chýb na určenie presnosti potrebnej v každom kroku na dosiahnutie používateľom špecifikovaného výsledku presnosti. Na konferencii NATO Software Engineering Conference v roku 1968 som vo svojom príspevku o softvérových komponentoch navrhol referenčné postupy, ktoré by mohli priniesť výsledky akejkoľvek požadovanej presnosti, ale nevedel som, ako ich implementovať v praxi. dc je stále jediný program, o ktorom viem, že to dokáže.

preklep

Preklep zoraďuje slová v texte na základe ich podobnosti so zvyškom textu. Preklepy ako „hte“ majú tendenciu skončiť na konci zoznamu. Robert Morris hrdo povedal, že program bude fungovať rovnako dobre v akomkoľvek jazyku. Aj keď vám preklep nepomôže nájsť fonetické chyby, bol darom z nebies pre všetkých sadzačov a bol veľmi užitočný, kým neprišla oveľa menej zaujímavá, ale presnejšia kontrola pravopisu slovníka.

Preklep je neočakávaný vo vnútri aj vonku. Algoritmus merania podobnosti je založený na frekvencii výskytu trigramov, ktoré sa počítajú v poli 26x26x26. V malej pamäti bolo sotva dosť miesta pre jednobajtové počítadlá, takže bola implementovaná schéma na kompresiu veľkých čísel do malých počítadiel. Aby sa zabránilo pretečeniu, počítadlá boli aktualizované na pravdepodobnostnom základe, pričom sa zachoval odhad logaritmu hodnoty počítadla.

ekv

S príchodom fotosadzby bolo možné, ale strašne zdĺhavé, vyrábať klasický matematický zápis. Lorinda Cherry sa rozhodla vyvinúť jazyk popisu na vyššej úrovni a Brian Kernighan sa k nej čoskoro pridal. Ich skvelým krokom bolo písomné vyjadrenie ústnej tradície, a preto sa ukázalo, že eqn sa dá prekvapivo ľahko naučiť. Prvý preprocesor matematického výrazového jazyka svojho druhu, eqn, odvtedy zaznamenal len malé zlepšenie.

štruktúr

Brenda Baker začala vyvíjať svoj prevodník Fortan-to-Ratfor proti rade svojho šéfa, mňa. Myslel som si, že by to mohlo viesť k špeciálnemu preskupeniu pôvodného textu. Bude bez čísel operátorov, ale inak nebude čitateľnejší ako dobre štruktúrovaný kód Fortran. Brenda mi dokázala, že som sa mýlil. Zistila, že každý program Fortran má kanonicky štruktúrovanú formu. Programátori uprednostňovali kanonickú formu pred tým, čo sami pôvodne napísali.

pascal

Diagnostika syntaxe v kompilátore, ktorý vytvorila skupina Sue Grahamovej v Berkeley, bola najužitočnejšia, akú som kedy videl – a bola automatická. Ak sa vyskytne chyba syntaxe, kompilátor vás vyzve na vloženie tokenu, aby ste mohli pokračovať v analýze. Žiadne pokusy vysvetliť, čo sa deje. S týmto kompilátorom som sa naučil Pascal za jeden večer, bez akéhokoľvek manuálu po ruke.

diely

Modul skrytý vo vnútri balíka WWB (Writer's Workbench). parts Lorinda Cherry určuje časti reči pre slová v anglickom texte len na základe malého slovníka, pravopisných a gramatických pravidiel. Na základe tejto anotácie program WWB zobrazuje štylometrické ukazovatele textu, ako je rozšírenosť prídavných mien, vedľajších súvetí a zložitých súvetí. Keď Lorinda dostala rozhovor v relácii NBC Today a hovorila o inovatívnej kontrole gramatiky WWB, bola to prvá zmienka o Unixe v televízii.

egrep

Al Aho dúfal, že jeho deterministický analyzátor regulárnych výrazov prekoná Kenov klasický nedeterministický analyzátor. Bohužiaľ, tento už dokončoval prechod cez zložité regulárne výrazy až do egrep vybudoval vlastnú deterministickú automatizáciu. Aby Al Aho stále vyhral tento závod, obišiel kliatbu exponenciálneho rastu tabuľky stavov automatu tým, že vynašiel spôsob, ako za behu zostaviť iba tie položky tabuľky, ktoré boli počas rozpoznávania skutočne navštívené.

kraby

Pôvabný metaprogram Lucu Cardelliho pre okenný systém Blit uvoľnil virtuálne kraby, ktoré sa potulovali po prázdnom priestore na obrazovke a odhryzli si čoraz viac okrajov aktívnych okien.

Niektoré všeobecné myšlienky

Aj keď to zvonku nie je vidieť, teória a algoritmy zohrali rozhodujúcu úlohu pri tvorbe väčšiny týchto programov: typo, dc, struct, pascal, egrep. V skutočnosti je to nezvyčajné použitie teórie, ktoré je najviac prekvapujúce.

Pôvodnými autorkami takmer polovice zoznamu – pascal, struct, parts, eqn – boli ženy, čo výrazne prevyšuje demografický podiel žien v informatike.

Douglas McIlroy
marca 2020

Zdroj: hab.com