/ Škola

Princípy programovacích jazykov a OOP (IPP) - poznámky

Polsem sa blíží a tak som sa rozhodol zverejniť moje poznámky z tohto predmetu. Ak pomôžu aspoň jednému študentovi lepšie pochopiť tento, na teóriu náročny predmet, malo to zmysel. Zároveň to môže by zaujímavé aj pre ľudí, ktorý by chceli pochopiť programovanie viac z teoretického hľadiska.

Tieto poznámky nie su konečné, a aj po publikovaní sa budú postupne rozširovať. Ak nájdete v poznámkach chybu, kontaktuje ma na:
spodlesny(ryba)gmail(bodka)sk

Changelog:
  • 5.3.2018 - začiatok prepisovania papierových poznámok
  • 11.3.2018 - Pridaný link na super PDF o lambda kalkul-e
  • 12.3.2018 - dokončená kapitola "Klasifikácia jazykov" z prvej študíjnej opory

Lambda kalkul

Klasifikácia jazykov

Programovanie

Činnost, ktorá istý postup, algoritmus (typicky myšlienkový) prevádza na postupnosť elementárnych úloh nejakého stroja (typicky počítača). Pritom dochádza k uloženiu tohoto postupu tak, aby ho stroj mohol opakovať periodicky.

Programátor

Ten, kto proces tvorby programu realizuje

Typické vlastnosti tvorby programu

  • vysoká náročnosť na čas a zdroje
  • znalosť programovacieho jazyka
  • špecifikácia poźiadaviek na cieľový produkt nie je bezchybná
  • preceňovanie/podceňovanie
  • ostré termíny

Programovací jazyk

  • prostredník medzi bežnou rečou a postupnosťou typicky binárnych číslíc
  • konečná mnoźina príkazov (prevádzaných do binárnej formy), ktorá má špecifickú syntaktickú štruktúru a pevne a presne vymedzenú sémantiku

Nevýhody prirodzeného jazyka

  • analýza je príliš náročná a do dnešného dňa neexistuje
  • nejednoznačnosť

Nevýhody binárneho jazyka

  • príliš náročný na zapamätanie
  • nevhodný pre zloźité programy
  • nevhodný pre rýchlu a efektívnu tvorbu programov

Počitačový program

  • zápis v programovacom jazyku, ktorý je abstrakciou reality
  • implementuje abstraktný model
    • myšlinkový postup aplikovateľný v realite je abstrahovaný
      a prispôsobený možnostiam počítača
  • abstrahuje model počítača/procesora
    • program zatieňuje konkrétnu podobu výpočtu a jeho realizácie na cieľovej platforme

Abstrakcia dát

Abstrakcia na dátovej úrovni v oblasti riadenia behu programu

Dátový model

Určuje ako su ktoré prvky reality modelované na úrovní dát a aká je ich vzájomná korešpondencia a význam

Výpočetný model

Definuje ako sa jednotlivé príkazy jazyka vzájomne prevezujú, ako dochádza k vetveniu výpoćtu a ako dochádza k predávaniu riadenia medzi jednotlivými časťami a pod.

Kategórie z hľadiska prístupu k deleniu a manipulácii s dátami

  • strojové/assemblery (x86, Thumb-2)
  • vyššej úrovne (než strojové, napr. Fortran, Cobol)
  • univerzálne jazyky (PL/I)
  • blokovo štrukturované jazyky
  • modulárne blokovo orientované jazyky
  • objektovo orientované jazyky
  • jazyky rozšírujúce dátové paradigma

Strojovo orientované jazyky

  • všetky dáta sú skupiny bitov či bajtov
  • typické aritmetické a bitové operácie
  • nulová podpora vyšej abstrakcia dát (neexistuje)
  • programy pre konkrétne zariadenie (?)

Prvé jazyky vyššej úrovne

  • len jednoduché dátové typy
  • dochádza k abstrakcii od cieľového systému
  • často maju definovanú pevnú štruktúru zdrojového textu
  • zloźitejšie dátové vzťahy sú obchádzané
  • predstaviteľ Fortran

Univerzálne jazyky

  • nikdy sa nepresadily
  • problem bol v tom, že sa mohli pouźívať iba uź existujúce štruktúry a typy (zoznam Osoba -> chýbajúce RČ -> vytvorenie nového typu zoznamu Osoba+)
  • predstaviteľ: PL/I

Blokovo štrukturované jazyky

  • patrí sem Pascal a čiastočnej aj C (bez modularity a kniźníc)
  • umožnuje definovať zloźitejšie dátové a riadiace štruktúry pomocou jednoduchých konštrukcii, ktoré je moźné spojovať alebo vnorova
  • ako prvá umožnuje pouźitie pouźitie a vyuźitie návrhových metodológii a SW inźinierstva (vďaka moźnosti definova vhodné dátové abstrakcie)

Modulárne blokovo štrukturované jazyky

  • umoźnuju oddeliť definíciu typu operácii, ktoré ho manipulujú
  • predstaviteľ C s kniźnicami (?)

Objektovo orientované jazyky

  • rozšíruju predchádzajúcu skupinu jazykov o moźnosť spojiť konkrétne dáta s operáciami, ktoré ich manipulujú

Jazyky iných paradigmat

  • logické
    • slúźia k automatickému dokazovaniu
    • na úrovni dát pracujú s predikátmi a termy
  • funkcionálne
    • riadia mezi dáta funkcie
  • pre sadzbu textu
    • dátova položka: typ písma, umiestnenie textu, nadpis, stránka a pod
  • pre definíciu a manipuláciu dát
    • DDL a DML užívané napríklad v relaćných databázach
    • datový typ tabuľka

Abstrakcia riadenia

  • procedurálne jazyky (imperatívne)
  • deklaratívne jazyky

Procedurálny jazyk

  • taký jazyk, kde programátor musí rieši tieto otázky riadenia behu programu:
    • aké operácie majú byť prevedené
    • v akom poradí majú byť prevedené
  • zostavujú program ako postupnosť príkazov, pričom niektoré je možné v urćitých jazykoch vnorovať
  • vyššie jazyky ponúkajú v podstate zhodnú sadu príkazov pre vyjadrenie opakovania a variantného výberu/vetvenia
  • na vyššej úrovni programového kódu rozoznávame tieto abstrakcie:
    • podprogramy
      • umožnujú vnorené spracovanie urćitých logických funkcii/operácii
      • volaný cez svoje rozhranie, ktoré definuje predávané parametre a výsledok
      • implementácia je skrytá v definícii podprogramu, kde môže dochádzať k volaniu iných programov alebo rekurzii
      • kaźdý podprogram má svj jedinečný identifikátor, ktorý ho sprístupňuje
    • bloky
      • nemajú meno
      • kód sa uplatňuje iba v mieste kde je vložený (nedá sa volať)
      • môže mať svoje lokálne definície
      • nie je možná rekurzia
    • ko-programy
      • pomenované bloky kódu
      • majú vzhľadom k sebe symetrický vzťah
      • spracovanie kódu je súćasne, prípadne prekladane (platformovo závislé)
      • rozhranie a identifikácia ako u podprogramov
    • paralelné programy/procesy
      • oproti ko-programom väčšie logické celky
      • vzťahy nie su nutne symetrické, avšak môže dochádzať k synchronizácii
      • na najvyšśej úrovni abstrakcie hovoríme o procesoch v rámci procesu o vláknach
      • ko-programi môžu byť implementované ako vlákna, ale nedysponujú synchronizačnými mechanizmami
    • odloźené spracovanie
      • vyhodnotenie operácie je pozdržané za predpokladu že výsledok nemusí byť nutne použitý
      • operácie sa vyhodnocujú sa až neskôr a aj to len v prípade že je topotreba

Deklaratívny jazyk

  • jazyky vysokej abstrakcie a vyjadrovacej sily
  • stretávamé sa s príkazmy pre vetvenie toku riadenia a opakovaní, ktoré je samozrejme moźné vnorovať
  • rôzne stratégie vyhodnocovania a volania podprogramov
  • stratégie volania podprogramu:
    • volanie hodnotou (call-by-value)
      • parametry sa vyhodnocujú pred volanim programu
      • v prípade eliminácie viacnásobného vyhodnocovania toho istého výrazu na viacerých miestach hovoríme o tzv. striktom vyhodnocovaní
    • volanie menom (call-by-name)
      • parametry sa predávajú nevyhodnotené a sú reprezentované zástupným menom
      • k vyhodnoteniu dôjde až do vyžaduje volaný program
      • označované ako nestriktné vyhodnotenie
    • volanie v prípade potreby (call-by-need)
      • program je najskôr zavolaný a až keď je potrebná hodnota parametru, tak dôjde k jeho vyhodnoteniu
      • hodnota sa uchováva, takže nedochádza k opakovanému vyhodnoteniu
      • tzv. lazy vyhodnotenie (nestriktné)

Špecifikácia jazyku, názvoslovie

Syntax jazyka

  • definuje štruktúru jazyka,t.j. akým spôsobom je dovolené radiť jednotlivé konštrukcie za seba
  • často sa pomocou syntaxe vysvetľuje taktiež i lexikálna stavba jazyka
  • pre definíciu syntaxe sa používa:
    • slovný popis (zriedkavo)
    • syntaktické grafy
    • BNF
    • EBNF
    • gramatiky

Sémantika jazyka

  • popis/definícia významu jednotlivých syntaktických konštrukcii, spôsobu ich vyhodnotenia, spracovania a pod.
  • pre popis sa väćšinou nepoužívajú formalizmy. Obvyklé ide o slovné vysvetlenie alebo príklad (na uźivateľskej úrovni)
  • formalizmy:
    • axiomatická sémantika - definovaná mnoźina axiómov, ktorá musí byť splnená, aby konštrukcia bola platná
    • operaćná sémantika - postupnosť prechodov medzi danými stavmi
    • denotačná sémantika - matematická funkcia zobrazujúca vstupy na výstupy
  • povahové vlastnosti sémantiky:
    • statická sémantika
      • popisuje vlastnosti, ktoré môžu byť študované a overené v dobe analýzy/prekladu programu
      • príklady: typová kontrola, existencia premenných a pod.
    • dynamická sémantika
      • popisuje vlastnosti, ktoré je možné overi až v dobe behu programu
      • príklady: veľkosť indexu poľa daného výrazom (?), veľkosť výsledku a pod.

Definícia vs deklarácia

Definícia

  • úplne vymedzuje atribúty danej entity a taktiež u premennych spôsob alokácie pamäte a u funkcii/precodúr taktiež telo funkcie
# definícia premennej
int ultimate_answer = 42;

# definícia funkcie
std::string what_was_the_question(int answer){
    sleep(99999999999999999999999999999999999);
    return "No one knows";
}

Deklarácia

  • úplne vymedzuje atribúty danej entity
  • implicitná alebo explicitná (?)
# deklarácia premennej
int ultimate_answer;

# deklarácia funkcie
std::string what_was_the_question(int answer);

Druhy väzieb medzi vytvorenou entitou a celou skupinou vlastnosti či atribútov (v čase)

  • počas definície samotného jazka
    • množina operácii nad daným typom
  • počas implementácie programu
    • priradenie typu premennej
  • počas prekladu programu
    • inicializačná hodnota premennej
  • počas spojovania preložených modulov (linking-u)
    • určenie adresy objektu cudzieho modulu pre prístup k nemu
  • počas spustenia programu
    • nadviazanie na štandardný vstup
  • v dobe behu programu
    • priradenie adresy lokálnej premennej
  • tieto väzby môžu byť statické aj dynamické

Vlastnosti premennej

  • meno
    • dĺžka mena
      • maximálna dĺžka mena
      • efektívna dĺźka mena (?)
        • udáva skutočný počet znakov, ktorý je skutočne spracovaný a rozlišovaný
    • povolené znaky
    • senzitivita
      • case sensitive / case insensitive
    • množina zakázaných identifikátorov
      • kľúćové slová ako if, for, while, return a pod.
  • adresa a umiestnenie/lokácia v pamäti
    • jedno meno premennej môźe byť spojované s viacerými umiestneniami a adresami
    • jedná adresa môže byť spojovaná s rôznymi menami
    • príklad: L=R, kde:
      • L-hodnota určuje umiestnenie a adresu v rámci tohto umiestnenia
      • R-hodnota reprezentuje hodnotu, ktorú obsahuje
    • väzba medzi umiestnením (t.j. adresou) a menom premennej, prípadne jej hodnotou môže byť ako statická, tak aj dynamická
      • statická
        • statické a globálne premenné
        • explicitne určená adresa premennej
        • viazaná hodnota ku konštante
      • dynamická
        • pri premenných lokálnych programov umiestňovaných na zásobných alebo pri premenných, vytváraných dynamicky na halde
        • rušenie môźe byť implicitné, explicitné alebo automatické
  • typ premennej
    • určuje mnoźinu možných hodnôt a operácii
    • väzba medzi typom a premennou je väčšinou statická
      • dynamická je pri skriptovacích jazykoch a interpreteroch
    • rozdelenie podľa typovosti:
      • beztypové (type-less)
      • netypované (non-typed)
      • typované (typed)
        • priradenie explicitné, alebo automaticky odvodené
  • rozsah platnosti premennej
    • určuje tú časť programu, kde je s premennou možné pracovať
    • nepliesť s dobou života premennej!
    • viditeľnosť premennej
      • aj keď je premenná platná, môže byť skrytá inou, rovnako pomenovanou premennou
  • doba źivota premennej
    • časový interval poćas ktorého je pre dannú premennú alokovana pamäť
    • alokácia môźe byť statická tak i dynamická (za behu)

Neštrukturované jazyky

  • predstavitelia Fortran, Basic a skriptovacie jazyky, ktoré sú však rozšírené aj o ďalšie, pokroćilejšie vlastnosti
  • syntax a sémantiku vysvetľuje dokumentácia cez slovný popis a príklady
  • formálnejšie zápisy typu BNF/EBNF sa väčśinou nepoužívaju (jednoduchá syntax)

Formálna báza

  • je taký formálny prostriedok (kalkul, algebra a pod.), ktorý umožnuje exaktne popísať všetky konštrukcie daného jazyka
  • slúži k tomu aby bolo možné vlastnosti jazyka dokázať či overi
    • často sa jedná hlavne o sémantiku, bezospornosť jazyka atď.
  • neštrukturované jazyky formálnu bázu nemajú!

Formálna verifikácia a validácia

  • pokiaľ chcem overiť že je nejaká vlastnosť algoritmu splnená
  • nie je používané a vlastne ani prakticky realizovateľné pri neštrukturovaných jazykoch

SW inźinierstvo

  • možnosť uplatnenia zásad SW inźinierstva je pomerne obmedzené, preto nie su odporúćané na rozsiahle projekty (poruśenie zásad dobrého programovania je velmi jednoduché)

Dátové a riadiace abstrakcie

  • neposkytujú buď źiadne dátové alebo riadiace abstrakcie, alebo len tie najjednoduchšie
  • dátová úroveň
    • stretávame sa hlavne so základnými numerickými typmi, znakovými reťazcami a poliami
  • riadiaca úroveň
    • cyklus s pevným krokom s riadiacou premennou (for), príkaz pre vetvenie (if) a skok

Otvorený podprogram

  • je uložený v rámci hlavného (často jediného) zdrojového textu
  • nemá pevne difonované rozhranie (vstupný/výstupny bod, parametry, výsledok a pod.)
  • vstup sa deje skokom na príkaz, ktorý má výpočet podprogramu začať
  • ukončenie podporgramu je dané vyvolaním príslušného príkazu (nie dobehnutím do/za určité miesto)
  • slúźia vlastne k uloženiu kódu, ktorý je možné spustiť viac krát a tak usporiť miesto v pamäti a čas programovania
  • častým nedostatkom je nemožnosť vnorovať volania a chýbajúca rekurzia
  • parametry a výsledky sú predávané cez globálne premenné
  • zvykom je umiestnovať podprogramy na začiatok programu s tým źe prvý príkaz je príkaz skoku
  • vysoká miera chybovosti a zloźitá štruktura pri väčších projektoch

Pseudo-moduly

  • otvorené podprogramy ale už oddelené od hlavného zdrojaku (v zvlášť súboroch)
  • stretávame sa pri takýchto jazykoch (ktoré pouźívaju pseudomoduly) s dynamickou definiciou premenných
  • preblem s cyklickým odkazovaním medzi sebou
    • väčšinou si to jazyk sám sleduje a dropuje to ako chybu
  • od otvorených podprogramov sa líśia v tom, źe vstupný bod je pevný, rovnako ako koniec
    • aj napriek tomu to nie je ani uzavretý podprogram, ani modul v pravom slova zmysle

Typy a ich spracovanie

  • väčšinou netypované
  • zmenám typu sa však dá zabrániť implicitným typom (rozpoznateľný podľa mena premennej)
  • väčšinou sa stretávame iba s poliami, číselnými a znakovými typmi

Tok riadenia programu

  • neštrukturované jazyky neponukaju źiadnu moźnosť ako blokovo śtrukturovať skupinu príkazov, ktoré sú radené sekvenćne, alebo logicky vnorené
  • jedná sa tak len o sekvenciu jednoduchých operácii, ktoré su interne previazané cez skoky
  • podprogramy maximálne ako otvorené podprogramy
    • vstupy často len skokom na daný riadok alebo cez návestia
  • tok riadenia a vyhodnotenia programu je ťažko čítateľný
  • prevod do štrukturovanej podoby je veľmi zloźitý

Spracovanie, analýza, vyhodnotenie, preklad

  • Obecne je možne vytvoriť a pouźiť tri základné typi programov:
    • analyzátor
    • vyhodnocovací program alebo interpreter
    • prekladač (compiler)

Analyzátor

  • program, ktorý analyzuje vstupný text a robí jeho dôkaldnú kontrolu ken na základe textu
  • vystupom je potencionálny zoznam chýb, varovaní a doporućení k danému programu
  • vhodný pokial preveruje vstup z hľadiska náležitosti k normám (PEP8 napríklad) alebo pokiaľ je analýza tak dôsledná že odhalí chyby, ktoré priahliada i samotný programátor (uloženie float-u do integeru napr. - warning)

Interpreter

  • program, ktorý rozpozná nejaký príkaz vo vstupnom programe a hned ho vykoná
  • prevádza tak vstupný program na postupnosť okamźite vykonávaných akcii (napríklad linuxový terminál)