Berekeningsmodellen

Werkvormen

  • 16 uur hoorcollege
  • 16 uur responsie-college
  • 52 uur zelfstudie

Toelichting werkvormen

Het grootste deel van deze cursus is taakgestuurd opgezet. Je volgt een wekelijkse cyclus van oriëntatie (hoorcollege), zelfstudie (leertaak) en nabespreking (responsiecollege). Elke leertaak heeft een vaste structuur, waarin bijvoorbeeld precies de leerdoelen en de op te leveren producten zijn gespecificeerd. Zo kun je ook (als je dat wilt) het cursusmateriaal zelfstandig en doelgericht doorwerken.
In een werkstuk laat je zien dat je semantische technieken kunt ontwikkelen en toepassen 'in het wild'. Dit onderdeel van de cursus wordt afgerond met een bespreking van het werkstuk met de docenten. Dit gesprek is onderdeel van de toetsing, maar heeft het karakter van een inhoudelijke (werk)bespreking met collega-semantici.

Vereiste voorkennis

Je hebt programmeerervaring met imperatieve en functionele talen. Verder kun je:
  • (programmeer)talen en taaluitbreidingen specificeren met behulp van contextvrije grammatica's;
  • operationele semantiek van imperatieve taalconstructies formuleren via natuurlijke semantiek (ns) en via structurele operationele semantiek (sos);
  • berekenbaarheid van numerieke operaties aantonen;
  • helder formuleren, zowel bij het motiveren van oplossingen als het weergeven van wiskundige redeneringen.
Deze voorkennis kun je opbouwen via de cursussen rond programmeren en de cursussen Talen en Automaten, Semantiek en Correctheid en Beweren en Bewijzen.

Leerdoelen

Na afloop van deze cursus kunnen de deelnemers:
  • Berekeningen in functionele talen modelleren met behulp van herschrijfsystemen (termherschrijfsystemen, lambda-calculus). Berekeningen in herschrijfsystemen analyseren, bijvoorbeeld confluentie- en terminatiegedrag.
  • Alternatieve state- en geheugenmodellen aangeven voor het modelleren van imperatieve talen.
  • Semantiek van een taal uit de praktijk modelleren. Daarvoor geschikte technieken selecteren en deze zo nodig enigszins uitbreiden. Hiermee een case-study uitvoeren. De resultaten op professionele wijze rapporteren en tegenover collega-semantici verantwoorden.

Inleiding

In deze cursus maak je kennis met berekeningsmodellen voor functionele programmeertalen. Deze berekeningsmodellen dienen als basis voor implementaties van zulke talen, en komen ook van pas bij het analyseren van het gedrag van functionele programma's.

Verder leer je alternatieve semantische modellen te kiezen bij het vastleggen van semantiek van imperatieve talen. Je past dit toe op een taal uit de praktijk. Dit gedeelte bouwt voort op de cursus Semantiek en Correctheid.

Onderwerpen

  • Semantiek van functionele talen en constructies: termherschrijven, normalisatie, confluentie, lambda-calculus, reductie, representatie berekenbare functies
  • Semantiek van imperatieve talen en constructies: abrupte terminatie, state, executiemodellen

Toetsvorm

De beoordeling is gebaseerd op twee onderdelen:
  • een schriftelijk tentamen,
  • het werkstuk.
Als je voor beide onderdelen minstens 5,5 hebt behaald, is het eindcijfer voor Berekeningsmodellen het gemiddelde van de twee resultaten. In andere gevallen is het eindcijfer het laagste van de twee.

Literatuur

We gebruiken een boek en enkele dictaten:

  • Hanne Riis Nielson en Flemming Nielson: Semantics with applications, 1999
  • Erik Barendsen: Semantics of abrupt completion: a case study in natural semantics
  • Hans Zantema: Termherschrijfsystemen
  • Henk Barendregt en Erik Barendsen: Introduction to lambda calculus

Zowel het boek als de dictaten zijn als PDF beschikbaar op de website van de cursus.

Website


Vakcode
NWI-IBC025
Studiepunten
3 ec
Periode
vierde kwartaal
Collegerooster opvragen
SWS / PersoonlijkRooster

Docenten

Opgenomen in

  • Bachelor Informatica