Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

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