IA014 Funkcionální programování

Fakulta informatiky
jaro 2003
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í)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: RNDr. Libor Škarvada
Rozvrh
Čt 17:00–19:50 B011
Předpoklady
! I014 Funkcionální programování
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
Mateřské obory/plány
předmět má 7 mateřských oborů, zobrazit
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.
Osnova
  • Netypovaný a typovaný lambda kalkul. Silná normalizace, Churchova-Rosserova vlastnost.
  • Rekurse, věta o pevném bodě.
  • Kombinátorový počet. Kombinátory S, K, I, B, C.
  • Jazyk PCF 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í.
  • 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, plně líné vynášení.
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!
Metody hodnocení
Kurs je ukončen závěrečnou písemnou zkouškou.
Informace učitele
http://www.fi.muni.cz/usr/skarvada/vyuka/IA014/
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, 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.