|
Edsger W. Dijkstra |
|
Gestructureerd
en correct programmeren, volgens E. W. Dijkstra (1930-2002) concept voor een artikel in
Pictogram najaar 2002, Jan Kraak, Augustus 2002 Op 6 augustus j. l. overleed in Nuenen op 72-jarige leeftijd dr. Edsger W, Dijkstra, ongetwijfeld Nederlands belangrijkste informaticus van de 20-e eeuw. Hij leed al geruime tijd aan kanker. Vooral in de jaren 70 en 80, toen er nog veel eigen programmatuur werd ontwikkeld, vonden Dijkstra's ideeën over gestructureerd programmeren gretig ingang binnen deze universiteit. Zijn methode voor correct programmeren wordt veel gedoceerd. In dit artikel zal ik, vanuit praktisch perspectief, wat vertellen over het werk van Dijkstra en enkele herinneringen ophalen. Enkele opmerkingen vooraf De 20-80 regel kent iedereen, zij het misschien niet bij naam. Bijvoorbeeld 20 % van alle mensen drinkt 80 % van alle geproduceerde bier. En omgekeerd drinkt 80 % van alle mensen slechts 20% van alle geproduceerde bier. De verhouding kan ook 10-90 zijn, het gaat om het globale idee. De regel geldt voor veel menselijke consumptiepatronen, iedere middenstander is er mee vertrouwd. Toegepast op software, verklaart de regel waarom een programma, ondanks veel programmeerfouten, toch tevreden gebruikers kan hebben. De meeste gebruikers passen namelijk slechts een klein, goed uitgetest, deel van alle mogelijkheden toe, waardoor ze niet in contact komen met de fouten in het ongebruikte deel. Zo zijn de programma's van de firma Microsoft zeker niet foutloos, maar toch is Bill Gates er de rijkste man van de wereld mee geworden. De meeste mensen hebben zich neergelegd bij het feit dat programma's nu eenmaal fouten hebben en dat daar best mee te leven valt. Net zo aanvaarden makers en gebruikers van Perzische tapijten een enkele verkeerde knoop. Ik las eens dat er soms met opzet een foute knoop in een tapijt wordt aangebracht omdat "alleen God perfect is". De uitdaging van correct programmeren Met dit soort redeneringen moet je niet aankomen bij de door software-fouten getergde 20 % van de gebruikers, bij gedreven programmeurs en al helemaal niet bij informatici voor wie het een kwestie van beroepstrots is om zo foutloos mogelijk te programmeren. Zij weten maar al te goed dat het schrijven van foutloze programma's erg lastig is, gezien de enorme complexiteit ervan: programma's van enkele miljoenen regels code zijn tegenwoordig geen uitzondering. Maar ze kennen ook goede gereedschappen en methoden om de uitdaging van correct programmeren aan te gaan. Het is vooral Dijkstra geweest die veel heeft bijgedragen tot de theorievorming en tot methoden om programma's zo foutloos mogelijk te maken. Semaforen In een eerder verhaal over een dag met Nederlandse computerpioniers in Delft inbegin 2000 , heb ik Dijkstra reeds geïntroduceerd als de "de eerste programmeur" van Nederland. Tijdens zijn studie theoretische natuurkunde ging hij in 1952 op het Mathematisch centrum in Amsterdam werken, waar hij de software ontwierp voor enkele van de eerste computers in Nederland. Met J. A. Zonneveld bouwde hij de allereerste compiler voor de goed ontworpen programmeertaal ALGOL 60. In 1962 werd Dijkstra hoogleraar wiskunde aan de TU Eindhoven waar hij onder meer het THE Multiprogramming System ontwierp voor de X8 computer. Door toepassing van de seinpaal-metafoor vond hij een elegante oplossing voor de samenwerking van meerdere processen, zoals gebruikersprogramma's en randapparaten, bijvoorbeeld printers. Iedere informaticastudent kent tegenwoordig semaforen. Van 1973 tot 1984 was hij nog maar één dag in de week verbonden aan de TU. De rest van de week was hij Research Fellow van Burroughs en kon hij, verlost van allerlei sores, volledig zijn eigen gang kon gaan. Notes on Structured Programming In Dijkstra's Eindhovense tijd gingen veel wetenschappers met computers werken. Ze programmeerden er zorgeloos op los, meestal in de ook toen al veel gebruikte programmeertaal FORTRAN. Voor administratieve toepassingen werd COBOL gebruikt. Hij zal waarschijnlijk wel eens programma's van deze nieuwe categorie gebruikers onder ogen hebben gekregen en hij zal er waarschijnlijk van hebben gegruweld. Te meer omdat hij aan zichzelf de hoogste eisen stelde en diep doordrongen was geraakt van de moeilijkheidsgraad van het maken van correcte programma's. Op grond deze ervaringen schreef hij
in 1969 zijn zeer opmerkelijke "Notes on Structured Programming".
Niet alleen de inhoud was opvallend, maar vooral de stijl. Terwijl iedereen
toen nog leerde dat je het woord "ik" zo veel mogelijk moest
vermijden, vooral in wetenschappelijke publicaties, gebruikte hij het woord
bijna onbeschaamd vaak. Het was alsof hier iemand vanuit zijn diepste
overtuiging sprak. Er werd de indruk gewekt dat hier grote wijsheden werden
verkondigd, die je niet kon negeren. In EWD-1308 (zie verderop) vertelt hij,
dat hij het stuk na een depressie schreef als een vorm van therapie. C Voorbeeld van een FORTRAN-fragment C met 'logische spaghetti' C een getal slaat op een label C IF (X) 1,2,3 betekent: C spring naar label 1 als x < 0, C spring naar label 2 als x = 0 C spring naar label 3 als x > 0 IF
(ISS)10,10,20 20 IF
(IX-IXO)12,21,12 21 IF
(IY-IYO)12,22,12 22 IF
(IS-ISO)12,23,12 23 CALL
PLALC(AM,NMAX,IRC)GO TO 73 10 IF
(IX2)13,50,13 13 IF
(IX2-MT)19,19,50 19 IF
(IY2)11,50,11 11 IF
(IY2-NT)12,12,50 12
IF(TIND(IX2,IY2,1)) GO TO 73 IF
(CV-AM(IX2,IY2))206,206,5 206 IF
(IDX**2+IDY**2-1)213,6,213 213
DCP=(AM(IX,IY)+AM(IX2,IY)+ +
AM(IX,IY2)+AM(IX2,IY2))/4.0 IF
(DCP-CV)5,217,217 217 IF
(INX(IS-1))214,215,214 214 IX=IX+IDX C ....... Fragment uit
FORTRAN 66 programma's met "logische spaghetti", The GOTO statement considered harmful Op het gevaar af zijn redeneringen te trivialiseren, zal ik trachten een paar ideeën uit dit werk onder woorden te brengen:
Over dit aparte probleem publiceerde Dijkstra in 1968 een korte notitie met de wat eigenaardige titel " The GOTO statement considered harmful". Velen kennen van Dijkstra alleen deze titel. Vooral in Japan heeft de titel bevreemding gewekt, omdat GOTO daar een bekende achternaam is. Een Japanner publiceerde een stuk getiteld "Dijkstra considered harmful".
Op zijn minst wiskundig ingenieur In het midden van de jaren 70 bezocht ik met enkele collega's, een studiedag over gestructureerd programmeren met Dijkstra als één van de sprekers. Voor een muisstille zaal - met vrijwel allemaal mannen, de meeste vrouwen hadden ook toen al belangrijker dingen te doen - vertelde hij met zachte stem een poëtisch verhaal over een fladderende vlinder. Wat hij daarmee probeerde te verduidelijken, is me echter ontgaan. Duidelijker was zijn sneer naar COBOL: hij verwachtte dat de verzekeringsmaatschappijen problemen zouden krijgen door hun in COBOL geschreven programma's, zodat ze COBOL zouden afzweren. Hij zei ook dat een programmeur op zijn minst wiskundig ingenieur moest zijn. Toen een serieuze programmeur, maar geen wiskundig ingenieur, hier tegen bezwaar maakte, nuanceerde hij deze uitspraak. Een andere spreker was G. A. Kroes, werkzaam bij Shell, die net SHELTRAN) had gemaakt voor gestructureerd programmeren. Door een postprocessor werden de SHELTRAN-commando's in het snel werkende FORTRAN omgezet. Kroes was een grote bewonderaar van Dijkstra en had aan zijn muur de spreuk "In den beginne was Dijkstra" hangen, zo vertelde hij. SHELTRAN werd in gebruik genomen bij Sterrenkunde, waar er nog steeds gebruik van wordt gemaakt. Bij Sterrenkunde-medewerker Hans Terlouw hangt een portret van Dijkstra op het prikbord. Soms kijkt hij er naar, in de hoop een goedkeurend knikje van de meester te krijgen. Herprogrammering KOMPLOT In 1975 was ik intensief bezig met het opnieuw programmeren van het grafiekenprogramma KOMPLOT dat toentertijd binnen de hele universiteit en ook daarbuiten veel werd gebruikt om grafieken te maken. Daarom vielen de ideeën over gestructureerd programmeren in me "als God's woord in een ouderling". Vanaf 1970 had ik KOMPLOT in de programmeertaal ALGOL 60 ontwikkeld, maar het bestaan daarvan kwam op de tocht te staan vanwege de overgang op CDC-computers. Daarom kreeg ik de kans om het bestaande programma geheel opnieuw op te zetten. Als programmeertaal leek het veel gebruikte FORTRAN een goede keuze, maar daar kleefden de door Dijkstra genoemde bezwaren aan. SHELTRAN lag voor de hand, maar daar heb ik toch maar van afgezien omdat dat weer een extra hulpmiddel, met alle problemen van dien, introduceerde. Toen heb ik een eigen manier van gestructureerd programmeren in FORTRAN bedacht, waarbij ik met de hand IF-THEN (-ELSE) constructies en andere structureringsinstructies vertaalde in GOTO's of met commentaar simuleerde. Ook paste ik top-down design toe. Ik begon met een klein, goed werkend, programma en vulde gaandeweg de ontbrekende functionaliteit aan. Zo ontstond, in een tijd dat FORTRAN nog geen goede structureringsinstructies had, toch een redelijk gestructureerd programma. Tot op de dag van vandaag heeft KOMPLOT vrijwel ongewijzigd gefunctioneerd. A discipline of programming Terwijl veel programmeurs nog gefascineerd waren door gestructureerd programmeren, was Dijkstra en zijn researchgroep in Eindhoven al weer lang bezig met een nieuw aspect: het bewijzen dat een programma(fragment) ook inderdaad doet wat je ervan verwacht. Dat is niet simpel, want testen is niet voldoende. Een veel aangehaalde uitspraak van Dijkstra is dat je met testen alleen kunt aantonen dat een programma fouten heeft, maar niet dat het zonder fouten is. Over correct programmeren publiceerde hij in 1976 "A discipline of programming". Het is gewaagd om in een paar zinnen de kern van dit boek uit te leggen, maar ik doe toch een poging. Om de correctheid van een programmafragment te bewijzen, moet zowel het fragment S als de specificatie van het doel (de zgn. postcondition P) de vorm van een logische uitdrukking hebben. De kunst is nu om uit beide logische uitdrukkingen langs formele weg de zgn. weakest precondition WP(S,P) af te leiden: een logische uitdrukking voor de beginvoorwaarden. Als W(S,P) geldt voorafgaande aan de uitvoering van S, dan geldt na uitvoering van S de postcondition P. Dus S is correct uitgevoerd. Een voorbeeld: de functie sqrt om een wortel te trekken in het statement Y:=sqrt(X); werkt alleen voor positieve argumenten, de precondition is X >=0. De postcondition is X=Y*Y. Het boek geeft veel voorbeelden van deze methode. Het is veel lastiger te lezen dan de "Notes", met name vanwege de afwisseling van ogenschijnlijke trivialiteiten en diepzinnigheden. Correct programmeren in Groningen In de academische wereld heeft Dijkstra veel aanhang. In Groningen doceerde onder meer zijn leerling prof. Dr. J. van de Snepscheut correct programmeren. Thans worden de colleges gegeven door prof. dr. W. H. Hesselink. In zijn inaugurale rede Specificatie van Berekening uit 1995 staat dat het doorzettingsvermogen vereist om correct te leren programmeren. Als student moet je namelijk beginnen met eenvoudige voorbeelden, waarvoor strenge correctheidsbewijzen niet nodig zijn. Maar je moet je daar toch door heen worstelen, om ze later zelf te kunnen uitvoeren voor ingewikkelde programma's. Hesselink illustreert hoe lastig de uitvoering van een correctheidsbewijs is voor een "echt" probleem. Op zichzelf waren de uit te voeren bewijsstappen nog niet zo moeilijk, maar door de enorme hoeveelheid stappen dreigde hij de draad kwijt te raken. Hij paste toen met succes de automatische stellingbewijzer NQTHM toe, die hem allerlei administratieve problemen uit handen nam. Omdat ze zoveel tijd kosten, maar ook omdat ze lang niet triviaal zijn, hebben grondige correctheidsbewijzen tot nu toe weinig ingang gevonden in de praktijk. Vaak kan men zich beperken tot kritische programmafragmenten, die bijvoorbeeld op meerdere computers tegelijk (parallel) draaien. Doeke de Vries, die de ontwikkelingen op programmeergebied altijd goed bij houdt, liet me zien hoe hij, via informele pre- en de postconditie's van C-functies, zorg draagt voor hun correctheid. Waarschijnlijk zijn er meer manieren om Dijkstra's ideeën in de praktijk toe te passen. Als Socrates Naast zijn wetenschappelijke publicaties, die veel succes hadden in de academische wereld, werd Dijkstra bij een groter publiek ook bekend om de prikkelende uitspraken die hij van tijd tot tijd deed over de praktijk van het programmeren en ander computergebruik. Voorbeelden daarvan staan bijvoorbeeld in "How do we tell truths that might hurt?" uit 1975: - Programming is one of the most difficult
branches of applied mathematics; the poorer mathematicians had better remain
pure mathematicians.
Recente uitspraken van Dijkstra staan in een artikel in Trouw van 18 oktober 2000. Dijkstra zal, als ex-gymnasiast, bij het doen van dit soort uitspraken waarschijnlijk de rol van de Griekse filosoof Socrates voor ogen hebben gestaan die zijn omgeving ook tartte. Maar Dijkstra is niet, zoals Socrates ongeveer 2400 jaar eerder, veroordeeld tot het drinken van de gifbeker. Ondanks alle weerstand tegen FORTRAN, is dat nog steeds de meest gebruikte programmeertaal voor high performance computing. EWD-notes Dijkstra was zeer productief. Veel van zijn ideeën heeft hij privé gepubliceerd in zijn serie EWD-notes die als een soort kettingbrief onder een grote schare bewonderaars werden verspreid. Een groot deel is met vulpen geschreven in een keurig handschrift. Er bestaat zelfs een TeX-font om een computertekst er uit te laten zien alsof Dijkstra die zelf had geschreven. In de, in totaal 1317, EWD-notes staan niet alleen wetenschappelijke resultaten, maar ook reisverslagen, colleges, allerlei opinies, een terechtwijzing van een nieuw lid van zijn dinsdagmiddag-club, een briefje aan een afstudeerder, etc. Door hun stijl zijn ze vaak zeer leesbaar. Sinds enige tijd zijn ze via Internet te lezen, dankzij de inspanningen van de universiteit van Texas in Austin, waaraan Dijkstra van 1984 tot 1999 was verbonden. |
