Autor artykułu Douglas McIlroy – amerykański matematyk, inżynier i programista. Najbardziej znany z opracowania potoku w systemie operacyjnym Unix, zasad programowania opartego na komponentach oraz kilku oryginalnych narzędzi: spell, diff, sort, join, speak, tr.

Czasami natrafiasz na naprawdę wyjątkowe programy. Przebierając w pamięci, sporządziłem listę prawdziwych perełek Uniksa na przestrzeni lat. Głównie są to dość rzadkie i niekoniecznie niezbędne programy. Ale to, co je wyróżnia, to ich oryginalność. Nie potrafię sobie nawet wyobrazić, żebym sam wpadł na pomysł któregokolwiek z nich.

Podzielcie się, jakie programy was też tak mocno zaskoczyły?

PDP-7 Unix

Na początek sama system PDP-7 Unix. Jej prostota i moc sprawiły, że przeszedłem z potężnego mainframe'a na maleńką maszynę. Tutaj jest kwintesencja hierarchicznego systemu plików, oddzielna powłoka oraz zarządzanie procesami na poziomie użytkownika, co Multics na mainframe'ach nie zdołał zrealizować po setkach ludzkich lat prac. Wady Uniksa (np. struktura rekordów w systemie plików) były tak samo pouczające i wyzwalające, jak jej innowacje (np. przekierowanie wejścia-wyjścia w powłoce).

dc

Matematyczna biblioteka dla kalkulatora stacjonarnego z zmienną precyzją Roberta Morrisa wykorzystywała odwrotną analizę błędów do określenia precyzji potrzebnej na każdym kroku, aby osiągnąć zamierzoną precyzję wyniku. Na konferencji NATO dotyczącej inżynierii oprogramowania w 1968 roku w swoim wystąpieniu na temat komponentów oprogramowania zaproponowałem standardowe procedury, które mogą dać rezultat o dowolnej pożądanej precyzji, ale nie wiedziałem, jak je wdrożyć w praktyce. dc nadal pozostaje jedynym znanym mi programem, który potrafi to zrobić.

typo

Typo porządkuje słowa w tekście według ich podobieństwa do reszty tekstu. Literówki, takie jak 'hte', mają tendencję do znajdowania się na końcu listy. Robert Morris z dumą mówił, że program będzie działał równie dobrze w każdym języku. Chociaż typo nie pomaga w znajdowaniu błędów fonetycznych, stała się prawdziwym skarbem dla wszystkich, którzy piszą tekst, i przyniosła wiele korzyści, zanim pojawiła się znacznie mniej interesująca, ale bardziej dokładna sprawdzanie pisowni w słownikach.

Typo jest tak samo zaskakująco skonstruowane wewnątrz, jak i na zewnątrz. Algorytm mierzenia podobieństwa oparty jest na częstotliwości występowania trigramów, które są liczony w tablicy 26×26×26. W maleńkiej pamięci ledwie starczało miejsca na jednobajtowe liczniki, dlatego zrealizowano schemat kompresji dużych liczb w małe liczniki. Aby uniknąć przepełnienia, liczniki były aktualizowane na podstawie probabilistycznej, utrzymując szacowanie logarytmu wartości licznika.

eqn

Wraz z pojawieniem się fotonaboru stało się możliwe, ale strasznie uciążliwe, wyprowadzanie klasycznej notacji matematycznej. Lorinda Cherry postanowiła opracować język opisu wyższego poziomu, a wkrótce dołączył do niej Brian Kernighan. Ich genialny ruch polegał na tym, by wyrazić tradycję ustną w formie pisemnej, dlatego eqn okazał się zaskakująco prosty do nauki. Pierwszy w swoim rodzaju preprocesor języka opisu wyrażeń matematycznych, eqn od tego czasu niemal w ogóle nie był ulepszany.

struct

Brenda Baker podjęła się opracowania swojego konwertera Fortran-to-Ratfor wbrew radzie swojego szefa — mnie. Pomyślałem, że może to prowadzić do specjalnego przeorganizowania kodu źródłowego. Będzie wolny od numerów operatorów, ale w pozostałych aspektach nie bardziej czytelny niż poprawnie zorganizowany kod Fortran. Brenda udowodniła, że się myliłem. Odkryła, że każda program Fortran ma kanoniczną postać strukturalną. Programiści preferowali tę kanoniczną formę, a nie to, co sami pierwotnie napisali.

pascal

Diagnostyka składni w kompilatorze stworzonym przez grupę Sue Graham w Berkeley była najbardziej przydatna z wszystkich, jakie kiedykolwiek widziałem — i odbywała się automatycznie. W przypadku błędu składniowego kompilator proponuje wstawienie leksyki, aby kontynuować analizę składniową. Żadne próby wyjaśnienia, co jest nie tak. Z tym kompilatorem nauczyłem się Pascala w jedną noc, nie mając żadnego przewodnika pod ręką.

parts

Ukryty wewnątrz pakietu WWB (Writer’s Workbench) moduł parts Lorindy Cherry definiuje części mowy dla słów w angielskim tekście na podstawie jedynie małego słownika, zasad ortografii i gramatyki. Na podstawie tej adnotacji program WWB generuje stylometryczne wskaźniki tekstu, takie jak przewaga przymiotników, zdań podrzędnych i zdań złożonych. Kiedy Lorinda udzieliła wywiadu w programie telewizyjnym Today na NBC i opowiedziała o innowacyjnym sprawdzaniu gramatyki w tekstach WWB, był to pierwszy raz, kiedy Unix został wspomniany w telewizji.

egrep

Al Aho miał nadzieję, że jego zdeterminowany rozpoznawacz wyrażeń regularnych wyprzedzi klasyczny niedeterministyczny rozpoznawacz Kena. Niestety, ten ostatni już kończył analizę złożonych wyrażeń regularnych, podczas gdy egrep budował swoją zdeterminowaną automatykę. Aby mimo wszystko wygrać w tym wyścigu, Al Aho zdołał obejść przekleństwo wykładniczego wzrostu tabeli stanów automatu, wynajdując sposób budowania na bieżąco tylko tych wpisów w tabeli, które są faktycznie odwiedzane podczas rozpoznawania.

kraby

Urokliwy program meta Luki Cardelliego dla systemu okienkowego Blit wypuszczał wirtualne kraby, które wędrowały po pustej przestrzeni ekranu, coraz bardziej odgryzając krawędzie aktywnych okien.

Kilka ogólnych myśli

Choć na zewnątrz to nie widać, teoria i algorytmy odegrały kluczową rolę w stworzeniu większości tych programów: typo, dc, struct, pascal, egrep. W rzeczywistości najbardziej zdumiewa niezwykłe zastosowanie teorii.

Oryginalnymi autorami prawie połowy listy — pascal, struct, parts, eqn — były kobiety, co znacznie przekracza demograficzny odsetek kobiet w dziedzinie informatyki.

Douglas McIlroy
Marzec, 2020

Źródło: habr.com