Předmět Funkcionální programování (KMI / PGSFP)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / PGSFP - Funkcionální programování, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).

Materiál	Typ	Datum	Počet stažení

Obsah

Předmět se zabývá metodami funkcionálního programování, vztahem k lambda kalkulu a souvisejícími výpočetními modely. Obsah je zaměřen na teoretické aspekty funkcionálního programování a výrazně rozšiřuje úvodní představení základních konceptů v bakalářském a magisterském studiu.Funkcionální programování a lambda kalkul: Syntax lambda výrazů a jejich vyhodnocování. Aplikace funkcí a currying, Lambda abstrakce. Operační sémantika lambda kalkulu: vázané a volné proměnné, beta-konverze, alfa-konverze; vzájemná zastupitelnost. Přepisovací systémy, terminace, konfluence, Churchova-Rosserova vlastnost, normální formy. Vazba na čistý lambda kalkul. Reprezentace booleovských formulí, přirozených čísel, $n$-tic. Vyčíslitelné funkce: lambda-vyčíslitelné, totální rekurzivní, částečné rekurzivní. Věty o pevném bodu, nerozhodnutelné vlastnosti. Rekurzivní funkce, Y kombinátor jako lambda abstrakce. Denotační sémantika lambda kalkulu. Překlad vyššího programovacího jazyka do lambda kalkulu: let-výrazy, letrec-výrazy, strukturované typy a porovnávání se vzory.Funkcionální programování a uspořádané algebry: Specifikace abstraktních datových typů: vícedruhové algebry, jejich podalgebry, morfismy a součiny; princip konečné algebraické rekurze; ekvacionální teorie, vícedruhová ekvacionální logika; ekvacionální specifikace; počáteční sémantika a operační sémantika. Uspořádané algebry, jejich morfismy a součiny. Uspořádané variety a jejich charakterizace pomocí volných uspořádaných algeber. Logika nerovností (inekvacionální logika). Striktní uspořádané algebry, omega-uspořádané algebry. Rekurzivní schémata funkcionálních programů a jejich sémantika, vypočtené hodnoty, symbolická řešení, sémantické ekvivalence.Zásobníkový model vyhodnocování symbolických výrazů: Funkcionální programy jako posloupnosti symbolických výrazů. Zásobníkový vyhodnocovací proces. Elementy jazyka: primitivní a definované procedury (funkce), speciální formy, makra, prostředí, páry. Rozšiřování vyhodnocovacího procesu: lexikální a dynamické vazby, líné vyhodnocování, vyhodnocování s vyrovnávací pamětí, imperativní rysy, únikové funkce, aktuální pokračování, nedeterminismus a paralelismus. Metody implementace interpretů a překladačů funkcionálních programovacích jazyků.

Získané způsobilosti

1. ZnalostPopsat a důkladně pochopit principy a metody funkcionálního programování.

Literatura

Leeuwen, J. van (ed.). Handbook Of Theoretical Computer Science: Formal Models and Semantics. Volume B, Elsevier, 1994. ISBN 0262720159.Bird R., Wadler P. Introduction to Functional Programming. Prentice Hall, Englewood Cliffs, New Jersey, 1988. ISBN 0-13-484197-2.Zlatuška J. Lambda-kalkul. Vydavatelství MU, Brno, 1993. ISBN 8021008261.H. Abelson, G. J. Sussman. Structure and Interpretation of Computer Programs (SICP). MIT Press, 1985. Church A. The Calculi of Lambda Conversion. Princeton University Press, Princeton, NJ, 1941. Peyton Jones S. L. The Implementation of Functional Programming Languages. Prentice Hall, 1987. ISBN 0-13-453333-X.Barendregt H. P. The Lambda Calculus: its Syntax and Semantics. 2nd reprint. Elsevier, Amsterdam, 1997. ISBN 0-444-87508-5.Manis V. S., Little J. J. The Schematics of Computation. Prentice Hall, Englewood Cliffs, New Jersey, 1995. ISBN 0-13-834284-9.Wechler W. Universal Algebra for Computer Scientists. Springer-Verlag Berlin Heidelberg, 1992. ISBN 3-540-54280-9.

Požadavky

Aktivní účast v hodině. Plnění zadaných úkolů. Složení ústní (příp. písemné) zkoušky.

Garant

doc. RNDr. Vilém Vychodil, Ph.D.

Vyučující

doc. RNDr. Vilém Vychodil, Ph.D.