Autor článku, Douglas McIlroy, je americký matematik, inženýr a programátor. Je nejlépe známý pro vývoj pipeline v operačním systému Unix, principy komponentně orientovaného programování a několik originálních utilit: spell, diff, sort, join, speak, tr.

Občas narazíte na opravdu úžasné programy. Poté, co jsem se prohrabal v paměti, sestavil jsem seznam skutečných unixových drahokamů v průběhu let. V zásadě se jedná o poměrně vzácné a ne tak potřebné programy. Čím ale vynikají, je jejich originalita. Nedokážu si ani představit, že bych s nápadem některého z nich přišel já sám.

Podělte se, jaké programy na vás také udělaly takový dojem?

PDP-7 Unix

Pro začátek samotný Unixový systém PDP-7. Jeho jednoduchost a síla mě přiměly přejít z výkonného sálového počítače na malý stroj. Je to typický hierarchický souborový systém, samostatný shell a řízení procesů na uživatelské úrovni, které Multics na sálovém počítači nebyl schopen dosáhnout po stovkách mužských let vývoje. Nedostatky Unixu (např. struktura záznamů souborového systému) byly stejně poučné a osvobozující jako jeho inovace (např. přesměrování I/O shellu).

dc

Matematická knihovna stolních kalkulaček s proměnnou přesností Roberta Morrise používala inverzní analýzu chyb k určení přesnosti požadované v každém kroku k dosažení uživatelem specifikované přesnosti výsledku. Na konferenci NATO Software Engineering Conference v roce 1968 jsem ve své zprávě o softwarových komponentách navrhl referenční postupy, které by mohly poskytnout jakoukoli požadovanou přesnost, ale nevěděl jsem, jak je uvést do praxe. dc je stále jediný program, o kterém vím, že to umí.

typo

Překlep seřadí slova v textu podle jejich podobnosti se zbytkem textu. Překlepy jako „hte“ bývají na konci seznamu. Robert Morris hrdě prohlásil, že program bude fungovat stejně dobře pro jakýkoli jazyk. Přestože vám překlep nepomůže najít fonetické chyby, byl skutečným přínosem pro všechny sazeče a udělal mnoho dobrého, než přišla mnohem méně zajímavá, ale přesnější slovníková kontrola pravopisu.

Překlep je stejně neočekávaný zevnitř jako zvenku. Algoritmus měření podobnosti je založen na frekvenci výskytu trigramů, které jsou počítány v poli 26×26×26. Malá paměť měla sotva dostatek místa pro jednobajtové čítače, takže bylo implementováno schéma pro kompresi velkých čísel do malých čítačů. Aby se zabránilo přetečení, byly čítače aktualizovány na pravděpodobnostním základě, přičemž byl zachován odhad logaritmu hodnoty čítače.

ekv

S příchodem fotosazby se stalo možné, ale strašně zdlouhavé, tisknout klasickou matematickou notaci. Lorinda Cherry se rozhodla vyvinout popisný jazyk na vyšší úrovni a brzy se k ní přidal Brian Kernigan. Jejich skvělým tahem bylo dát ústní tradici do písemné podoby, takže se to dalo pozoruhodně snadno naučit. První preprocesor matematického výrazového jazyka svého druhu, eqn, se od té doby příliš nezlepšil.

struct

Brenda Baker začala vyvíjet svůj konvertor Fortan-to-Ratfor proti radám svého šéfa, mě. Myslel jsem, že by to mohlo vést ke zvláštnímu přeuspořádání původního textu. Bude bez čísel výpisů, ale jinak nebude čitelnější než dobře strukturovaný kód Fortran. Brenda mi dokázala, že se mýlím. Zjistila, že každý program Fortran má kanonicky strukturovanou formu. Programátoři preferovali kanonickou formu, spíše než to, co sami původně napsali.

pascal

Diagnostika syntaxe v kompilátoru vytvořeném skupinou Sue Grahamové v Berkeley byla nejužitečnější, jakou jsem kdy viděl – a byla provedena automaticky. Při chybě syntaxe vás kompilátor vyzve k vložení tokenu, aby bylo možné pokračovat v analýze. Žádný pokus vysvětlit, co je špatně. S tímto kompilátorem jsem se naučil Pascal za jeden večer bez jakéhokoli manuálu po ruce.

díly

Skryto uvnitř modulu WWB (Writer's Workbench). parts Lorinda Cherry určuje slovní druhy pro slova v anglickém textu pouze na základě malého slovníku, pravidel pravopisu a gramatiky. Na základě této anotace program WWB zobrazuje stylometrické ukazatele textu, jako je převaha přídavných jmen, vedlejších vět a souvětí. Když Lorinda měla rozhovor na NBC's Today a hovořila o inovativní kontrole gramatiky v textech WWB, byla to první zmínka o Unixu v televizi.

Egrep

Al Aho očekával, že jeho deterministický překladač regulárních výrazů předběhne Kenův klasický nedeterministický resolver. Bohužel tento již dokončoval průchod složitými regulárními výrazy, zatímco egrep vybudoval vlastní deterministickou automatizaci. Aby Al Aho stále vyhrál tento závod, obešel prokletí exponenciálního růstu tabulky stavů automatu tím, že vynalezl způsob, jak za běhu sestavit pouze ty položky v tabulce, které jsou skutečně navštěvovány během rozpoznávání.

krabi

Okouzlující metaprogram Lucy Cardelliho pro okenní systém Blit uvolnil virtuální kraby, kteří se potulovali po prázdném prostoru na obrazovce a stále více okusovali okraje aktivních oken.

Některé obecné myšlenky

I když to není zvenčí vidět, teorie a algoritmy sehrály rozhodující roli při tvorbě většiny těchto programů: typo, dc, struct, pascal, egrep. Ve skutečnosti je to neobvyklá aplikace teorie, která je nejvíce překvapivá.

Téměř polovina seznamu – pascal, struct, parts, eqn – byla původně napsána ženami, což výrazně převyšuje demografický počet žen v informatice.

Douglas McIlroy
Březen, 2020

Zdroj: www.habr.com