Kursplan för Avancerad funktionell programmering

Kursplan fastställd 2021-02-26 av programansvarig (eller motsvarande).

Kursöversikt

  • Engelskt namnAdvanced functional programming
  • KurskodTDA342
  • Omfattning7,5 Högskolepoäng
  • ÄgareMPALG
  • UtbildningsnivåAvancerad nivå
  • HuvudområdeDatateknik, Informationsteknik
  • InstitutionDATA- OCH INFORMATIONSTEKNIK
  • BetygsskalaTH - Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3), Underkänd

Kurstillfälle 1

  • Undervisningsspråk Engelska
  • Anmälningskod 02117
  • Blockschema
  • Sökbar för utbytesstudenterJa

Poängfördelning

0110 Laboration 4,5 hp
Betygsskala: TH		 4,5 hp
0210 Tentamen 3 hp
Betygsskala: TH		 3 hp
  • 19 Mar 2022 fm J
  • 22 Aug 2022 em J

I program

Examinator

Gå till kurshemsidan (Öppnas i ny flik)

Behörighet

Grundläggande behörighet för avancerad nivå
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Särskild behörighet

Engelska 6
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Kursspecifika förkunskaper

För att vara behöriga för kursen skall studenterna ha klarat av två år av en utbildning på väg mot en högskoleexamen inom datateknik eller motsvarande. Mer specifikt krävs kurserna TDA452 Funktionell programmering, TMV210 Introduktion till diskret matematik och minst en av kurserna DAT151 Programming language technology eller DAT121 Programming paradigms eller motsvarande.

Koncept: Abstrakt syntaxträd, semantik, interpretator, kompilator. Algoritm, komplexitet, "divide-and-conquer". Induktionsbevis, logik, likhetsbevis (equality reasoning).

Det är rekommenderat, men inte ett krav, att läsa följande kurser i förväg: Algorithms och ("Logic in computer science" eller "Finite automata theory and formal languages").

Syfte

Kursens mål är att utforska de kraftfulla mekanismer som funktionella programspråk erbjuder när det gäller att lösa verkliga problem och strukturera större program. Fokus ligger på design av programbibliotek och inbäddade språk.

Lärandemål (efter fullgjord kurs ska studenten kunna)

  • designa inbäddade domänspecifika språk (EDSL)
    • förklara och ge exempel på (abstrakt) syntax, semantik, etc.
    • implementera EDSL i Haskell (som kombinatorbibliotek)
  • läsa, förstå och utöka Haskellprogram som använder sig av avancerade typsystemegenskaper:
    • typklasser
    • (generaliserade) algebraiska datatyper
    • funktorer, monader och monadtransformerare
  • använda specifikationsbaserade utvecklingstekniker
    • formulera och testa egenskaper som programmet ska uppfylla
    • resonera om funktionella programs korrekthet
    • transformera program baserat på sådana resonemang
  • förklara och diskutera de ämnen som beskrivs ovan

Innehåll

En stor fördel med funktionella programspråk är att de flesta språkkonstruktionerna kan namnges och därmed återanvändas som högre ordningens funktioner. Funktionella program kan därför ofta konstrueras genom att kombinera konstruktioner från ett funktionsbibliotek. Den här metoden gör det möjligt att snabbt konstruera program med en hög grad av korrekthet. Detta är den centrala idén i kursen.

Vi kan lära oss en hel del genom att studera standardbibliotekens list-funktioner som map, fold osv. Dessa funktioner kan generaliseras så att de fungerar för andra datatyper.

Realistiska funktionella program måste också hantera tillståndsförändringar, avbrott, "backtracking" och andra "icke-funktionella" beteenden. Vi kommer att jobba med hur dessa kan modelleras rent funktionellt. Det matematiska begreppet "monad" hjälper oss med detta.

Med hjälp av dessa kunskaper kommer vi att konstruera domänspecifika programbibliotek ämnade att lösa problem inom ett ett visst tillämpningsområde. Den här sortens bibliotek kan sägas definiera ett domänspecifikt språk eftersom konstruktionerna som programmeraren använder huvudsakligen består av biblioteksfunktioner. Vi kommer att studera bibliotek för inläsning (parsning), utskrift (pretty printing), grafik, webbprogrammering och interaktion. Kursen kommer också att presentera en del aktuell forskning vilket kan göra att innehållet varierar en del mellan åren. Kursen använder sig huvudsakligen av programmeringsspråket Haskell.

Organisation

Det är två 2-timmars förelåsningar varje vecka. Studenterna förväntas lägga rätt mycket egen tid på programmering och självstudier. Mycket hjälp erbjuds också.

Litteratur

Se separat litteraturlista.

Examination inklusive obligatoriska moment

Det är 2-3 obligatoriska programmeringslaborationer som genomförs i par, och en skriftlig tentamen i slutet av kursen.

Kursens examinator får examinera enstaka studenter på annat sätt än vad som anges ovan om särskilda skäl föreligger, till exempel om en student har ett beslut från Chalmers om pedagogiskt stöd på grund av funktionsnedsättning.