De skriuwer fan it artikel, Douglas McIlroy, is in Amerikaanske wiskundige, yngenieur en programmeur. Hy is fral bekend om it ûntwikkeljen fan de pipeline yn it Unix-bestjoeringssysteem, de prinsipes fan komponint-rjochte programmearring en ferskate orizjinele nutsbedriuwen: spell, diff, sortearje, join, speak, tr.

Soms komme jo wat echt geweldige programma's tsjin. Nei it graven troch myn ûnthâld, haw ik in list gearstald fan guon fan 'e wiere Unix-edelstenen oer de jierren. Yn prinsipe binne dit frij seldsum en net sa needsaaklike programma's. Mar wat se ûnderskiedt is har orizjinaliteit. Ik kin my net iens foarstelle dat ik foar ien fan har sels op it idee kaam.

Diele, hokker programma's hawwe jo ek sa yndruk makke?

PDP-7 Unix

Om te begjinnen, it PDP-7 Unix-systeem sels. De ienfâld en krêft makken my oerskeakelje fan in krêftige mainframe nei in lytse masine. It is it typyske hiërargyske bestânsysteem, aparte shell, en proseskontrôle op brûkersnivo dat Multics op mainframes net koe ymplementearje nei hûnderten manjierren fan ûntwikkeling. De tekortkomingen fan Unix (lykas de rekordstruktuer fan it bestânsysteem) wiene like ynstruktive en befrijend as har ynnovaasjes (lykas shell I/O-omlieding).

dc

Robert Morris's math-bibleteek foar buroblêdrekner mei fariabele presyzje brûkte inverse flateranalyse om de krektens te bepalen dy't nedich is by elke stap om in troch de brûker spesifisearre presysresultaat te berikken. Op 'e 1968 NATO Software Engineering Conference, yn myn papier oer softwarekomponinten, stelde ik referinsjeprosedueres foar dy't resultaten fan elke winske krektens koene produsearje, mar ik wist net hoe't se se yn 'e praktyk ymplementearje moasten. dc is noch altyd it ienige programma dat ik wit dat dit kin.

typo

Typo oarderet wurden yn tekst op basis fan harren oerienkomst mei de rest fan de tekst. Misspellings lykas 'hte' hawwe de neiging om oan 'e ein fan' e list te einigjen. Robert Morris sei grutsk dat it programma yn elke taal like goed soe wurkje. Hoewol't typflater jo net helpt by it finen fan fonetyske flaters, wie it in geskink foar alle typesetters en wie it tige nuttich foardat de folle minder nijsgjirrige, mar krekter staveringskontrôle fan it wurdboek kaam.

Typo is fan binnen like ûnferwacht as bûten. It algoritme foar gelikensensmjitting is basearre op 'e frekwinsje fan foarkommen fan trigrams, dy't teld wurde yn in 26x26x26-array. D'r wie amper genôch romte yn it lytse ûnthâld foar ienbyte-tellers, sadat in skema waard ymplementearre om grutte oantallen yn lytse tellers te komprimearjen. Om foar te kommen oerlêst, tellers waarden fernijd op in probabilistic basis, behâlden in skatting fan de logaritme fan de teller wearde.

eqn

Mei de komst fan fotoset waard it mooglik, mar ferskriklik ferfeelsum, om klassike wiskundige notaasje te meitsjen. Lorinda Cherry besleat in beskriuwingstaal op heger nivo te ûntwikkeljen, en Brian Kernighan kaam al gau by har. Harren briljante stap wie om mûnlinge tradysje skriftlik út te drukken, en dat is de reden dat eqn ferrassend maklik te learen blykte te wêzen. De earste wiskundige útdrukking taal preprocessor yn syn soarte, eqn hat sjoen bytsje ferbettering sûnt doe.

struktuer

Brenda Baker begon har Fortan-to-Ratfor-konverter te ûntwikkeljen tsjin it advys fan har baas, my. Ik tocht dat dit kin resultearje yn in spesjale weroardieling fan de oarspronklike tekst. It sil wêze frij fan operator nûmers, mar oars net mear lêsber as goed strukturearre Fortran koade. Brenda bewiisde my ferkeard. Se ûntduts dat elk Fortran-programma in kanonysk strukturearre foarm hat. Programmeurs leaver de kanonike foarm as wat se sels oarspronklik skreaunen.

pascal

De syntaksisdiagnoaze yn 'e gearstaller boud troch Sue Graham's groep yn Berkeley wiene de nuttichste dy't ik ea sjoen haw - en se wiene automatysk. As d'r in syntaksisflater is, freget de kompilator jo om in token yn te foegjen om troch te gean mei parsearjen. Gjin besykjen om út te lizzen wat der mis is. Mei dizze gearstaller learde ik Pascal yn ien jûn, sûnder hânboek by de hân.

dielen

Module ferburgen yn it pakket WWB (Writer's Workbench). parts Lorinda Cherry bepaalt dielen fan spraak foar wurden yn Ingelske tekst allinich op basis fan in lyts wurdboek, staverings- en grammatikaregels. Op grûn fan dizze annotaasje toant it WWB-programma stylometryske yndikatoaren fan 'e tekst, lykas it foarkommen fan eigenskipswurden, bysinnen en komplekse sinnen. Doe't Lorinda waard ynterviewd op NBC's Today-show en praat oer de ynnovative grammatikakontrôle fan WWB, wie it de earste fermelding fan Unix op televyzje.

egrep

Al Aho hope dat syn deterministyske reguliere ekspresje-parser de klassike net-deterministyske parser fan Ken soe prestearje. Spitigernôch, de lêste wie al it ynfoljen fan in pass troch komplekse reguliere útdrukkingen oant egrep boude syn eigen deterministyske automatisearring. Om noch winne dizze race, Al Aho omsloech de flok fan eksponinsjele groei fan 'e steat tafel fan' e automaat troch it útfine fan in manier te bouwen op 'e flecht allinnich dy tabel yngongen dy't waarden eins besocht tidens erkenning.

krabben

Luca Cardelli's sjarmante meta-programma foar it Blit-finstersysteem liet firtuele krabben frij dy't om 'e lege skermromte swalken, en mear en mear fan 'e rânen fan aktive finsters byten.

Guon algemiene gedachten

Hoewol it net fan bûten sichtber is, spile teory en algoritmen in beslissende rol by it meitsjen fan de measte fan dizze programma's: typo, dc, struct, pascal, egrep. Yn feite is it de ûngewoane tapassing fan 'e teory dy't it meast ferrassend is.

De oarspronklike auteurs fan hast de helte fan 'e list - pascal, struct, dielen, eqn - wiene froulju, wat it demografyske oandiel fan froulju yn 'e kompjûterwittenskip sterk grutter is.

Douglas McIlroy
Maart, 2020

Boarne: www.habr.com