Gevorderde Programmeertechnieken Studiewijzer
Opleiding Bachelor of Science in Informatica, van de Faculteit Wetenschappen, Universiteit Antwerpen. Nota’s bij de cursus voor academiejaar 2007 - 2008.
J. Broeckhove Onderzoeksgroep Computationeel Modelleren en Programmeren
Inhoudsopgave
1 Overzicht 1.1 Aanvangscompetentie 1.2 Inhoud . . . . . . . . 1.3 Eindcompetentie . . . 1.4 Lesvormen . . . . . . 1.5 Algemeen . . . . . . 1.6 Studiematerialen . . . 1.7 Evaluatie . . . . . . . 1.8 Contact informatie . . 2 Projectopdracht 2.1 Werkvorm . . . . 2.2 Projectvoering . . 2.3 Record gebaseerde 2.4 Concrete opdracht 2.5 Uitvoeringsplan . 2.6 Evaluatietabel . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
2 2 2 3 3 3 4 4 4
. . . . . . . . . . . . . . filestructuur . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
6 6 6 7 8 10 11
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
HOOFDSTUK
1
Overzicht
1.1 Aanvangscompetentie Zoals de naam van het opleidingsonderdeel aangeeft, moet je beschikken over een aanzienlijke voorkennis in de programmeertaal C++ en daarnaast over een ruime programmeerervaring. Dit zowel op gebied van theoretische kennis als op gebied van praktische vaardigheden.
1.2 Inhoud In deze cursus worden aspecten wordt een grondige studie gemaakt van het generisch programmeren aan de hand van templates in C++ . Het verschil met het interface-implementation model uit de object georinteerde sfeer wordt onderzocht. Vervolgens onderzoeken we function objects, als oplossing voor de rigiditeit van oproepstructuren, en expression templates. Diverse techieken die toelaten generische code te maken zoals sequences en iteratore, traits, policy-based programmeren, meta-programmeren, type functions, , worden behandeld. De technieken moeten in een gentegreerd project, dat ieder jaar een nieuw onderwerp aanpakt, gebruikt worden. Dat project wordt via pair programming uitgevoerd.
1.3. EINDCOMPETENTIE
3
1.3 Eindcompetentie Je bent in staat te discussi¨eren en redeneren over programmacode. Je bent in staat gevorderde taalconstructen, zoals templates in C++, te bestuderen en toe te passen. Dit betekent dat je de technische uitwerking doorziet en dat je de mogelijkheden en beperkingen kan inschatten om zo weloverwogen programmadesign keuzes te maken.
1.4 Lesvormen Het opleidingsonderdeel Gevorderde Programmeertechnieken vertegenwoordigt drie studiepunten met vijftien contacturen voor theoretisch onderricht en vijftien contacturen voor praktijk onderricht. Het theoretisch deel zal een combinatie zijn van hoorcolleges en interactieve sessies waarin aan voorbeeldprogramma’s gewerkt wordt. Deze lessen zullen door de studenten voorbereid moeten worden door de lectuur van delen uit handboeken of uit de cursusnota’s. De lesgever is J. Broeckhove. Bij het praktisch deel wordt gewerkt aan opdrachten die kaderen in de onderwerpen die op dat ogenblik aan de orde zijn bij de theorie. Hierbij wordt een zekere zelfstandigheid en initiatief van de student verwacht. Het werk zal in groepen van twee studenten uitgevoerd worden en bestaat uit het uitwerken van programma’s. Daarnaast wordt er een project opdracht voorzien waarin alle aspecten uit het theoretische luik samen toegepast moeten worden. De begeleider is K. Vanmechelen.
1.5 Algemeen De kalender voor het opleidingsonderdeel ziet er als volgt uit: lesweek 1:
Inleiding
lesweek 2:
Templates (I)
lesweek 3:
Templates (II)
lesweek 4:
Generisch programmeren (STL) + Traits
lesweek 5:
Practicum
lesweek 6:
Practicum
lesweek 7:
Policy-gebaseerd programmeren & Practicum
lesweek 8:
Practicum
lesweek 9:
Metaprogrammeren & Practicum
lesweek 10:
Vrij
lesweek 11:
Practicum
lesweek 12:
Practicum
lesweek 13:
Vragenuurtje
1.6. STUDIEMATERIALEN
4
1.6 Studiematerialen De belangrijkste materialen voor het theoretische deel zijn ongetwijfeld: • Het handboek , “The C++ Programming Language”, (Stroustrup, 2000), uitgegeven door Addison-Wesley. Er bestaat ook een Nederlandstalige versie van dit standaardwerk, getiteld “De programmeertaal C++”, (Stroustrup, 2002) van dezelfde uitgeverij. • De nota’s die enerzijds aanvullend materiaal uit andere bronnen aanbrengen en anderzijds selecteren en klemtonen leggen in de stof die in het handboek behandeld wordt. • Voorbeeldprogramma’s voor de verschillende aspecten van template programming. Een deel van deze programma’s worden expliciet behandeld in (Vandevoorde and Josuttis, 2003), maar zijn evenzeer nuttig bij de studie in (Stroustrup, 2000). De broncode wordt bij het begin van de lessen ter beschikking gesteld. In de nota’s zijn artikels opgenomen die aanvullend materiaal behandelen. Daarenboven wordt ook nog geput uit “C++ Templates: The Complete Guide”, (Vandevoorde and Josuttis, 2003), en “Modern C++ Design: Generic Programming and Design Patterns Applied”, (Alexandrescu, 2001).
1.7 Evaluatie De evaluatie bestaat uit een interview dat gebaseerd is op een codeinspectie van je portfolio van uitgewerkte opdrachten. De opdrachten worden individueel met je besproken in ongeveer twintig minuten. Ook voor het deel dat in p”pair programming” werd afgwerkt ben je verantwoordelijk. De vragen spitsen zich toe op de gebruikte technieken, waarom ze gebruikt werden, wanneer ze niet gebruikt kunnen worden, etc. Met andere woorden: een goed ge¨ınformeerde, kritisch kijk op de programmeertechnieken en bijbehorende design keuzes kunnen weergeven. Je mag hierbij alle bronnen raadplegen die je ter beschikking hebt. Uiteraard wordt ook de documentatie bekeken.
1.8 Contact informatie Wie vragen heeft over de leerstof, het studiemateriaal, het examen enzovoort kan die steeds stellen voor, tijdens of op het einde van de les. Wil men buiten de lesuren contact opnemen, dan kan dat ook. Wie vragen heeft over de theoretische leerstof wendt zich bij voorkeur tot de lesgever, namelijk Naam: Jan Broeckhove
1.8. CONTACT INFORMATIE
5
Email:
[email protected] Lokaal: Gebouw G, G205 Voor vragen in verband met de praktijk opdrachten wendt men zich bij voorkeur tot de assistent Naam: K. Vanmechelen Email:
[email protected] Lokaal: Gebouw G, G214 Het is zeker aan te raden eerst een afspraak te maken via email, en daarbij de vraag voor te leggen, zodat het antwoord kan voorbereid worden.
HOOFDSTUK
2
Projectopdracht
De doelstelling is te toetsen of je de concepten en de technieken van het template programmeren doorgrondt, en kan toepassen op een programmeerprobleem.
2.1 Werkvorm Je werkt samen met een collega student. Hierbij wordt het principe van pair programming gehanteerd. Dit houdt in dat je beide op ´e´en PC werkt waarbij persoon A (de driver ) code schrijft terwijl persoon B (de observer ) deze code evalueert. Hierbij wordt beoogd om overleg te stimuleren in zowel de aanpak en het ontwerp van de software, alsook in de finale codering. Na het vormen van de groepen zal er voor de practica een schema worden opgesteld dat bepaald wie voor elke week observer en driver is.
2.2 Projectvoering Je hebt de vrije keuze wat betreft de gebruikte ontwikkelingsomgeving: UNIX/Linux omgeving met de GNU g++ compiler, Make en Eclipse of een Windows met de MS Visual 8 C++ compiler of met Eclipse en Cygwin. Maar de projectvoering moet voldoen aan volgende vereisten:
directory structuur
Bij oplevering moet de directory structuur identisch zijn aan degene die je aantreft in de directory met voorbeeld codes. Ook de Makefiles en projectdefinitie files (Visual, Eclipse) moeten een identische structuur hebben (maar met een aangepaste inhoud uiteraard).
2.3. RECORD GEBASEERDE FILESTRUCTUUR
7
compilatie
Het project moet compileren met zowel de MS Visual 8 C++ compiler, als met de GNU g++ compiler gebruik makend van make, op de toestellen van de computerklas.
version control
Je bent zelf verantwoordelijk voor het gebruik van een version control tool om opeenvolgende versies of releases van je code te beheren en indien vereist te reconstrueren.
werkvorm en opvolging
Tijdens de practicumsessies werk je volgens de pair programming methode. Je organiseert je werk zodat er periodisch een release gemaakt kan worden die in Blackboard gepost wordt. Dit is essentieel om feedback op het verloop van je project te kunnen geven.
2.3 Record gebaseerde filestructuur Files kunnen op diverse manieren gestructureerd worden. Denk maar aan streams, het basismodel dat in de standard library ondersteund wordt, of aan XML files of de diverse formaten die in de multimedia wereld gehanteerd worden. Hier bekijken we kort de record gebaseerde file structuur.
2.3.1 Context In gestructureerde files wordt de data conceptueel benaderd in de vorm van record structuren. Een record is een aggregaat van een aantal velden. Figuur 1 geeft een voorbeeld van een record dat de product gerelateerde informatie (titel, artiest, uitgever, speeltijd) bevat van een CD.
Figuur 2.1: Voorbeeld van een CD record Records worden in een fysische file opgeslaan als een stroom van bytes. Een ASCII voorstelling van zulk een stroom voor een file met CD records wordt getoond in figuur 2.2. Money for Nothing;Dire Straits;Warner;62;#Opeth;Still Life;Peaceville;75;# Figuur 2.2: Twee CD records ondergebracht in een gestructureerd file. In dit voorbeeld worden karakters (; en #) gebruikt om de data in het file te structureren. Het ; karakter duidt het einde van een veld aan, terwijl het # karakter het recordeinde aanduidt.
2.4. CONCRETE OPDRACHT
8
2.3.2 File organizatie en access Het file organizatie aspect heeft betrekking op de interne opslagstructuur van de data in het file. Een specifieke file organizatie legt een antwoord vast op volgende vragen: • Zijn de records in het file van vaste of variabele lengte? • Zijn de individuele velden van een record van vaste of variabele lengte? • Hoe kunnen we de individuele records in een file van elkaar onderscheiden? • Hoe kunnen we de inviduele velden van een record van elkaar onderscheiden? Het file access aspect heeft betrekking op de toegangsmogelijkheden waarmee de data in het file geaccedeerd kan worden. De twee manieren van file access die in dit project aan bod zullen komen zijn: • Sequenti¨ele access: Records in het file worden geaccedeerd via een sequenti¨ele doorloop van het file. • Direct Access: Het file kan met een O(1) tijdscomplexiteit de locatie van een record bepalen.
2.3.3 Relatieve file In een relatieve file heeft het recordnummer, het volgnummer van het record in het file, de betekenis die een index bij een vector heeft. Deze file vorm ondersteunt zowel sequenti¨ele toegang, in beide richtingen van doorloop, als directe toegang op basis van het recordnummer. In andere organisaties kan de toegang gebeuren op basis van een sleutel, de waarde van een specifiek veld in het record. Het equivalent bij containers is bijvoorbeeld een map. File organizatie en access hebben invloed op elkaar. Zo zal een relative file met records van vaste lengte O(1) access ondersteunen door het recordnummer te vermenigvuldigen met de vaste grootte van de records in het file. Een relative file met records van variabele lengte heeft daarvoor een extra indexeringsstructuur nodig.
2.4 Concrete opdracht Ontwikkel in C++ een record-based relative file structuur met bidirectionele sequenti¨ele en directe acces. Maak zoveel mogelijk gebruik van template technieken.
startpunt
Om je op weg te zetten met het initieel ontwerp en architectuur, wordt er een presentatie voorzien bij de aanvang van de projectgerichte practica. Verder in deze nota’s vindt je een plan dat je bij uitvoering kan volgen. Bovendien krijg je een ”File” klasse ter beschikking zodat alle interacties met C++ file streams reeds voorzien zijn.
Zorg ervoor dat je klassen generisch genoeg zijn om met records van zowel variabele als vaste grootte om te gaan. Je moet echter enkel een implementatie voorzien voor records met vaste grootte. Modeleer de interface van je relatieve file klasse op die van de vector klasse uit de Standaard Library.
2.4. CONCRETE OPDRACHT
9
2.4.1 Record vereisten De velden van het record moeten allemaal een vaste lengte hebben, met uitzondering van het laatste veld. Het aantal velden en de types van de velden liggen vari¨eren niet tussen records van hetzelfde file. Voor records met velden van vaste lengte, bestaat de mogelijkheid om op compile time de grootte van het record te berekenen op basis van een lijst die de types van elk veld in het record beschrijft. Maak gebruik van de boost MPL library om met type lijsten en compile time operaties op lijsten en types om te gaan. Het moet ook mogelijk zijn om de gebruiker een grootte voor het record te laten specifi¨eren. Voorzie volgende compile-time controles op de veldspecificatie: • Enkel het laatste veld van een record mag een variabele grootte hebben. • Indien het laatste veld van het record een variabele grootte heeft, dan moet de gebruiker een compile-time grootte opgeven voor het record. • Indien de gebruiker een compile-time lengte opgeeft, pas dan een compile-time check toe die nagaat of de opgegeven lengte groter is dan de minimum lengte van het record op basis van de compile-time berekening van de record grootte. Je mag er vanuit gaan dat enkel velden met een fundamental type een vaste grootte hebben.
2.4.2 Access vereisten Het relative file moet: • Bidirectionele sequenti¨ele doorloop ondersteunen. • O(1) direct record access op basis van het record nummer. Deze voorzieningen moeten gemodeleerd worden op de containers van de Standaard Template Library door iteratoren in te voeren.
2.4.3 Filebewerking vereisten Volgende basis operaties moeten voor elk file beschikbaar zijn: • Aanmaak van het file • Verwijderen van het file • Lezen van een record • Schrijven van een record • Verwijderen van een record Het verwijderen van records uit een file kan door de records te markeren als zijnde ”verwijderd”met een bepaalde byte sequentie (of een speciaal character). Dit heeft als voordeel dat, indien er voor deze markering extra plaats voorzien wordt in het file, de verwijdering van het record nog ongedaan gemaakt kan worden zolang het niet werd overschreven. Bij het implementeren van deze operaties moet voldoende aandacht besteed worden aan policies voor het afhandelen van situaties als openen van een niet-bestaand file, cre¨eeren van een reeds bestaand file, overschrijven van een record, verwijderen van een niet-bestaand record, lezen van een niet-bestannd record enzomeer.
2.5. UITVOERINGSPLAN
10
2.5 Uitvoeringsplan Je kan het volgende plan aanhouden (een suggestie dus): 1. Ontwerp een buffer klasse ter ondersteuning van records met vaste grootte. Voorzie methodes om een record veld te lezen en te schrijven naar de buffer. Ga er aanvankelijk van uit dat de gebruiker de grootte van het record op compile-time moet specifi¨eren, en dat het laatste veld van vaste grootte is. 2. Ontwerp een klasse waarvan de data in record vorm zal geserialiseerd worden door gebruik te maken van de buffer. 3. Implementeer een relatief file dat de aangegeven basisoperaties ondersteunt. Ga ervan uit dat er gebruik gemaakt wordt van records met een vaste grootte. Maak hierbij gebruik van de File klasse (cfr. Blackboard), die alle interacties met de C++ file streams voor zijn rekening neemt. 4. Voorzie iteratoren op het relatieve file. 5. Maak het voor de gebruiker mogelijk om de types van de velden in het record op compile time te specifi¨eren. Maak van deze type informatie gebruik om te verhinderen dat een gebruiker een bepaald veld in de buffer schrijft met een verkeerd type. Voorzie aanvankelijk een mogelijkheid tot specificatie zonder gebruik te maken van Boost type lists. 6. Breid je ontwerp uit zodat een gebruiker een Boost type list kan gebruiken worden ter beschrijving van de veld types. 7. Maak gebruik van policy-based programming om flexibel om te gaan met de situaties beschreven in 2.4.3 8. Identifieer een concept voor je library en voorzie checks gebruik makend van de boost concept check library. 9. Laat de eis vallen dat het laatste veld van de buffer ook een vaste lengte heeft. 10. Maak van de lijst van veld types gebruik om op compile-time informatie over het record af te leiden, e.g. record grootte, aantal velden,... . 11. Voorzie compile-time checks op de lijst van veld types (cfr. sectie 2.4) 12. Pas je ontwerp aan zodat code voor records van variabele lengte makkelijk kan ingeplugd worden. Tests worden hierbij incrementeel uitgewerkt bij de oplevering van nieuwe functionaliteit. Lever tevens een demoprogramma af dat een nieuw file aanmaakt, enkele records toevoegt en vervolgens de inhoud van de records in het file dumpt naar de standard output. Bovendien moet je demoprogramma het opzoeken van een record op basis van een veldwaarde demonstreren.
2.6 Evaluatietabel Tabel 2.6 geeft aan wat de gewichten zijn van de diverse facetten van het project. Om een voorbeeld te geven: wie alles heeft ge¨ımplementeerd behalve de compile-time checks en de automatische berekening van de record grootte (twee items die samen een gewicht van 3/20 hebben), zal hoogstens 17/20 als quotering krijgen. In hoeverre die 17/20 gehaald wordt is dan afhankelijk van de kwaliteit van het opgeleverde project (directorystructuur, leesbaarheid van de code, niveau van documentatie, code conventions, coverage van de tests,...), en de kwaliteit van het ontwerp met correct gebruik van de technieken. Voor de documentatie volstaat code documentatie via doxygen en een overzichtelijk demo programma. Voor de tests wordt gebruik van cppunit sterk aanbevolen.
Gewicht
Ge¨ımplmenteerde Vereisten • Basis operaties van het relatieve file ge¨ımplementeerd
5/20
• Genericiteit aanwezig m.b.t. de gebruikte record organizatie • Templates aangewend om code duplicatie tegen te gaan m.b.t. de afhandeling van lees/schrijf operaties op de buffer. • Correcte toepassing van het STL container concept
3/20
• Correcte toepassing van het STL iterator concept • Unit test voorzieningen
3/20
• Ondersteuning voor de compile-time beschrijving van de veld types (met en zonder Boost typelists) • Toepassing van de traits techniek in de library • Voorzie minstens 1 concept check, gebruik makend van de Boost Concept Check Library
4/20
• Template classes stellen voldoende type informatie ter beschikking via typedefs • Laatste veld van buffer kan een variabele lengte hebben. • Minstens 4 policies ge¨ıdentifieerd en ge¨ımplementeerd.
3/20
• Automatische berekening van de grootte van fixed-size records op basis van de compile-time veld beschrijving • Compile-time checks op veldspecificatie cfr. sectie 2.4.1. • Opzoeken van een record op basis van de waarde van een bepaald veld in demo programma opgenomen
2/20
• Ontwerp is voldoende generisch om makkelijk records met variabele lengte aan te kunnen (implementatie voor deze ondersteuning moet echter niet aanwezig zijn). Tabel 2.1: Gewichten van de diverse facetten van het project
Bibliografie
Alexandrescu, A. (2001), Modern C++ Design:Generic Programming and Design Patterns Applied, Addison-Wesley Publishing Company, Inc., Reading, Massachusetts. Stroustrup, B. (2000), The C++ Programming Language, Special Edition, AddisonWesley Publishing Company, Inc., Reading, Massachusetts. Stroustrup, B. (2002), De programmeertaal C++, Pearson Education Inc. Vandevoorde, D. and Josuttis, N. M. (2003), C++ Templates: The Complete Guide, Pearson Education.
