9 ECTS credits
255 u studietijd

Aanbieding 1 met studiegidsnummer 1000441BNR voor alle studenten in het 2e semester met een verdiepend bachelor niveau.

Semester
2e semester
Inschrijving onder examencontract
Niet mogelijk
Beoordelingsvoet
Beoordeling (0 tot 20)
2e zittijd mogelijk
Ja
Inschrijvingsvereisten
Studenten die dit opleidingsonderdeel opnemen, moeten geslaagd of ingeschreven zijn voor “Structuur van computerprogramma’s I”.
Onderwijstaal
Nederlands
Faculteit
Faculteit Wetenschappen en Bio-ingenieurswetensch.
Verantwoordelijke vakgroep
Computerwetenschappen
Onderwijsteam
Coen De Roover (titularis)
Onderdelen en contacturen
0 contacturen Exam
39 contacturen Lecture
39 contacturen Practical exercises
Inhoud
Deze cursus is een introductie tot de implementatie van programmeertalen aan de hand van verschillende evaluatoren en een compiler. Inhoudelijk correspondeert de cursus met de tweede helft van het beroemde boek "Structure and Interpretation of Computer Programs" door Abelson en Sussman. 
 
We vertrekken van een evaluator voor de hoog-niveau taal Scheme, geïmplementeerd in Scheme. Diens implementatie biedt een precieze, uitvoerbare definitie van het omgevingsmodel dat in de cursus "Structuur van Computerprogramma's 1" gehanteerd werd. Via variaties op deze evaluator bestuderen we verschillende keuzes in het ontwerp (bv. normal-order evaluatie van de argumenten voor een procedure-oproep) en in de implementatie (bv. het scheiden van de syntactische analyse en de evaluatie van expressies) van programmeertalen. We ronden dit hoofdstuk af met een evaluator voor een zogenaamde "logische" programmeertaal die niet langer de lambda-calculus als motor gebruikt, maar concepten uit de predicatenlogica. 
 
Na de voorgaande hoog-niveau talen, richten we onze blik op een primitieve taal die veel weg heeft van assembly. We implementeren een evaluator voor de taal, en bestuderen programma's in deze taal met aandacht voor de verschillen tussen subroutines en procedures. Vervolgens implementeren we een vorm van automatische geheugenbeheer (nl. stop-and-copy garbage collection), alsook een nieuwe evaluator voor Scheme in deze primitieve taal. Op deze manier verduidelijken we de rol van stapels bij het afhandelen van procedure-oproepen, alsook hoe staartrecursieve procedures tot iteratieve processen leiden. We sluiten af met een compiler die Scheme programma's naar equivalente programma's in de primitieve taal vertaalt.
 
Inhoud
 
1. Interpretation
  • Meta-circular evaluators for higher-order procedural languages
  • Separating evaluation from syntactic analysis as an optimisation  
  • Lexical versus dynamic scoping, applicative versus normal-order evaluation
  • Evaluators for logic languages: unification and resolution
 
2. Compilation
  • Evaluators for assembly languages: registers, subroutines, stack
  • Explicit-control evaluators in assembly language for higher-order procedural languages
  • Automated memory management (stop-and-copy garbage collection)
  • Compilation from procedural languages to assembly languages
     
Studiemateriaal
Digitaal cursusmateriaal (Aanbevolen) : Slides uit de hoorcolleges, opgaven en oplossingen voor de oefeningen uit de werkcolleges
Handboek (Vereist) : Structure and Interpretation of Computer Programs, Harold Abelson and Gerald Jay Sussman with Julie Sussman, 2de, MIT Press, 9780262510875, 1996
Bijkomende info

  

  

 

Leerresultaten

Algemene competenties

De doelstelling van dit vak is de studenten vertrouwd te maken met noties van computerhardware, de rol van programmeertalen in dit kader, de architectuur van een vertolker voor een programmeertaal, zowel meta-circulair als uitgedrukt in de onderliggende registermachinecode; simulatie van registermachines; architectuur van computergeheugen en het beheer daarvan; compilatie van programma's naar registermachines met inbegrip van een aantal eerste optimalisatietechnieken.
 
 
De hieraan gekoppelde leerresultaten zijn: 
 
m.b.t. het herinneren en begrijpen van kennis:
  • de student kan de manier waarop Scheme programma's uitgevoerd worden verduidelijken aan de hand van de besproken implementatie van de meta-circulaire evaluator 
  • de student kan de besproken variaties op de brontaal illustreren aan de hand van zowel voorbeeldprogramma's als evaluator-extracten
  • de student kan de controle over het evalueren van deelexpressies situeren in de besproken evaluatoren  
  • de student kan de syntactische analyse van expressies situeren in de besproken evaluatoren en de besproken compiler
  • de student kan de toestand van het geheugen schetsen vóór en ná de toepassing van het besproken stop-and-copy garbage collection algoritme
  • de student kan het concept van staartrecursie-optimalisatie toelichten aan de hand van extracten uit de besproken evaluator voor Scheme in registermachinetaal 
  • de student kan het concept van staartrecursie-optimalisatie toelichten aan de hand van extracten uit de besproken compiler van Scheme naar registermachinetaal 
 
m.b.t. het toepassen van kennis:
  • de student kan, voor een gegeven registermachine-programma, het gebruik van registers en de stack voorspellen
  • de student kan, voor een gegeven uitbreiding aan een besproken evaluator, de corresponderende variatie op de brontaal reconstrueren 
  • de student kan, voor code geproduceerd door de compiler van Scheme naar registermachinetaal, het corresponderende bronprogramma reconstrueren
 
m.b.t. analyseren:
  • de student kan variaties op de besproken implementatietechnieken herkennen in evaluatoren en compilers voor gelijkaardige talen
 
m.b.t evalueren: 
  • de student kan, voor een gegeven variatie op de brontaal Scheme, de voordelen en nadelen van de besproken implementatietechnieken afwegen
 
m.b.t. creëren:
  • de student kan zelfstandig eenvoudige variaties op en uitbreidingen van de brontaal Scheme implementeren in de besproken evaluatoren 
  • de student kan zelfstandig eenvoudige lijst-bewerkende algoritmes implementeren in de besproken logische programmeertaal
  • de student kan zelfstandig eenvoudige algoritmes implementeren in de besproken registermachine-taal 
 

Beoordelingsinformatie

De beoordeling bestaat uit volgende opdrachtcategorieën:
Examen Schriftelijk bepaalt 100% van het eindcijfer

Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:

  • Examen met een wegingsfactor 1 en aldus 100% van het totale eindcijfer.

    Toelichting: Het examen bestaat uit een verplicht schriftelijk deel en een facultatieve mondelinge verderzetting.

Aanvullende info mbt evaluatie
Het examen bestaat uit een verplicht schriftelijk deel en een optioneel mondeling deel.
Indien de student deelneemt aan het optioneel mondeling gedeelte, worden de punten voor schriftelijk en het mondeling gedeelte als volgt gewogen:
- 80% schriftelijk deel
- 20% mondeling deel
Anders geldt het cijfer voor het schriftelijk deel als eindresultaat. 
 
Tijdens het schriftelijk gedeelte mag het volgende studiemateriaal (in gedrukte, geprinte, of handgeschreven vorm) geconsulteerd worden: het cursusboek, de slides van de hoorcolleges, de eigen notities, en de eigen oplossingen voor de oefeningen uit de werkcolleges.
 
Toegestane onvoldoende
Kijk in het aanvullend OER van je faculteit na of een toegestane onvoldoende mogelijk is voor dit opleidingsonderdeel.

Academische context

Deze aanbieding maakt deel uit van de volgende studieplannen:
Bachelor in de computerwetenschappen: Standaard traject