( ) Gestructureerd en tegelijk

-

Pictogram 5

E•

I oktober/november 2002

w• Dijkstra (1930-2002)

Jan Kraak [email protected]

Gestructureerd en tegelijk correct programmeren

Op 6 augustus jl. overleed in Nuenen op 72-jarige leeftijd prof.

dr. Edsger W. Dijkstra, ongetwijfeld Nederlands belangrijkste informaticus van de 20e eeuw. Hij leed al geruime tijd aan kanker.

Dijkstra's ideeën over gestructu-

fouten, toch tevreden gebruikers

ware-fouten getergde 20% van

reerd programmeren vonden gre-

kan hebben. De meeste gebrui-

de gebruikers, bij gedreven pro-

tig ingang bij sommigen binnen

kers passen namelijk slechts een

grammeurs en al helemaal niet bij

deze universiteit. Zijn methode

klein, goed uitgetest, deel van

informatici voor wie het een

voor

programmeren

alle mogelijkheden toe, waardoor

kwestie van beroepstrots is om zo

wordt op veel plaatsen gedo-

correct

ze niet in contact komen met de

foutloos mogelijk te programme-

ceerd. In dit artikel zal ik, vanuit

fouten in het ongebruikte deel.

ren . Ze zullen wijzen op program-

praktisch perspectief, wat vertel-

Zo zijn de programma's van de

ma's die absoluut correct moeten

len over het werk van Dijkstra en

firma Microsoft zeker niet fout-

zijn, zoals programma's die een

enkele herinneringen ophalen.

loos, maar toch is Bil! Gates er de

kernreactor beveiligen of naviga-

rijkste mens van de wereld mee

tiesystemen van vliegtuigen .

geworden .

Zij weten maar al te goed dat het

De 20-80 regel kent iedereen, zij

De meeste mensen hebben zich

schrijven van foutloze program-

het misschien

neergelegd bij het feit dat pro-

ma's erg lastig is, gezien de enor-

Bijvoorbeeld 20% van alle men-

gramma's nu

eenmaal fouten

me complexiteit ervan: program-

sen drinkt 80% van alle geprodu-

hebben . Net zo aanvaarden ma-

ma 's van enkele miljoenen regels

20-80 egel

niet bij

naam.

ceerde bier. En omgekeerd drinkt

kers en gebruikers van Perzische

code zijn tegenwoordig geen uit-

80% van alle mensen slechts 20%

tapijten een enkele verkeerde

zondering. Maar ze kennen ook

van alle geproduceerde bier. De

knoop. Ik las eens dat er soms met

goede gereedschappen en me-

verhouding kan ook 10-90 zijn,

opzet een foute knoop in een ta-

thoden om de uitdaging van cor-

het gaat om het globale idee. De

pijt wordt aangebracht omdat 'al-

rect programmeren aan te gaan.

regel geldt voor veel menselijke

leen God perfect is'.

consumptiepatronen, iedere win-

Het is vooral Dijkstra geweest die veel heeft bijgedragen tot de

kelier is er mee vertrouwd.

De uitdagin_g van correct

theo rievorming en tot methoden

Toegepast op software verklaart

programmeren

om programma's zo foutloos mo-

de regel waarom een program-

Met dit soort redeneringen moet

gelijk te maken .

ma, ondanks veel programmeer-

je niet aankomen bij de door soft-

•

Pictogram 5

I

oktober/november 2002

•

Semaforen

gramma's van deze nieuwe cate-

de stijl. Terwijl iedereen toen nog

In een artikel over een dag met

gorie

leerde dat je het woord 'ik' zo veel

Nederlandse

computerpioniers

hebben gekregen en hij zal er

mogelijk moest vermijden, vooral

in Delft (zie Pictogram ap rii2000L

waarschijnlijk van hebben ge-

in wetenschappelijke publicaties,

heb ik Dijkstra reeds geïntrodu-

gruwd . Te meer omdat hij aan

gebruikte hij het woord bijna on-

ceerd als de 'de eerste program-

zichzelf de hoogste eisen stelde

beschaamd vaak. Hier sprak ie-

meur' van Nederland. Tijdens zijn

en diep doordrongen was ge-

mand vanuit zijn diepste overtui-

gebruikers onder ogen

studie theoretische natuurkunde

raakt van de moeilijkheid van pro-

ging . Er werd de indruk gewekt

ging hij in 1952 op het Mathe-

grammeren.

dat hier grote wijsheden werden verkondigd, die je niet kon nege-

matisch Centrum in Amsterdam

Op grond van deze ervaringen

werken . Met J. A. Zonneveld

schreef hij in 1969 zijn zeer op-

ren. In EWD-1308 (zie verderop)

bouwde hij de allereerste compi-

merkelijke 'Notes on Structured

staat dat Dijkstra de 'Notes' na

Ier voor de goed ontworpen pro-

Programming'. Niet alleen de in-

een depressie schreef, als een

grammeertaal ALGOL 60. In 1962

houd was opvallend, maar vooral

vorm van therapie.

werd Dijkstra hoogleraar wiskunde aan de TU Eindhoven waar hij

Voorbeeld van een FORTRAN-fragment met ' logische spaghetti'

onder meer het THE Multiprogramming System ontwierp voor de X8 computer. Door toepassing van de seinpaal-met afoorvond hij een elegante oplossing voor de

c c c c

(X) l , 2 ,3 bet e k e n t o spring naa r l a b e l l al s~~ G, sp r ing n a ar l a bel 2 al s ~ = G spring naar l abel 3 al s ~ > G

IF

samenwerking van meerdere processen, zoals gebruikersprogram-

20

ma's en randapparaten, bijvoor-

2l

beeld printers. ledere 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

I F

(ISS)lO , l0 , 20

IF

(I X - IXO )l2, 2 l , l2

IF 2 2 I F 2 3

C A LL PLALC \AM • "NM.A}{. '"I.RC.)

GO TO 73 10 IF (IX2 ) 13,SO,l3

13 IF

(IX2-MT)l9,19,S0

19 IF

(IY2)11,50,ll

l l IF

Fellow van Burroughs en kon hij,

IF

213

gen veel wetenschappers met

meerden er zorgeloos op los, meestal in de ook toen al veel ge-

'

**2+~DY ** 2-"\.)2"\.~ ,

DCP~(AM(~X,~

214

bruikte programmeertaal FOR-

Hij zal waarschijnlijk wel eens pro-

~0 l~ ~ 1. "\. ~ I

+~\~X2 , ~~)~

y

)

2

~~2))1~-~

+ AM.(IX,1.Y2)+AM-\1.~ I 1 IF \DC~-C~)S,2l1 ,21 2~~ IF ~INX~IS-~))2~~,2~S, 217

computers werken. Ze program-

passingen werd COBOL gebruikt.

\CV-

206 IF ( IDX

In Dijkstra's Eindhovense tijd gin-

TRAN. Voor administratieve toe-

GO

~(IX2 IY2))2~~,2~~ , S

12

zijn eigen gang kon gaan.

Programming'

(IY2-NT)12,12,5~

IF(TIND(IX2,IY2,~ÎÎ

verlost van allerlei sores, volledig

' Notes on Structured

( I Y -IYO )l 2, 2 2 ,l2 ( IS -I S O ) l2, 23 , l 2

c

IX==IX+IDX

.......

Pictogram 5 I oktober/november 2002

'lhe GOTO statement

deze

considered harmful'

GOTO het artikel 'Dijkstra consi-

Kroes, werkzaam bij Shell, die net

Op het gevaar af zijn redenerin-

dered harmful'.

SH ELTRAN had gemaakt voor ge-

gen te trivialiseren, zal ik trachten

- Het gebruik van GOTO-state-

structureerd programmeren. Door

anekdote

schrijft

prof.

Een andere spreker was G. A.

een paar ideeën uit dit werk

ments is te vermijden door IF-

een

onder woorden te brengen :

THEN-ELSE, FOR-WHILE etc.

SHELTRAN-commando's in het

- Programmeren is zeer lastig,

preprocessor

werden

de

instructies te gebruiken. Aldus

snel werkende FORTRAN omge-

gestructureerde

zet. Kroes was een grote bewon-

tie. Daarvan moeten we ons be-

programma's. Thans heeft elke

deraar van Dijkstra en had aan zijn

wust zijn, en daarom moeten we

taal structureringsinstructies.

het vergt een grote concentra-

ons bescheiden opstellen en

ontstaan

ons

muur de spreuk 'In den beginne

abstractievermogen

was Dijkstra' hangen, zo vertelde

moeten we gebruik maken bij

hij. SHELTRAN werd in gebruik

beperkte mentale eigenschap-

het top-down ontwerpen van

genomen bij Sterrenkunde, waar

pen en naar eenvoud streven.

programma's.

goed gebruik maken van onze

- Van

er

het nog steeds gebruik wordt in

We moeten denkwijzen gebruiken waarin we goed zijn, zoals

hetvermaarde programma GIPSY

eademische vorming

(Groningen

Image

Processing

logisch redeneren en abstrac-

vereist

System) . Bij Sterrenkunde-mede-

tie.

In het midden van de jaren 70 be-

werker Hans Terlouw hangt een

- Door overvloedig gebruik van

zocht ik met enkele collega 's,

portret van Dijkstra op het prik-

sprongen in een programma is

waaronder Adri den Arend, Jo-

bord . Soms kijkt hij er naar, in de

het dynamische gedrag moeilijk

han Kelders, Doeko Homan en

hoop een goedkeurend knikje

uit de tekst te halen . Dijkstra ge-

Doeke de Vries, die thans werk-

van de meester te krijgen .

bru ikte de term ' logische spa-

zaam is bij Wiskunde, een studie-

ghetti' voor dit soort program-

dag

ma's.

Het prog rammeerhulp-

over gestructureerd

pro-

grammeren met Dijkstra als één

l:l erprogrammei ing KOMPLOT

te

van de sprekers. Voor een muis-

In 1975 was ik intensief bezig met

maken, het GOTO-statement

stille zaal - met vrijwel allemaal

het opnieuw programmeren van

dat prominent in

FORTRAN

mannen - vertelde hij met zachte

het grafiekenprogramma KOM-

aanwezig is, moet daarom in de

stem een poëtisch verhaal over

PLOT dat toentertijd binnen de

ban worden gedaan.

een fladderende vlinder.

hele universiteit en ook daarbui-

Over dit aparte probleem publi-

Wat hij daarmee probeerde te

ten veel werd gebruikt om grafie-

ceerde Dijkstra in 1968 een korte

verduidelijken, is me echter ont-

ken te maken . Daarom vielen de ideeën over gestructureerd pro-

middel

om

een

sprong

notitie met de wat potsierlijke

gaan . Duidelijker was zijn sneer

titel 'The GOTO statement consi-

naar COBOL: hij verwachtte dat

grammeren in me 'als God's

dered harmful'. Velen kennen van

de

verzekeringsmaatschappijen

woord in een ouderling '. KOMPLOT was in ALGOL 60 gepro-

Dijkstraalleen deze titel. Vooral in

problemen zouden krijgen door

Japan heeft de titel bevreemding

hun in COBOL geschreven pro-

grammeerd, maar dat werd niet

gewekt, omdat GOTO daar een

gramma's, zodat ze COBOL zou-

verder ondersteund op de toen

bekende achternaam is: Op een

den afzweren . Hij zei ook dat een

nieuwe COC-computer. Daarom

conferentie stond eens een kleine

programmeur een academische

kreeg ik de unieke kans om het

Japanner op. Hij boog beleefd

opleiding moest hebben. Toen

bestaande

naar Dijkstra en vroeg hem : 'Why

een serieuze programmeur, maar

opnieuw op te zetten.

programma

geheel

am I considered harmful?' . U

geen academicus, hier tegen be-

Als prog rammeertaal leek het

raadt het al : dat was professor

zwaar maakte, nuanceerde hij

toen ook al veel gebruikte FORT-

GOTO. In een andere versie van

deze uitspraak.

RAN een goede keuze, maar daar

Pictogram 5

I

oktober/november 2002

•

kleefden de door Dijkstra ge-

discipline of programming'. Het is

In zijn inaugurale rede 'Specifica-

noemde bezwaren aan. SHELT-

lastig om in een paar zinnen de

tie van Berekening' uit 1995 staat

RAN lag voor de hand, maar daar

kern van dit boek uit te leggen,

dat het doorzettingsvermogen

heb ik toch maar van afgezien

maar ik doe toch een poging .

vereist om correct te leren pro-

omdat dat weer een extra hulp-

Om te kunnen spreken van de

grammeren. Als student moet je

middel, met alle problemen van

correctheid van een programma-

namelijk beginnen met eenvoudi-

dien, introduceerde. Toen heb ik

fragment 'S', moet worden ge-

ge voorbeelden, waarvoor stren-

een eigen manier van gestructu-

specificeerd onder welke precon-

ge correctheidsbewijzen niet no-

reerd programmeren in FORT-

ditie 'Q' de uitvoering van 'S' ein-

dig zijn. Maar je moet je daar toch

RAN bedacht, waarbij ik met de

digt in de gewenste postconditie

doorheen worstelen, om ze later

hand IF-THEN (-ELSE)-construc-

'P' . Hierbij zijn 'P' en 'Q' logische

zelf te kunnen uitvoeren voor in-

ties en andere structureringsin-

uitdrukkingen in termen van de

gewikkelde programma's.

structies vertaalde in GOTO's of

variabelen van 'S' .

Hesselink illustreert hoe lastig de

met

Het correctheidsbewijs van de

uitvoering van een correctheidsbewijs is voor een 'echt' pro-

commentaar

simuleerde .

Ook paste ik top-down design

programmaspecificatie,

toe: ik begon met een klein, goed

teerd als {Q} S {P}, is in het alge-

bleem . Op zichzelfwaren de uitte

werkend, programma en vulde

meen lastig, vooral als 'S' is sa-

voeren bewijsstappen nog niet zo

gaandeweg

mengesteld uit meerdere state-

moeilijk, maar door de enorme

de

ontbrekende

geno-

functionaliteit aan. Zo ontstond,

ments. Daarom voerde Dijkstra

hoeveelheid stappen dreigde hij

in een tijd dat FORTRAN nog

de zwakste beginvoorwaarde in,

de draad kwijt te raken. Hij paste

structureringsin-

de zgn. weakest precondition

toen met succes de stellingbewij-

structies had (versie FORTRAN

wp(S,P), met bijbehorende reken-

zer NQTHM toe, die de adminis-

66), toch een redelijk gestructu-

regels, waardoor correctheidsbe-

tratie voor hem deed.

reerd programma. Tot op de dag

wijzen beter uitvoerbaar worden .

Omdat ze zoveel tijd kosten,

van vandaag heeft KOMPLOT

Een voorbeeld : de functie sqrt

maar ook omdat ze lang niet tri-

om een wortel te trekken in het

viaal zijn, hebben grondige cor-

statement Y:=sqrt(X); werkt al-

rectheidsbewijzen tot nu toe wei-

geen

vrijwel

goede

ongewijzigd

gefunctio-

neerd.

leen voor positieve argumenten,

nig ingang gevonden in de prak-

'A discipline of,___ _ __

de preconditie is X >=0. De post-

tijk. Vaak beperkt men zich tot kleine, kritische programmafrag-

programming'

conditie is X=Y*Y.

Terwijl veel programmeurs nog

Het boek geeft veel voorbeelden

menten. Doeke de Vries, die de

gefascineerd waren door gestruc-

van deze methode. Het is veellas-

ontwikkelingen op programmeer-

tureerd programmeren, was Dijk-

tiger te lezen dan de 'Notes', met

gebied altijd goed bijhoudt, liet

stra en zijn groep in Eindhoven al

name vanwege de afwisseling van

me zien hoe hij, via informele pre-

weer lang bezig met een nieuw

ogenschijnlijke trivialiteiten

en

en de postconditie's van (-func-

aspect: het bewijzen dat een pro-

diepzinnigheden.

gramma(fragment)

ook

inder-

ties, zorg draagt voor hun correctheid. Waarschijnlijk zijn er

daad doet wat je ervan verwacht.

Correct p.-ogrammeren in

meer

Dat is niet simpel, want testen is

Gron ingen

ideeën in de praktijk toe te pas-

niet voldoende. Een veel aange-

In de academische wereld heeft

sen .

haalde uitspraak van Dijkstra is

Dijkstra veel aanhang. In Gronin-

manieren

om

Dijkstra's

dat je met testen alleen kunt aan-

gen doceerde zijn leerling prof.

tonen dat een programma fouten

dr. J . van de Snepscheut correct

Naast zijn wetenschappelijke pu-

heeft, maar niet dat het zonder

programmeren. Thans worden

blicaties, die veel succes hadden

fouten is. Ove r correct program-

deze colleges onder meer gege-

in de academische wereld, werd

meren publiceerde hij in 1976 'A

ven door prof. dr. W. H. Hesselink.

Dijkstra bij een groter publiek ook

Als Socrates

Pictogram 5

-fhe

0

I

oktober/november 2002

I he pv.rpo se of fhi.s ~i.s\-ori cco.\ n ofe i -a -\-o des cri be ~xperiMces whic'h in hi-ndsijh~ Seem 1-o hc.ve ln-

u.e"ced

{;Jhe'"' 1 wro~e

me

" No~es

tt...J1)'149

on

S+n..Acf~Ared ?r-o3.ra,.,.....m inj 1969. 1he note. is bc..sed o,., \,J'lo.~ T r~me....,'ber i 1 """"' SI.A.re. .,.....), -«~ emo') ho..s been 5elec }i ve and h ence do,.., 't clo. i,..,... the. ob. jcdivi ~..) +he r·ofes$ioflo.l hïs+orio.n . 11

;"

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 teil truths that might hurt?' uit 1975: - 'Programming is one of the

of

T wo.s jl'\frodt..<.c~ d ~o Jro:3ro.""' ,..,..,;"j a~ +he 1951 5 ..... "'1'\...,.,er School, jive"' in Cam'bridje bj WilkC'~. Wheeler- O."~ Siil, ond beco..me in 195~ 0'1 0. rc.rt--1-ime ~si-;; - inl}io.~ 2 clo.J~ w~k- -J.h~ projro."..,mer +h~ MoJhemc..l-icc.l Ce"}re in Ar>'ls}-erdc:.""'; the res~ of the wee~ T sl-<--.di~d 1he.ordico.l 'Ph.Jsics

rer

of in

lejde.._.

most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians' .

are

+'he

when a"'d

- 'The easiest machine applications

M.'J o.... ~'J

for

technical/scientific

computations' .

desi;;nin_j

der"-, by now nearly 20 years, is hopelessly inadequate for whatever computer application you

W'o..S .fhe projro.....-.

in Cc.o-.bri~")e; l

projrGir'f\

~er-dc.YV\ .

wos

v...

con-serv-~fi v~ pro:::;rc..""fY'ler . Add +_o

''a'-' ~o co d ers''.

pensive to use'. - 'The use of COBOL cripples the mind; its teaching should, therefore, be regarded as a crimi-

ven in een keurig handschrift. Als

etc. Hij schrijft ook ergens dat de

na! offence' .

grap heeft iemand dat hand-

'considered

- Etc.

schrift eens via TeX door een com-

werk is van Niklaus Wirth .

Dijkstra zal, als ex-gymnasiast, bij

puter laten genereren .

Door hun stijl, voor wie daar van

het doen van dit soort uitspraken

In de, in totaal1317, EWD-notes

houdt, zijn de EWD-notes vaak

waarschijnlijk

staan niet alleen wetenschappe-.

zeer leesbaar. Sinds enige tijd zijn

Griekse filosoof Socrates voor

lijke resultaten, maar ook reisver-

ze via internet te lezen, dankzij de

ogen hebben gestaan die zijn om-

slagen, colleges, allerlei opinies,

inspanningen van de universiteit

geving ook tartte. Maar Dijkstra is

een terechtwijzing van een nieuw

van Texas in Austin, waaraan

niet, zoals Socrates ongeveer

lid van zijn dinsdagmiddag-club,

Dijkstra van 1984 tot 1999 was

2400 jaar eerder, veroordeeld tot

een briefje aan een afstudeerder,

verbonden .

van

de

harmful'-titel

het drinken van de gifbeker.

EWD-notes Dijkstra was zeer productief. Veel van zijn ideeën heeft hij privé ge-

Links:

publiceerd in zijn serie EWDnotes die als een soort ketting-

www. rug. n 1/h pc/peo pI e/p ion i ers

brief onder een grote schare be-

www. es. utexas.ed u/u sers/EWD

wonderaars werden verspreid . Een deel is met vulpen geschre-

1-he inp1.1t I

Hds +hc.t +he RtJ?h~C s Jnstn. . . .::~ion tH_._(fe...- 11J1~h c.. cv.yc.ci ~j of one fro.ck of fhe dr ...... ........_, destr.,~e~ +"he s1or~ ho-mojef'le.i~J, o""d doi.A. will understG\nd tho..l- T did no~ em bc..rk o'"' advef'l ~LAres like

clumsy, toa risky, and toa ex-

rol

in 8ms -

the nel
have in mind today: it is nowtoo

de

orjc.l"\.i·z,"'-tiol"'

foliowed .~ dose) >"\.~c.tion, '"'P'""'J, ov.~pt....~

libr:.Cj o~c.ni 5o.fion ~r +he R':!3_~A

dec..r'

- 'FORTRAN -"the infantile disor-

vnodel

Ë'DSAC

het