IB015 Neimperativní programování Organizace a motivace kurzu, programovací jazyk Haskell Jiří Barnat Sekce Organizace kurzu IB015 Neimperativní programování – 01 str. 2/36 Cíle kurzu Cíle kurzu Studenti se seznámí s funkcionálním a logickým paradigmatem programování, díky čemuž se odprostí od imperativního způsobu uvažování o problémech a jejich řešení. V rámci kurzu se studenti blíže seznámí s funkcionálním programovacím jazykem Haskell a s logickým programovacím systémem Prolog. IB015 Neimperativní programování – 01 str. 3/36 Schopnosti absolventa Schopnosti absolventa Rozumí funkcionálnímu a logickému výpočetnímu paradigmatu. Je schopen dekomponovat výpočetní problém na jednotlivé funkce a tuto schopnost používá při vytváření vlastních kódů i v imperativních programovacích jazycích. Chápe nedostatky techniky COPY-PASTE programování a umí tuto techniku programování efektivně nahradit. Má základní znalost programovacích jazyků Haskell a Prolog. IB015 Neimperativní programování – 01 str. 4/36 Požadavky a předpoklady pro úspěšné absolvování Předpoklady Možné úspěšně absolvovat bez znalosti programování. Schopnost abstraktního myšlení. Znalost imperativního programování Je výhodou pro pochopení rozdílného způsobu myšlení v imperativním a neimperativním světě. Může být zpočátku mentální bariérou. IB015 Neimperativní programování – 01 str. 5/36 Požadavky na ukončení Forma ukončení Závěrečný písemný test. Vnitrosemestrální písemný test (! nelze opakovat). Možnost získat až 10 bodů za domácí úlohy ze cvičení. Možnost získat až 10 bodů za aktivitu na cvičení. Požadavky na úspěšné ukončení Nutno získat 48 bodů ze 100+. Body za aktivitu na cvičení se přičtou pouze pokud součet ostatních bodů je alespoň 48. IB015 Neimperativní programování – 01 str. 6/36 Kontext v rámci FI Obory IB015 je povinná součást studijního základu. Doporučen převážně do 3. semestru studia. Navazující předměty IB016 Seminář z funkcionálního programování IB013 Logické programování IA014 Funkcionální programování (???) IA008 Výpočetní logika IB015 Neimperativní programování – 01 str. 7/36 Zdroje a učební materiály Funkcionální paradigma http://haskell.cz/ Thompson, Simon. Haskell: the craft of functional programming. Structure and Interpretation of Computer Programs [http://mitpress.mit.edu/sicp/full-text/book/book.html] Logické paradigma http://www.learnprolognow.org Nerode, Shore: Logic for Applications IB015 Neimperativní programování – 01 str. 8/36 Sekce Co znamená programovat? IB015 Neimperativní programování – 01 str. 9/36 Programování a programovací jazyk Programování Vytváření a zápis postupu řešení problému s takovou úrovní detailů a přesnosti, aby tento popis mohl být mechanicky vykonáván strojem, zejména počítačem. Zápis postupu = zdrojový kód programu. Programovací jazyk Uměle vytvořený jazyk pro přesný a jednoznačný zápis programů člověkem. IB015 Neimperativní programování – 01 str. 10/36 Co znamená umět programovat? Schopnost programovat Mentální schopnost nacházet mechanicky proveditelné postupy za účelem řešení daného problému. Schopnost přesně formulovat postupy v daném programovacím jazyce. Volba a znalost programovacího jazyka Programovacích jazyků je mnoho. Volba programovacího jazyka klade omezení na způsob formulace zamýšlených postupů. IB015 Neimperativní programování – 01 str. 11/36 Riziko moderní doby Riziko Dokumentace k programovacím jazykům jsou snadno dostupné i ve formě tutoriálů, avšak samotné poznání syntaxe a sémantiky programovacího jazyka nedělá dokonalého programátora. IB015 Neimperativní programování – 01 str. 12/36 Riziko moderní doby Riziko Dokumentace k programovacím jazykům jsou snadno dostupné i ve formě tutoriálů, avšak samotné poznání syntaxe a sémantiky programovacího jazyka nedělá dokonalého programátora. Nedokonalé vs. dokonalé IB015 Neimperativní programování – 01 str. 12/36 Riziko moderní doby Riziko Dokumentace k programovacím jazykům jsou snadno dostupné i ve formě tutoriálů, avšak samotné poznání syntaxe a sémantiky programovacího jazyka nedělá dokonalého programátora. Nedokonalé vs. dokonalé IB015 Neimperativní programování – 01 str. 12/36 Programovací jazyky Klasifikace Imperativní — C/C++, Java, Perl, php, . . . Funkcionální – Haskell, OCaML, Erlang, Lisp, . . . Logické – Prolog, . . . Kombinované – C#, Scala, C++, . . . . . . Jakým jazykem mluví počítač? Strojový kód. Program ve strojovém kódu je posloupnost čísel. Pro spuštění programu je potřeba provést překlad zdrojového kódu programu do strojového kódu procesoru. Překlad se realizuje pomocí překladače nebo interpretru. Pro každý programovací jazyk je potřeba jiný překladač/interpretr. IB015 Neimperativní programování – 01 str. 13/36 Překladače a interpretry Překladač Pro soubor se zdrojovým kódem programu vytvoří soubor obsahující popis programu ve strojovém kódu. Výsledný soubor je spustitelný. Pracuje se soubory. Interpret Pro daný výraz / příkaz vytvoří odpovídající překlad do strojového kódu a ihned jej provede. Nevytváří výsledný spustitelný soubor. Často má možnost pracovat interaktivně. Pracuje s jednotlivými příkazy/výrazy. IB015 Neimperativní programování – 01 str. 14/36 Příklad překladu a interpretace Programovací jazyk Haskell Překladač – ghc. Interaktivní interpretr – ghci (dříve též hugs). Neinteraktivní interpretace – runghc. Překladače programovacího jazyka C/C++ GNU C++ Compiler (g++, gcc) Intel C++ Compiler Microsoft Visual C++ Compiler IB015 Neimperativní programování – 01 str. 15/36 Sekce Programujeme pomocí funkcí IB015 Neimperativní programování – 01 str. 16/36 Co je to funkce? Funkce v programování Funkce je předpis jak z nějakého vstupu vytvořit výstup. Transformace vstupů na výstupy musí být jednoznačná. Příklady funkcí f x = x*(x+2) objemkvadru a b c = a*b*c ... IB015 Neimperativní programování – 01 str. 17/36 S čím funkce pracují Typ funkce Vymezení objektů, se kterými daná funkce pracuje a které vrací na výstup, je součástí definice funkce. Mluvíme o tzv. typu funkce. Příklady Funkce, která otočí obrázek o 90 stupňů směrem vpravo. rotate90r :: Obrázek -> Obrázek Objem kvádru. objemkvadru :: Číslo × Číslo × Číslo -> Číslo Počet hran polygonu. hranypolygonu :: Polygon -> Celé_číslo IB015 Neimperativní programování – 01 str. 18/36 Aplikace funkce – příklad Předpoklady rotate90r :: Obrázek -> Obrázek hranypolygonu :: Obrázek -> Celé_číslo :: Obrázek Aplikace funkcí rotate90r = hranypolygonu = 3 IB015 Neimperativní programování – 01 str. 19/36 Funkce jako základní stavební kameny Pozorování Složitější úkony lze realizovat pomocí jednodušších operací. Složitější funkce lze definovat složením jednodušších. IB015 Neimperativní programování – 01 str. 20/36 Funkce jako základní stavební kameny Pozorování Složitější úkony lze realizovat pomocí jednodušších operací. Složitější funkce lze definovat složením jednodušších. Skládání – cesta ke složitějším objektům a funkcím IB015 Neimperativní programování – 01 str. 20/36 Skládání funkcí Operátor . f1 ( f2 x ) = (f1 . f2) x Čteme jako „f1 po f2”. Příklad Mějme funkci double, která vezme obrázek a vytvoří nový obrázek zkopírováním původního obrázku dvakrát vedle sebe. double :: Obrázek -> Obrázek double = Novou funkci rotate_and_double můžeme definovat takto: rotate_and_double :: Obrázek -> Obrázek rotate_and_double x = (double . rotate90r) x rotate_and_double = IB015 Neimperativní programování – 01 str. 21/36 Skládání funkcí a priority operací v Haskellu Složené funkce a η-redukce Složení funkcí je možné definovat bez uvedení parametru. Tj. definici rotate_and_double x = (double.rotate90r) x lze zapsat také jako rotate_and_double = double.rotate90r POZOR na prioritu vyhodnocování v Haskellu Aplikace funkce na parametry má nejvyšší prioritu. double.rotate90r = double.(rotate90r ) ERROR Závorky kolem výrazu double.rotate90r jsou při aplikaci na hodnotu nutné. IB015 Neimperativní programování – 01 str. 22/36 Příklady (rotate_and_double . rotate_and_double) = ((double . double) . double) = (double . hranypolygonu) = IB015 Neimperativní programování – 01 str. 23/36 Příklady (rotate_and_double . rotate_and_double) = ((double . double) . double) = (double . hranypolygonu) = IB015 Neimperativní programování – 01 str. 23/36 Příklady (rotate_and_double . rotate_and_double) = ((double . double) . double) = (double . hranypolygonu) = IB015 Neimperativní programování – 01 str. 23/36 Příklady (rotate_and_double . rotate_and_double) = ((double . double) . double) = (double . hranypolygonu) = ERROR IB015 Neimperativní programování – 01 str. 23/36 Příklady – pokračování Jak lze pomocí double, rotate90r a vyrobit následující? a) b) IB015 Neimperativní programování – 01 str. 24/36 Terminologie Typová signatura: rotate_and_double :: Obrázek ->Obrázek Jméno funkce rotate_and_double x = (double.rotate) x Tělo funkce rotate_and_double x = (double.rotate) x Definice funkce rotate_and_double x = (double.rotate) x IB015 Neimperativní programování – 01 str. 25/36 Terminologie – pokračování Formální parametr rotate_and_double x = (double.rotate) x Aktuální parametr rotate_and_double Výraz rotate_and_double Podvýraz rotate_and_double (rotate_and_double ) IB015 Neimperativní programování – 01 str. 26/36 Sekce Funkcionální programování v Haskellu IB015 Neimperativní programování – 01 str. 27/36 Funkcionální výpočetní paradigma Funkcionální výpočetní paradigma program = výraz + definice funkcí výpočet = úprava (zjednodušování) výrazu výsledek = hodnota (nezjednodušitelný tvar výrazu) Příklad programu definice funkcí square x = x * x pyth a b = square a + square b výraz pyth 3 4 IB015 Neimperativní programování – 01 str. 28/36 Výpočet funkcionálního programu Program definice funkcí square x = x * x pyth a b = square a + square b výraz pyth 3 4 Výpočet pyth 3 4 square 3 + square 4 3 * 3 + square 4 3 * 3 + 4 * 4 9 + 4 * 4 9 + 16 25 IB015 Neimperativní programování – 01 str. 29/36 Základy Haskellu – Lokální definice Lokální definice Definují symboly (funkce, konstanty) pro použití v jednom výrazu, vně tohoto výrazu jsou tyto symboly nedefinované. Lokální definice mají vyšší prioritu než globální definice. V Haskellu pomocí let ... in let definice in výraz let fcube x = x * x * x in fcube 12 let fcube x = x * x * x in let c = 12 in fcube c let fcube x = x * x * x; c = 12 in fcube c IB015 Neimperativní programování – 01 str. 30/36 Základy Haskellu – Základní datové typy Čísla Integer – libovolně velká celá čísla Int – celá čísla do velikosti slova procesoru Float – reálná čísla Fractional – racionální čísla Znaky a řetězce Char – znak, příklady hodnot: ’a’, ’2’, ’>’ String – řetězec, například: "Toto je řetězec." String je totéž co [Char] Pravdivostní hodnoty Bool Typ Bool má pouze 2 hodnoty: True a False IB015 Neimperativní programování – 01 str. 31/36 Základy Haskellu – Víceřádkové definice Příklad Definujte funkci jedna_nebo_dva, která vrací True pokud dostane na vstupu číslo 1 nebo 2, jinak vrací False. jedna_nebo_dva :: Integer -> Bool jedna_nebo_dva 1 = True jedna_nebo_dva 2 = True jedna_nebo_dva _ = False Víceřádkové definice funkcí Na místě formálních parametrů se použijí tzv. vzory. Použije se první vzor, který vyhovuje. Symbol _ vyhovuje libovolnému parametru. Lze použít pro větvení výpočtu. IB015 Neimperativní programování – 01 str. 32/36 Základy Haskellu – Větvení výpočtu Podmíněný výraz if podmínka then výraz1 else výraz2 podmínka – výraz, který se vyhodnotí na hodnotu typu Bool výraz1 se vyhodnotí pokud se podmínka vyhodnotí na hodnotu True, výraz2 se vyhodnotí, pokud se podmínka vyhodnotí na hodnotu False. Výrazy výraz1 a výraz2 musejí být stejného typu. Test na rovnost Pro dotaz na rovnost používáme symbol ==. 3 == 4 False 3 = 4 Error IB015 Neimperativní programování – 01 str. 33/36 Základy Haskelu – Infix, Prefix, Parametry Možnosti zápisu binárních funkcí Infixový zápis binárních funkcí: 3+4, 4*5 Prefixový zápis binárních funkcí: (+) 3 4, (*) 4 5 Volání funkce a parametry Jméno funkce a použité parametry jsou odděleny mezerou, pokud je některý z parametrů výraz, který je sám o sobě aplikace funkce na argumenty, je třeba celý tento výraz ozávorkovat. (*) 3 4 + 5 17 (*) 3 + 4 5 Error (*) 3 (+) 4 5 Error (*) 3 ( (+) 4 5 ) 27 IB015 Neimperativní programování – 01 str. 34/36 Základy Haskellu – Komunikace s uživatelem Vstup výstupní operace Operace, které čtou a zapisují data z/do souborů, či terminálu. Program v Haskellu je reprezentován výrazem main. Program je sekvence vstup-výstupních akcí. Funkcionální princip vstup/výstupních akcí je složitý, bude vysvětlen později. do notace programu v Haskellu main = do putStr "Zadej celé číslo: " x <-getLine print ((+) 1 (read x::Int)) Textové zarovnání je důležité! IB015 Neimperativní programování – 01 str. 35/36 Práce na doma Zadání Napište a spusťte program v Haskellu, který bude řešit dělitelnost dvou čísel, tj. zeptá se uživatele na dělence, načte ho, pak se zeptá na dělitele, kterého také načte, a sdělí uživateli, zda je zadaný dělenec dělitelný beze zbytku zadaným dělitelem. IB015 Neimperativní programování – 01 str. 36/36