Artikelforfatter Douglas MacIlroy er en amerikansk matematiker, ingeniør og programmør. Han er mest kendt for udviklingen af ​​pipeline i Unix-operativsystemet, principperne for komponentbaseret programmering og flere originale værktøjer: spell, diff, sort, join, speak, tr.

Nogle gange støder man på virkelig fantastiske programmer. Efter at have gravet lidt i hukommelsen har jeg lavet en liste over ægte perler fra Unix gennem årene. Det er for det meste ret sjældne og ikke så nødvendige programmer. Men det, der adskiller dem, er deres originalitet. Jeg kan ikke engang forestille mig, at jeg selv kom på idéen til nogen af ​​dem.

Del gerne, hvilke programmer også har imponeret dig så meget?

PDP-7 Unix

For det første er selve systemet PDP-7 Unix. Dets enkelhed og styrke fik mig til at skifte fra en kraftfuld mainframe til en lille maskine. Her finder vi essensen af ​​et hierarkisk filsystem, separate shell og processtyring på brugerniveau, noget som Multics på mainframes ikke kunne realisere efter hundredevis af mand-års udvikling. Mangelene ved Unix (som fx strukturen af ​​postninger i filsystemet) var lige så lærerige og befriende som dens innovationer (som fx input-output-omdirigering i shell).

dc

Den matematiske bibliotek til skrivebordskalkulatoren med variabel præcision af Robert Morris brugte invers fejlanalyse til at bestemme den nødvendige præcision ved hvert skridt for at opnå den ønskede præcision af resultatet. På NATO-konferencen om software engineering i 1968 præsenterede jeg i mit oplæg om softwarekomponenter standardprocedurer, der kan give et resultater med enhver ønsket præcision, men jeg vidste ikke, hvordan man skulle implementere dem i praksis. dc er stadig det eneste program, jeg kender til, som kan gøre dette.

typo

Typo sorterer ord i teksten baseret på deres lighed med resten af teksten. Fejl som 'hte' har tendens til at dukke op i slutningen af ​​listen. Robert Morris sagde stolt, at programmet ville fungere godt for ethvert sprog. Selvom typo ikke hjælper med at finde fonetiske fejl, er det blevet en virkelig opdagelse for alle, der indtaster tekst, og har været til stor hjælp, før der kom en langt mindre interessant, men mere præcis stavekontrol baseret på ordbogen.

Typo er lige så uventet konstrueret indeni som udenpå. Algoritmen til at måle lighed er baseret på frekvensen af trigrammer, som tælles i et array på 26×26×26. I den lille hukommelse var der næppe plads til enbytes tællere, så der blev implementeret en komprimeringsordning for store tal i små tællere. For at undgå overfyldning blev tællerne opdateret på en probabilistisk basis, hvilket opretholdt en vurdering af logaritmen til tællerens værdi.

eqn

Med fremkomsten af fotonsamling blev det muligt, men særdeles trættende, at udtrykke klassisk matematisk notation. Lorinda Cherry besluttede at udvikle et højere niveau beskriftsprog, og snart sluttede Brian Kernighan sig til hende. Deres geniale træk bestod i at udtrykke den mundtlige tradition skriftligt, derfor viste eqn sig at være overraskende nemt at lære. Den første af sin slags præprocessor for et beskriftsprog for matematiske udtryk, eqn har stort set ikke været forbedret siden.

struct

Brenda Baker satte sig for at udvikle sin Fortan-til-Ratfor konverter på trods af råd fra hendes chef – mig. Jeg tænkte, at det kunne føre til en særskilt omorganisering af den originale tekst. Den ville være fri for operatørnumre, men ellers ikke mere læsbar end en velstruktureret Fortran-kode. Brenda bevist, at jeg tog fejl. Hun opdagede, at hver Fortran-program har en kanonisk struktureret form. Programmører foretrak den kanoniske form fremfor det, de oprindeligt havde skrevet.

pascal

Diagnosen af syntaksen i kompileren, skabt af Sue Grahams gruppe i Berkeley, var den mest nyttige, jeg nogensinde har set – og den blev udført automatisk. Ved syntaksfejl foreslår kompileren at indsætte et leksikon for at fortsætte syntaksanalyse. Ingen forsøg på at forklare, hvad der var galt. Med denne compiler lærte jeg Pascal på en aften uden at have nogen form for vejledning ved hånden.

parts

Modulet gemt inden i WWB (Writer’s Workbench) pakken parts Lorinda Cherry definerer ordklasser for ord i engelske tekster baseret kun på et lille ordforråd, stave- og grammatikregler. Dette resulterer i, at WWB-programmet genererer stilometriske indikatorer for teksten, såsom overvægt af adjektiver, bisætninger og komplekse sætninger. Det var første gang, Unix blev nævnt på tv, da Lorinda gav et interview i tv-programmet Today på NBC og talte om den innovative grammatikkontrol i WWB-tekster.

egrep

Al Aho forventede, at hans determinerede regulære udtryksparser ville overhale den klassiske nondeterminerede parser fra Ken. Desværre var den sidstnævnte allerede ved at afslutte sin gennemgang af komplekse regulære udtryk, mens egrep han byggede sin determinerede automat. For at vinde dette løb undgik Al Aho forbandelsen ved eksponentiel vækst i automattens tilstandstabel ved at opfinde en metode til dynamisk at konstruere kun de tabelposter, der faktisk besøges under genkendelsen.

krabber

Luca Cardellis charmerende metaprogram til vinduessystemet Blit udgav virtuelle krabber, der vandrede rundt i den tomme plads på skærmen og konstant bedte kanterne af aktive vinduer.

Nogle generelle tanker

Selvom det ikke er synligt udefra, har teorien og algoritmerne spillet en afgørende rolle i udviklingen af de fleste af disse programmer: typo, dc, struct, pascal, egrep. Det mest overraskende er faktisk den usædvanlige anvendelse af teorien.

De originale forfattere af næsten halvdelen af listerne — pascal, struct, parts, eqn — var kvinder, hvilket overstiger den demografiske andel af kvinder inden for datalogi betydeligt.

Douglas McIlroy
Marts, 2020

Kilde: habr.com