Rysy imperativně orientovaných jazyků, jazyků funkcionálního programování a logického programování. Rysy objektově orientovaných jazyků. Znalost na úrovni porozumění základním paradigmatům.
V tomto případě je program tvořen posloupností příkazů (odtud imperativní).V každém kroku je určeno co se má vykonat v kroku následujícím a v každém kroku se změní stav progarmu. Programátor tak musí analyzovat všechny situace, do kterých se může program dostat a podle toho tvořit program.
Z toho vyplývá, že program napsaný v imperativním programovacím jazyce předpisuje jak něco spočítat.
Imperativní jazyky mají svou podstatou blízko k samotným počítačům, které provádějí strojový kód, který je sekvence nějakých příkazů. Např. imperativní programovací jazyky běžně používají explicitní přiřazení do proměnné a její uložení na nějaké paměťové místo. Vyšší programovací jazyky pak mohou používat cykly, podmínky cyklů, funkce a procedury.
Mezi první imperativní programovací jazyky patřil např. FORTRAN, dále ALGOL a COBOL. Mezi v současnosti rozšířené imperativní programovací jazyky patři C, Pascal případně PHP.
Imperativní programování využívá tři základní skupiny příkazů.
Přiřazení obecně provádí operaci s informací uloženou v paměti a ukládá výsledek do paměti pro pozdější použití. Vyšší programovací jazyky navíc dovolují provádění komplexnějších výrazů, jež mohou sestávat z kombinace aritmetických operací, programových funkcí a přiřazování výsledných hodnot do paměti.
Cykly dovolují opakovat sekvenci příkazů několikrát za sebou. Počet opakování pak může být přesně určen nebo se sekvence může opakovat do té doby, dokud se nezmění určená podmínka.
Větvení dovoluje provést určitou část příkazů jen tehdy, byla-li splněna příslušná podmínka. V opačném případě je tato část přeskočena a pokračuje se v provádění příkazů bezprostředně následujících. Příkazy pro větvení také umožňují přejít do jiné části programu, zpravidla voláním podprogramu (funkce, procedury).
Funcionální programování je paradigma postavené na evaluaci funkcí. Nepoužívá stavy ani neprovádí přiřazení do proměnných.
Určitý základ funkcionálních programovacích jazyků lze nalézt v lamda kalkulu (i když se jednalo spíše o matematickou abstrakci) a dále v tzv. logice kombinátorů, kterou lze nahlížet jako lambda kalkul bez proměnných.
– znamená, že v daném kontextu představuje proměnná vždy jednu a tutéž hodnotu nebo také, že volání funkce na stejných parametrech vrátí vždy stejnou hodnotu (chybí totiž globální proměnné, vedlejší efekty a přiřazení do proměnné).
Příklad:
y = f(x) * f(x);
může kompilátor transformovat na
z = f(x);
y = z * z;
a ušetří jednu evaluaci funkce.
Výrazy můžeme vyhodnocovat obecně mnoha způsoby, způsob vyhodnocování je určen redukční strategií. Redukční strategie je pravidlo, které pro každý výraz jednoznačně určuje první redukční krok. Tedy redukční strategie určuje, který podvýraz se bude redukovat jako první.
Volba redukční strategie může ovlivnit, zda vůbec dospějeme k výsledku. Nemůže se však stát, abychom dvěma různými strategiemi dospěli k různým výsledkům.
Striktní a líné vyhodnocování – funkcionální jazyky se mohou dělit podle toho zda používají striktní, nebo líné vyhodnocování. Striktní vyhodnocování vyžaduje předávání funkce hodnotou, kdežto líné vyhodnocování může za parametry funkce předávat i nevyhodnocený výraz.
Striktní redukční strategie je taková strategie, při které vyhodnocujeme nejdříve argumenty, tedy aplikaci upravujeme tak, že nejdříve, pokud to jde, redukujeme podvýraz použitím striktní strategie. Pokud nelze, redukujeme striktně , pokud také nelze tak a tak dále. Pokud nelze redukovat žádný z podvýrazů , tak redukujeme striktní strategií podvýraz . Pokud ani ten nelze, znamená to, že již nelze zjednodušit a celý výraz nahradíme pravou stranou jeho definice s dosazením hodnot výrazů za její parametry.1)
sq x = x * x
Výraz sq(sq 3) se při použití striktní redukční strategie bude vyhodnocovat:
sq (sq 3) ~> sq (3 * 3) ~> sq 9 ~> 9 * 9 ~> 81
f x = f x const x y = x
Ve výrazu const 3 (f 1) se bude podvýraz f 1 při použití striktní redukční strategie vyhodnocovat nekonečně dlouho, tedy výpočet se zacyklí a k výsledku nedojdeme nikdy:
const 3 (f 1) ~> const 3 (f 1) ~> const 3 (f 1) ~> ...
eat x y = x && (x || y)
Redukujeme-li výraz eat (not False) (not True) striktně, vyhodnotí se každý z argumentů jednou.
Normální redukční strategie je taková, při které aplikaci upravujeme tak, že nejdříve redukujeme (pokud to jde) podvýraz použitím normální strategie, pokud to nejde, znamená to že M již nelze zjednodušit a celý výraz nahradíme pravou stranou její definice s dosazením výrazů za její parametry.2)
sq x = x * x
Výraz sq(sq 3) se při použití normální redukční strategie bude vyhodnocovat:
sq (sq 3) ~> sq 3 * sq 3 ~> (3 * 3) * sq 3 ~> 9 * sq 3 ~> 9 * (3 * 3) ~> 9 * 9 ~> 81
f x = f x const x y = x
Výraz const 3 (f 1) se při použití normální redukční strategie bude vyhodnocovat:
const 3 (f 1) ~> 3
eat x y = x && (x || y)
Redukujeme li výraz eat ( not False) ( not True) normálně, vyhodnotí se první argument dvakrát a druhý se nevyhodnotí ani jednou.3)
Jedná se o modifikovanou verzi normální redukční strategie, využívající faktu, že funkcionální jazyky jsou referenčně transparentní, tedy že jakýkoli výraz se ve stejném prostředí vyhodnotí vždy stejně, vyhýbá se tak opakovanému vyhodnocování stejných podvýrazů.
Líná redukční strategie je taková, při které aplikaci upravujeme tak, že nejdříve redukujeme, pokud to jde, podvýraz M použitím líné strategie. Když M redukovat nelze, znamená to, že M je funkce a celý výraz nahradíme pravou stranou její definice s dosazením výrazů za její parametry stejně jako u normální redukční strategie. Nyní si však při každém násobném dosazení zapamatujeme, které podvýrazy vzniklé dosazením za různé výskyty téže proměnné jsou stejné, a při jejich případném dalším vyhodnocování je redukujeme jen jednou, jakoby všechny naráz.4)
eat x y = x && (x || y)
Redukujeme li výraz eat (not False) (not True) líně, vyhodnotí se první argument jednou a druhý ani jednou.
– které berou za vstup opět funkce
- často se používá místo iterace
Mezi funkcionální jazyky patří např. LISP, ML a mezi čistě funkcionální jazyky pak např. Haskell, Miranda.
Logické programování vychází z použití matematické logiky v programování. Patří mezi deklarativní paradigma – obdobně jako funkcionální programování je jeho úkolem zadat co je třeba spočítat nikoliv jak to spočítat.
Logické programování je založeno na ohraničené části logicky prvního řádu. Pro logiku prvního řádu platí, že dovoluje užívání predikátů „Pro každé něco“ nebo „Existuje něco“, ale něco musí být individuum, ne predikát. Dále je založeno na logice Hornových klauzulí, což jsou konečné množiny literálů spojených disjunkcí, a které se pro potřeby logického programování přepisují do tvaru:
(P1 & P2 & P3 … ) → Q
Literály jsou výrokové proměnné nebo jejich negace.
Program v jazyce Prolog je pak konečná množina Hornových klauzulí a skládá se z tzv. faktů, pravidel a dotazů.
Ilustrace z čeho se skládá:
otec(Jan, Pavel) – Fakt
otec(Pavel, Jana) – Fakt
děda(X,Y) :- otec(X,Z), (X,Y) – Pravidlo
A dotaz:
?-otec(jan,pavel) yes
Zástupcem logického programování je programovací jazyk Prolog, jehož vznik se datuje do roku 1972.
Základní princip objektového programování je jednoduchý – vše jsou objekty. Objekt má svůj obraz v reálném světě, má vlastnosti a chování reprezentovány atributy a metodami. Objekt navenek zpřístupňuje rozhraní, pomocí kterého se s objektem pracuje. Veřejné rozhraní objektu je dáno veřejnými metodami objektu. Dále se pak uplatňují následující vlastnosti.
Třídy
Jsou vyjádřením abstrakce skupiny stejných objektů (stejné atributy a vlastnosti). Např. třída člověk. Každý objekt ze třídy je pak instance třidy a dědí z ní všechny atributy a metody.
Person kuba = new Person("Kuba"); //novy objekt kuba je instanci tridy Person
Jednotlivé atributy a metody jsou vlastnosti instancí objektu, nikoliv tříd.
kuba.name //atribut instance uchovavajici jmeno kuba.getName() //metoda vracejici jmeno
Speciálním případem třídy je abstraktní třída. Je to třída která obsahuje nejméně jednu abstraktní metodu a z této abstraktní třídy není dovoleno vytvářet instance. Teprve třída, která je jejím potomkem (viz dále) a implementuje všechny abstraktní metody, může vytvářet instance. Neabstraktní metody abstraktní třídy jsou společné všem potomkům.
public abstract class SqlOperations { abstract void sqlConnect(); //tato metoda bude rozdilna pro Oracle, MySQL... } public class MySqlOperations extends SqlOperations{ void sqlConnect() { //implementace podle potreby } }
Interface (rozhraní) je množina hlaviček metod, které mohou být implementovány třídou. Pokud třída implementuje rozhraní, musí doimplementovat všechny jeho metody. Pokud tedy existuje rozhraní
public interface ElectricalDevice { public void switchOn(); public void switchOff(); }
a nějaká třída jej implementuje, můžeme si být jisti, že instance dotyčné třídy obsahují metody switchOn() a switchOff(). V C++ interface není.
if (microwave instanceof ElectricalDevice) { //trida Microwave implementuje ElectricalDevice microwave.switchOn(); }
Dědičnost
Pomocí dědičnosti se generuje hierarchie tříd, kde potomci přebírají všechny metody a atributy z rodičovské třídy a mohou si přidávat své vlastní a tak mohou rozšiřovat funkčnost bez zasahování do kódu rodiče (overriding - překrytí, předefinování rodičovských metod + vytváření vlastních).
Dědičnost odpovídá vztahu generalizace specializace (automobil → nákladní automobil lze dědit, protože nákladní automobil je speciální případ automobilu, ovšem bod → bod+poloměr dědit nelze, protože kruh není speciální případ bodu). V Javě je možné, aby třída byla přímým potomkem pouze jedné třídy.
Zapouzdření
Objekt, se kterým pracujeme, je černá skřínka s rozhraním, komunikujeme s ním pomocí rozhraní, nemůžeme mu sahat dovnitř a od jeho vnitřní implementace se abstrahujeme. Souvisí to s přístupovými právy jednotlivých tříd, atributů a metod (v Javě public, protected, implicitní práva, private).
Atributy by měly být privátní (jinak porušení zapouzdření), přístup k nim by měl být povolen pouze přes metody (viz Spolupráce objektů). Příklad:
public class Person(){ private String personName; public void changePersonName(String newName){ //tato metoda umoznuje kontrolu jmena pred jejim prirazenim atributu //k samotne personName neni z vnejsku tridy pristup if (allowNewName(newName)) { personName = newName; } } }
Polymorfismus
Stejně pojmenovaná metoda se může chovat různě v různých případech. Obecně rozlišujeme 3 druhy polymorfismu:
abstract class Zvire(){ public Zvire(){} abstract void makeNoise(); public void runAway(){ System.out.print("Zvire utika pryc."); } } public class Kocka() extends Zvire{ //Kocka dědí metody třídy Zvire, jde o dedičnost public Kocka(){ } public void makeNoise(){//**(1)** System.out.print("Mnau mnau."); } } public class Ptak() extends Zvire{ public Ptak(){} public void makeNoise(){//**(1)** System.out.print("Pip pip."); } @Override public void runAway(){ //**(2)** System.out.print("Zvire odletlo pryc."); } public makeNoise(string zvuk){ //**(3)** System.out.print("Pip pip."+zvuk); } public makeNoise(int times){ //**(3)** System.out.print("Pip pip "+times.toString()+" krát"); } }
Spolupráce objektů Pokud objekty implementují rozhraní, tak z vnějšku s tímto objektem komunikují ostatní objekty pomocí rozhraní.
Spolupráce objektů je úzce svázaná s Objektově orientovaným návrhem. V návrhu se definují vazby mezi jednotlivými třídami, tj. volání metod mezi třídami, přistupování k atributům tříd atd. Pokud je dobře provedený návrh, tak je možné z tohoto návrhu rovnou vygenerovat balíčky, rozhraní a třídy včetně metod a atributů a programátor pak jen naimplementuje jednotlivé metody.
Funguje to podobně jako volání metod v rámci jedné třídy - vytvoříme si instanci třídy (nebo použijeme vhodnou existující), zavoláme metodu a dostaneme návratovou hodnotu(pokud je void, tak jen provede kód a nevrátí nic). Samozřejmě je třeba myslet i na výjimky.
Většina jazyků již má hotové nejrůznější balíčky objektů, které můžeme použít při běžné práci - například při komunikaci s databází, tvorbu GUI atd.
Zástupcem objektových programovacích jazyků je např. SmallTalk, C++ či Java.
Prolog je logický programovací jazyk. Patří mezi tzv. deklarativní programovací jazyky, ve kterých programátor popisuje pouze cíl výpočtu, přičemž přesný postup, jakým se k výsledku program dostane, je ponechán na libovůli systému. Prolog se snaží o pokud možno abstraktní vyjádření faktů a logických vztahů mezi nimi s potlačením imperativní složky. Prolog je využíván především v oboru umělé inteligence a v počítačové lingvistice (obzvláště zpracování přirozeného jazyka, pro nějž byl původně navržen).
Vyhodnocovací mechanizmus Prologu prochází SLD-strom do hloubky zleva doprava a hledá (první) úspěšnou cestu (backtracking) – případně projde celý strom a vyhlásí, že to není možné.
- zadání středníku (;) po úspěšném vyhodnocení čísla vynutíme backtracking a hledání alternativního důkazu
- odpověď „no“ systému znamená, že daný cíl není logickým důsledkem programu (případně že nemá alternativní důkaz) prologovská strategie prohledávání stavového prostoru (do hloubky) může vést k zacyklení (i v případě, že existují úspěšné větve)
Příklad programu, který vede k zacyklení, i když existují úspěšné větve:
q:- r.
r:- q.
q.
?- q.
Logické programování:
Prolog
Řekl bych, že zadání zhruba odpovídá těmto vypracovaným otázkám z bakalářských státnic:
A taky:
Pouze poznámky
Typy
Deklarativní paradigmata
Imperativní paradigmata
Marek Menšík UČO 266679
Nevím přesně, kdo otázky zpracoval přede mnou, pouze jsem je sem umístil, doplnil chybějící věci a opravil nepřesnosti. Připomínám, že věci zde uvedené nemusí být korektní a zatím neprošly kontrolou žádného z profesorů. Z mé strany je tato otázka dokončena a případné chybějící věci a chyby mě můžete napsat na UČO mail nebo se registrujte a upravte je sami.