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

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Funkcionális programozás C++-ban

    A tantárgy angol neve: Functional Programming in C++

    Adatlap utolsó módosítása: 2020. július 24.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar
    Villamosmérnöki szak
    Műszaki informatika szak
    Szabadon választott
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VITMAV47   1/0/1/f 2  
    3. A tantárgyfelelős személy és tanszék Dr. Varga Pál,
    4. A tantárgy előadója

    Dr. Varga Pál, PhD - egyetemi docens (TMIT)

    Németh Gábor - egyetemi tanársegéd (TMIT)

    Janky Ferenc Nándor (TMIT)

    5. A tantárgy az alábbi témakörök ismeretére épít C++ programozás alapjai
    6. Előtanulmányi rend
    Ajánlott:
    A programozás alapjai 2
    7. A tantárgy célkitűzése

    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.

    A gyakorlati megközelítésen, feladatok megoldásán túl fontos szerepet kap a tantárgyban az első funkcionális programnyelvnek is tekinthető lambda-kalkulus, valamint a kategóriaelmélet rövid bemutatása is - ezzel is segítve a bemutatott programozási fogások és struktúrák mind mélyebb megértését.
    8. A tantárgy részletes tematikája

    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.

    Laborfeladat: Gyakorlati feladat - ellenőrző mérés

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    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.

    10. Követelmények

    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 2 alkalommal lehet (ez 14 oktatási héttel, heti 2x45 perces laboratóriumi órával számolva minimum 85%-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)

    A tárgy félévközi jegyét a fenti követelmények teljesítése esetén a zárthelyi dolgozat, valamint a gyakorlati feladat során mutatott teljesítmények átlaga adja. A végső érdemjegy kialakításának értékelési rendszere megegyezik a zárthelyi dolgozat és a gyakorlati feladat értékelési módszerével.
    11. Pótlási lehetőségek

          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).

    12. Konzultációs lehetőségek

    Igény esetén, előzetes egyeztetés alapján.

    13. Jegyzet, tankönyv, felhasználható irodalom

    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

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra28
    Félévközi készülés órákra 
    Felkészülés zárthelyire10
    Házi feladat elkészítése22
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés 
    Összesen60
    15. A tantárgy tematikáját kidolgozta Németh Gábor, Janky Ferenc Nándor, Dr. Varga Pál
    IMSc tematika és módszer -
    IMSc pontozás -