PROGRAMMEERTALEN EN -PARADIGMA S. Universiteit Utrecht

PROGRAMMEERTALEN EN -PARADIGMA’S Jeroen Fokker Informatica-instituut Universiteit Utrecht

Willem van der Vegt Chr. Hogeschool Windesheim Zwolle

1

2

INHOUDSOPGAVEInleiding Geschiedenis van programmeertalen Programmeer-paradigma’s IMPERATIEF PROGRAMMEREN Variabelen en toekenning Imperatief programmeren Waarden Geheugen Opdrachten Imperatieve computertaal Notatie voor variabelen Notatie voor waarden Notatie voor toekenning Berekeningen Type van variabelen Programma Procedures Programmastructuur Subroutines vs. procedures : voorbeelden Subroutines vs. procedures Declaraties van variabelen Lokale variabelen Parameters Parameters: variaties Programmastructuur Keuze en herhaling Keuze (1) Keuze (2) Herhaling (1) Herhaling (2) Structured programming Herhaling (3) Functies Procedures vs. functies Procedures vs. functies: voorbeelden Aanroepen van functies Recursieve functies Datatypes Arrays Types

Records/structures Abstracte datatypes Voorbeeld ADT Object-oriëntatie Voorbeeld OO-programmeren Subklassen Overerving (inheritance) Pointers Dynamische datastructuren Gebruik van pointers (Pascal) Gebruik van pointers (C++) Gebruik van pointers (Java) Toepassing van pointers DECLARATIEF PROGRAMMEREN Programmeer-paradigma’s Declaratief programmeren Functioneel programmeren Functiedefinitie Keuze Herhaling Lijsten Polymorfie Hogere-ordefuncties Algoritmen: insertion sort Algoritmen: quicksort Logisch programmeren Feiten en afleidingsregels Uitvoeren van een programma Voorbeeld APPENDIX Reflectievragen Praktijkopdrachten

3

Deze (korte) cursus biedt een overzicht van een aantal concepten van hedendaagse programmeertalen. Om enige orde te scheppen in de vele talen worden deze ingedeeld in een zestal zogenoemde paradigma’s. Deze cursus is geen programmeer-cursus: daarvoor is er de module “Visueel programmeren met Java”, waarin het gebruik van de taal Java in detail wordt behandeld. In de voorliggende cursus worden de voorbeelden deels geput uit Java, maar ook uit C, C++, Pascal, Basic, machinetaal, Haskell en Prolog. In zo’n kort bestek als deze kunnen de genoemde talen natuurlijk niet volledig behandeld worden, maar dat is ook helemaal niet nodig. Aan de hand van de beschreven concepten wordt het hopelijk veel eenvoudiger allerlei eigenschappen van deze talen te kunnen plaatsen (ten opzichte van Java) en op hun waarde te kunnen schatten. Dat maakt het ook mogelijk om tegenover leerlingen meer beslagen ten ijs te komen. Het is bovendien geod mogelijk dat deze cursus ook het begrip van de taal Java zelf verhoogt. Dit boekje is opgebouwd rond een vijftigtal overhead-transparanten, die tegelijk een samenvatting van de inhoud vormen. Acherin het boekje is bij vrijwel elk onderwerp een “reflectievraag” opgenomen; het (proberen te) beantwoorden daarvan kan leiden tot beter begrip van de stof, en kan bovendien dienen als ideeënbron voor discussies in de klas-situatie. Daarna volgt een 12-tal praktijkopdrachten. Ook deze dienen in eerste instantie ter eigen lering, maar kunnen voor een deel ook worden uitgewerkt en aangepast tot projectjes voor leerlingen. Bij het boekje hoort een CD met vrij kopieerbare versies van compilers voor diverse programmeertalen. Ze zijn niet allemaal van productiekwaliteit (maar sommige wel!), maar ze zijn in ieder geval geschikt voor enig experimenteren. Op de CD staan bovendien de Powerpoint-file van de transparanten, en de Word-file van dit boekje. Ook dit materiaal mag vrij gebruikt, gereproduceerd en aangepast worden voor gebruik in het Nederlandse voortgezet onderwijs. Wij wensen u veel aha-ervaringen toe bij het bestuderen van deze cursus! Jeroen Fokker Informatica-instituut Universiteit Utrecht [email protected]

4

Willem van der Vegt Chr. Hogeschool Windesheim Zwolle [email protected]

Programmeertalen werden al in de 1930’s, bij wijze van gedachten-experiment, ontworpen. Maar de eerste echte talen onstonden natuurlijk pas tegelijk met de computer, rond 1946. Aanvankelijk had elk type computer zijn eigen taal: de machinetaal voor die specifieke computer. Omdat het programmeren met behulp van code-getallen voor instructies erg lastig is, werden er al snel assembler-talen gebruikt, waarin de instructies met afkortingen werden weergegeven. Assembler-talen zijn echter nog machine- of processor-specifiek. De eerste machine-onafhankelijke taal was Fortran, speciaal voor numerieke toepassingen met veel formules (de naam is dan ook een afkorting van “Formula Translator”). Dit was het begin van een Babylonische toren met bijbehorende spraakverwarring. Het hangt er een beetje van af wat je allemaal meetelt, en of je “dialecten” apart telt, maar een recente lijst van alle gepubliceerde programmeertalen bevat zo’n 3000 ingangen. Veel talen lijken echter op elkaar: concepten uit de ene taal zie je overgenomen worden in andere talen. In deze cursus bekijken we vooral de ontwikkeling van een aantal concepten die in moderne programmeertalen voorkomen, en als vanzelf krijgen we zo een overzicht van de belangrijkste historische ontwikkelingen. Er is een duidelijke lijn van Fortran naar een recente taal zoals Java. Sommige van de tussenliggende stappen (Algol en Simula) kunnen als “dode” taal worden beschouwd, maar zijn historisch wel interessant. Sommige talen (Fortran, C) worden nog steeds gebruikt, al of niet uit conservatisme.

Andere talen (Basic, Pascal) die sinds hun ontstaan zelf een ontwikkeling hebben doorgemaakt in steeds nieuwe dialecten. Recente versies van Pascal lijken meer op C++ dan op het oorspronkelijke Pascal. Waar we het in deze cursus over Basic en Pascal hebben slaat dat vooral op de concepten die in de oorspronkelijke versies aanwezig waren. De nieuwe concepten in recente dialecten zijn ontleend aan andere talen, en komen zo vanzelf ter sprake. De taal Algol was de eerste taal die expliciet bedoeld was voor algemeen gebruik. De naam staat voor “Algorithmic Language”, een taal waarin algoritmes (berekeningsvoorschriften) geformuleerd kon worden. Er zijn twee versies: Algol60 en Algol68. De laatste is als een dinosaurus aan zijn eigen complexiteit ten onder gegaan; de les die de wereld daarvan heeft geleerd is dat taalontwerp vooral op simpelheid gericht moest worden. De taal Basic (“Beginners All-purpose Symbolic Instruction Code”) was bedoeld als eenvoudige taal voor beginners, en is vooral populair geworden door gebruik op huiscomputers vanaf 1978. Pascal (geen afkorting, maar een eerbetoon aan Blaise Pascal) was ook bedoeld als speciale onderwijstaal, waarin anders dan in Basic gestructureerd programmeren voorop stond. Als je mensen dingen leert gaan ze het gebruiken ook, en daardoor is Pascal de vervanger van Algol geworden als taal voor algemeen gebruik. Voor het schrijven van operating systems wass Pascal echter echt niet geschikt. Voor de ontwikkeling van Unix werd daarom de taal C (opvolger van A en B) bedacht. Het succes van Unix maakte dat C ook in het algemeen gebruikt ging worden voor andere toepassingen waarvoor Pascal net tekort schoot. De komst van window-systemen in de jaren 80 maakte een speciale stijl van programmeren noodzakelijk, en daarmee nieuwe programmeertalen zoals C++ (“iets meer dan C”). Met de komst van Internet werden vooral veiligheid en machine-onafhankelijkheid extra belangrijk, kenmerken die voorop stonden in Java (geen afkorting, maar genoemd naar de coffeshop van de ontwerpers). Naast de “main stream” van programmeertalen voor algemeen gebruik zijn er ook programmeertalen voor een specifiek doel. Een belangrijk toepassingsgebied is bijvoorbeeld het beheer van databases. Daartoe zijn aparte programmeertalen ontwikkeld, te beginnen bij Cobol (“COmmon Business Oriented Language”) in de zestiger jaren. SQL (“Structured Query Language”) is een recenter voorbeeld in deze categorie. Verder zijn er nog programmeertalen waarin geëxperimenteerd wordt met bepaalde onorthodoxe concepten. Bouwend op een traditie die met Lisp begonnen is, is ook hier sprake van een evolutie, compleet met invloedrijke maar inmiddels dode talen (bijvoorbeeld Miranda), en nieuwe ontwikkelingen (bijvoorbeeld Haskell) die echter vast nog niet het eindpunt zijn.

Behalve historisch of naar toepassingsgebied kun je programmeertalen ook ordenen naar de concepten die er een rol in spelen. Groepjes programmeertalen met gemeenschappelijke concepten staan bekend als een programmeer-paradigma. Het woord “paradigma” is afkomstig uit de wetenschapsfilosofie, en staat voor het kader van theorievorming van een bepaalde wetenschap in een bepaalde periode. In het schema hierboven zijn een aantal paradigma’s weergegeven, met enkele talen in elk paradigma (de donker-gekleurde talen zijn in onbruik geraakt, maar wel van grote invloed geweest op de ontwikkeling). Het meest voorkomende paradigma is het imperatieve. Je kunt spreken van “imperative programmeertalen” en van “imperatief programmeren”. Je ziet dit paradigma wel eens gecontrasteerd met het “procedurele” en het “objectgeoriënteerde” paradigma. Dat is eigenlijk minder juist, want in die laatste twee zijn de imperatieve principes niet overboord gegooid, maar verfijnd. In het schema is dit aangegeven; ook zie je dat het object-georiënteerde paradigma weer een verfijning is van het procedurele. Wel heel anders dan het imperatieve paradigma is het declaratieve. Daarvan zijn er twee belangrijke deel-paradigma’s: het functionele en het logische. In deze cursus bespreken we achtereenvolgens het imperatieve paradigma en de twee verfijningen daarvan, en aan het eind ook kort de twee declaratieve paradigma’s.

5

Het imperatieve paradigma sluit direct aan bij het eenvoudigste model van de architectuur van de computer. Het is waarschijnlijk daarom, dat het het oudste en meest gebruikte programmeer-paradigma is. In dit model bestaat een computer uit een processor die opdrachten kan uitvoeren. Doel daarvan is om de waarden die in het geheugen zijn opgeslagen te veranderen. Natuurlijk bestaan concrete computersystemen uit meer componenten dan alleen geheugen en processor: diskdrives, monitor, muis, enzovoorts. Maar als je de zaak maar abstract genoeg bekijkt, is al die randapparatuur in zekere zin als geheugen te beschouwen. Soms is dat ‘write only’ geheugen (monitor), soms is het ‘read only’ geheugen (muis); soms is het langzaam (disk), soms behoorlijk snel (RAM), soms erg snel (registers op de processor-chip). Sommige randapparatuur ziet er voor de processor daadwerkelijk uit als geheugen (memory mapped I/O), maar ook als dat niet het geval is kunnen we, om het model niet te ingewikkeld te maken, doen alsof. Het woord “imperatief” betekent letterlijk “gebiedend” of “bevelend”. Het refereert aan het feit dat in dit paradigma de uit te voeren opdrachten aan de processor worden voorgeschreven.

6

Het geheugen bestaat in principe uit losse bits, de spreekwoordelijke “enen en nullen”. In de meeste gevallen worden deze bits echter gemanipuleerd in groepjes van bijvoorbeeld 8 bits (een byte) of een veelvoud daarvan. In 8 bits kun je 28=256 verschillende waarden opslaan. Wat de interpretatie van die waarden is, hangt af van de manier waarop die gebruikt worden. Je kunt de 256 waarden gebruiken om een getal tussen 0 en 255 aan te duiden, maar ook om bijvoorbeeld een letterteken de coderen (met 256 waarden kun je alle hoofdletters, kleine letters, cijfers en leestekens een vaste code geven, en dan houd je zelfs nog over voor speciale symbolen en accenten). Als je behalve positieve getallen ook negatieve getallen wilt kunnen opslaan dan is dat ook mogelijk. Bij 256 verschillende codes kun je dan bijvoorbeeld de getallen van 0 tot en met 127, en van –128 tot en met –1 representeren. Voor het opslaan van een waarheidswaarde (ja/nee) is in principe 1 bit genoeg, maar met 8 bits kan het natuurlijk ook. Enige voorwaarde is dat er een afspraak is hoe de bitpatronen geïnterpreteerd moeten worden. Daarvoor zijn natuurlijk allerlei standaarden in gebruik: in het voorbeeld hierboven is voor symbolen de ISO-codering gebruikt, en voor negatieve getallen de zgn. 2’s-complement notatie. Aan het pure bitpatroon (bijvoorbeeld 01000001) kun je niet zien welke interpretatie bedoeld is: uit de context moet duidelijk zijn welk type waarden opgeslagen is, en bovendien volgens welke coderingswijze dat is gebeurd.

Een groepje bits in het geheugen waarin een waarde kan worden opgeslagen heet een variabele: de waarde kan immers in de loop van de tijd variëren. Je kunt de opgeslagen waarde veranderen, en later nog eens bekijken welke waarde er is opgeslagen. Je moet daarbij kunnen aangeven over welke variabele je het hebt; daarom hebben variabelen een naam. Een variabele heeft dus een (vaststaande) naam, en een (in de tijd variërende) waarde. De naam van een variabele wordt over het algemeen niet in het geheugen opgeslagen; de waarde natuurlijk wel. Men zegt wel dat de naam een stukje van het geheugen adresseert (aanduidt). In de wiskunde worden ook van oudsher variabelen gebruikt. Er is een subtiel verschil met de variabelen uit de informatica. Wiskunde-variabelen duiden immers een vaste, maar mogelijk nog onbekende waarde aan (“de oplossing van 2x=10”), of bestrijken juist een heel gebied (“voor alle x tussen 0 en 10 geldt…”). Informatica-variabelen daarentegen hebben altijd een bepaalde waarde, die echter wel in de tijd kan veranderen.

Het uitvoeren van een opdracht moet blijvende sporen achterlaten – anders had je het uitvoeren de opdracht net zo goed achterwege kunnen laten. De enige manier om sporen achter te laten is om het geheugen te veranderen (of door iets op het beeldscherm of printer te zetten, maar printer en beeldscherm waren in wezen een bijzonder soort geheugen, dus dat valt ook onder de noemer “geheugen veranderen”). Opdrachten zijn dus voorschriften om het geheugen te veranderen. Een programma is in het imperatieve paradigma in feite slechts een lange reeks opdrachten. De opdrachten worden één voor één uitgevoerd door de processor. Die is daartoe voorzien van een program counter (ook wel instruction pointer genoemd, omdat het ding niet zozeer programma’s telt, als wel de huidige instructie aanwijst). Het meest gebruikelijke Engelse woord voor “opdracht” is statement. Dat is taalkundig eigenlijk niet juist, want de letterlijke betekenis van statement is niet zozeer “opdracht” als wel “uitspraak, verklaring”. Het woord instruction wordt alleen gebruikt op machinetaal-nivo. Het woord command is nooit echt doorgebroken. Gelukkig maar, want behalve dat het erg militair klinkt ligt ook begripsverwarring met comment (=toelichting) op de loer.

7

Een imperatief programma is een reeks opdrachten. Een imperatieve programmeertaal is dus een notatiewijze om deze opdrachten te formuleren. Omdat de opdrachten bedoeld zijn om het geheugen te veranderen, moet er in ieder geval een notatie zijn voor de opdracht die één variabele in het geheugen verandert. In die opdracht zal op een of andere manier de te veranderen variabele moeten worden aangeduid, en bovendien de nieuwe waarde die de variabele door het uitvoeren van de opdracht moet gaan krijgen. Er zullen in de programmeertaal dus notaties zijn om variabelen en waarden aan te duiden.

8

Een hele simpele manier om de variabelen in het geheugen aan te duiden is om ze gewoon te nummeren: byte nummer 1, byte nummer 2, en zo verder tot byte nummer 32 miljoen (of hoeveel geheugen er ook maar aanwezig is). In de vroege assembler-talen was dit inderdaad de manier om variabelen aan te duiden. Uitzondering vormden een klein aantal in de processor-chip ingebouwde variabelen (registers); die hadden eerst namen als A en B, later A t/m E, en toen het er steeds meer werden namen als A0 t/m A16. Echt handig zijn dat soort genummerde variabelen niet. Vergissing tussen variabele 15478 en variabele 15487 ligt immers voor de hand, en bovendien is de betekenis van dit soort “namen” niet duidelijk. In de wiskunde was het al veel langer gebruikelijk om variabelen met een letter aan te duiden. Vaste conventies dienden als geheugensteuntje: x is (bijna) altijd een onbekende, n is een aantal, α is een hoek, en ε een heel klein getal. Omdat in programma’s vaak erg veel variabelen nodig zijn, is in computertalen het gebruik ontstaan om meer-letterige variabelen te gebruiken, waarin vaak ook cijfers en (afhankelijk van de taal) symbolen als dollar, onderstreping en accent gebruikt mogen worden. Van lieverlee onstond de gewoonte om variabelen een toepasselijke naam te geven, dus bijvoorbeeld niet x9a of tb, maar totaalbedrag. Je ziet dan ook het aantal letters dat in een variabele gebruikt mag worden steeds toenemen.

Het aanduiden van waarden door middel van bitpatronen (zoals 01000001) zou erg omslachtig zijn. Daarom bieden alle programmeertalen notaties om waarden in de meest voorkomende interpretaties te noteren. Duidelijkste voorbeeld hiervan zijn getallen, die in de gewone decimale notatie in plaats van de binaire mogen worden genoteerd, al dan niet voorzien van min-teken. Getallen met “cijfers achter de komma” worden naar angelsaksisch gebruik meestal met een “decimale punt” genoteerd, en voor hele grote getalen kan vaak de E-notatie worden gebruikt: 3.0E8 betekent 3.0 maal 108, oftewel 300000000. Enige uitzondering vormen assembler-talen: omdat getallen hier al gebruikt worden om variabelen aan te duiden, moeten “echte” getallen op een speciale manier worden genoteerd, vaak met het teken “#”. Lettertekens en andere symbolen kunnen in veel talen direct gebruikt worden, zodat het onnodig is om coderings-tabellen uit het hoofd te kennen. Om verwarring met variabelen te voorkomen moeten symbolen altijd tussen aanhalingstekens worden gezet – ze moeten immers letterlijk worden genomen. De taal Pascal gebruikt enkele aanhalingstekens voor zowel losse letters als meerletterige teksten; in C en Java kan onderscheid worden gemaakt tussen de losse letter ‘a’ en de 1-letterige tekst “a”. Sommige talen kennen een aanduiding voor waarheidswaarden (False en True); die namen zijn dan uigesloten voor gebruik als variabele. Andere talen gebruiken 0 en 1 voor waarheidswaarden, op het gevaar af van verwarring met getallen.

In elke imperatieve taal is er een notatie beschikbaar om een variabele een nieuwe waarde te geven. Dit wordt een “toekenningsopdracht” (assignment statement) genoemd, omdat er een nieuwe waarde aan de variabele wordt toegekend. Onderdeel van de toekenningsopdracht is in ieder geval een aanduiding van de variabele die moet veranderen, alsmede diens nieuwe waarde. In sommige talen noem je eerst de waarde en dan de variabele, in andere talen is dat andersom. De manier waarop de twee onderdelen aan elkaar worden gelijmd verschilt per taal. In Cobol had men (tevergeefs) het ideaal om een programma op omgangstaal te doen lijken; recentere talen worden steeds symbolischer. In Pascal werd om didactische redenen het symbool “:=” ingevoerd, zodat het onderscheid tussen de opdracht “aap:=12” (maak aap, ongeacht de huidige waarde, gelijk aan 12!) en de test “aap=12” (is aap op dit moment gelijk aan 12?) goed duidelijk is. Het symbool “:=” dient daarbij te worden uitgesproken als “wordt”; immers, de variabele is nog niet noodzakelijk gelijk aan de waarde, maar wordt dat na uitvoeren van de opdracht. In C en Java is het symbool voor toekenning “=”, dat voor de duidelijkheid toch het beste uitgesproken kan worden als “wordt”. In deze talen wordt de gelijkheidstest genoteerd met een dubbel “==” teken, wat voor de Pascal-kenners dan weer verwarrend is. Het blijft natuurlijk maar een notatiekwestie, en als je daar doorheen kijkt is de toekenningsopdracht in alle imperatieve talen in wezen hetzelfde.

9

Als er alleen maar constante waarden in een toekenningsopdracht gebruikt zouden mogen worden, dan zou een computer zijn naam geen eer aandoen. Een computer kan behalve waarden transporteren natuurlijk ook rekenen. In assemblertalen zijn er instructies beschikbaar waarmee alle rekenkundige berekeningen (optellen, vermenigvuldigen) op een variabele en een waarde kunnen worden uitgevoerd. Cobol volgt hetzelfde principe. Het formuleren van ingewikkelde berekeningen door middel van losse deelopdrachten, is een slechte gewoonte die wiskundigen al in de renaissance hebben afgeleerd (en de Arabieren onder hen al in de achtste eeuw). De belangrijkste vernieuwing in Fortran was dan ook dat aan de rechter- (waarde-)kant van een toekennings-opdracht behalve een waarde ook een formule mag staan. De betekenis van de naam Fortran is dan ook “formula translator”. Bij het uitvoeren van een opdracht waar zo’n expressie in voorkomt wordt eerst de waarde van die expressie berekend, gebruik makend van de huidige waarde van de variabelen die in de expressie voorkomen, waarna deze waarde wordt toegekend aan de variabele links in de toekenningsopdracht. In expressies mogen de bekende wiskundige operatoren (+, -, * en /) worden gebruikt, alsmede een aantal standaardfuncties (zoals sqrt). Het enige verschil met de wiskunde is dat vermenigvuldiging expliciet moet worden geschreven (met een sterretje); dat is de prijs van het toestaan van meer-letterige variabele-namen.

10

Niet alle soorten berekeningen zijn zinvol op alle typen waarden. Je kunt wel getallen vermenigvuldigen, maar geen waarheidswaarden; je kunt een tekst wel naar hoofdletters vertalen, maar een getal niet. De uitkomst van een worteltrekking is over het algemeen een gebroken getal en niet een geheel getal. Als je dit soort dingen per ongeluk toch probeert, zullen de in het geheugen opgeslagen bit-patronen op de verkeerde manier worden geïnterpreteerd. Veel talen proberen dit soort vergissingen tegen te gaan. Alleen in assemblertalen mag alles, en daarin is het dan ook moeilijk om foutloze programma’s te schrijven. In vrijwel alle andere talen wordt een vorm van type-controle uitgevoerd, die nagaat of operaties wel zinvol zijn. Daartoe is het nodig dat het bekend is wat het bedoelde type van variabelen is. In Fortran was de typering eenvoudig: namen van variabelen die met een i t/m n beginnen zijn gehele getallen, de rest is floating-point (uit die tijd stamt de hardnekkige gewoonte om tellertjes i en j te noemen). In Basic was de naamgeving vrij, maar van gehele getallen moest de naam op een %-teken eindigen. Tekstvariabelen eindigden op een $-teken, de rest was floating-point (men herkent mensen die met Basic zijn opgevoed aan het uitspreken van ‘$’ als ‘string’!). In recentere talen is er een trend naar steeds meer verschillende types. Dit soort naamgeving-schema’s zijn daardoor niet meer mogelijk. In plaats daarvan is de naamgeving vrij, maar moeten alle variabelen expliciet gedeclareerd worden. Dit heeft als extra voordeel dat tikfouten in variabele-namen aan het licht komen.

In de modernere programmeertalen zul je in een programma behalve opdrachten dus ook declaraties aantreffen. In Pascal moet dat gebeuren voorafgaand aan de opdrachten, in C en Java kunnen de declaraties en de opdrachten elkaar afwisselen. Dat laatste is uit didactisch oogpunt eigenlijk jammer, want het verschil tussen een declaratie en een opdracht wordt er minder duidelijk van. Het verschil tussen een declaratie en een opdracht is echter wel belangrijk. De opdrachten worden tijdens het uitvoeren van het programma uitgevoerd. Eventuele declaraties die ertussen staan kosten daarbij geen tijd. De declaraties waren in een eerdere fase van belang, namelijk tijdens het compileren van het programma: ze zijn een aanwijzing voor de compiler over hoe deze de variabelen die in opdrachten voorkomen moet interpreteren, en dus hoe de opdrachten naar machinetaal vertaald moeten worden.

In vrijwel alle programma’s komen deel-taken voor die meer dan eens moeten worden uitgevoerd. Vanaf de allervroegste programmeertalen zijn er daarom mechanismes om een deel van het programma meer dan eens te gebruiken. In de diverse programmeertalen verschilt de terminologie voor zo’n deelprogramma, en er zijn ook wel verschillen, maar gemeenschappelijk is dat het deel-programma meermalen kan worden gebruikt, door middel van een speciale opdracht. Dat staat in alle talen bekend als het aanroepen van de subroutine/ procedure/functie/methode (Engels: call, of hoogdravender: invoke).

11

In Assembler-talen en in Basic zijn de opdrachten in principe genummerd. Er is een speciale opdracht (GOSUB) waarmee de subroutine met een bepaald regelnummer kan worden uitgevoerd. Uitvoeren van de speciale opdracht RETURN heeft tot gevolg dat het programmaverloop wordt voortgezet bij de opdracht volgend op de GOSUB-opdracht. Merk op dat aan de structuur van programma niet te zien is dat er op regel 100 een subroutine begint; dit is alleen impliciet te zien aan het feit dat er “GOSUB 100” opdrachten in het programma staan. Het is ook denkbaar dat je halverwege in een subroutine springt, of dat subroutines in elkaar overvloeien. In Pascal hebben (in navolging van het inmiddels in onbruik geraakte Algol) de procedures een naam, en is het in de programmatekst, los van de aanroepen, direct duidelijk dat het om een procedure gaat. Na de procedures volgt het eigenlijke programma (het zogenaamde hoofdprogramma), waarin de procedures kunnen worden aangeroepen. Het is nu niet meer mogelijk om een procedure “half” aan te roepen, of om de RETURN-opdracht te vergeten. In C worden de procedures functies genoemd, maar de structuur is hetzelfde als in Pascal. Nieuw is dat men heeft ingezien dat het hoofdprogramma in weinig verschilt van de procedures (het is een groepje opdrachten dat bij elkaar hoort). In C wordt daarom het hoofdprogramma ook als functie geschreven, die de naam main moet hebben. Starten van het programma kan worden beschouwd als aanroep van de main-functie. In Java is deze traditie ook aangehouden.

12

Een procedure bestaat uit een aantal opdrachten die bij elkaar horen. Anders dan bij subroutines is aan de programmatekst, los van eventuele aanroepen, te zien dat een groepje opdrachten één procedure vormt. De opdrachten zijn daartoe gebundeld met de woorden begin en end. Deze woorden zijn zelf echter geen opdracht – ze kunnen immers niet worden uitgevoerd. Het zijn veleer een soort leestekens: haakjes-openen en -sluiten, waarmee de opdrachten die samen de procedure vormen worden afgebakend. In C en Java is dat nog duidelijker, omdat hier daadwerkelijk haakjes (of liever gezegd accolades) worden gebruikt om de opdrachten af te bakenen. We zijn hier getuige van een zeer belangrijke stap in de evolutie van programmeertalen. In Assembler, Fortran en Basic werd de programmastructuur gedicteerd door (genummerde) tekstregels; in Algol, Pascal, C en Java wordt de programmastructuur expliciet bepaald door haakjes of haakjes-achtige keywords. De regelovergangen verliezen daarmee hun betekenis, waardoor de door esthetische overwegingen ingegeven programma-layout zijn intrede doet.

Met de aanwezigheid van duidelijk afgebakende procedures is het mogelijk om declaraties van variabelen te plaatsen in zo’n procedure. In Pascal gebeurt dat tussen de prcedure-kop en het woord begin, in C gebeurt het net na het {-haakje, maar dat is slechts een notationeel verschil. Hoofdzaak is dat de gedeclareerde variabele alleen geldig is binnen die ene procedure. Zo’n variabele die alleen plaatselijk geldig is heet een lokale variabele, en de declaratie ervan is een lokale declaratie.. Variabelen die buiten een procedure zijn gedeclareerd, en dus in alle procedures mogen worden gebruikt, heten in contrast daarmee globale variabelen. Het kan gebeuren dat in verschillende procedures een variabele wordt gedeclareerd met dezelfde naam. Die hebben niets met elkaar te maken; de procedures kunnen immers niet van elkaar “weten” welke lokale variabelen er in gebruik zijn. Het zijn dus wel degelijk verschillende variabelen, en het feit dat ze dezelfde naam hebben is daarbij niet storend, omdat zo’n naam toch alleen maar lokaal binnen de respectievelijke procedures geldig is. Bij elke aanroep van de procedure worden de lokale variabelen opnieuw gemaakt. Het is dus niet zo dat lokale variabelen de procedure overleven, en bij een volgende aanroep nog onveranderd beschikbaar zijn.

Globale variabelen mogen in alle procedures (en in het hoofdprogramma) worden gebruikt; lokale variabelen alleen maar in de procedure waar ze zijn gedeclareerd. Je kunt je afvragen wat er het voordeel van is om een variabele lokaal te declareren; dat legt immers alleen maar beperkingen op aan het gebruik ervan. Een belangrijk voordeel is, dat lokale variabelen niet per ongeluk gewijzigd kunnen worden bij aanroep van een andere procedure. Na aanroep van een procedure hebben je eigen lokale variabelen gegarandeerd nog dezelfde waarde; voor globale variabelen hoeft dat niet zo te zijn, die kunnen immers door de aangeroepen procedure veranderd zijn. Je zou dit effect ook kunnen bereiken door in alle procedures variabelen met verschillende namen te gebruiken. Dan moet je wel goed weten welke andere procedures er in hetzelfde programma gebruikt worden, en als het programma door een team wordt geschreven, kan dat heel wat vergadertijd opsouperen. Het is veel gemakkelijker als elke programmeur zijn eigen lokale variabelen kan kiezen, zonder daarover met collega’s te hoeven vergaderen. Ook kun je op deze manier een procedure uit een ander programma “lenen”, zonder je druk te maken over de naamgeving van de variabelen binnen de procedure. Bij programma’s die door één programmeur worden geschreven gelden deze voordelen onverkort: deze programmeur kan zich op één procedure tegelijk concentreren, zonder zich druk te maken over de details van de, mogelijk vele, andere procedures.

13

Vaak gebeurt het dat een deel-taak weliswaar meermalen moet worden uitgevoerd, maar dat daarbij enkele details toch verschillen. Om in zo’n geval toch met één procedure (die meermalen wordt aangeroepen) te kunnen volstaan kunnen procedures parameters krijgen. Een parameter is in feite een lokale variabele, die bij de aanroep van de procedure alvast een waarde krijgt. De declaratie van een parameter gebeurt in de meeste talen tussen haakjes in de procedure-kop: int x in het voorbeeld hierboven. Dit in tegenstelling tot declaraties van lokale variabelen, die pas volgen na de procedure-kop: int a in het voorbeeld. De waarde die de parameter bij de aanroep moet krijgen wordt, tussen haakjes, bij de aanroep opgeschreven. Let op: bij de definitie van de procedure staat er dus een declaratie tussen de haakjes, terwijl er bij de aanroep een expressie (een formule met een waarde) staat. Die expressie kan een constante zijn, zoals 3 of 4, maar ook een berekening, zoals y+1. In feite mag er alles staan wat ook aan de rechterkant van een toekenningsopdracht mag staan. In het bijzonder is een losse variabelenaam ook toegestaan (zoals y), en vooral daar kan er allicht verwarring ontstaan met de procedure-definitie (zoals int x in het voorbeeld).

14

Op het thema “parameters” zijn nog diverse variaties mogelijk. Zo is het in C++ mogelijk om in de definitie van een procedure de parameter van een default waarde te voorzien. Als de procedure met “te weinig” parameters wordt aangeroepen, dan geldt de default waarde voor de betreffende parameter. Hierbij geldt de beperking dat de parameters met zo’n default-waarde aan het eind van de lijst moeten staan, omdat er anders ambigue situaties kunnen onstaan. Deze vernieuwing van C++ t.o.v. C is in Java overigens weer afgeschaft. Een nadeel van de parameter-overdracht zoals die in Pascal, C, Java en vrijwel alle andere talen verloopt, is de essentiële rol die de volgorde van de parameters speelt. Bij de aanroep is niet meer te zien welk van de parameters welke rol speelt, en dat kan bij procedures met tien parameters verwarrend en dus foutgevoelig zijn. In enkele talen moet daarom bij aanroep van een procedure de naam van de parameters worden genoemd, waarmee de verplichting vervalt om ze in volgorde op te sommen. Een voorbeeld hiervan is de taal HTML. Met een beetje goede wil kan het gebruik van tags zoals in deze taal als procedure-aanroep worden beschouwd; parameters worden daarbij met hun naam aangeduid.

Het voordeel van lokale declaraties was dat programmeurs van verschillende procedures onafhankelijk van elkaar konden werken, en niet hoefden te vergaderen over hun lokale variabelen. Het enige waar het team het over eens hoefde te worden, waren de namen van de procedures. Bij echt grote programma’s onstaat voor de namen van procedures hetzelfde probleem als wat eerder gold voor het gebruik van variabele-namen: het is onduidelijk welke namen nog gebruikt mogen worden en welke niet. Ook bij het gebruik van procedure-bibliotheken treedt dit probleem op. De oplossing van dit probleem ligt in weer een nieuwe laag in de hiërarchie: procedures kunnen worden gebundeld in een zogenaamde klasse. Binnen de klasse kunnen de procedures elkaar gewoon aanroepen; buiten de klasse moet daarbij de naam van de klasse genoemd worden. Voor globale variabelen (die dus niet meer echt “globaal” zijn) geldt hetzelfde. In talen als C++ en Java kunnen, waar dit mogelijk is, programmeurs van verschillende klassen dus hun gang gaan, zonder zich druk te maken over de naamgeving van procedures in de andere klassen. In Java kunnen zelfs de klassen weer worden ondergebracht in packages, mocht de naamgeving van de klassen op zijn beurt weer verwarrend worden. Keerzijde van dit moois is dat je in Java ook voor simpele programma’s de klasse-stuctuur moet aanleggen, zelfs als er maar één klasse is. In kleine voorbeelden kan dat omslachtig overkomen t.o.v. bijv. Basic, maar al bij iets grotere programma’s betaalt de moeite zich terug.

Om het programmaverloop zich te laten ontwikkelen afhankelijk van de voorgeschiedenis of bijvoorbeeld door de gebruiker ingevoerde waarden, is het nodig om bepaalde opdrachten voorwaardelijk uit te voeren of juist over te slaan. In Assembler-talen is er daarom een instructie aanwezig om op grond van de waarde van de laatst gedane berekening het programmaverloop elders voort te zetten (in feite is dat een voorwaardelijke toekenning van een nieuwe waarde aan een speciale variabele: de program counter). In het voorbeeld wordt de sprong gemaakt als de uitkomst van de CMP (compare) opdracht ongelijk nul is, maar er zijn ook sprongen mogelijk op grond van een handjevol andere criteria. Belangrijke vernieuwing van talen als Fortran en Basic was de mogelijkheid om een willekeurige opdracht (bijvoorbeeld een toekenning of een subroutineaanroep) voorwaardelijk uit te voeren.

15

Voor iets ingewikkeldere constructies, waarbij meerdere opdrachten voorwaardelijk moeten worden uitgevoerd, of waarbij, in het geval dat de voorwaarde niet waar is, juist een andere opdracht moet worden uitgevoerd, schiet de simpele IF-opdracht van het oorspronkelijke Fortran en Basic tekort. Het is wel mogelijk, maar het programmaverloop moet dan expliciet worden beïnvloed met GOTO-opdrachten, waardoor het geheel wel erg op Assembler gaat lijken. In talen als Pascal en C is het, ten behoeve van procedures-definities, toch al mogelijk om opdrachten te groeperen met begin/end of accolades. Deze groepering van opdrachten komt nu ook goed van pas om meerdere opdrachten tot body van een if-opdracht te maken. Doordat de koppeling met tekstregels is losgelaten, is het bovendien mogelijk om op een overzichtelijke manier ook nog plaats te bieden aan een else-gedeelte. De opdrachten achter if en else kunnen op hun beurt weer if-opdrachten bevatten. Door handig gebruik te maken van inspringen kan in een netwerk van keuzemogelijkheden toch redelijk overzichtelijk het programmaverloop worden vastgelegd.

16

Vaak komt het voor dat een reeks opdrachten meerdere malen achter elkaar moet worden uitgevoerd. In eenvoudige talen kan dit worden bereikt met behulp van twee GOTO-opdrachten. In talen met een begin/end-blokstructuur kan dit veel duidelijker worden aangegeven met een while-opdracht. De body van deze opdracht bevat de opdracht die moet worden herhaald; is dit er meer dan één, dan kunnen de opdrachten worden gebundeld met begin/end (respectievelijk accolades). Voordeel hiervan is dat zo’n while-opdracht dichter ligt bij de belevingswereld van de programmeur: je ziet gemakkelijk welke opdracht(en) worden herhaald, en hoelang dat het geval is, zonder dat daarvoor de GOTO-opdrachten hoeven te worden uitgeplozen.

Een veel voorkomende vorm van herhaling is die, waarbij het aantal malen dat een opdracht wordt herhaald wordt bepaald door een variabele, waarin het aantal herhalingen wordt geteld. In Basic een tweetal opdrachten beschikbaar: FOR en NEXT. Hierin is een soort blokstructuur avant-la-lettre te herkennen, maar het ging wel degelijk om twee aparte opdrachten. Kwaadwillende programmeurs zouden de NEXT-opdracht voorwaardelijk kunnen maken, of in een subroutine plaatsen… Het belang van een constructie met een tellende variabele werd echter in zowel Pascal als C wel onderkend. In beide talen is er daarom een for-opdracht. Een aparte opdracht om het einde aan te geven is natuurlijk niet nodig, omdat ook hier de blokstructuur gebruikt kan worden om de reikwijdte van de body aan te duiden. Was het in Pascal nog alleen maar mogelijk om met een for-opdracht te tellen (eventueel met een stapgrootte anders dan 1, of achteruit), in C is de for-opdracht ook voor andere vormen van herhaling te gebruiken: hier kan de initialisatie, het voortgangscriterium, en de stap-opdracht vrij worden gekozen, zelfs als er “geteld” wordt met andere variabelen dan integers.

Het gebruik van blokstructuur in programmeertalen is nu gemeengoed. Toch is dat niet altijd zo geweest. In 1968 was het een knuppel in het hoenderhok toen de (Nederlandse) informaticus E.W.Dijkstra een artikel publiceerde met de toentertijd provocerende titel Go To Statement Considered Harmful (strikt genomen was het een ingezonden brief, van slechts één pagina, aan het vaktijdschrift Communications of the ACM). Dit artikel wordt vaak genoemd als zou Dijkstra hierin de “spaghetti”-structuur van programma’s met GOTO-opdrachten veroordelen. Hij noemt echter alleen het woord “mess”, en zijn hoofdargument is bovendien dat de toestand van het programmaverloop met GOTO-opdrachten lastig te beschrijven is, en dat het daarom lastig is om uitspraken te doen over de correctheid ervan. De gevaren kunnen worden beteugeld door gebruik te maken van if- en while-constructies. Het artikel was hoe dan ook het begin van een richting in het programmeeronderwijs die bekend staat als “gestructureerd programmeren”, zeg maar met gebruikmaking van Pascal (1971) in plaats van Basic. Taalontwerpers waren huiverig om de GOTO-opdracht helemaal te schrappen: in zowel Pascal als C is deze opdracht toch nog mogelijk. Pas in Java is hij echt geschrapt. (Het is nog een tijdje mode geweest om artikelen te publiceren met de woorden “considered harmful” in de titel (global variables…, assignment statement…), totdat het tijdschrift-redacties te gortig werd, en dit soort epigoon-artikelen bij voorbaat werden geweigerd.)

17

Het strikt toepassen van de nieuwe leer van het gestructureerd programmeren bleef niet zonder problemen. Zo was het voortijdig afbreken van een herhaling in Basic bepaald gemakkelijker dan in Pascal, waar dit alleen mogelijk was met een whileopdracht in plaats van een for-opdracht, en een extra boolean hulpvariabele. In C werd er daarom een nieuw soort opdracht ingevoerd: de break-opdracht. De betekenis hiervan is dat de verwerking van de omvattende while-, for- of switchopdracht wordt onderbroken. Het is, zo men wil, een vorm van “gestructureerde goto”, en wordt in de praktijk veel gebruikt. Aanhangers van de strikte gestructureerd-programmeren-leer vinden de breakopdracht toch verdacht, bijvoorbeeld omdat de betekenis ervan niet zonder de context kan worden beschreven. Een ander theoretisch nadeel is dat aan de header van een for-opdracht niet meer eenduidig de stop-voorwaarde is af te lezen. Er zijn dan ook C- en Java-leerboeken waarin het voortijdig stoppen van een for-opdracht op de Pascal-manier wordt besproken. Het blijft natuurlijk de vraag of dat het voor beginners veel duidelijker maakt.

Naast procedures is het in Pascal ook mogelijk om zogenaamde functies te maken. Een functie heeft dezelfde eigenschappen als een procedure (je groepeert eenmalig een aantal opdrachten onder een header, en kunt die vervolgens meermalen aanroepen), maar daarenboven wordt door een functie een waarde berekend, die door de aanroeper kan worden gebruikt. Zo’n functie-resultaat kan gebruikt worden om informatie terug te geven aan de aanroeper; dit in tegenstelling tot parameters, die juist bedoeld zijn om informatie van de aanroeper naar de procedure of functie te transporteren. De aanroep van een procedure heeft zelf de status van een opdracht. Je kunt zo’n aanroep immers uitvoeren (met als gevolg dat de opdrachten in de body van de procedure worden uitgevoerd). De aanroep van een functie heeft daarentegen de status van een expressie: hij kan worden gebruikt aan de rechterkant van een toekenning, in een grotere formule, of zelfs als parameter van een andere aanroep. Expressies zijn immers programmaconstructies met een waarde, en een functie-aanroep levert een waarde op.

18

Omdat een procedure, anders dan een functie, geen resultaat-waarde oplevert, moeten alle nuttige effecten van een procedure afkomstig zijn van manipulatie van de buitenwereld. Elke procedure zal dus ófwel een toekenning doen aan globale variabelen, ófwel output genereren (wat in wezen hetzelfde is). Het enige alternatief is dat de procedure andere procedures aanroept die deze effecten veroorzaken. Een functie levert een resultaatwaarde op. In de header van de functie moet het type van de resultaatwaarde worden gespecificeerd (in Pascal aan het eind van de header, in C en Java juist aan het begin). Bovendien moet ergens in de functiebody worden aangegeven wat nu eigenlijk het resultaat is van de functie. In Pascal gebeurt dit door toekenning aan de functienaam, in C en Java met de speciale return-opdracht. In Pascal zijn procedures en functies verschillende constructies, aangeduid met verschillende keywords. Bij een functie moet een resultaat-type worden opgegeven en bij een procedure juist niet. Toch is er grote gelijkenis in de structuur van procedure- en functie-definities: beide hebben een naam, parameters, en een body. In C en Java is deze gelijkenis nog duidelijker: de opbouw van procedures is hetzelfde als die van functies. Als resultaat-type van procedures wordt het speciale type void gebruikt. Letterlijk betekent dit “leeg” of “niets”, en dat klopt: een procedure (of in C-terminologie: “void-functie”) heeft geen resultaatwaarde. Er hoeft dan ook geen return-opdracht te staan in de body.

Als parameter van een functie moeten waardes worden meegegeven. Die kunnen het resultaat zijn van het uitrekenen van een expressie, en een van de mogelijkheden daarvoor is het aanroepen van een andere functie. In de body van een functie staan opdrachten. Die opdrachten kunnen aanroepen zijn van andere (void-)functies. De opdrachten in de body daarvan kunnen ook weer aanroepen zijn van weer andere functies, enzovoorts. Na afloop van het uitvoeren van een functie keert het programmaverloop altijd terug naar de plaats van de aanroep. Als functies elkaar aanroepen moet er een hele stapel van posities in het programma onthouden worden (“als dit is afgelopen moeten we verder op positie A, en als dát is afgelopen verder op positie B”). Al die terugkeerposities worden door de processor dan ook bijgehouden in een speciaal stuk van het geheugen, dat de naam stack draagt. In het voorbeeld hierboven bevat de stack, op het moment dat de body van tekenpunt wordt uitgevoerd, de programmapostie in de functie tekenlijn van waaruit tekenpunt werd aangeroepen, de positie in tekenvierkant van waaruit tekenlijn werd aangeroepen, en de positie in tekenkubus van waaruit tekenvierkant werd aangeroepen. In het andere voorbeeld is een minder grote stack nodig. De stack bevat de positie van waaruit oplos werd aangeroepen. Dan wordt de functie kwad aangeroepen, en gaat de stack dus de programmapositie van deze aanroep bevatten. Na afloop van de aanroep van kwad wordt deze positie weer van de stack verwijderd, en pas daarna wordt de functie sqrt aangeroepen.

19

Een aardig idee is dat je in de body van functies, naast andere functies, ook de functie zelf weer kunt aanroepen. Op het eerste gezicht lijkt er dan een Drosteeffect te onstaan (want die aangeroepen functie zal ook weer zichzelf aanroepen, enzovoorts). Voor de administratie daarvan zou een oneindig grote stack nodig zijn. Toch kan zo’n zogenaamde recursieve aanroep heel handig zijn, mits je er met een if-opdracht voor zorgt dat de functie niet altijd zichzelf aanroept. Via een parameter, die bijvoorbeeld bij elke aanroep 1 kleiner wordt, kun je er voor zorgen dat de niet-recursieve tak van de if-opdracht zich vroeg of laat zal voordoen. Vanaf dat moment wordt de hele stack, waarop alle programmaposities in de diverse “incarnaties” van de functie staan, weer helemaal afgebroken. Met een recursieve functie kun je een herhalings-effect bereiken (de functie wordt net zolang opnieuw aangeroepen, totdat het niet-recursieve geval zich voordoet), zonder daarbij een while- of een for-opdracht te gebruiken; een if-opdracht is voldoende. Het debat over de wenselijkheid van recursieve aanpak van problemen slingert heen en weer tussen enerzijds de elegantie die zo’n recursieve formulering ten toon kan spreiden, en anderzijds de prijs van de extra benodigde stackruimte die dat met zich meebrengt.

20

Als je alle variabelen in een programma apart zou moeten declareren, zou het lang duren voordat je 32 megabyte vol hebt. Gelukkig is het mogelijk om met één declaratie een hele rij variabelen te declareren (allemaal van hetzelfde type). De notatie daarvoor varieert natuurlijk weer per taal, maar het idee is hetzelfde: er wordt in één keer een stuk geheugen van een bepaalde afmeting gereserveerd. Anders dan losse variabelen moeten deze zogenaamde arrays in Basic wèl gedeclareerd worden. Dat gebeurt met het zogeheten DIM-statement, wat in feite helemaal geen opdracht is maar een declaratie. In Pascal moet de ondergrens en de bovengrens van de array worden opgegeven (het is dus mogelijk om een array met indexnummers van 10 tot en met 20 te maken!). In C en Java moet het aantal elementen worden opgegeven, en begint de telling altijd bij 0. Bij een aantal elementen van 10, is het nummer van het laatste element dus 9, iets wat nog wel eens voor verwarring zorgt. Deze op het eerste gezicht merkwaardige keuze is in C bewust gemaakt; het alternatief zou zijn dat een array die is gedeclareerd met int a[10] elf elementen bevat, en dat zou ook weer raar zijn.

In vrijwel alle getypeerde talen zijn er een aantal standaardtypes aanwezig. Daaronder bevinden zich meestal de gehele getallen (int of integer) en floatingpoint getallen (float of real). Dat dit twee verschillende types zijn vindt zijn reden in het feit dat met integers sneller en zonder gevaar van afrondfouten gerekend kan worden. Fortran was de taal van technisch/natuurkundige berekeningen, en als extra type onstond hierin de behoefte aan complexe getallen. In een beginnerstaal als Basic was er veeleer behoefte aan tekst-variabelen, die de naam string kregen. Pascal zocht het in een andere richting: vanwege de ordelijkheid werden char en boolean hier als aparte types geïntroduceerd. Een apart type string was niet nodig, want daarvoor kon een array van char gebruikt worden. C was meer een taal van de praktijk dan van het onderwijs. Hierin kwamen aparte types voor “extra grote” integers en floats: respectievelijk long en double. De boolean werd vergeten, maar wel was er ook het type void, te gebruiken als “resultaat-type” van procedures. Java heeft alle succesvolle types uit andere talen overgenomen en er nog wat toegevoegd. Ook de string uit Basic keerde terug, zij het strikt genomen niet als standaardtype. Naast het gebruiken van standaardtypes is het in alle talen vanaf de “gestructureerd programmeren” revolutie mogelijk om het repertoire uit te breiden, door middel van type-definities. Zo kun je een ingewikkeld array-type bijv. de naam tabel geven, en vervolgens variabelen van dat type declareren.

In een array hebben alle onderdelen hetzelfde type. Soms is het echter zinvol om een aantal variabelen van verschillend type te groeperen. Klassiek voorbeeld daarvan is een record uit een database. In Pascal is het mogelijk om het type van zo’n record eenmalig de definiëren, en dat type vervolgens te gebruiken in variabele-declaraties. Ook kun je arrays van dit soort records maken, en ze als parameter aan functies meegeven (maar, gek genoeg, niet als resultaat opleveren). In C is een vergelijkbare constructie mogelijk. Hier wordt een record, om zich van de concurrentie te onderscheiden, een struct genoemd. Ook hier kun je de structuur van zo’n struct eenmalig vastleggen, en vervolgens variabelen van dat type declareren. (Je zou in de struct-definitie eigenlijk het woord typedef weer verwachten. Waarom dat in C++ niet hoeft, en in C wel maar met weer een andere onlogische draai, is een beetje ingewikkeld om uit te leggen, en ook eigenlijk niet zo interessant.) De onderdelen van een record, respectievelijk struct, zijn te benaderen met behulp van de “punt-notatie”: de naam van de record-variabele, gevolgd door een punt en het gewenste onderdeel; bijvoorbeeld: “voorzitter.leeftijd” .

21

Een goede programmeer-gewoonte, die mogelijk wordt gemaakt door het bestaan van record/structure-typen, is het gebruik van zogenaamde abstracte datatype. Dit is dan ook een standaard ingrediënt in de “gestructureerd programmeren” didactiek. Eerste stap is het definiëren van een stucture-type. Vervolgens worden een aantal functies gedefinieerd die zo’n structure als eerste parameter hebben. Door middel van commentaar wordt duidelijk gemaakt dat die functies bij elkaar en bij het type horen. In het hoofdprogramma kunnen nu variabelen van het nieuwe type worden gedeclareerd. Deze variabelen kunnen worden gemanipuleerd door middel van het aanroepen van de daarvoor bestemde functies. Zelfbeheersing moet ervoor zorgen dat de variabelen ook alleen maar via die functies worden gemanipuleerd, en dus niet door middel van direct aanspreken van de component-variabelen. Het aardige van deze aanpak is dat de programmeur van het hoofdprogramma de details van de functies niet hoeft te kennen: hij hoeft alleen maar de headers te kennen (en een algemene beschrijving van het doel van de functies). Ook kan in een later stadium de body van de functies worden aangepast, zonder dat het hoofdprogramma daaronder te lijden heeft. Zo wordt het “hoe” van het “wat” gescheiden, een belangrijk uitgangspunt in de software engineering.

22

Een voorbeeld van een abstract datatype is de modellering van een stapel brieven. Eerst moet daartoe gedefinieerd worden wat een “brief” precies is. In het voorbeeld nemen we aan dat dat in een eerder stadium al gebeurd is, en gaan we verder om een ADT te maken van het begrip “stapel”. In de type-definitie wordt beschreven dat een brieven-stapel is geïmplementeerd door een array van brieven, tezamen met een integer die aangeeft tot hoever de array gevuld is. Vervolgens zijn er een drietal functies: een void-functie “leg” om een (als parameter te specificeren) brief bovenop een (ook als parameter te specificeren) stapel te leggen, een functie “pak” die de bovenste brief van een stapel pakt en als resultaatwaarde oplevert, en een functie “werk” die aangeeft of er op een bepaalde stapel nog werk (in casu: brieven) te wachten ligt. Nu kunnen we het hoofdprogramma schrijven. Hierin kunnen, ondanks de ingewikkelde interne structuur, met gemak variabelen van het type “Stapel” worden gedeclareerd. Door aanroep van de functies kan nu bijvoorbeeld een programma geschreven worden dat de brieven van de stapel “in” pakt en ze weer neerlegt op de stapel “uit”. De methodologie schrijft voor dat de programmeur van het hoofdprogramma zich niet direct aan de component-variabelen vergrijpt. Een manier om dat te garanderen is dat de programmeur van het ADT de type-definitie geheim houdt.

Het begrip ADT (abstract datatype) is enigszins in onbruik geraakt, sinds dit principe ondersteund wordt door het object-georiënteerde (OO) programmeerparadigma. In dit paradigma worden de abstracte datatypen klassen genoemd, en de variabelen van zo’n type objecten. Object-georiënteerd programmeren is populair geworden met de komst van window-gebaseerde systemen, omdat windows zo handig gemodelleerd kunnen worden als objecten. De taal C++ onstond in 1985 als object-georiënteerde uitbreiding van C, en in Java (1995) is de object-georiënteerde aanpak nog rigoreuzer aangehouden. Toch is het principe al ouder. Algemeen wordt de (inmiddels vergeten) taal Simula (1975) als eerste OO-taal beschouwd. En het principe van ADT’s was natuurlijk ook al langer bekend. De taal Smalltalk uit 1980 was een andere vroege OO-taal. In deze taal werden de eerste muis-bediende computersystemen geprogrammeerd. In een OO-taal horen de functies (die methodes worden genoemd) nu officieel bij de type-definitie: dit wordt in de programmatekst aangegeven, niet alleen in commentaar. De programmeur hoeft nu niet meer op te schrijven dat de methodes het object als eerste parameter meekrijgen. Achter de schermen gebeurt dat nog wel, maar je hoeft dat niet meer te noteren en kan het dus ook niet vergeten. De attributen van het object mogen in de methodes direct gebruikt worden. Buiten de methodes mogen de attributen van een object niet gebruikt worden; probeer je het toch, dan wordt dat door de compiler afgekeurd.

Hier is nog eens hetzelfde voorbeeld (modellering van een stapel brieven), ditmaal in de OO-notatie van Java. De typedefinitie begint nu met het woord class, en behalve de attribuut-declaraties staan ook de methode-definities daar in (de sluit-accolade van de klasse staat pas helemaal aan het eind!). Anders dan in de ADT-benadering hebben de methoden nu geen Stapel-parameter meer; de methoden “pak” en “werk” hebben dus helemaal geen (expliciete) parameter meer over. De attributen “bak” en “aantal” mogen in de methoden direct gebruikt worden. Declaratie van de objecten in het hoofdprogramma is hetzelfde. Bij aanroep van de methoden hoeft het object niet meer als parameter te worden meegegeven. Maar het moet natuurlijk wel duidelijk zijn welk object de methoden moeten manipuleren: daartoe heeft de punt-notatie een nieuwe betekenis gekregen. Op het eerste gezicht lijken de attributen een soort globale variabelen te zijn: ze mogen immers in alle methoden worden gebruikt. Maar het is belangrijk om te bedenken dat er meerdere setjes van die variabelen kunnen zijn: elk object heeft zijn eigen exemplaar. Wil je werkelijk begrijpen wat er gebeurt, bedenk dan dat dit gewoon een andere notatie is voor het ADT-voorbeeld, en dat de objecten wel degelijk als extra parameter worden meegegeven. Waarschijnlijk is dat voor beginners niet echt verhelderend, en het is daarom dat OO-gebaseerde leerboeken zo’n geheel eigen jargon ontwikkeld hebben voor de belangrijkste OO-concepten.

23

Bij het programmeeren komt het vaak voor dat je wilt voortborduren op werk van anderen (of van eigen eerder werk). De oudste manier om dat te doen is om een kopie te maken van de klasse, en daarin toe te voegen wat nieuw is; zie in het voorbeeld de klasse “Drie” rechtsboven, waarin een derde attribuut, en een nieuwe methode is toegevoegd t.o.v. de klasse “Twee” (linksboven). Het nadeel van deze aanpak is dat als later de methode “oud” in de klasse “Twee” wordt verbeterd (bijvoorbeeld door hem te vervangen door een efficiëntere versie), deze wijziging niet automatisch in de klasse “Drie” ook wordt doorgevoerd. Een al wat betere aanpak heet “Delegatie” (linksonder). In de nieuwe klasse worden alleen de extra attributen en methoden opgenomen, en verder een extra attribuut, die een object van de oorspronkelijke klasse bevat. Een nadeel van deze aanpak is de asymmetrie: de attributen moeten op verschillende wijze worden benaderd. In het voorbeeld: het nieuwe attribuut z kan direct worden gebruikt, maar het gebruik van de oude attirbuten x en y moeten worden gedelegeerd aan het object t. Bij herhaalde delegatie krijg je dan expressies als a.b.c.d.e.x, en dat is niet overzichtelijk. In Object-georiënteerde talen is daarom een derde aanpak mogelijk: “Subklassen” (rechtsonder). In de header kun je specificeren dat de klasse een “extensie” is van een andere klasse. Je kunt dan zonder meer de attirbuten en methoden van de oorspronkelijke klasse gebruiken, net als bij de knip-en-plak werkwijze; maar nu kun je oorspronkelijke klasse nu wel zonder versie-probleem wijzigen.

24

In alle object-georiënteerde talen kun je voor objecten van de subklasse de methoden en attributen gebruiken die in de klasse waar deze een extensie van is (de “superklasse”) zijn gedefinieerd. Deze attributen en methoden worden, zoals dat heet, “geërfd” (inherited). Object-georiënteerde talen verschillen in de manier waarop dit mechanisme verder is uitgewerkt. Zo is het bijvoorbeeld in C++ mogelijk om een klasse een uitbreiding te laten zijn van meerdere superklassen. Dat lijkt op het eerste gezicht handig, maar wat gebeurt er als die klassen zelf allebei een extensie zijn van een vierde klasse? Erf je de attributen daarvan dan éénmaal of tweemaal? Om dit soort vragen te vermijden is in Java slechts één superklasse toegestaan. Attributen en methoden kunnen bedoeld zijn voor gebruik door wie dat maar wil (public), of alleen voor gebruik door andere methoden in dezelfde klasse (private). Bij het maken van een subklasse rijst de vraag of je daarin nu wel of niet gebruik mag maken van private attributen en methoden van de superklassen. In C++ is het antwoord “ja”; in Java luidt het “nee”, maar is er een derde soort beveiliging: protected attributen en methoden mogen wél in de subklassen, maar niet door de buitenwereld worden gebruikt.

25

Declaraties zijn aanwijzingen voor de compiler over het te reserveren geheugen. Op dat moment is de waarde van variabelen nog niet bekend. Daarom moet de lengte van arrays in Pascal, C en C++ tijdens de compilatie vastliggen: het moet een constante zijn. Ook is het niet mogelijk om in bijvoorbeeld een for-opdracht steeds opnieuw een variabele te declareren. Toch is het in deze talen mogelijk om tijdens het uitvoeren van het programma te beslissen om nieuw geheugen te gaan gebruiken. Daartoe is het nodig om pointers te gebruiken. Pointers zijn variabelen die kunnen verwijzen naar geheugen. De pointers zelf moeten wel gedeclareerd worden, en hebben dus een naam, maar het geheugen waar ze naar wijzen wordt tijdens het programmaverloop gereserveerd. De compiler heeft daar geen weet van, en dit geheugen is dan ook naamloos. Toch is dit geheugen te gebruiken, en wel door de pointer (de “wijzer”) te volgen. Daar is een speciale notatie voor.

26

Dit is een voorbeeld van het gebruik van pointers in Pascal. Er worden drie variabelen gedeclareerd: k is een losse integer, jan is een Persoon-record, en p is een pointer die ooit nog eens naar een Persoon-record kan gaan wijzen, maar dat door puur de declaratie nog niet doet. In het type wordt dat aangegeven met een pijltje (^). In het programma worden de variabelen van waarden voorzien. De integer k krijgt een waarde door een toekenningsopdracht. De componenten van het record jan kunnen ook door toekenningen een waarde krijgen. De ponter-variabele p krijgt echter een waarde door middel van de speciale opdracht new(p). De waarde van p wordt hiermee een verwijzing naar een stuk run-time aangemaakt geheugen: een naamloos Persoon-record. De componenten van het record-waar-p-naar-wijst kunnen worden aangesproken met de notatie p^. ; het pijltje duidt er op dat de pointer gevolgd moet worden. Didactisch belangrijk bij het tekenen van dit soort plaatjes is het benadrukken dat het de pijl is die de waarde is van de pointer-variabele. Dat wordt hier nog eens gesymboliseerd door de stip bij de oorsprong van de pijl, die heel duidelijk in de variabele ontspringt, terwijl de pijlpunt juist naar de rand van de aangewezen record wijst. Het is opvallend hoe slordig hier in tekstboeken vaak mee wordt omgesprongen (bijvoorbeeld, pijlen die ontspringen aan de rand van de pointervariabele). Let ook op dat er géén pijl staat tussen de naam van een variabele en het hokje dat deze geheugenruimte symboliseert: daar loopt immers geen pointer.

Dit is nogmaals hetzelfde voorbeeld, maar ditmaal in C++. Ook nu wordt bij de declaratie van p aangegeven dat het om een pointer-variabele gaat (in C++ gebeurt dat met een sterretje in plaats van met een pijltje). De manier waarop een pointer naar nieuw geheugen gaat wijzen verschilt van Pascal. Ook nu wordt het keyword new gebruikt, maar in C++ heeft dit de status van een expressie, niet van een opdracht. Daarom kan de frase new Persoon() aan de rechterkant van een gewone toekenningsopdracht aan p staan. Voor het manipuleren van de componenten van de structure-waar-p-naar-wijst is er de speciale notatie “->”, die aan een pijltje moet doen denken. Ook toegestaan is de notatie “(*p).leeftijd”, die meer op de Pascal-versie lijkt, maar die door het benodigde extra paar haakjes in de praktijk zelden gebruikt wordt. Je kunt in C++ pointers ook laten wijzen naar variabelen die wèl zijn gedeclareerd, mits die van het geschikte type zijn. Daartoe kan met de speciale operator “&” een pijl worden gecreëerd naar een variabele, die vervolgens in de pointer-variabele kan worden opgeslagen.

Hoewel Java in veel opzichten lijkt op C++, is het gebruik van pointers duidelijk anders. Om te beginnen is het in Java helemaal niet mogelijk om objecten direct te declareren: de variabele jan in het voorbeeld kan dus niet worden gedeclareerd zoals in Pascal en C++. Wel is het mogelijk om de pointer p te declareren. Omdat verwarring met losse object-variabelen (die immers niet zijn toegestaan) niet mogelijk is, hoef je in Java het pointer-zijn van p niet expliciet met een pijltje of sterretje aan te geven. Ook bij manipulatie van attributen (en methoden) van het object kan direct de punt-notatie worden gebruikt. Voor C-programmeurs is dat even wennen. Er wordt wel eens gezegd dat Java, in tegenstelling tot C++, geen pointers kent. Dat is niet juist: in zekere zin kent Java eigenlijk alleen maar pointers! Objecten, en ook arrays, worden in Java altijd dynamisch aangemaakt; dat wat gedeclareerd wordt is alleen maar de pointer ernaartoe. Een van de voordelen hiervan is, dat de lengte arrays in Java niet bij compilatie hoeft vast te liggen: de lengte hoeft geen constante te zijn. Wel wordt de lengte van de array “bevroren” op het moment dat het dynamische geheugen wordt gecreëerd.

27

Als een pointer naar één enkel object wijst, is de winst nog niet groot. Immers, dat object hoeft dan wel niet gedeclareerd te worden, maar de pointer zelf weer wel, en daarmee ligt de hoeveelheid geheugen toch weer reeds bij het compileren vast. Interessant wordt het pas als de objecten zelf ook weer pointers bevatten naar andere objecten, die ook weer pointers bevatten… Op die manier kunnen gelinkte datastructuren ontstaan waarin alle objecten naamloos zijn, maar die via-via wel te bereiken zijn vanuit een enkele pointer. Ook leuk is het als een object een pointer bevat naar eenzelfde type object. Je kunt dan recursieve datastructuren maken: ketens van objecten die allemaal naar elkaar wijzen. De keten kan worden afgestopt met de speciale pointer-waarde nil (Pascal), NULL (C++) of null (Java). Zo’n keten van objecten kun je bijvoorbeeld gebruiken als alternatief voor een array. Anders dan bij een array kun je in zo’n keten door het omleggen van een paar pointers heel gemakkelijk elementen tussenvoegen. Helemaal spannend wordt het als er in het object twee pointers naar gelijksoortige objecten staan: er onstaan dan vertakte, boom-vormige datastructuren. Dat soort datastructuren kunnen op een heel natuurlijke wijze worden gemanipuleerd met recursieve functies.

28

Hier is nog eens het schema van programmeerparadigma’s. Imperatieve talen hebben met elkaar gemeen dat er een vorm van toekenningsopdracht is. Procedurele talen voegen daar een concept van tekstueel afgebakende proceduredefinities aan toe. In object-georiënteerde talen kunnen de procedures (methoden) bovendien worden gekoppeld aan de datatypen waar ze op werken. Als we een wezenlijk ander paradigma dan het imperatieve willen bekijken, dan moeten we dus de toekenningsopdracht afzweren. Op het eerste gezicht lijken variabelen en toekenningsopdrachten onlosmakelijk verbonden met de computer. Toch is het mogelijk om zonder deze begrippen tot nuttige programmeertalen te komen. In het functionele paradigma staan de begrippen waarde, expressie, en functie veel centraler dan variabele, opdracht en procedure. In het logische paradigma staan de begippen feit, voorwaarde en relatie centraal. De programma’s in een declaratieve programmeertaal kunnen gewoon worden uitgevoerd op een computer, die wel degelijk over een toekenningsopdracht beschikt. Deze paradox is echter niets nieuws: het was immers ook mogelijk om de goto-opdracht af te zweren, en toch een processor te gebruiken waarin zo’n opdracht wel degelijk bestaat. De compiler schermt ons af voor de gevaren en de verleidingen ervan. Zo is het ook met de declaratieve talen: de compiler zorgt ervoor dat het programma wordt vertaald naar een gangbare machinetaal; de details daarvan zijn voor de programmeur echter niet relevant.

In een declaratieve programmeertaal zijn er geen variabelen, en geen toekenningsopdrachten. Er zijn zelfs helemaal geen opdrachten, en we hoeven ons dus ook geen zorgen te maken over de volgorde waarin de opdrachten worden uitgevoerd. Maar wat is een programma dan wel? Een programma bestaat voor het grootste deel uit de definitie van functies (in een functionele taal) of relaties (in een logische taal). We beperken ons nu even tot functionele talen. Die functies zijn vergelijkbaar met Pascal/C/Java-functies, alleen mag er in de body van die functies alleen maar een return-opdracht staan. Het hoofdprogramma bestaat uit de aanroep van één enkele functie, waarvan dan de waarde berekend wordt. Maar dat is eigenlijk niets nieuws: ook in C/Java bestaat het hoofdprogramma uit de aanroep van de main-functie. Het begrip waarde moet je daarbij ruim zien: het resultaat van zo’n functie zou bijvoorbeeld een array van characters kunnen zijn, zodat het programma wel degelijk in staat is tot verwerking van iets ingewikkelders dan een losse getalswaarde. Als voorbeeld bespreken we op de volgende pagina’s enkele aspecten van de functionele taal Haskell.

Het aardige van functionele programma’s is dat ze ideeën zo mooi compact kunnen uitdrukken, zonder veel notationeel gedoe. Neem bijvoorbeeld de functie even, die bepaalt of zijn parameter deelbaar is door twee (en dus een even getal is). In Java is die functie gemakkelijk te schrijven: de body bestaat uit een enkele return-opdracht die de gewenste test uitvoert. In Haskell is zelfs dat woord “return” niet nodig, omdat de body altijd uit alleen maar de resultaat-expressie bestaat. Ook de accolades om de body zijn niet nodig, omdat de body één enkele expressie is. En nu we toch aan het bezuinigen zijn: de haakjes rond de parameter zijn ook niet nodig. Het even-zijn van x is simpelweg de uitkomst van de test “x%2==0”, en dat kun je dan ook direct zo opschrijven. De types van parameter en resultaat worden in Haskell in een aparte kopregel opgeschreven. Het symbool “::” dient daarbij uitgesproken te worden als “heeft het type”.

29

Ook in funtionele talen ontkomen we niet aan het begip “keuze”. Maar bij het ontbreken van opdrachten is dat niet een voorwaardelijke opdracht, maar een voorwaardelijke functie-definitie. In Haskell is er een speciale notatie voor zo’n voorwaardelijke functie-definitie. Voorafgaand aan de “=” die in het midden van elke functiedefinitie staat mag, achter een verticale streep, een voorwaarde staan. In één functiedefinitie mogen meerdere voorwaarden met bijbehorende resultaatwaarde staan. Als je al die voorwaarden netjes onder elkaar zet, kun je ook gemakkelijk overzien of je niet een situatie vergeten bent.

30

In Haskell is er geen aparte constructie voor het begrip “herhaling”. Maar dat is ook helemaal niet nodig, want we hebben al functies en keuze, en met behulp van recursie is daarmee ook een vorm van herhaling te maken. Recursie is in functionele talen niet iets bijzonders, maar een zeer veelgebruikt mechanisme. Op deze manier kan bijvoorbeeld een machtsverhef-functie gemaakt worden. Anders dan in Haskell is er geen hulpveriabele nodig, noch een tellertje. We specificeren gewoon direct dat de uitkomst 1 is als de parameter 0 is, en anders moet de functie recursief worden aageroepen en de uitkomst nog eenmaal met x vermenigvuldigd worden. Een aardigheidje van Haskell is dat je naast functies ook infix-operatoren zelf mag definiëren. Zo kan de machtsverhef-functie als machtsverhef-operator gescheven worden. Een andere bijzonderheid is te zien in de alternatieve formulering van de operatordefinitie. We zien hier de expressie n+1 staan op de plaats van de formele parameter. Dat is raar, want we zijn op die plaats een declaratie gewend! Toch heeft dit betekenis. Zouden we bijvoorbeeld 3^6 aanroepen, dan zorgt de compiler ervoor dat x de waarde 3 krijgt (zoals gebruikelijk), en dat n+1 de waarde 6 krijgt, en dus n de waarde 5. Die waarde van n kunnen we direct gebruiken aan de rechterkant van de functiedefinitie. Ook constanten zijn toegestaan op de plaats van de formele parameter. In het voorbeeld wordt zo het geval dat de exponent gelijk is aan 0 afgehandeld.

Om grotere hoeveelheden informatie te kunnen verwerken dan losse getallen, kennen functionele talen ook datastructuren. Een zeer belangrijke is de lijst. (De eerste functionele taal dankt daar ook zijn naam aan: Lisp is een afkorting van “List Processor”). Een lijst bevat 0 of meer elementen. Een lijst zonder elementen kun je in Haskell aanduiden met [ ], een lijst met elementen kun je opbouwen met gebruikmakeing van de operator : , die een nieuw element op kop van een al bestaande lijst zet. Door herhaalde toepassing van : kun je de lijst zo lang maken als je wilt. Functies die een lijst als parameter hebben, bestaan vaak uit twee helften: een regel specificeert wat de uitkomst is als de parameter toevallig de lege lijst is (dit is weer een geval waarbij een constante dienst doet als formele parameter, net als in de definitie van x^0 in het vorige voorbeeld). Is de lijst niet leeg, dan is hij ontstaan door met de operator : een element x op kop te zetten van een lijst xs. Let ook op de manier waarop in het voorbeeld het type van de parameter wordt aangegeven: [Int] is het type “lijst met elementen van type integer”, niet te verwarren met een expressie als [3] (“de lijst met als enige element 3”).

Voor sommige functies die op lijsten werken is het niet van belang wat het type van de elementen is. De functie lengte bijvoorbeeld, die het aantal elementen van een lijst telt, kan dat doen op lijsten van integers, maar ook op lijsten van characters of wat dan ook. In Haskell kan het type van dergelijke polymorfe functies worden aangeduid met behulp van type-variabelen. Dit is eigenlijk een heel voor de hand liggen principe, en het is dan ook verbazingwekkend hoe lastig een vergelijkbare functie te schrijven is in de bekende imperatieve talen. In Pascal kan het helemaal niet, in C++ is er een speciale template constructie die niemand begrijpt. In Java kun je objecten van verschillend type alleen in een array onderbrengen als je er een array van Object-ojecten van maakt. Op het moment dat je specifieke eigenschappen van zo’n array-element wilt gebruiken, moet je dat object met een cast weer converteren tot het gewenste type. De controle of dat geoorloofd is wordt dan run-time uitgevoerd, iets wat een verslechtering is ten op zichte van compile-time typecontrole.

31

In een functionele taal is een functie een “waarde” met dezelfde rechten als iedere andere waarde. Zo kan een functie bijvoorbeeld ook als parameter worden meegegeven aan een andere functie. Let wel, de functie als geheel; niet het resultaat van de aanroep van de functie. Een mooi voorbeeld hiervan is de functie die meestal map wordt genoemd. Deze functie heeft twee parameters, waarvan de eerste zelf een functie is, en de tweede een lijst is. Het resultaat van de functie is ook een lijst. Dat staat ook duidelijk te lezen in de typerings-regel van de functie. Bovendien is hier te zien dat de map polymorf is: de functie-parameter mag een willekeurige functie zijn van a naar b, mits de lijst-parameter dan een lijst van a’s is; het resultaat zal dan een lijst van b’s zijn. De functiedefinitie splitst de gevallen uit dat de lijst leeg is of niet. Bij een lege lijst is het resultaat ook leeg; anders wordt de functie-parameter op het eerste element toegepast, en map recursief aangeroepen op de overige elementen. Netto effect: de functie-parameter wordt op alle elementen van de lijst-parameter toegepast. Later kun je de map-functie gebruiken om alle elementen van een bepaalde lijst te bewerken. Het is een beetje te vergelijken met een for-opdracht in een imperatieve taal, met dat verschil dat de for-opdracht hard is ingebouwd, en dat je de mapfunctie zelf kunt maken! Je kunt zo zelf een repertoire van controle-structuren bouwen. De filter-functie is een andere voorbeeld hiervan. Niets ingebouwds aan!

32

Het is opmerkelijk hoe simpel bepaalde algoritmen er uit kunnen zien, als ze eenmaal ontdaan zijn van de notationele ballast die ze bij formulering in de gangbare imperatieve talen hebben. Neem bijvoorbeeld het invoegen van een nieuw element in een geordende lijst. Is de lijst leeg, dan wordt het nieuwe element het enige. Zat er al minstens één element in de lijst, dan hangt het ervan af of het nieuwe element kleiner is dan dat. Zo ja, dan komt het nieuwe element op kop en blijft de rest ongewijzigd; zo nee, dan moet het nieuwe element elders in de staart worden ingevoegd, en blijft het oude element op kop. Sorteren is vervolgens gemakkelijk: een lege lijst is al gesorteerd, en anders voeg je het eerste element op de juiste plaats in in de recursief gesorteerde rest. Met heel eenvoudige middelen kunnen we in de functionele notatie de essentie van het sorteer-algoritme in kwesie doorzien. In een imperatieve formulering met arrays, hulpvariabelen, geneste for-opdrachten, parameter-mechanismen en wat dies meer zij wordt het begrip toch al snel vertroebeld.

Hier is nog een ander sorteer-algoritme. Een lege lijst is vanzelf gesorteerd. Anders is er een eerste element x en een rest xs. We kunnen de lijst xs in twee delen splitsen: de elementen die kleiner zijn dan x, en de elementen die groter zijn dan x. Deze twee helften kunnen we bepalen met twee aanroepen van de functie filter. De twee helften sorteren we allebei met een recursieve aanroep van sort, en vervolgens plakken we de resultaten aan elkaar met de standaard-operator ++, waarbij we het element x in het midden zetten. Dit algoritme staat bekend onder de naam quicksort, en wie alleen de imperatieve formulering ervan kent zal niet direct willen geloven dat het eigenlijk zo simpel is! Let nog even op de aanroep van filter. De eerste parameter van filter moet een functie zijn met het type a->Bool. Die functie bouwen we door de operator < , die zelf twee parameters heeft en een Bool resultaat, alvast te voorzien van één van zijn twee parameters. Wat overblijft is een functie met één parameter, die we kunnen meegeven aan filter. Dit heet partiële parametrisatie, en komt goed van pas in situaties zoals deze.

Een ander declaratief programmeerparadigma dan het functionele is het logische paradigma. De bekendste taal uit dit paradigma is Prolog (een afkorting van “Programming in Logic”). In Prolog bestaat een programma uit de definitie van een aantal relaties. Er zijn twee manieren om een relatie te definiëren: door het geven van feiten en door het geven van afleidingsregels. In het voorbeeld specificeren we door middel van het opsommen van een aantal feiten welke personen met elkaar in de moeder-relatie staan (of liever gezegd: in de moeder-kind-relatie). Elke database is in wezen een opsomming van feiten: elke tabel specificeert een relatie met zoveel parameters als er kolommen in de tabel staan. Wat niet kan in een database is het geven van afleidingsregels. In het voorbeeld specificeren we dat A de oma is van C als er een B te vinden is zodat A de moeder is van B en B de moeder van C.

33

Het starten van een logisch programma gebeurt door het doen van een query. In het voorbeeld kunnen we bijvoorbeeld vragen wie de oma is van Alex. Het antwoord zal zijn dat Juul in de oma-kleinkind-relatie staat met Alex. Het aardige is, dat het niet uitmaakt op welke plaats de onbekende staat. Je kunt dus ook vragen van wie Mien de oma is. Er zijn twee antwoorden: Mien is de oma van zowel Bea als Griet. Het is zelfs mogelijk om op beide parameter-posities een onbekende te plaatsen. Als antwoord krijg je dan alle oma-kleinkind-combinaties die door middel van de afleidingsregels in het programma afleidbaar zijn. Dit is het meest prominente verschil met het functionele paradigma: functies zijn slechts in één richting te gebruiken en hebben één resultaat; relaties zijn ook in “omgekeerde” richting te gebruiken, en queries kunnen meerdere resultaten hebben. Relaties hebben altijd één parameter meer dan de overeenkomstige functie in een functioneel programma; immers, in de definitie van de relatie neemt het resultaat van de functie ook een parameter-positie in.

34

In logische programma’s kun je relaties gebruiken om nieuw relaties te definiëren. Zo kun je bijvoorbeeld een tante-relatie definiëren met behulp van de oma- en moeder-relatie: T is de tante van neefje/nichtje N als er een grootmoeder X is die de moeder is van T en tegelijkertijd de oma van N. Op deze manier is de relatie echter te ruim gedefinieerd: iemands eigen moeder zou volgens deze definitie ook als “tante” beschouwd worden, en dat is niet de bedoeling. Dit soort uitzonderingen worden nogal eens over het hoofd gezien (het is ook een rijke bron van raadseltjes). In een logisch programma komen ze echter keihard aan het licht. Om de definitie te repareren moeten we gebruik maken van de not-operator van Prolog. En daarmee begeven we ons op glad eis: de voorwaarde stelt dat T niet de moeder van N mag zijn. De computer controleert of dit het geval is – althans, op grond van de kennis die in het programma aanwezig is. En daar zit een belangrijk probleem: de not-operator werkt alleen zoals je zou verwachten indien de closed world assumption geldt: alle relevante feiten zijn in het programma gemodelleerd. De alternatieve formulering, die gebruikt maak van de “ongelijk”-operator, kent dezelfde restrictie.

Reflectievragen (de nummers refereren aan de nummers van de dia’s, tevens bladzijden in dit boekje) 4. Welke concrete componenten van een moderne computer zijn direct als geheugen te beschouwen? Welke op een enigszins gekunstelde wijze ook? Waarom is het niet correct om een chip zoals de Pentium puur als “processor” te omschrijven?

15. In Pascal wordt onderscheid gemaakt tussen procedures en functies. Hoe worden deze twee respectievelijk in C genoemd? Een Java-methode is niet precies hetzelfde als een C-functie. Wat is in Java het precieze equivalent van een Cfunctie? 16. In C en Java bestaat er toch ook een return-opdracht. Wat is daarvan de betekenis?

5. Welke types kunnen er nog meer zinvol zijn? Ligt de codering van een bepaald type eenduidig vast? Zo ja, hoe dan; zo nee, ken je voorbeelden van types waarvoor verschillende coderingen gebruikt worden?

18. Kan een lokale variabele worden gebruikt om bij een eerste aanroep een waarde te bewaren, om die bij een latere aanroep weer terug te vinden en verder te bewerken (bijvoorbeeld: een variabele die bijhoudt hoe vaak een functie is aangeroepen)? Zo ja, wat is dan de waarde van die variabele bij de eerste aanroep; zo nee: hoe kun je dit dan wel doen?

9. Welke connotaties worden opgeroepen door de variabele-namen x, y, i, j, c, h, n, f, temp, max, hulp, foo, aap? Zijn er in je eigen vakgebied variabele-namen die een vaste betekenis hebben?

19. Bekijk het voorbeeld “Namensorteren” in paragraaf 7.6 van deel 1 van het EduActief-boek. Welk bezwaar kent dit programma? Hoe kan het verbeterd worden?

10. Strings worden met een speciaal symbool begonnen en geëindigd. Hoe moet dat als je dat speciale symbool zelf in een string wilt opnemen? In diverse talen zijn er verschillende oplossingen voor gekozen. Welke ken je?

20. Kun je in de body van een functie een toekenning doen aan een variabele die als parameter is meegegeven? Is dat zinvol? Is dat wenselijk?

12. Vermenigvuldigen gaat voor optellen. Daarom heeft a*a+b*b de betekenis (a*a)+(b*b), ook als je die haakjes niet opschrijft. Deze gewoonte is gegroeid, omdat deze betekenis het meest waarschijnlijk is, en je dus alleen in uitzonderingsgevallen met haakjes hoeft aan te geven dat je (a*a+b)*b bedoelt. Hoe zit het met de prioriteit van de == operator ten opzichte van + en * ? En met de prioriteit van de logische “en” en “of”-operator? Wat is het handigst? Hoe is dit in je favoriete taal geregeld? En hoe moet herhaald gebruik van dezelfde operator worden geïnterpreteerd, zoals 1-2-3 of 1/2/3 of x=y=z ? 13. De huisstijl van Microsoft voor het schrijven van Windows-programma’s schrijft voor dat aan de naam van variabelen het type is af te lezen. Zo begint een integer altijd met de letter “n” (bijvoorbeeld nAantal), een pointer met de letter “p”, en een string met de letters “lpsz” (bijvoorbeeld “lpszNaam”), omdat het een “long pointer to string with zero termination” gaat. Wat moeten we daarvan vinden? 14. In C en Java mag je schrijven: int x = 0; . Is dit een declaratie of een opdracht? Wat zijn hiervan de didactische consequenties?

21. Welke ambigue situatie onstaat er, als default-parameters ook in het midden van de parameterlijst zijn toegestaan? 22. Welke packages kent Java zoal, en welke klassen zijn in de diverse packages geplaatst? 25. Een gevaar van while-opdrachten is dat de voorwaarde altijd maar waar blijft, en de computer dus steeds maar bezig blijft met het uitvoeren van de body ervan. Zijn daar nuttige toepassingen voor? Kun je een while-opdracht schrijven die gegarandeert “blijft hangen”? Kan een compiler waarschuwen voor dit soort while-opdrachten? 26. Hoe kun je de for-opdracht van C en Java simuleren met behulp van een whileopdracht? 27. Hoe zou je iets kunnen zeggen over de correctheid van een while-opdracht? 28. Stel dat V een voorwaarde is bij de uitvoering van een while-opdracht. V is een logische (Boolean) expressie, die “waar” of “onwaar” kan zijn. Welke logische 35

expressie geldt in Pascal direct na afloop van de while-opdracht in ieder geval? Is dat in Java ook zo? 29. Een procedure levert geen resultaatwaarde op. Hoe kan een procedure dan toch blijvende resultaten tot gevolg hebben, m.a.w.: hoe kun je merken dat een procedure aangeroepen geworden is geweest? 30. Kun je in een (niet-void) functie iets printen? Zo nee, waarom niet; zo ja, is dat een goed idee? 31. Wat kun je je voorstellen bij een “terugkeerpositie”? Hoeveel ruimte neemt zo’n stack in het geheugen in? 32. Wat gebeurt er met de lokale variabelen van een functie, als deze functie zichzelf recursief aanroept, en er dus een nieuwe incarnatie onstaat met diezelfde variabelen? 33. Hoe ziet in C of Java een for-opdracht die een array behandelt er typisch uit? 34. Hoe is de uitspraak van het woord “boolean”? En van “bool”? En van “char”? 35. Kan een van de velden van een record van datzelfde recordtype zijn, m.a.w. bestaan er “recursieve” records? Zo ja, is daar een toepassing voor; zo nee, waarom niet? 36. Het gebruik van abstracte datatypes had het millenium-probleem kunnen voorkómen. Hoe?

43. In C en C++ is het in principe ook mogelijk om een pointer naar een pointer te maken. Is daar een toepassing voor? Kan dit in Java ook? 44. In C en C++ is het mogelijk om een pointer “op te hogen” (met de notatie “p+ +”), en zelfs om ermee te rekenen (“p=p+5”). Wat is daarvan een toepassing? Waarom is dit in Java verboden? 45. Waarom staan pointers in C en C++, in tegenstelling tot in Java, bekend als “onveilig”? 46. Stel dat in de getekende recursieve datastructuur in elk object een pointer genaamd “next” naar het volgende object wijst, en er daarnaast een integer genaamd “data” bestaat. Schrijf een functie met twee parameters die nagaat of een gegeven integer (eerste parameter) ergens in een gegeven lijst (tweede parameter) voorkomt. 48. Beschouw een niet-windows programma, dus een programma dat invoer krijgt vanaf een toetsenbord, en tekstuitvoer print op een scherm. Hoe kan zo’n programma worden beschouwd als wiskundige functie, d.w.z. wat zijn de types van parameter en resultaat (of, in wiskunde-jargon, wat zijn het domein en het bereik)? Hoe zit dat voor window-gebaseerde programma’s? 49. Hoe kun je in Java het symbool “=” didactisch verantwoord uitspreken? En in Haskell? En het symbool “==”? 50. Hoe luidt de definitie van de “absolute waarde” functie in Haskell?

37. In welke zin kan het gebruik van ADT’s de correctheid van programma’s bevorderen?

51. Waar moet je op leteen bij het schrijven van een recursieve functie? En bij het gebruik van een while-opdracht?

38. Methoden in Java die zonder parameter worden gedeclareerd, hebben impliciet dus tóch een parameter. Hoe kan daaraan in de body worden gerefereerd?

52. Wat is in Haskell het type van de operator : ? En van de lege lijst [ ] ?

39. Op welke manier kunnen in Java de attributen van een object worden beschremd tegen onbevoegd gebruik? 42. Wat kun je jeconcreet voorstellen bij een “pointer”? Hoeveel ruimte neemt zo’n pointer in het geheugen in? Is het mogelijk om de “waarde” van een pointervariabele (dus niet van het object waar die naar wijst) af te drukken? Te testen op gelijkheid?

36

53. Kun je in Java een array van arrays maken? Zijn al die arrays dan even lang, of kunnen ze variëre in lengte? Hoe zit dat in Haskell? Kun je ook lijsten van lijsten van lijsten maken? Zijn daar toepassingen voor? 54. Schrijf een Haskell-functie die alle getallen in een lijst bij elkaar optelt (en 0 oplevert bij een lege lijst). Kun je de functie generaliseren, zodat er in plaats van optelling een andere, als parameter te specificeren operator gebruikt wordt (en een,

als extra parameter te specificeren, neutrale waarde voor het geval van de lege lijst)? Wat is het type van die functie?

Praktijkopdrachten

55. Probeer sort te schrijven als aanroep van de hierboven geschreven functie.

Bereid met z’n tweeën een presentatie voor van circa 20 minuten, liefst ondersteund door Powerpoint-plaatjes en/of “live” voorbeelden. Als doelgroep gelden je collega’s; het nivo hoeft niet hoger te liggen dan je bij leerlingen zou gebruiken. Kies één van onderstaande casus, en plaats ze in de context van de bespreking van programmeerparadigma’s. Leg ook een relatie tot de doelen van programmeeronderwijs, zoals je die bijvoorbeeld in de CITO-syllabus aantreft. Je kunt je daarbij laten inspireren door de gestelde vragen, al hoeven niet alle vragen aan de orde te komen. Het is niet nodig dat het gehoor tot in de details de taal uit de besproken casus leert kennen (al kan een voorbeeld natuurlijk heel verhelderend werken).

56. Een functie met twee parameters heeft het type a->b->c . Dat lijkt een enigszins merkwaardige notatie; logischer lijkt iets als (a,b)->c . Verklaar waarom, in verband met de mogelijkheid van partiële parametrisatie, de notatie toch zinvol is. Moet a->b->c begrepen worden als (a->b)->c of als a->(b->c) ? 57. Een relatie heeft altijd een parameter meer dan de overeenkomstige functie. Verklaar dit.

Leerdoelen van deze opdracht zijn: • het kunnen hanteren van de concepten uit de verschillende paradigma’s • het zelfstandig eigen kunnen maken van de hoofdzaken van een nieuwe programmeertaal (zonder die taal in detail te leren), op grond van herkenningspunten die de cursus heeft gegeven • het doceren van informatica-theorie, en het daarbij hanteren van ITpresentatiemiddelen daarbij • het plaatsen van leerstof binnen de doelen van informaticaonderwijs 1.

2.

Spreadsheets. Bekijk een spreadsheet, bijvoorbeeld Microsoft Excel. Dit is op te vatten als programmeertaal. Wat is als een programma te beschouwen, en hoe wordt het uitgevoerd? Tot welk paradigma behoort deze programmeertaal? Zijn er variabelen; hoe verloopt de naamgeving daarvan, en wat kun je er vanuit het programma mee doen? Zijn er functies, en kun je die zelf ook maken? Is de taal getypeerd, en wat gebeurt er dan bij typeringsfouten? Hoe verloopt keuze? Is er herhaling, recursie? Wat komt overeen met een “array”, en hoe verloopt indicering daarin? Hoe programmeer je een opzoek-tabel? Er is een pakket met programmeeropdrachten in spreadsheets beschikbaar. Gebruik tenminste één van die opdrachten om daar je verhaal mee te illustreren. Postscript. Postscript is een taal die in eerste instantie bedoeld is om documenten vorm te geven (net als HTML). Maar Postscript is ook te beschouwen als programmeertaal. Wat is een programma, en hoe wordt het uitgevoerd? Tot welk paradigma behoort Postscript? Zijn er variabelen, en kun je die inspecteren en veranderen? Hoe kunnen expressies worden uitgerekend? Hoe verloopt keuze en herhaling? Kun je procedures en functies maken, en kunnen deze parameters krijgen? 37

3.

4.

5.

6.

7.

8.

9.

38

Haskell versus wizards. Bekijk de Haskell-functies map, filter, foldr, en zip. Hoe zou je vergelijkbare zaken in Java aanpakken? In Java schrijf je foropdrachten vaak op een routinematige manier. Kun je tot een klassificatie komen van “typische for-opdrachten”, steunend op het begrippenkader van Haskell? In sommige Java-compilers zijn “wizards” voorhanden om routineus samengestelde stukjes programma voor je te schrijven. In welk opzicht schiet Java als taal tekort, dat de behoefte aan dergelijke wizards zich doet voelen? Diagrammen. Bij het ontwerpen van programma’s wordt soms gebruikt gemaakt van grafische weergaves van de opzet van het programma. Bekende typen diagrammen zijn: flow-charts, structuur-diagrammen, E-R-diagrammen, UML-ontwerpen. Op welke programmeerparadigma’s zijn deze (en eventuele andere) diagramtypen toegesneden? Biedt het gebruik ervan didactische voordelen, en zo ja welke? (Let op, deze vraag dient vooral kritisch beantwoord te worden. Sommige veelgebruikte diagramtypen bieden bepaald geen voordelen, andere wel!) Lay-out. Bekijk programma’s in Pascal, C, C++ en Java uit diverse bronnen. Welke lay-out conventies zijn in gebruik voor blokstrucktuur (begin/end respectievelijk accolades) en de naamgeving van variabelen e.d.? Welke daarvan verdient uit didactisch oogpunt de voordelen? Hoe kan commentaar worden geschreven in deze talen, en op welke plaats gebeurt dat vaak/zou dat het beste kunnen gebeuren? Ontleden in Haskell. Grammatica’s zijn een goede manier om een taal te beschrijven. Het opstellen van zo’n grammatica is echter een theoretische aangelegenheid, en daarna heb je nog niet iets werkends in handen. Bekijk welke functies in Haskell geschreven kunnen worden om het gebruik van grammatica’s te ondersteunen. Familierelaties in Prolog. De documentatie van de programmeertaal Visual Prolog geeft een groot aantal voorbeelden van toepassingen van deze taal. Verzamel tenminste vijf voorbeelden van programma’s waarin familierelaties worden beschreven, beschrijf de afleidingsregels die daarin gebruikt worden en geef voorbeelden van relaties die niet of veel moeilijker binnen dit kader geformuleerd kunnen worden. De Prolog-moordzaak. Eén van de toepassingen van Prolog is het oplossen van puzzels. Zo bevat één van de voorbeelden bij Visual Prolog de beschrijving van allerlei feiten die te maken hebben met een moordzaak. Ook allerlei redeneringen die je zou kunnen gebruiken om de dader te vinden zijn in het programma opgenomen. Zoek uit welke in Prolog ingebouwde mechanismen het mogelijk maken zo inderdaad de moordzaak op te lossen. Practica in LOGO. De programmeertaal Logo wordt vaak gebruikt bij inleidend programmeeronderwijs. Het gebruik van de “turtle graphics” wordt door sommigen gezien als een attractieve manier om de eerste concepten van

het werken met een programmeertaal te behandelen. Anderen hebben het gevoel dat het gaat om “programmeren op je hurken”. Onderzoek twee inleidende practica in Logo. Geef aan welke doelen van programmeeronderwijs er wel en welke niet zijn te realiseren met deze practica, en plaats Logo binnen de programmeerparadigma’s die in de cursus aan de orde zijn geweest. 10. Simuleer een busrit. Uit de inleidende programmeercolleges van de Nijmeegse universiteit (prof. Koster) is de opdracht afkomstig om op basis van een aantal bouwstenen de simulatie te maken van een busrit. Van deze opgave is inmiddels een Java-toepassing bekend. Gegeven zijn een aantal objecten en hun methodes; te schrijven is de methode main om een en ander aan elkaar te knopen. Presenteer je uitwerking en vertel iets over de voor- en nadelen van een dergelijke practische opdracht. 11. Op contract werken. Gegeven is een programma waarmee een voorspelling kan worden gedaan van de uitslag van de Amerikaanse presidentsverkiezingen. In tegenstelling tot opdracht 10 is hier het globale programma reeds aanwezig, even als een aantal functies. Van de andere functies is alleen de header en het commentaar bekend. Er is een contract geformuleerd waarin staat aangegeven hoe je de betreffende functie moet laten werken en samenwerken met de andere functies. Je moet deze functies bouwen om zo het hele programma aan de praat te krijgen. Ook deze opdracht is naar Java omgebouwd en daar beschikbaar. 12. Tentamens programmeren. Beschikbaar zijn een aantal tentamens die na inleidend programmeeronderwijs aan studenten in het HBO zijn voorgelegd. Behandel in je voordracht enkele vragen uit deze tentamens, vooral gericht op de doelen van programmeeronderwijs in het voortgezet onderwijs. Zijn er ook doelen die niet getoetst worden? Zo ja, geef daarvoor alternatieve toetsmogelijkheden aan.