PRG005 Neprocedurální programování

• Obsah a cíle předmětu
• Co bylo na přednášce
• Podmínky pro získání zápočtu
• Zkouška
• Požadavky ke zkoušce
• Ukázkové zadání písemky ve formátu rtf
• Literatura
  • Základní literatura
  • Doplňková literatura
• Překladač SWI
• Stránka k mému cvičení úterý 14:00 S6

Obsah a cíle předmětu

• První část přednášky je věnována programování v jazyce Prolog.
  V Prologu se také vytvářejí a ladí zápočtové úlohy.
• V druhé (velmi krátké) části přednášky se seznámíme se základy funkcionálního programování na bázi jazyka LISP.
  V seminářích (jednom nebo dvou) se přesvědčíte, že řadu obratů, které jste si osvojili v Prologu, velmi snadno přenesete do programování v LISPu. Cílem této části je připravit půdu pro třetí část přednášky, LISP se u zkoušky nevyžaduje.
• Poslední část přednášky je věnována výkladu funkcionálního programování na bázi jazyka Haskell.
  Nepůjdeme do teoterických detailů jazyka, ale soustředíme se spíše na praktické programování v něm.

Podmínky pro získání zápočtu

Student může získat zápočet za splnění dvou požadavků :

• Aktivní účast na seminářích a průběžné znalosti během semestru.
• Vytvoření a odladění zápočtového programu v Prologu.
  K zápočtovému programu je potřeba vytvořit smysluplnou dokumentaci. Součástí předávaného programu musí být i zkušební ladící data. Jejich volba je součástí toho, co se na programu hodnotí.

Získání zápočtu je podmínkou připuštění ke zkoušce.
Vzhledem k množství studentů nebude umožněno se ke zkoušce přihlásit dokud nebudete mít zápočet. Není to však prakticky žádné omezení. Jazyk Prolog se úplně probere na 5-7 prvních přednáškách.

Podmínky pro udělení zápočtu upřesňuje a kontroluje vedoucí semináře, na který student chodí. Při přebírání zápočtového programu se zpravidla vhodným způsobem přesvědčí zda student program vytvořil sám (např. může požadovat provedení drobných změn v programu v reálném čase).

Pokud student (kombinovaného) studia nemůže semináře navštěvovat, dohodne si začátkem semestru náhradní podmínky udělení zápočtu s přednášejícím.

Literatura:

Základní literatura (bude ještě doplněna):

1. Rudolf Kryl: Úvod do programovacího jazyka Prolog
   učební text - ke stažení z WWW stránek přednášejícího aktuální verze 3.03 ve formátu pdf nebo zip.
   Text byl původně napsán pro čtenáře s o poznání menší programátorskou erudicí, než má většina z Vás. Proto by mělo jít o "nenáročné čtení před usnutím". Text pokrývá přibližně první polovinu látky z Prologu. Obsahuje řadu jednoduchých programů. Budu vděčný za připomínky a opravy chyb - posílejte je na můj mail a v subjectu uveďte název textu a číslo verze, ke které se připomínky vztahují.
2. Přehled předdefinovaných forem ve vykládaném dialektu LISPu
   Ke stažení ve formátu pdf
3. Miran Lipovača: Learn You Haskel
   Pěkná základní online učebnice. Je ale určena čtenářům, kteří mají o hodně menší programátorské schopnosti a zkušenosti než Vy. V podstatě tam nejsou složitější příklady. Mnohdy také řešení (jednoduché) úlohy je vlastně jen použitím nějaké vhodné knihovní funkce. Na zkoušce budu požadovat, abyste úlohy i tyto funkce naprogramovali nebo to udělali jinak základními prostředky jazyka.
4. Paul Hudak, Joseph H. Fasel: A Gentle Introduction to Haskell
   ke stažení z www.haskell.org
   Poměrně čtivý základní text o programovacím jazyku Haskell (jeho starší verzi). Pokrývá většinu toho, co probereme. Některé partie vynecháme, půjdeme však podstatně dál v programátorské obtížnosti úloh.
5. Haskell 2010 - Language report
   přesná definice jazyka - není na běžné čtení, ale můžete použít jako zdroj informaxcí o daném konkrétním rysu jazyka i jako zdroj pěkně napsaných definicí funkcí.
   
Na dané adrese můžete získat úplný přehled o problematice jazyka Haskell a stáhnout si prostředí.

Doplňková literatura (není nutná)

1. P.Jirků a kol. : Programování v jazyku Prolog
   SNTL 1991
   Pěkná knížka v češtině. Neobsahuje mnoho těžších příkladů, věnuje se však dost podrobně souvislostem s logikou.
2. Bratko I.: PROLOG Programming for Artificial Intelligence
   Addison-Wesley, Reading, Massachussets, 1986 ISBN 0-201-14224-4
   Stále velmi pěkná knížka. První díl obsahuje výklad Prologu (náš přístup k výkladu je do značné míry poplatný přístupu této knihy), druhý obsahuje výklad některých základních partií umělé inteligence pomocí programů v Prologu.
3. Harold Abelson, Gerald Jay Sussman, Julie Sussman : Structure and Interpretation of Computer Programs
   Mc Graw-Hill Book Company 1985 ISBN 0-07-000-422-6
   Výklad principů programování na bázi jazyka XSCHEME (dialekt jazyka LISP). Kniha byla používána v základnídním kursu programování na MIT.
   My použijeme tohoto jazyka i příkladů z této knihy k velmi zběžnému seznámení s principy LISPu.
4. Ivan Kalaš : Iné programovanie - stretnutie s jazykom Lisp
   Alfa 1992
   Krásná kniha s množství originálních příkladů. Uživaný dialekt LISPu se poněkud liší od toho, se kterým budeme pracovat na přednášce my.

Překladač prologu SWI

K ladění zápočtových programů a experimentům v Prologu doporučuji překladač SWI Prolog. Jde o volně stažitelný výborný překladač, který je k dispozici pro všechny platformy. Obecně lze experimenty s jazykem vřele doporučit, možná však je dobré počkat až z přednášky a seminářů ovládnete základy jazyka. Na třetí nebo na čtvrté přednášce si o práci s tímto překladačem řekneme více.

Informace o zkoušce

Požadavky ke zkoušce

Zkouška má písemnou a ústní část, větší váhu má část písemná.

Písemná část

1. Technická - čas 120 minut (bude ještě upřesněno)

   Bude obsahovat (algoritmicky) jednoduché úlohy na programování v Prologu a Haskellu.

2. Programátorská - 90 minut

   Úkolem bude vyřešit v Haskellu středně obtížnou úlohu, požaduje se volba vhodných datových struktur, rozumného algoritmu a vytvoření odpovídajícího kódu v Haskellu.
   Složitost zvoleného algoritmu nemusí být optimální, ale nesmí být neúnosně velká.
   Haskell je pro tuto část předepsán proto, že naprostá většina studentů řeší zápočtovou úlohu v Prologu.

Součástí řešení úloh v písemné části nemusí být vstup a výstup, ale "jen" algorimická část řešení.
U všech funkcí v Haskellu je nutné napsat jejich typovou specifikaci.
Není nutné znát předdefinované funkce v Haskellu, ale pokud je budete používat je nutné je naprogramovat,
Je nutné (alespoň pasivně) znát základní konstrukce pro definování typů, funkcí a tříd v Haskellu, abyste byli schopni odpovídat na otázky typu "co dělá tato funkce" resp. " je daná definice dobře?" a pod.
V obou částech písemné práce se požadují taková řešení, která vycházení z principů neprocedurálního programování, za správná nebudou uznána taková, která jsou založena tom, jak tyto principy obejít.

Ústní část zkoušky se skládá

• ze společné (zkoušející a zkoušený) opravy písemné části a diskuse nad vytvořenými programy
• ze zodpovězení otázek z některého z dále uvedených témat

Témata pro ústní zkouškut :

• PROLOG
  1. Tvar programu v Prologu a jeho interpretace
  2. Deklarativní a operační sémantika programu v Prologu
  3. Operátor řezu
  4. Negace
  5. Edinbugrský model vstupu a výstupu.
  6. Definování a použití operátorů
  7. Predikáty pro řízení databáze (assert,...)
  8. Predikáty grupování termů (bagof, setof) a jejich užití
  9. Neúplně definované datové struktury, rozdílové seznamy
  10. Efektivita programů v Prologu
 
• HASKELL
  1. Typy v Haskellu, typová specifikace funkce
  2. Sémantika "mečování" parametrů: proměnné, datové konstruktory, as patterns ( @s ), žolíky ( _ ), lazy-parametry ( ˜x ), aritmetické parametry.
  3. Lazy vyhodnocování, "nekonečné" termy, funkce v Haskellu nejsou striktní.
  4. Lambda abstrakce.
  5. Třídy, podtřídy, instance.
  6. Moduly, abstraktní typy dat
  7. Pole v Haskellu.
  8. Principy I-O operací, monáda IO
  9. Pojem monády, příklady konkrétních monád.