Inhoud leereenheid 16
Imperatief programmeren Introductie 9 Leerkern 10 1 Sleutelbegrippen 10 2 Pragmatisme 10 3 Case study: C 10 4 Case study: Ada 11 5 Overzicht van concepten in C en Ada 14 Zelftoets 15 Terugkoppeling 16 1 Uitwerking van de opgaven 16 2 Uitwerking van de zelftoets 17
8
OUN
Leereenheid 16
Imperatief programmeren I N T R O D U C T I E
Het imperatieve programmeerparadigma is nog steeds het meest toegepaste paradigma. Het gebruik van Cobol, een van de oudste imperatieve talen. is vandaag de dag zelfs nog groter dan het gebruik van de qua ontwerp veel modernere talen als Pascal, C en Ada. Voor een deel is dit te verklaren uit het feit dat bedrijven destijds veel geld hebben geïnvesteerd in de ontwikkeling van programmatuur en dat de kosten van het ‘onderhouden’ van deze programma’s – het herstellen van fouten en aanpassen aan nieuwe omstandigheden en wensen – al zo’n zestig procent van het totale softwarebudget opslokken. Het herschrijven van deze programma’s in een andere programmeertaal is alleen mogelijk als dit budget fors wordt verhoogd. Een tweede verklaring is dat programma’s geschreven in deze talen door de bank genomen efficiënt gebruik maken van de hardware; de talen staan dicht bij de machine en men duidt ze daarom ook wel aan als ‘high‐level‐assemblers’. In de praktijk zien we dat men voor bestaande toepassingen zo lang mogelijk de oudere talen blijft hanteren en de nieuwere talen (zowel imperatieve talen als niet‐imperatieve talen) alleen inzet bij de ontwikkeling van nieuwe toepassingen. In deze leereenheid bekijken we twee bekende representanten van de klasse van conventionele imperatieve talen: C en Ada. Met ‘conventioneel’ bedoelen we hier imperatieve talen die niet specifiek zijn ontworpen voor objectgeoriënteerd programmeren. Op de specifieke verschillen tussen deze beide paradigma’s (imperatief en objectgeoriënteerd) gaan we in leereenheid 18 nader in. LEERDOELEN
Na het bestuderen van deze leereenheid wordt verwacht dat u – vier essentiële kenmerken van een imperatieve taal kunt noemen – aan kunt geven of, en op welke wijze, de hierna genoemde concepten zijn gerealiseerd in respectievelijk C en Ada: typen, expressies, opdrachten, variabelen, declaraties, abstracties, parameters, inkapseling, polymorfie, exceptions – aan kunt geven in hoeverre C en Ada voldoen aan de in de cursus geformuleerde ontwerpprincipes voor een programmeertaal – het verschil kunt aangeven tussen de concepten genericiteit en parametrische polymorfie – aan de hand van de behandelde taalconcepten de sterke en zwakke kanten van C en Ada kunt aangeven. Relatie met het tekstboek In deze leereenheid gebruiken we hoofdstuk 11 van het tekstboek. Het voorbeeld ̒A simple spellchecker̉ dient slechts ter illustratie van de concepten. U kunt volstaan met het globaal doorlezen van de paragrafen
OUN
9
Concepten van programmeertalen
die daarop betrekking hebben, namelijk paragraaf 11.3.8 en paragraaf 11.4.9. Studeeraanwijzingen In deze leereenheid komt uiteraard een aantal C‐ en Ada‐voorbeelden voor. Het is niet de bedoeling dat u dergelijke voorbeelden zelf kunt schrijven, wel moet u deze voorbeelden kunnen begrijpen. Tevens moet u globaal aan kunnen geven op welke wijze een bepaald concept is geïmplementeerd in C of Ada. Gebruik hiervoor tabel 16.1 als richtlijn. De studielast van deze leereenheid is circa 3 uur. L E E R K E R N
1
Opmerking
Kwalificatie‐ principe
Abstractieprincipe
Sleutelbegrippen Geen verdere aanvullingen op het tekstboek. 2 Pragmatisme Geen verdere aanvullingen op het tekstboek. 3 Case study: C Om te beoordelen of de taal voldoet aan de geformuleerde principes, maken we uitsluitend gebruik van de informatie gegeven in het tekstboek. Andere versies of varianten van de taal kunnen uiteraard andere voorzieningen bevatten, waardoor de beoordeling anders zou komen te liggen. Deze opmerking geldt ook voor de andere beoordeelde talen. C kent alleen blokopdrachten, geen blokexpressies (alleen body van een procedure) of blokdeclaraties. De taal voldoet dus niet aan het in leereenheid 4 geformuleerde kwalificatieprincipe: in elke taalconstructie kunnen lokale declaraties worden gemaakt. In leereenheid 5 hebben we het abstractieprincipe geformuleerd: van elke taalconstructie kan een abstractie worden gemaakt, die later kan worden aangeroepen.
OPGAVE 16.1
Voldoet C goed of slecht aan dit abstractieprincipe? Correspondentie‐ C voldoet slecht aan het correspondentieprincipe uit leereenheid 5: elke principe soort declaratie heeft een corresponderend parametermechanisme en omgekeerd. C kent slecht een parametermechanisme: copy‐in. De typedeclaratie en proceduredefinitie in C hebben geen corresponderend parametermechanisme. In het voorgaande zagen we dat C slecht voldoet aan de in de cursus geformuleerde ontwerpprincipes voor een programmeertaal. Daarnaast zijn er op basis van de behandelde taalconcepten meer negatieve punten in het ontwerp van C aan te wijzen (zie opgave 16.2).
10
OUN
Leereenheid 16 Imperatief programmeren
OPGAVE 16.2
a Geef ten minste vijf punten van kritiek op de taal C. b Noem ook een positieve kant van C. 4 Case study: Ada Typevolledigheids‐ Ada voldoet beter aan het typevolledigheidsprincipe dan C. Waarden principe van standaardtypen, samengestelde typen en pointer‐typen mogen alle op dezelfde wijze worden gemanipuleerd. Variabelereferenties mogen we echter alleen als argument van een procedure of functie gebruiken, functies en procedures zelf zijn op geen enkele wijze te manipuleren, ze kunnen zelfs niet als argument worden doorgegeven. Ada kent blokopdrachten en blokdeclaraties (packages), maar geen blokexpressies. De taal voldoet dus niet geheel aan het in leereenheid 4 Kwalificatie‐ geformuleerde kwalificatieprincipe. principe Evenals bij C kunnen we nagaan in hoeverre Ada aan het Abstractieprincipe abstractieprincipe voldoet. OPGAVE 16.3
Voldoet Ada goed of slecht aan het abstractieprincipe? Correspondentie‐ Evenals C voldoet Ada slecht aan het correspondentieprincipe. De principe functie‐ en proceduredeclaratie hebben geen corresponderend parametermechanisme. Het reference‐mechanisme correspondeert niet met een declaratie: Ada kent geen variabeledefinitie. Daar komt nog bij dat een Ada‐implementatie voor samengestelde typen mag kiezen tussen het kopieermechanisme en het definitiemechanisme. OPGAVE 16.4
Gegeven is de volgende procedure in Ada: type Vector is array (1..n) of Float; procedure add(v, w: in Vector; sum: out Vector) is begin for i in 1 .. n loop sum(i) := v(i) + w(i); end loop; end;
a Toon aan dat de procedureaanroep add(a, b, c) het verwachte effect heeft als er voor de parameters gebruik wordt gemaakt van hetzij het kopieermechanisme of het referentiemechanisme. Gebruik in het geval van het kopieermechanisme voor de in‐parameters copy‐in‐parameters en voor de out‐parameter een copy‐out‐parameter. Gebruik in het geval van het referentiemechanisme voor de in‐ parameters, constant‐parameters en voor de out‐parameter een variable‐ parameter. b Toon dat ook voor de aanroep add(a, b, b) en laat zien dat in dat geval aliasing kan plaatsvinden.
OUN
11
Concepten van programmeertalen
Genericiteit en parametrische polymorfie
In Ada kunnen we generieke packages en generieke procedures en functies declareren. Zo op het eerste gezicht lijkt het concept genericiteit (generics) van Ada hetzelfde als de parametrische polymorfie uit leereeenheid 8. Een generieke functie is echter iets anders dan een polymorfe functie en een generiek type is iets anders dan een (geparametriseerd) polymorf type. We laten aan de hand van twee voorbeelden de verschillen tussen beide concepten zien. De volgende polymorfe Haskell‐functie snd mogen we op parameters van verschillende typen toepassen:
Polymorfe versus generieke functies
snd :: (a, b) -> b snd (_, y) = y Hugs> snd (13, True) True Hugs> snd ("Jeffrey", "Watt") "Watt" Hugs>
a en b zijn typevariabelen die elk een nog vrij te kiezen type representeren. In Ada kunnen we de volgende generieke functie snd declareren. generic type a type b function begin return end;
is private; is private; snd (x : a; y : b) return b is y;
a en b zijn hier formele typeparameters (dus geen typevariabelen) met behulp waarvan we een type kunnen doorgeven. Voor we snd kunnen gebruiken, moeten we de generieke functie eerst instantiëren met concrete typen als actuele parameters: function snd_1 is new snd (Integer, Boolean); function snd_2 is new snd (String, String);
Hierna kunnen we van snd_1 en snd_2 gebruikmaken: snd_1 (13, True) = True snd_2 ("Jeffrey", "Watt") Polymorfe versus generieke typen
=
"Watt"
In feite creëren we eerst twee afzonderlijke functies, een voor de typen Integer en Boolean en een voor het type String, en er is dus geen sprake van één (polymorfe) functie die op parameters van verschillende typen mag worden toegepast. In leereenheid 8 is in voorbeeld 8.10 in Haskell het volgende polymorfe type List gedefinieerd samen met onder andere de functies head en tail met de volgende specificaties: data List a = Nil | Cons (a, List a) head :: List a -> a tail :: List a -> List a
12
OUN
Leereenheid 16 Imperatief programmeren
In de definitie van List geeft de typevariabele a aan dat het type van de elementen van List willekeurig kan zijn. De functies head en tail zijn polymorfe functies, het maakt voor deze functies niet uit wat het type van de lijstelementen is. Een generieke package‐declaratie voor het type List (een generiek abstract type) kan in Ada als volgt luiden. generic type a is private package list_type is type List is limited private; function cons (x : a; xs : List) return List; function head (xs : List) return a; function tail (xs : List) return List; private type Node; type List is access Node; type Node is record element : a; rest : List; end record; end list_type;
a is hier weer een typeparameter. Voor ieder verschillend elementtype van List moet een nieuwe package worden geïnstantieerd met dat elementtype als actuele parameter, bijvoorbeeld: package list_type_int is new list_type (Integer); package list_type_char is new list_type (Character);
Deze beide instantiaties resulteren in twee verschillende lijsttypen (namelijk list_type_int.List en list_type_char.List) en in twee verschillende functies voor zowel head als tail (list_type_ int.head en list_type_char.head, idem voor tail). Er is dus geen sprake van één (polymorf) type List en evenmin van polymorfe functies head en tail. Aanvulling bij voorbeeld 11.12
Hoewel we de naam swap gebruiken voor waarden van een willekeurig type, is ook hier geen sprake van een polymorfe procedure. Door verschillende instantiaties van de generieke procedure krijgen we immers verschillende ‘gewone’ procedures met elk een eigen naam en parametertype.
OPGAVE 16.5
Maak van exercise 11.4.4 op bladzijde 294 in het tekstboek de vragen a en b. Aanwijzing: een blokopdracht heeft in Ada de volgende vorm. declare
declaraties
begin
opdrachten
end;
OUN
13
Concepten van programmeertalen
Kanttekeningen bij Ada
taalconcept
Ada kent meer geavanceerde taalconcepten dan C, onder meer inkapseling en exceptions. Dat is ook logisch, gezien het feit dat de taal tien jaar later dan C is ontworpen. We kunnen ons echter afvragen of het ontwerp van Ada, gezien in het licht van de in de blokken 1 en 2 behandelde taalconcepten, inderdaad zo goed is als men vaak suggereert. In de voorgaande paragraaf zagen we reeds dat Ada aan de vier ontwerpprincipes niet volledig voldoet. Daarnaast zijn nog de volgende punten van kritiek te noemen: – polymorfie is niet mogelijk; weliswaar kent Ada het concept generics, maar zoals we in deze paragraaf aangeven, is dit wat anders dan parametrische polymorfie en kunnen we het hoogstens zien als een soort surrogaat hiervoor – Ada kent weliswaar contextafhankelijke overloading van procedures, functies en operatoren, maar mist de fundamentele aanpak van overloading met typeklassen à la Haskell – net als in C kunnen recursieve typen alleen met behulp van pointers worden gemaakt – naast garbage collection kent Ada ook de mogelijkheid om zelf expliciet aan te geven dat een heap‐variabele niet langer nodig is (‘unchecked deallocation), hetgeen het gevaar van dangling references met zich meebrengt – naast escape‐opdrachten en exceptions is er ook nog een (overbodige) goto‐opdracht – de taal is groot en mede daardoor lastig te leren en te interpreteren. 5 Overzicht van concepten in C en Ada In tabel 16.1 zetten we de concepten die al dan niet in Ada en C zijn te vinden, op een rijtje . TABEL 16.1 Taalconcepten in C en Ada (x = aanwezig) C
Ada
numerieke typen
x (integer, floating-point)
karakters boolean enumeration
– – x
x (integer, floating-point, fixed-point) x x x
samengestelde typen
cartesisch product disjuncte vereniging functieruimte recursieve typen subtypen
x x x – –
expressies
toekenningsexpressie functieaanroep conditionele expressies iteratieve expressies blokexpressies
x x x – –
– x – – –
variabelen
globale variabelen locale variabelen heap-variabelen allocator
x x x (low-level) x (malloc)
x x x x (new)
primitieve typen
14
OUN
(structure) (union type, untagged) (array) (via pointers)
x x x – –
(record) (discriminated record) (array) (via pointers) (ja, maar is geen type)
Leereenheid 16 Imperatief programmeren
opdrachten
lege opdracht toekenningsopdracht procedureaanroep sequentiële opdracht conditionele opdracht iteratieve opdracht blokopdracht sequencer jump exception handling
x – – x x x x x (break, continue, return) x –
x x x x x x x x (exit, return) x x
globale typedefinities globale variabelen functiedefinities locale declaraties locale variabelen statische variabelen
program units met procedures, packages, generieke units
x – (via void)
x x
copy-in geen reference parameter (wel via pointer) functies geen eersteklas-waarden
in-parameter in-out-parameter out-parameter procedures geen eersteklas-waarden voor samengestelde waarden keus tussen by copy of by reference
overloading
–
x
generieke abstractie
–
x (generieke packages, generieke proceduren)
compilatie
onafhankelijke
gescheiden
binding, scope
abstractie van proceduren
functie procedure
parametermechanismen
Z E L F T O E T S
l Noem enkele essentiële kenmerken van een imperatieve programmeertaal. 2 Noem enkele taalconcepten die C niet biedt en Ada wel. 3 Wat is het kenmerkende verschil tussen een polymorfe functie in Haskell en een generieke functie in Ada? 4 Geef ten minste vier punten van kritiek op de taal Ada.
OUN
15
Concepten van programmeertalen
T E R U G K O P P E L I N G
Uitwerking van de opgaven In C kunnen we alleen abstracties maken van een expressie (functie) en een opdracht (functie met terugkeerwaarde van type void). De taal kent geen abstracties van bijvoorbeeld een variable‐access (selector‐ abstractie), declaratie (generieke abstractie) of type (abstract type) en voldoet dus slecht aan het abstractieprincipe. a Naast het slecht voldoen aan de ontwerpprincipes voor een taal, kunnen als negatieve punten van C verder worden genoemd: – het typesysteem is zwak – C kent geen abstractie van gegevens, geen generieke abstracties, geen exceptions – C heeft een beperkt aantal primitieve typen – C ondersteunt geen directe recursie – opdrachten kunnen in onleesbare vorm geformuleerd worden – door de onafhankelijke compilatie kan de consistentie in gevaar komen. b C is een populaire programmeertaal die uitstekend gebruikt kan worden voor het schrijven van efficiënte software op systeemniveau. In Ada kunnen we abstracties maken van een expressie (functie), een opdracht (procedure), een type (abstract type) en een declaratie (generiek package), echter niet van een variable‐access (selector). Hiermee voldoet de taal in redelijke mate aan het abstractieprincipe. a We bekijken eerst de aanroep add(a,b,c) voor beide mechanismen. 1 v en w zijn copy‐in‐parameters, sum is een copy‐out‐parameter: Bij aanroep van add worden de lokale variabelen v, w en sum gecreëerd en worden de waarden van de actuele parameters a en b toegekend aan respectievelijk v en w. Vervolgens wordt in de procedure de waarde van sum (de som van v en w) bepaald en bij beëindiging van add wordt deze waarde toegekend aan c. De waarden van a en b zijn niet gewijzigd. 2 v en w zijn constant‐parameters en sum is een variable‐parameter: Bij aanroep worden de namen v, w en sum gebonden aan respectievelijk a, b en c. In de procedure wordt vervolgens de waarde van sum (= c) gewijzigd in de som van a en b. De waarden van a en b blijven ongewijzigd. b We bekijken nu de aanroep add(a,b,b) voor beide mechanismen. 1 v en w zijn copy‐in‐parameters, sum is een copy‐out‐parameter: Bij aanroep van add worden de lokale variabelen v, w en sum gecreëerd en worden de waarden van de actuele parameters a en b toegekend aan respectievelijk v en w. Vervolgens wordt in de procedure de waarde van sum (de som van v en w) bepaald en bij beëindiging van add wordt deze waarde toegekend aan b. De waarde van a is niet gewijzigd; de waarde van b is gewijzigd in de som van a en de oude waarde van b. 2 v en w zijn constant‐parameters en sum is een variable‐parameter: Bij aanroep wordt de naam v gebonden aan a en de namen w en sum aan b. Vervolgens wordt in de procedure de waarde van sum (de som van v en w) bepaald. Hierdoor verandert tevens de waarde van w (sum en w zijn aliassen). Deze aliasing is in dit geval niet erg, omdat w in de procedure niet meer wordt gebruikt. Bij beëindiging van add is de 1
16.1
16.2
16.3
16.4
16
OUN
Leereenheid 16 Imperatief programmeren
waarde van a niet gewijzigd; de waarde van b is gewijzigd in de som van a en de oude waarde van b. 16.5 a Instantiatie en aanroep van de generieke procedure kan overal gerealiseerd worden met een blokopdracht: declare procedure swapint is new swap (Integer); begin swapint (a(i), a(I+1)); end;
1
2
3
4
b Instantiatie en aanroep van een generieke functie kan niet op vergelijkbare wijze worden gerealiseerd omdat Ada geen blokexpressie kent. 2 Uitwerking van de zelftoets – Een imperatieve programmeertaal is gebaseerd op de architectuur van de hardware. – Imperatieve talen kunnen hierdoor in principe efficiënt worden geïmplementeerd. – Een programma in een imperatieve taal bestaat uit een rij opdrachten die in een voorgeschreven volgorde moeten worden verwerkt. – Voor de opslag van waarden worden (veranderbare) variabelen gebruikt die geheugenplaatsen in de computer representeren. – Er bestaat een toekenningsopdracht voor het veranderen van de waarden van deze variabelen. De volgende concepten zijn niet in C aanwezig, maar wel in Ada: – packages (inkapseling) – generieke abstracties – generieke procedures en functies – overloading (door programmeur) – exceptions. Een polymorfe functie is een functie die geen gebruikmaakt van de specifieke eigenschappen van een parameter. De functie kan daarom op waarden van elk type worden toegepast. In het type van de functie komt dit tot uiting in de vorm van typevariabelen. Een generieke functie heeft een typeparameter met behulp waarvan een type kan worden doorgegeven. Voor we de functie op een bepaald type kunnen toepassen, moeten we eerst een instance van de generieke functie creëren voor dat bepaalde type. Voor alle typen waarvoor we de functie nodig hebben, moeten we evenzovele functies creëren met elk een unieke naam; er is dus geen sprake van één polymorfe functie. Als kritiekpunten op de taal Ada kunnen we onder meer noemen: – Ada voldoet aan geen van de ontwerpprincipes volledig – polymorfie is niet mogelijk – Ada kent geen typeklassen à la Haskell – recursieve typen zijn alleen mogelijk met behulp van pointers – de mogelijkheid van ‘unchecked deallocation’ van heap‐variabelen – er is een overbodige goto‐opdracht – de taal is groot en lastig te leren.
OUN
17