Þessi síða notar kökur (e. cookies) til að auðvelda þér að vafra um vefinn.

Edsger Wybe Dijkstra – Stysta leiðin að fallegum kóða

eyjo 1Árið 2012 var svokallað Turing ár en þá voru liðin 100 ár frá fæðingu Alan Turing.  Þekkingarsetur í fræðilegri tölvunarfræði við Háskólann í Reykjavík (ICE-TCS) skipulagði fyrirlestraröð þar sem fjallað var um líf og störf Alan Turing.  Ákveðið var að halda áfram á sömu braut og halda fyrirlestraröðina, Pearls of Computation, þar sem fjallað er um einstaklinga sem hlotið hafa hin virtu Turing verðlaun eða önnur virt verðlaun á sviði tölvunarfræðinnar.  Edsger Wybe Dijkstra hlaut Turing verðlaunin árið 1972 og er einn þeirra sem fjallað var um í þessum fyrirlestrum. Hægt er að nálgast glærur af flestum fyrirlestrum á slóðinni http://www.icetcs.ru.is/poco.html.

Á síðustu áratugum hafa orðið miklar framfarir í notkun á sjálfvirkri vegvísun, þ.e. þegar fundin er hagkvæmasta leiðin milli tveggja staða. Hvort sem um er að ræða GPS staðsetningartæki í bílum eða kortakerfi eins og Google Maps eða ja.is þá er notuð aðferð sem er afbrigði af svokölluðu reikniriti Dijkstra (e. Dijkstra’s algorithm). Segja má að allar fræðilegar framfarir fyrir vandamálið að finna stystu leið frá upphafspunkti (e. Single Source Shortest Path (SSSP)) í almennum stefndum og óstefndum netum hafa frá árinu 1959 byggst á reikniriti Dijkstra [0].

Edsger Wybe Dijkstra fæddist í Rotterdam í Hollandi þann 11. maí árið 1930.  Hann hóf nám í stærðfræði og fræðilegri eðlisfræði við Leiden háskólann en komst fljótlega að því að tölvunarfræðin ætti betur við hann. Hann orðaði það sjálfur þannig að hann hafi talið að tölvunarfræðin byði upp á meiri möguleika á því að kljást við vitsmunalega krefjandi vandamál en fræðileg eðlisfræði.  Á þeim tíma sem Dijkstra var að hefja feril sinn sem tölvunarfræðingur þá var tölvunarfræðin ekki samþykkt sem sérstakt fræðasvið.  Þegar Dijkstra gifti sig árið 1957 var hann skráður sem fræðilegur eðlisfræðingur á giftingarvottorðinu því starfsheitið „forritari“ var ekki samþykkt.  Dijkstra hóf ferill sinn í Amsterdam en flutti síðan yfir til Tækniháskólans í Eindhoven árið 1962.  Árið 1984 flutti hann yfir til háskólans í Austin, Texas, og starfaði þar þangað til hann lét af störfum árið 2000.

Dijkstra hannaði hið svokallaða reiknirit Dijkstra árið 1956 þegar hann var að vinna við tölvu sem var smíðuð við Mathematical Centre í Amsterdam.  Til að sýna fram á reiknigetu tölvunnar þá vantaði vandamál sem tölvan gæti leyst.  Dijkstra segist hafa verið á kaffihúsi með konu sinni þegar hann fór að hugsa hver væri hagkvæmasta leiðin frá Rotterdam til Groningen og hannaði reikniritið á u.þ.b. 20 mínútum [1].  Reikniritið var hins vegar ekki birt fyrr en 1959.  Á þessum tíma voru stærðfræðitímarit ekki ginkeypt fyrir vandamálum þar sem markmiðið var að leysa endanleg vandamál hratt. Flest áhugaverð vandamál þessa tíma fjölluðu um óendanlega hluti og því þótti reiknirit Dijkstra ekki spennandi.  Það tók því þrjú ár að fá greinina birta en síðan þá hefur verið vísað í hana rúmlega 10.500 sinnum [2].

Edsger Wybe Dijkstra var um margt einstakur og á það ekki síst við um vinnulag hans.  Ólíkt flestum fræðimönnum á 6. og 7. áratugnum þá var hann ekki með ritara til að vélrita greinar sínar heldur vélritaði hann þær sjálfur.  Einnig skrifaði hann sjaldan hefðbundnar greinar sem sendar voru í tímarit heldur skrifaði hann einungis til lítils hóps starfsfélaga og vina.  Dijkstra vélritaði hugsanir sínar, ljósritaði og sendi á þennan hóp og var þar bæði um að ræða fræðilegar vísindagreinar, ferðasögur eða bollaleggingar um það sem honum var efst í huga.  Dijkstra var mjög skipulagður og tölumerkti allt sem hann skrifaði, og kallast þessi rit í dag EWD skýrslurnar (e. EWD Reports).  Þegar Dijkstra birti  vísindagreinar í fagtímaritum þá var það oft einhver úr hópnum sem fékk upprunalegu skýrsluna sem áframsendi efnið til birtingar.  Um 1970 hætti Dijkstra að nota ritvél og hóf að handskrifa allt sem frá honum kom. Dijkstra var með mjög skýra, formfasta og sérstaka rithönd sem búið er að setja upp sem niðurhalanlega leturgerð, og  þannig hefur fólki verið gert kleift að skrifa eins og  Dijkstra. Seinasta EWD skýrslan er númer 1318 og var skrifuð í apríl 2002.  Hægt er að sækja allar EWD skýrslurnar sem vitað er um á slóðinni http://www.cs.utexas.edu/~EWD/.  Dijkstra áleit að það ætti að vera hægt að fullvinna greinar, lausnir og texta áður en byrjað er að skrifa, hann notaði því aldrei ritvinnsluforrit heldur skrifaði sínar greinar frá upphafi til enda án þess að gera uppkast.

Dijkstra leit á það sem skyldu sína sem vísindamaður að vera gagnrýninn og var óhræddur við að láta í ljós óánægju sína með þá hluti sem honum fannst gagnrýniverðir. Þessi lífsskoðun hans varð ekki til þess að afla honum mikilla vinsælda enda margt sem fór í taugarnar á honum, þar á meðal tölvunarfræðingar sem byrja lista á staki 1 en ekki staki 0, viðvaningsleg vinnubrögð í forritun, lélegt skipulag í fyrirlestrum, persónugerving, vondur ritháttur í stærðfræðiformúlum, óþarflega flóknar stærðfræðiframsetningar og nokkur forritunarmál, þar á meðal Basic, Fortran, Cobol og PL/I.  Óvild hans í garð forritunarmálsins Basic var slík að hann taldi að ef nemandi hefði lært Basic þá væri búið að eyðileggja þann einstakling andlega þannig að hann ætti ekki afturkvæmt. Þar af leiðandi neitaði Dijkstra að taka við slíkum nemendum í þeim áföngum sem hann kenndi.  Hin stöðuga og harkalega gagnrýni Dijkstra varð til þess að hann eignaðist marga óvildarmenn, bæði innan fræðasviðsins sem og utan þess.  Eftir stutta ritdeilu við Alan Kay um mismun á tölvunarfræðinni milli Evrópu og Bandaríkjanna þá setti Alan Key fram í ræðu sinni þessi orð: "ég veit ekki hversu mörg ykkar hafið hitt Dijkstra, en þið vitið væntanlega að hroki í tölvunarfræði er mældur í nanó-Dijkstras" [5].

Ein frægasta ritdeila Dijkstra snerist um GOTO skipunina.  Á þeim tíma var GOTO mikið notað, sérstaklega í forritunarmálum eins og Basic, Fortran og Cobol sem Dijkstra hafði einmitt mikla andúð á. Árið 1968 skrifaði Dijkstra hugleiðingar sínar um notkun GOTO í forritun, þar sem kom meðal annars fram sú skoðun hans að „gæði forritara eru í öfugu hlutfalli við þéttleika GOTO skipana í þeim forritum sem þeir skrifa“ [6].  Dijkstra sendi þessar hugleiðingar til tímaritsins Communications of the ACM en ritstjóri þess var Niklaus Wirth.  Til að flýta fyrir birtingu þessara hugleiðinga þá breytti hann forminu yfir í bréf til ritstjórans ásamt því að breyta titlinum í „GOTO considered harmful“, eða „GOTO talið hættulegt“.  Fljótlega hófst mikil umræða um gildi GOTO skipunarinnar í forritun.  

Árið 1987 birti Frank Rubin grein í sama tímariti undir nafninu „„GOTO considered harmful“ considered harmful“, þar sem hann réðist gegn grein Dijkstra og reyndi að sýna fram á að ómögulegt væri að leysa sum vandamál innan forritunar án þess að nota GOTO [7]. Moore og félagar reyndu að svara Rubin með grein sinni „„„GOTO considered harmful“ considered harmful“ considered harmful?“ [8].  Þá fékk Dijkstra nóg af þessari vitleysu og sendi inn grein sem kallast „On a somewhat disappointing correspondence“ [9].  Í þeirri grein byrjar Dijkstra á að fullyrða að Rubin geti ekki verið alvöru tölvunarfræðingur því hann byrjar að telja lista í 1 en ekki í 0.  Að því loknu rífur hann grein Rubins kerfisbundið í tætlur og setur fram sýnidæmi sem afsanna fullyrðingar Rubins.  Það er hins vegar bersýnilegt að það sem veldur Dijkstra mestum vonbrigðum í þessari ritdeilu er sú staðreynd að Moore og félagar hafi verið tilbúnir til að samþykkja eitthvað af rökum Rubin.  Breyting Niklaus Wirth á titli greinar Dijkstra átti eftir að hafa meiri breytingar í för með sér en lönguvitleysuna í ritdeilunni um GOTO.  Ef leitað er á netinu að forskriftinni „... considered harmful“ þá má finna þúsundir tilvísana þar sem flestallir hlutir milli himins og jarðar eru taldir hættulegir.  Til gamans má nefna tilraun Eric Mayer til að sporna við þessari þróun með því að birta grein árið 2002 sem kallast „„Considered Harmful“ Essays Considered Harmful“ [10].

Dijkstra hafði mikil áhrif á tölvunarfræði, forritun og þróun tölvunnar.  Hann var oft í fararbroddi á miklum umbyltingartímum og þróaði margt sem við teljum sjálfsagt í forritun í dag.  Til að mynda er gagnatagið stafli (e. stack) hannað af Dijkstra, semafórur (e. semaphores) sem eru notaðar í flestöllum stýrikerfum til að stjórna aðgengi að takmörkuðum auðlindum voru settar fram af Dijkstra, lagskipting stýrikerfa, eins og er reglan í öllum stýrikerfum í dag, var sett fyrst fram í THE stýrikerfinu en Dijkstra var framarlega í hópnum sem bjó til það kerfi.  Einnig má nefna framlag Dijkstra til sviða eins og self-stabilizing kerfi með dreifðri stjórnun [11], en fyrir það framlag voru PODC verðlaunin endurskírð sem Dijkstra verðlaunin árið 2002.  Þegar Dijkstra hlaut Turing verðlaunin þá var ástæðan gefin upp sem: „For fundamental contributions to programming as a high, intellectual challenge; for eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness; for illuminating perception of problems at the foundations of program design.“ [12]  Í þakkarræðu sinni, sem kallaðist „hinn auðmjúki forritari“ [13] þá réttlætir Dijkstra viðhorf sitt til agaðra vinnubragða og lýsir þeirri skoðun sinni að það sé lífsnauðsynlegt fyrir framtíð tölvunarfræði og forritunar að forrit séu eins fáguð og hægt er og að aldrei sé slakað á kröfum um fagleg vinnubrögð.

Dijkstra lést 6. ágúst 2002. Hann hefur markað djúp spor í sögu tölvunarfræðinnar, en bestu eftirmæli hans eru líklega komin frá honum sjálfum.  Í EWD skýrslu númer 1213 sem hann birti árið 1995 þá berst talið að ódauðleika, og þá setur hann fram eftirfarandi línur: „If 10 years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself: „Dijkstra would not have liked this.“, well that would be enough immortality for me.“ [14].

Höfundur Eyjólfur Ingi Ásgeirsson, lektor tækni- og verkfræðideild Háskólans í Reykjavík

Heimildir:
[0] Mikkel Thorup, ‘Undirected single-source shortest paths with positive integer weights in linear time’, Journal of the ACM 46(3): 362–394, 1999.

[1] Thomas J. Misa and Philip L. Frana. 2010. An interview with Edsger W. Dijkstra. Commun. ACM 53, 8 (2010), 41-47.

[2] A note on two problems in connexion with graphs, Numerische mathematik, 1959.

[3] EWD 498, „How Do We Tell Truths that Might Hurt“, http://www.cs.utexas.edu/~EWD/ewd04xx/EWD498.PDF

[4] EWD 1304, „The end of Computing Science?“, https://www.cs.utexas.edu/~EWD/ewd13xx/EWD1304.PDF

[5] Alan Kay, 1997 ACM Conference on Object-Oriented Programming, Systems, Languages and applications (OOPSLA) keynote speech.

[6] „GOTO considered harmful“. A letter to the editor of Communications of the ACM (1968).  Editor Niklaus Wirth

[7] „„GOTO considered harmful" considered harmful““ by Frank Rubin (Comm. ACM, 1987)

[8] „„„GOTO considered harmful“ considered harmful“ considered harmful?“ by Moore et al (Comm. ACM, 1987)

[9] EWD 1009 „On a somewhat disappointing correspondence.“ (1987), http://www.cs.utexas.edu/~EWD/ewd10xx/EWD1009.PDF

[10] http://meyerweb.com/eric/comment/chech.html

[11] EWD 426: Self-stabilizing systems in spite of distributed control. Commun. ACM 17 (1974), 11: 643–644.

[12] http://amturing.acm.org/award_winners/dijkstra_1053701.cfm

[13] EWD 340: „The humble programmer“ (1972), http://www.cs.utexas.edu/~EWD/ewd03xx/EWD340.PDF

[14] EWD 1213: „Introducing a Course on Calculi“ (1995), http://www.cs.utexas.edu/~EWD/ewd12xx/EWD1213.PDF

Lesið 2452 sinnum Síðast breytt mánudagur, 17 February 2014 14:11