Funkcionális programozás C++-ban

VERSENY IDEJE, HELYSZÍNE
November 21 (hétfő) 9:00-12:00, J202

VERSENYFELELŐS TANSZÉK
Távközlési és Médiainformatikai Tanszék

VERSENYFELELŐS OKTATÓ
Varga Pál

A VERSENY SZÖVEGES LEÍRÁSA
Hogy melyik a legjobb programozási paradigma? A versenynek nem célja ennek a kérdésnek a megválaszolása. De azok számára, akik már elgondolkodtak azon, hogy a modern C++-ban megjelenő új típusoknak hol kereshető a gyökere, azok számára kíván érdekes feladatok mentén betekintést nyújtani a funkcionális programozás tárházába. A verseny két részből áll. A gyakorlati részén rövid, elgondolkodtató C++ programok, függvények megírása a feladat, amelyek nem algoritmikus nehézségükkel, hanem elsősorban a megoldás során használható eszközökben való megkötéssel sarkallják funkcionális gondolkodásra a versenyzőket. Az elméleti megmérettetés a funkcionális programozás matematikai gyökereihez kalauzolja a versenyzőket: a lambda kalkulus és a kategóriaelmélet világába. A verseny időtartama három óra, amelyet a versenyzők tetszőlegesen oszthatnak meg a gyakorlati és elméleti rész között. A versenyen nem cél az összes feladat megoldása, a feladatokat úgy válogatjuk, hogy akár csak az elméleti, vagy akár csak a gyakorlati feladatok megoldásával előkelő helyezést lehessen elérni. A versenyen a BME minden BSc-s és MSc-s képzésén résztvevő hallgatója indulhat.

VERSENYEREDEMÉNY BESZÁMÍTÁSA
A tárgyat hallgatók számára a sikeres szereplés a vizsgán elért eredménybe is
beleszámít, kiemelkedő eredmény esetén megajánlott jelest is eredményezhet.

MINTA FELADATSOR

• A versenyen alapvetően az alábbi feladattípusokkal találkozhatnak a résztvevők:
  Programozás: egyszerű feladatok megoldása C++-ban megadott kritériumok
  mellett (pl. nem szabad ciklust használni)
• Sablonok: általános funkcionális függvények, adatstruktúrák tervezése és
  implementálása
• Bizonyítás: kategória- és funktortulajdonságok bizonyítása
• Redukciós szabályok, evolúciós szabályok: λ-kalkulus, illetve annak bővítése
  szintaktikus édesítőszerekkel

KATEGÓRIÁK
Nincs

HASZNÁLHATÓ SEGÉDESZKÖZÖK
Egy saját kézzel írt A4-es lap (2 oldal), számológép (amire nem lesz szükség), illetve papír és íróeszköz. A gyakorlati feladatok megoldása során használható laptop (használatát ajánljuk is), de annak használata után már nem lehet visszatérni az elméleti feladatokhoz. Nem szabad használni telefont, másik versenyzőt, ill. a felügyelő oktató(ka)t.

TÉMAKÖRÖK
λ-kalkulus, redukció, kategóriaelmélet, funktorok, monádok, funkcionális programozás, variadikus sablonok

FELKÉSZÜLÉST SEGÍTŐ ANYAGOK

• Csörnyei Zoltán: Lambda-kalkulus
• Benjamin C. Pierce: Types and Programming Languages
• Ivan Čukić: Functional Programing in C++
• Bartosz Milewski: Category Theory for Programmers
• Ivan Horton, Peter Van Weert: Beginning C++17, From Novice to Professional
• Tai-Danae Bradley: What is Applied Category Theory?
• Philip Wadler: Propositions as Types