Funkcionális programozás C++-ban
A tantárgy angol neve: Functional Programming in C++
Adatlap utolsó módosítása: 2023. május 17.
Dr. Varga Pál, PhD - egyetemi docens (TMIT)
Németh Gábor - egyetemi tanársegéd (TMIT)
Janky Ferenc Nándor (TMIT)
A C++-t a kialakulásának körülményei folytán gyakran az objektumorientált nyelvek közé sorolják, a sablonok és a funkcionális nézőpont mindig is a C++ szerves részét képezték: nélkülük a szabvány számos fontos részét képező STL (Standard Template Library) is elképzelhetetlen lenne.
A tantárgy a napjainkban egyre nagyobb figyelmet kiváltó funkcionális programozás szemszögéből közelíti meg a C++ nyelvet. A kibővített nyelvi elemek vizsgálatán túl - különös figyelmet fordítva a szabvány adta új lehetőségekre - gyakorlati megoldásokat is bemutat.
1. hét
Bevezetés; a megközelítés motivációja.
A move szemantika és a tökéletes továbbítás. Az lvalue és rvalue referenciák. A move szemantika bemutatása, a std::move és a std::move_if_noexcept alkalmazása. Sablonok. A tökéletes továbbítás és a std::forward. Copy elision, RVO.
Laborfeladat: A move szemantika és a tökéletes továbbítás gyakorlása. Osztály sablonparaméterének a dedukciójának vizsgálata. 2. hét
Variadikus sablonok. Variadikus sablonparaméterek feldolgozása fordítási idejű rekurzióval. Fold kifejezések (fold expression). Fordítási idejű döntés: constexpr if, template specializáció, tag dispatching, SFINAE.
Laborfeladat: Típusbiztos printf. Fordítási idejű rekurzió. 3. hét
Lambda-kalkulus I. Megismerkedés az első funkcionális programnyelvnek is tekinthető lambda kalkulussal. A magasabb rendű függvények fogalma és a körrizés. λ-kifejezések gráfja. λ-kifejezések átalakítási szabályai: a β- és az α-konverzió.
Laborfeladat: Konverziók gyakorlása. 4. hét
Lambda-kalkulus II. A λ-kifejezések legegyszerűbb alakra hozása. Normálforma. Redukálási stratégiák és a lusta paraméterkiértékelés. Elsőrendű típusos λ-kalkulus.
Laborfeladat: Redukálási stratégiák összehasonlítása.
5. hét
Funkcionális programozás C++-ban. Függvényobjektumok és lambda kifejezések írása és összehasonlítása. STL algoritmusok (a és fejállományok). Az általános célú függvényburkoló (function wrapper), a std::function, bemutatása.
Laborfeladat: Algoritmikus problémák megoldása az STL segítségével funkcionális szempontból. 6. hét
Kategóriaelméleti bevezető (morfizmus, objektumok, funktorok, kompozíció, algebrai adattípusok). Tiszta függvények (pure functions). Változó állapotok elkerülése. Funktorok és Monádok. A std::optional vizsgálata funkcionális szempontból.
Laborfeladat: Monádok (pl. maybe monád) implementálása C++-ban.
7. hét
Algebrai adattípusok, ezek megvalósítása és használata C++-ban. A std::variant és a std::tuple.
Laborfeladat: A std::apply és a std::visit használata. Type matching inline visitor írása.
8. hét
Magasabb rendű függvények használata C++-ban. Tail recursion. Folding és lifting. A std::invoke.
Laborfeladat: Magasabb rendű függvények implementálása.
9. hét
Lusta kiértékelés implementálása C++-ban. Memoization.
Laborfeladat: Cache készítése függvény kiszámolt értékeinek tárolására. 10. hét
A range-ek használata C++-ban, kapcsolatuk a lusta kiértékeléssel. Range adapterek és a | operátor.
Laborfeladat: Range-ek, view-k. Algoritmusok írása range-ek felhasználásával. 11.hét
Funkcionális és imperatív adatstruktúrák összehasonlítása és vizsgálata (algoritmusok és ezek aszimptotikus komplexitása). Perzisztens lista. Copy on Write.
Laborfeladat: Perzisztens lista implementálása C++-ban.
12.hét
Párhuzamosság és funkcionális programozás: párhuzamos végrehajtás modelljei, párhuzamosság által elérhető gyorsulás elvi határa, Amdahl törvénye, szál alapú vs. opcionális párhuzamosság, taszk alapú (run-to-completion) párhuzamosság, Reaktív programozás es reaktív stream-ek, Actor modell.
Laborfeladat: Korábbi laborgyakorlatokon elkészült funkcionális komponensek párhuzamosítása, távközlési alkalmazás implementálása Actor modell szerint. 13. hét
C++ szoftver tesztelése, tesztelési keretrendszerek ismertetese. Fuzz-testing. Szoftverteljesítmény mérése, teljesítményvezérelt optimalizáció.
Laborfeladat: Catch unit-test rendszer használata, tesztek írása korábbi alkalmakon elkészült kódokhoz. Teljesítmény mérése a “perf” vagy “vsperf” használatával, teljesítménymérés eredményének a feldolgozása, értelmezése. Coverage alapú elemzés és Fuzz-testing a libAFL használatával.
14. hét
Programozási paradigmák összehasonlítása. Funkcionális és imperatív gondolkodás. Funkcionális programozás és OOP, valamint ezek kombinált alkalmazása.
Előadás és laboratórium. A tárgy minden hetében előadás és laboratórium is van, utóbbin a hallgatók valódi programozási feladatokat oldanak meg a laborvezetők támogatásával. Tehát, minden héten 45+45=90 perc kontakt óra van, amibe az előadások és a labor feladatok is beleértendők.
A tantárgy aláírásának és a félévközi jegy megszerzésnek feltételei a hatályos BME Tanulmányi és Vizsgaszabályzatával (TVSz) összhangban a következők:
● Jelenlét: A laboratóriumi órákon a részvétel kötelező. Hiányozni maximum 5 alkalommal lehet (ez 14 oktatási héttel, heti 2x45 perces laboratóriumi órával számolva minimum 64%-os részvételt jelent). A hiányzásokat pótolni kell.
● Zárthelyi dolgozat: A félév végén az elméleti ellenőrző mérés keretében a hallgatók zárthelyi dolgozatot írnak. A dolgozatot legalább elégséges szintre kell megírni.
● Gyakorlati feladat: A félév végén a gyakorlati ellenőrző mérés keretében a hallgatók gyakorlati feladatot oldanak meg. A gyakorlati feladatot legalább elégséges szinten meg kell oldani.
A zárthelyi dolgozat és a gyakorlati feladat értékelése az alábbiak alapján történik:
0-49 %: elégtelen (1)
50-69 %: elégséges (2)
70-79 %: közepes (3)
80-89 %: jó (4)
90-100 %: jeles (5)
● Zárthelyi dolgozat: A zárthelyi dolgozat pót ZH formájában pótolható az erre kijelölt pótlási időpontban (a szorgalmi időszakban vagy a pótlási héten).
● Gyakorlati feladat: A gyakorlati feladat pótolható pót-ellenőrző mérés formájában az erre kijelölt pótlási időpontban (a szorgalmi időszakban vagy a pótlási héten).
Igény esetén, előzetes egyeztetés alapján.
A tantárgy témaköreinek elmélyítését segítő szakirodalmak:
Csörnyei Zoltán: Lambda-kalkulus, Typotex kiadó, 2007, ISBN: 978-963-9664-46-3
Ivan Čukić: Functional Programing in C++, Manning Publications, 2018, ISBN: 978-1617293818
Bartosz Milewski: Category Theory for Programmers, 2019, ISBN: 9780464243878, elérhető: https://github.com/hmemcpy/milewski-ctfp-pdf
Ivan Horton, Peter Van Weert: Beginning C++17, From Novice to Professional, 5. kiadás, Apress, 2018, ISBN: 978-1484233658
Tai-Danae Bradley: What is Applied Category Theory?, 2018, https://arxiv.org/abs/1809.05923
Philip Wadler: Propositions as Types, elérhető: https://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf