Nápady na zápočtové programy z Neprocedurálního programování

Naposledy upraveno: 2020-06-24

Byl bych rád, kdybyste si vymysleli vlastní, smysluplný, netriviální projekt. Pokud ale potřebujete inspiraci, tak se můžete podívat do následujícího seznamu. Témata rozhodně nejsou ekvivalentní/přiměřená obtížností – určitě je potřeba se mnou konzultovat jejich obtížnost!

Programovací jazyky (Haskell)

Napište parser a interpreter pro:

  • nějaký jednoduchý procedurální jazyk
    • Pascal se celkem jednoduše parsuje
    • můžete si ale vzít nějaké C--
    • klidně může být ezoteričtější – třeba s podporou českého jazyka jako definuj x; přiřaď x 20; atd.
  • Scheme, popřípadě nějaký Lisp
  • konkatenativní jazyk jako Forth
  • funkcionální jazyk (nějaký mini-Haskell)

Ke všemu výše uvedenému jdou dělat i věci jako:

  • pretty printer
  • zkombinováním parseru a pretty printeru dostanete zdarma formátovátko
  • typová analýza
  • statická analýza jako analýza mrtvého kódu, nebo CSE
  • optimalizátor kódu
  • makro expander – je libo generika v Go 1?
  • refaktorovací asistent, kterému dáte kus kódu a řeknete “argument 2 ve funkci foo přejmenuj na y” nebo “funkci bar všude inlinuj”
  • debugger
  • kompilátor/transpiler do RAMu/assembleru/LLVM/JavaScriptu/Céčka/něčeho jiného
  • virtuální stroj
  • language server protokol (pro napojení na Vim/VSCode)

K výše uvedeným nápadům mám hodně zdrojů, v případě zájmu určitě napište! :)

Programovací jazyky v přestrojení (spíše Haskell)

  • Vyrobte program, který bude provádět SQLovité dotazy nad databází v CSV/YAML/JSON souborech
  • Překladač z nějakého low-level jazyka na Turingův stroj + simulátor Turingova stroje
  • Vyhodnocovač lambda-kalkulového výrazu po krocích s volbou vyhodnocení uvnitř/zvenku, ideálně s barvičkami
  • Maličkatý SAT solver, třeba pomocí DPLL algoritmu
  • Malinkatý důkazový asistent, který umí i základy predikátové logiky – nabídne pár rozumných kroků kudy dál a nechá uživatele si vybrat
    • Tady se nabízí hezké vypisování ve stylu přirozené dedukce
  • Nástroj, který dostane co chcete regexem namatchovat a on vám vyrobí nějaký malý deterministický konečný automat (ideálně vyrobí rovnou regex pomocí Brzozwského metody)
    • Bonus: nástroj pochopí i negativní matche, tedy na příkladný vstup “mám rád pizzu”, “nemám rád pizzu” a “!mám rád koprovku” vrátí třeba ^^(?:ne)?mám rád pizzu$

Složitější algoritmy a datové struktury (jak Prolog, tak Haskell)

Vezměte nějaký netriviální algoritmus / netriviální datovou strukturu a naprogramujte jej / ji. Nezapomeňte si rozmyslet, jestli vybraný algoritmus vlastně jde naprogramovat v daném jazyce rozumně/efektivně!

Hádanky a puzzles (spíše Prolog)

  • Vyrobte AI pro nějakou jednoduchou deskovku – šachy, dáma, backgammon, reversi, lodě
  • Vyrobte efektivní řešítko pro nějaký puzzle – sudoku, nonogram, Lloydova patnáctka

Zpracování přirozeného jazyka (Prolog)

  • Naparsujte rovnici z textového popisu, např. “sedm plus závorka dva krát tři konec závorky” -> 7 + (2 * 3) a vyhodnoťte ji (a možná zapište výsledek zase slovy)
  • Vyrobte AI pro nějakou úzkou doménu, třeba pro souborový systém s dotazy “který soubor ve složce home je největší?”
  • Vyrobte jednoduchý překladač z lidského jazyka A do lidského jazyka B.
  • Vyrobte nějakého základního chatbota!
  • Vezměte jednoduchý jazyk jako Esperanto a vyrobte:
    • Překladač z daného jazyka do češtiny (či naopak)
    • Sémantický slovníček, kterému dáte za úkol najít slovo pro “vtipný člověk”, který pomocí spojování slov vyhodí amaz-ul-o, tedy “klaun”.
    • Syntaktický analyzátor – z věty vyrobí strom syntaxe
    • Sémantický analyzátor – u vět typu “Ferda je můj kamarád. On jezdí na koni.” bude schopen zjistit, že “On” v druhé větě je “Ferda”. Alternativně umí odpovědět na dotaz stylu “Co všechno víš o Ferdovi?”

Alternativní užitečnosti

Tato kategorie je velmi obecná – pokud si ji budete chtít vybrat, tak se určitě musíme domluvit na konkrétní podobě!

  • Prográmek, který vám ulehčí práci na bakalářce nebo souvisí s ročníkovým projektem
  • Chatbot / Permissions bot / jiný bot na IRC / Discord / Slack
  • Něco, co rozumně využije Haskell, tedy něco, co v tomto seznamu je označeno jako “Mature” nebo jako “Best in class”
  • Rozumné, netriviální vylepšení stávajícího projektu psaného v Haskellu/Prologu
    • Například můžete vylepšit editor, ve kterém běžně probíhají naše cvičení!
    • Dává také smysl vylepšovat tooling – ať už pro Haskellový LSP plugin nebo pro Prologový VSCode plugin, kde druhý zmíněný potřebuje forknout a zásadně updatovat

Podobné seznamy: