De auteur van het artikel, Douglas McIlroy, is een Amerikaanse wiskundige, ingenieur en programmeur. Hij is vooral bekend door het ontwikkelen van de pijplijn in het Unix-besturingssysteem, de principes van componentgeoriënteerd programmeren en verschillende originele hulpprogramma's: spell, diff, sort, join, speak, tr.

Soms kom je echt prachtige programma's tegen. Nadat ik door mijn geheugen had gerommeld, stelde ik door de jaren heen een lijst samen van echte Unix-juweeltjes. Kortom, dit zijn vrij zeldzame en niet zo noodzakelijke programma's. Maar wat hen onderscheidt, is hun originaliteit. Ik kan me niet eens voorstellen dat ik zelf op het idee van een van hen kwam.

Deel van welke programma's je ook zo onder de indruk bent?

PDP-7 Unix

Om te beginnen het PDP-7 Unix-systeem zelf. Door zijn eenvoud en kracht ging ik van een krachtig mainframe naar een kleine machine. Het is het typische hiërarchische bestandssysteem, de aparte shell en de procescontrole op gebruikersniveau die Multics op het mainframe na honderden manjaren van ontwikkeling niet heeft kunnen bereiken. De tekortkomingen van Unix (zoals de recordstructuur van het bestandssysteem) waren net zo leerzaam en bevrijdend als zijn innovaties (zoals shell I/O-omleiding).

dc

Robert Morris' Variable Precision Desktop Calculator Math Library gebruikte inverse foutanalyse om de precisie te bepalen die nodig is bij elke stap om een ​​door de gebruiker gespecificeerde resultaatprecisie te bereiken. Op de NAVO Software Engineering Conferentie van 1968 stelde ik in mijn rapport over softwarecomponenten referentieprocedures voor die elke gewenste nauwkeurigheid konden opleveren, maar ik wist niet hoe ik ze in de praktijk moest brengen. dc is nog steeds het enige programma dat ik ken dat dit kan.

typfout

Typo rangschikt woorden in tekst op basis van hun gelijkenis met de rest van de tekst. Spelfouten zoals 'hte' staan ​​vaak aan het einde van de lijst. Robert Morris zei trots dat het programma voor elke taal even goed zou werken. Hoewel typefouten je niet helpen bij het vinden van fonetische fouten, was het een echte zegen voor alle letterzetters, en het deed veel goeds voordat de veel minder interessante maar nauwkeurigere spellingcontrole voor woordenboeken op de markt kwam.

Typo is van binnen net zo onverwacht als van buiten. Het algoritme voor het meten van overeenkomsten is gebaseerd op de frequentie van voorkomen van trigrammen, die worden geteld in een 26×26×26-array. Het kleine geheugen had nauwelijks genoeg ruimte voor tellers van één byte, dus werd er een schema geïmplementeerd om grote getallen in kleine tellers te comprimeren. Om overflow te voorkomen, werden de tellers bijgewerkt op probabilistische basis, met behoud van een schatting van de logaritme van de tellerwaarde.

gelijk aan

Met de komst van fotozetwerk werd het mogelijk, maar vreselijk vervelend, om klassieke wiskundige notaties af te drukken. Lorinda Cherry besloot een beschrijvingstaal van een hoger niveau te ontwikkelen, en al snel sloot Brian Kernigan zich bij haar aan. Hun briljante zet was om de mondelinge traditie op schrift te stellen, dus eqn was opmerkelijk gemakkelijk te leren. Eqn, de eerste taalpreprocessor voor wiskundige uitdrukkingen in zijn soort, is sindsdien niet veel verbeterd.

struct

Brenda Baker begon haar Fortan-naar-Ratfor-converter te ontwikkelen tegen het advies van haar baas, mij in. Ik dacht dat dit zou kunnen leiden tot een speciale herordening van de originele tekst. Het zal vrij zijn van afschriftnummers, maar verder niet leesbaarder dan goed gestructureerde Fortran-code. Brenda bewees dat ik ongelijk had. Ze ontdekte dat elk Fortran-programma een canoniek gestructureerde vorm heeft. De programmeurs gaven de voorkeur aan de canonieke vorm boven wat ze zelf oorspronkelijk schreven.

pascal

De syntaxisdiagnostiek in de compiler, gemaakt door de groep van Sue Graham in Berkeley, was de meest behulpzame die ik ooit heb gezien - en het gebeurde automatisch. Bij een syntaxisfout vraagt ​​de compiler u om een ​​token in te voegen om door te gaan met parseren. Geen poging om uit te leggen wat er mis is. Met deze compiler leerde ik Pascal in één avond zonder handleiding bij de hand.

onderdelen

Verborgen in de WWB-module (Writer's Workbench). parts Lorinda Cherry bepaalt woordsoorten voor woorden in een Engelse tekst op basis van slechts een klein woordenboek, spelling- en grammaticaregels. Op basis van deze annotatie geeft het WWB-programma stilometrische indicatoren van de tekst weer, zoals de prevalentie van bijvoeglijke naamwoorden, bijzinnen en complexe zinnen. Toen Lorinda werd geïnterviewd op NBC's Today en sprak over de innovatieve grammaticacontrole in WWB-teksten, was dat de eerste keer dat Unix op televisie werd genoemd.

egr

Al Aho verwachtte dat zijn deterministische oplosser voor reguliere expressies de klassieke niet-deterministische oplosser van Ken zou inhalen. Helaas was laatstgenoemde al bezig met het doorlopen van complexe reguliere expressies, while egrep bouwde zijn eigen deterministische automatisering. Om deze race toch te winnen, omzeilde Al Aho de vloek van de exponentiële groei van de statustabel van de automaat door een manier te bedenken om tijdens de herkenning alleen die vermeldingen in de tabel te bouwen die daadwerkelijk worden bezocht.

krabben

Het charmante metaprogramma van Luca Cardelli voor het Blit-venstersysteem liet virtuele krabben los die door de lege schermruimte zwierven en steeds meer de randen van actieve vensters afbijten.

Enkele algemene gedachten

Hoewel het van buitenaf niet zichtbaar is, speelden theorie en algoritmen een beslissende rol bij het maken van de meeste van deze programma's: typo, dc, struct, pascal, egrep. In feite is het de ongebruikelijke toepassing van de theorie die het meest verrassend is.

Bijna de helft van de lijst - pascal, struct, parts, eqn - is oorspronkelijk geschreven door vrouwen, veel groter dan de demografie van vrouwen in de informatica.

Douglas McIlroy
Maart, 2020

Bron: www.habr.com