I014 Funkcionální programování

Fakulta informatiky
jaro 1999
Rozsah
3/0. 3 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
RNDr. Libor Škarvada (přednášející)
Garance
Kontaktní osoba: RNDr. Libor Škarvada
Předpoklady
I015 Úvod do funkc. progr.
Předpokládá se absolvování kursu I015 Úvod do funkcionálního programování.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Osnova
  • Kurs přináší pohled na funkcionální jazyky z hlediska jednoduchých matematických formalismů, kterými jsou různé modifikace a rozšíření (typovaného) lambda kalkulu. Věnuje se rovněž problematice implementace interpretů a kompilátorů a optimalizaci výpočtu.
  • Netypovaný a typovaný lambda kalkul. Silná normalizace, Churchova-Rosserova vlastnost.
  • Rekurse, věta o pevném bodě.
  • Jazyk PCF, denotační a operační semantika, úplná abstrakce, paralelní or.
  • Typy. Problém otypování.
  • Polymorfismus. Predikativní a impredikativní typové systémy.
  • Typové třídy a konstruktorové třídy. Podtypy. Typové systémy pro OOP.
  • Imperativní prvky, vstup/výstup, ošetření výjimek, nedeterminismus, přepisovatelná pole, stav. Pokračování.
  • Monády. Monadický datový typ IO.
  • Implementace funkcionálních jazyků. SECD stroj. Překlad definic podle vzoru, strážených klauzulí, intensionálních seznamů.
  • Grafová redukce. G-stroj. Superkombinátory, vynášení.
  • Optimální redukce, plná lenost, plně líné vynášení.
Informace učitele

Termín

Kurs je veden formou přednášek a probíhá v letním semestru v rozsahu 3 jednotky (150 minut) týdně.

Některé odkazy

Věta o konfluenci (PS, DVI)
Monadické kombinátory pro syntaktickou analýzu (článek Graham Huttona a Erika Meijera),
ukázky úloh z minulých zkoušek
Příklady funkcionálních programů
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích léto 1996, léto 1997, léto 1998, jaro 2000, jaro 2001, jaro 2002.