Obsah

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  N_{1} ... N_{n} upravujeme tak, že nejdříve, pokud to jde, redukujeme podvýraz N_{n} použitím striktní strategie. Pokud nelze, redukujeme striktně N_{n-1}, pokud také nelze tak N_{n-2} a tak dále. Pokud nelze redukovat žádný z podvýrazů N_{1} - N_{n}, tak redukujeme striktní strategií podvýraz M. Pokud ani ten nelze, znamená to, že M již nelze zjednodušit a celý výraz M  N_{1} ... N_{n} nahradíme pravou stranou jeho definice s dosazením hodnot výrazů N_{i} za její parametry.1)

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

Příklady

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

Normální redukční strategie

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

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

Příklady

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 
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 
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.3)

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 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  N_{1} ... N_{n} 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  N_{1} ... N_{n} nahradíme pravou stranou její definice s dosazením výrazů N_{i} 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)

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

Příklady

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.

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.

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(); 
} 

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:

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:

  1. 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)
  2. překrytí(override) - objekt přetěžuje(znovu definuje) poděděnou metodu (2)
  3. 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)
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.

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

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í:

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

Prolog

Syntax : datové objekty

Syntax: program

  1. množina programových klauzulí
  2. proměnné v lokální klauzuli
  3. pravidla: hlava:- tělo.
    1. date(D,M,Y):- day(D), month(M), year(Y).
  4. fakta: pravidla s prázdným tělem
  5. cíle: klauzule bez hlavy, reprezentují dotazy

Poznámky


Ř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

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.

1) , 2)
miniskripta, kapitola 3, strana 12
3)
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.
4)
miniskripta, kapitola 3, strana 13