460-4022/01 – Paradigmata programování (PP)
Garantující katedra | Katedra informatiky | Kredity | 6 |
Garant předmětu | Ing. Marek Běhálek, Ph.D. | Garant verze předmětu | Ing. Marek Běhálek, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
Ročník | 1 | Semestr | letní |
| | Jazyk výuky | čeština |
Rok zavedení | 2010/2011 | Rok zrušení | 2019/2020 |
Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Cílem předmětu je seznámit studenty s teoretickými i praktickými základy deklarativních programovacích jazyků a naučit je zvládat programovací techniky založené na rekurzivních datových strukturách a rekurzi obecně.
Znalost logického programování, specielně Prologu, a funkcionálního programování v jazyce Haskell.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Studenti získají znalosti logického programování, specielně Prologu, a funkcionálního programování v jazyce Haskell.
Povinná literatura:
Materiály k předmětu jsou průběžně zveřejňované na: http://www.cs.vsb.cz/behalek/education/pp/
Doporučená literatura:
Materiály k programovacímu jazyku Haskell na: http://www.haskell.org
Materiály k programovacímu jazyku Prolog na:
http://www.swi.psy.uva.nl/projects/SWI-Prolog/
Simon Thompson: Haskell: The Craft of Functional Programming, Addison-Wesley Professional; 3 edition (October 2, 2011), English, ISBN-10: 0201882957
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínky udělení zápočtu:
Pro udělení zápočtu je třeba získat alespoň 21 bodů za dva projekty.
E-learning
Další požadavky na studenta
Další požadavky na studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Úvod: Cíle a náplň předmětu, požadavky, organizace cvičení, literatura. Klasifikace programovacích jazyků. Účel a základní aplikace překladačů. Zdrojový a cílový jazyk. Popis programovacích jazyků. Formální metody pro popis syntaxe a sémantiky.
Historie programovacích jazyků a překladačů: Teoretická východiska. První programovací jazyky a překladače. Vyšší programovací jazyky. Strukturované programování. Modulární jazyky. Objektově-orientované jazyky. Skriptovací jazyky.
Funkcionální a logické programovací jazyky: Deklarativní styl programování, jeho výhody a nevýhody. Základy lambda kalkulu. Praktická implementace jednoduchých úloh v programovacím jazyce Haskel.
Skriptovací jazyky: Popis odlišnosti od tradičních jazyků. Základní představitele. Praktické ukázky skriptovacích jazyků. Stručný úvod do programovacího jazyka PHP.
Imperativní programovací jazyky: Základní principy. Jiná paradigmata programování.
Objektově orientované programování: Shrnutí základních principů. Méně obvyklé objektově orientované programovací jazyky. Programování založené na prototypech.
Struktura a funkce překladače: Modely zdrojového kódu, transformace. Organizace překladače - fáze překladu, průchod. Jednoprůchodové a optimalizující překladače. Pomocné programy. Testování a údržba překladače.
Lexikální analýza: Funkce lexikálního analyzátoru, implementace lexikálního analyzátoru.
Syntaktická analýza: Účel a metody syntaktické analýzy. Analýza shora dolů a zdola nahoru. LL(1) gramatiky, výpočet množin FIRST a FOLLOW. Rozkladová tabulka.
Implementace syntaktického analyzátoru: Analýzu rekurzivním sestupem. Nástroje pro generování překladačů (jako příklad JavaCC)
Syntaxí řízený překlad: Překladová gramatika, atributová překladová gramatika. Implementace atributového překladu při analýze shora dolů.
Tabulka symbolů a struktura programu v době běhu: Základní pojmy - vazba, rozsah platnosti, viditelnost, doba života. Funkce tabulky symbolů, blokově strukturovaná tabulka symbolů. Implementace. Systém řízení běhu programu. Podprogramy - aktivace, statická a dynamická struktura, aktivační záznam. Organizace paměti, přidělování paměti pro aktivační záznamy, přístupové ukazatele.
Poslední fáze při překladu: Generování vnitřní reprezentace programu (formáty vnitřní reprezentace - graf, zásobníkový kód, tříadresový kód), Provádění optimalizaci (základní rozdělení optimalizací, příklady různých optimalizací), generování cílového kódu.
Projekty:
V předmětu budou realizovány dva projekty. První projekt bude realizace vybrané úlohy v nějakém méně známém programovacím jazyce. Druhý projekt pak bude jednoduchý překladač.
Počítačové laboratoře:
Řešení problémů s využitím různých paradigmat na základě intuitivního zavedení potřebných jazykových konstrukcí
Ukázky deklarativního stylu programování. Praktické realizace jednoduchých úloh v programovacím jazyce Haskell.
Praktická realizace úloh v jazyce Haskel.
Skriptovací jazyky: Praktická realizace jednoduchých úloh ve skriptovacím jazyce PHP
Imperativní a objektové jazyky: Ukázky netradičních programovacích jazyků a různých paradigmat pro programování.
Praktická tvorba programů v nějakém netradičním jazyce, vytváření vlastních jednoduchých příkladů.
Samostatná práce na prvním projektu. Možnost konzultací prvního projektu.
Implementace jednoduchých filtrů a lexikálního analyzátoru.
Realizace příkladů gramatik pro základní syntaktické konstrukce (opakování, opakování s oddělovačem, složitější konstrukce). Převod gramatiky s regulárními výrazy na standardní tvar.
Implementace algoritmů pro výpočet množin FIRST a FOLLOW.
Demonstrace činnosti syntaktického analyzátoru LL(1) a LR(1). Implementace překladače rekurzivním sestupem.
Implementace lexikálního a syntaktického analyzátoru s využitím programu JavaCC.
Samostatná práce na druhém projektu.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky