IA014 Funkcionální programování

Fakulta informatiky
jaro 2010
Rozsah
3/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
RNDr. Libor Škarvada (přednášející)
Mgr. Matej Kollár (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: RNDr. Libor Škarvada
Rozvrh
Čt 14:00–16:50 B011
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
Cíle předmětu
Kurs přináší přehled hlavních teoretických výsledků využívaných ve funkcionálním programování. Funkcionální jazyky jsou zavedeny jako různé modifikace a rozšíření (typovaného i netypovaného) lambda kalkulu. Pozornost se věnuje též typovým systémům pro funkcionální jazyky, a dále problematice implementace interpretů a kompilátorů a optimalizaci výpočtu. Absolvování kursu si pomůže studentům hlouběji si uvědomit souvislosti mezi různými matematickými kalkuly a funkcionálními jazyky, jakož i vazbu na matematickou logiku a teorii typů.
Osnova
  • Netypovaný a typovaný lambda kalkul. Silná normalizace, Churchova-Rosserova vlastnost.
  • Rekurse, věta o pevném bodě.
  • Jednoduchý jazyk a jeho sémantika.
  • Typy. Problém otypování, parametrický polymorfismus. Impredikativní typové systémy. Otypování v predikativních typových systémech.
  • Podtypy, hodnotově závislé typy, PTS.
  • Imperativní prvky, vstup/výstup, ošetření výjimek, nedeterminismus, přepisovatelná pole, stav. Pokračování.
  • Typové a konstruktorové třídy. Monády. Monadický datový typ pro vstup/výstup. Monadické kombinátory pro syntaktickou analýzu.
  • Implementace funkcionálních jazyků. 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.
Literatura
  • FIELD, Anthony J. a Peter G. HARRISON. Functional programming. 1st ed. Wokingham: Addison-Wesley Publishing Company, 1988, 602 s. ISBN 0-201-19249-7. info
  • JONES, Simon L. Peyton. The implementation of functional programming languages. New York: Prentice Hall, 1987, xvi, 445 s. ISBN 0-13-453325-9. info
Záložky
https://is.muni.cz/ln/tag/FI:IA014!
Výukové metody
Kurs probíhá formou přednášek.
Metody hodnocení
Kurs je ukončen závěrečnou písemnou zkouškou.
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2003, jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2011, jaro 2012, jaro 2013, podzim 2014, podzim 2015, jaro 2017, jaro 2018, jaro 2019, jaro 2020, jaro 2021, jaro 2022, jaro 2023, jaro 2024, jaro 2025.