====== N-AP9 ======


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.
====== Rysy imperativně orientovaných jazyků ======
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.

===== Základní typy příkazů =====
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).

====== Rysy jazyků funkcionálního programování ======


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.


===== Vlastnosti =====


=== Referenční transparentnost ===

 – 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.

=== Redukční strategie ===

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 ==

**Striktní redukční strategie** je taková strategie, při které **vyhodnocujeme nejdříve argumenty**, tedy aplikaci <m>M  N_{1} ... N_{n}</m> upravujeme tak, že nejdříve, pokud to jde, redukujeme podvýraz <m>N_{n}</m> použitím //striktní strategie//. Pokud nelze, redukujeme //striktně// <m>N_{n-1}</m>, pokud také nelze tak <m>N_{n-2}</m> a tak dále. Pokud nelze redukovat žádný z podvýrazů <m>N_{1} - N_{n}</m>, tak redukujeme striktní strategií podvýraz <m>M</m>. Pokud ani ten nelze, znamená to, že <m>M</m> již nelze zjednodušit a celý výraz <m>M  N_{1} ... N_{n}</m> nahradíme pravou stranou jeho definice s dosazením hodnot výrazů <m>N_{i}</m> za její parametry.((miniskripta, kapitola 3, strana 12))

<note>
  * Při striktní redukční strategii postupujeme zevnitř. 
  * Při použití striktní redukční strategie vyhodnocujeme argumenty funkcí právě jednou.
  * Striktní redukční strategii se zejména v imperativních jazycích říká volání hodnotou.
  * Striktní redukční strategie se používá v jazycích, které nejsou čistě funkcionální, je výhodnější v menší spotřebě paměti při vyhodnocování. V jazycích s vedlejšími efekty by bylo líné vyhodnocování nepřehledné -- to je další důvod, kdy je vhodné používat striktní redukční strategii.
</note>

=== Příklady===
<box blue 100%>
Mějme funkci **sq** definovanou:


  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
</box>

<box blue 100%>Mějme funkce **f**, **const** definované předpisy:


  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) ~> ...
</box>

<box blue 100%>Mějme funkci **eat** definovanou :


  eat x y = x && (x || y)

Redukujeme-li výraz **eat (not False) (not True)** striktně, vyhodnotí se každý z argumentů jednou.
</box>

== Normální redukční strategie ==

**Normální redukční strategie** je taková, při které aplikaci <m>M  N_{1} ... N_{n}</m> upravujeme tak, že nejdříve redukujeme (pokud to jde) podvýraz <m>M</m> použitím normální strategie, pokud to nejde, znamená to že M již nelze zjednodušit a celý výraz <m>M  N_{1} ... N_{n}</m> nahradíme pravou stranou její definice s dosazením výrazů <m>N_{i}</m> za její parametry.((miniskripta, kapitola 3, strana 12))

<note>
  * Pokud je možné výraz M redukovat nějakou redukční strategií na výslednou hodnotu, dospějeme k ní použitím normální redukční strategie po konečném počtu kroků -- tedy normální redukční strategie je **efektivně normalizující**, výpočet se nezacyklí, pokud nemusí.
  * Při normální strategii postupujeme z vnějšku.
  * Normální redukční strategie nemusí vést k nejkratšímu výpočtu.
  * Normální redukční strategie bývá nazývána zejména v imperativních jazycích volání jménem.
  * Při normální redukční strategii vyhodnocujeme argumenty tolikrát, kolikrát na to při výpočtu dojde.
</note>

=== Příklady ===
<box blue 100%>Mějme funkci:

  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
</box>

<box blue 100%>Mějme funkce **f**, **const** definované předpisy:

  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
</box>

<box blue 100%>Mějme funkci **eat** definovanou :

  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.((Počítá se s tzv. zkráceným vyhodnocováním u operátoru ||, součástí jehož definice je následující předpis: True || _ = True ... proto se druhý argument nevyhodnotí ani jednou.))
</box>

== Líná redukční strategie ==

 
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 <m>M</m> 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 <m>M  N_{1} ... N_{n}</m> 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 <m>M  N_{1} ... N_{n}</m>   nahradíme pravou stranou její definice s dosazením výrazů <m>N_{i}</m> 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.((miniskripta, kapitola 3, strana 13))

<note>
  * Platí obdobné tvrzení jako u normální strategie, pokud má výraz nějakou výslednou formu, dospěje se k ní po konečném počtu kroků líné redukční strategie.
  * Při líné redukční strategii vyhodnocujeme každý argument nejvýše jedenkrát.  
  * Díky líné redukční strategii je možné pracovat i s nekonečnými datovými strukturami.
</note>

=== Příklady ===
<box blue 100%>Mějme funkci **eat** definovanou:

  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.</box>

=== Funkce vracející funkce ===
 – které berou za vstup opět funkce

=== Rekurze ===
 - č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.

====== Rysy jazyků logického programování ======


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. 

====== Rysy objektově orientovaných jazyků ======


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.
<code java>
Person kuba = new Person("Kuba");    //novy objekt kuba je instanci tridy Person</code>

Jednotlivé **atributy** a **metody**  jsou vlastnosti instancí objektu, nikoliv tříd.
<code java>
kuba.name         //atribut instance uchovavajici jmeno
kuba.getName()    //metoda vracejici jmeno
</code>
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.
<code java>
public abstract class SqlOperations {
    abstract void sqlConnect(); //tato metoda bude rozdilna pro Oracle, MySQL...
}

public class MySqlOperations extends SqlOperations{
    void sqlConnect() {
        //implementace podle potreby
    }
}

</code>

**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í
<code java>
public interface ElectricalDevice {
    public void switchOn();
    public void switchOff();
}
</code> 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í. <code java>
if (microwave instanceof ElectricalDevice) {    //trida Microwave implementuje ElectricalDevice
    microwave.switchOn();
}
</code>

===== Koncepty OOP =====

**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: <code java>
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;
        }
    }
}
</code>

**Polymorfismus**

Stejně pojmenovaná metoda se může chovat různě v různých případech. Obecně rozlišujeme 3 druhy polymorfismu:
     - objektový polymorfismus - v objektovém programovacím jazyku pod pojmem polymorfismus rozumíme to, že dva objekty rozšiřující třídu různým způsobem implementují stejnou abstraktní metodu **(1)**
     - překrytí(override) - objekt přetěžuje(znovu definuje) poděděnou metodu **(2)**
     - pretížení (overload) - stejně nazvaná metoda má stejnou obecnou funkcionalitu, ale může pracovat s různými parametry (např. zásobník.push(X) s parametry int X, bool X, string X bude fungovat vždy jako zásobník) **(3)**
<code java>
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");
      }
}
</code>



**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 [[home:prog:ap14|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.

====== Ostatní ======

===== Prolog =====
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). 


==== Výpočetní mechanismus Prologu ====
  * úspěšné cesty v SLD-stromě jsou ty, které končí □, ostatní jsou neúspěšné.

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.''


==== Základy programování v Prologu ====
 
**Logické programování:**
  - logický program = libovolná konečná množina programových Hornových klauzulí
  - odvozování (dokazování) cílů založené na SLD-rezoluci
  - deklarativní (specifikace programu je přímo programem)
  - teoretický model, zachovává úplnost

**Prolog** 
  * konkrétní implementace logického programovacího jazyka 
  * ztráta úplnosti (možnost zacyklení)
  * vhodný na řešení problémů týkajících se objektů a vztahů mezi nimi, 
  * do značné míry využívá rekurzi


=== Syntax : datové objekty ===
  * Základem jsou **termy** (konstanty, proměnné, složené termy)
      - konstanty 
              - celá čísla (0, -12, ...)
              - desetinná čísla (1.0, 4.5E7, ...)
              - atomy ('ježek', [], ==, ...)
      - proměnné (N, VYSLEDEK, ...)
      - složené termy: 
              - funktor (jméno, arita)
              - argumenty (bod(X,Y,Z),tree(Value, tree(LV,LL,LR), tree(RV,RL,RR)))

=== Syntax: program ===
              - množina programových klauzulí
              - proměnné v lokální klauzuli
              - pravidla: **hlava:- tělo.**
                        - **date(D,M,Y):- day(D), month(M), year(Y).**
              - fakta: pravidla s prázdným tělem
              - cíle: klauzule bez hlavy, reprezentují dotazy
=== Poznámky ===
  * do značné míry využívá rekurzi
  * patří mezi deklarativní programovací jazyky

  * využíván v oboru umělé inteligence a zpracování přirozeného jazyka

  * založen na predikátové logice prvního řádu, zaměřuje se na Hornovy klauzule
              - seznamy 
                   - definovány induktivně
                   - [] - prázdný seznam
  * základní využívané přístupy jsou unifikace a rekurze

  * anonymní proměnná **_** (podtržítko), její hodnota není podstatná
              - používá se v pravidlech **je_dite(X):- dite(X,_).**
  * základ Prologu je databáze klauzulí (fakta a pravidla), nad kterou je možno klást dotazy formou tvrzení, kde Prolog vyhodnocuje jejich pravdivost
              - fakta - nejjednodušší klauzule, vypovídající o vlastnostech a vztazích mezi objekty, př. **dívka(monika)**
              - pravidla - odvozování nových dat pomocí aplikace **hlavička:- tělo.**
                         - hlavička - odvozovaný fakt
                         - tělo - podmínky
                         - př. **syn(A,B):- rodic(B,A), muz(A).**


----

Řekl bych, že zadání zhruba odpovídá těmto vypracovaným otázkám z bakalářských státnic:
  * [[home:prog:ap3|AP3, IN3 Programování]]
  * [[home:prog:ap4|AP4, IN4 Objektově orientované programování]]
  * [[home:inf:ap13|AP13 Prolog]]

A taky:
  * [[home:inf:ap4|AP4, IN4 Výroková logika]]
  * [[home:inf:ap6|AP6, IN6 Rekurze]]
  * [[home:inf:ap7|AP7, IN7 Vyhodnocování výrazů]]
  * [[home:inf:ap14|AP14 Predikátová logika prvního řádu]]
  * [[home:inf:ap15|AP15, IN15 Datové struktury a jejich implementace]]


----

Pouze poznámky

Typy
  * Silně typovaný vs slabě typovaný
  * Dynamicky typovaný vs staticky typovaný
  * Kontextově závislé vs nezávislé přetížení funkce
  * Kovariance a Kontravariance ([[http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)]])

  * připomenutí: XSLT je funkcionální jazyk

**Deklarativní paradigmata**
  * Program popisuje, co je výsledkem.
  * Funkcionální –- program je výraz a výpočet je jeho úprava.
  * Logické –- program je teorie a výpočet je odvození z ní.

**Imperativní paradigmata**
  * Program popisuje, jak se dospěje k výsledku.
  * Procedurální –- výpočet je provádění procedur nad daty.
  * Objektové -– výpočet je předávání zpráv mezi objekty.

====== Vypracoval ======
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.

~~DISCUSSION~~