Cvičení 2

Témata

• Opakování algoritmizace - jednoduché příklady
• Programovací jazyky
  • Nižší a vyšší jazyky
  • Kompilační a interpretační jazyky

Opakování algoritmizace - jednoduché příklady

Proměnné

Obdobně jako v matematice je klíčovým pojmem v programování proměnná. V programování je však potřeba ji chápat méně abstrakně než v matematice. Úvodní stať o proměnných v programování se skrývá pod odkazem: Proměnné v programování

Elementárním algoritmem pro práci s proměnnými je výměna obsahu dvou proměnných. Vytvoření algoritmu je náplní první úlohy.

Úloha 2.1

Napište algoritmus pro výměnu obsahu dvou proměnných a, b.

Řešení: Řešení úlohy 2.1

Úloha 2.2

Napište algoritmus, který nalezne maximum ze tří hodnot uložených v proměnných a, b, c a uloží jej do proměnné max.

Řešení: Řešení úlohy 2.2

Úloha 2.3

Modifikujte algoritmus z úlohy 2.2 tak, aby nalezel maximum z pole prvků o velikosti n. Předpokládejte, že indexy prvků jsou v rozsahu 0 až n-1 v souladu s pravidly jazyka C.

Řešení: Řešení úlohy 2.3

Programovací jazyky

Nižší a vyšší jazyky

Nižší programovací jazyky (strojově orientované) jsou takové, kde příkazy jazyka přímo odpovídají instrukcím procesoru, pro který program píšeme (jsou to jejich zkratky) - viz cvičení 1. Programování v takovém jazyce je náročné, zápis není příliš srozumitelný a program není přenositelný na jiné typy procesorů (počítačů). Dnes se používají pouze výjímečně, např. při psaní rychlých programů pro řídicí jednočipové mikropočítače (i když i tam dnes převládá jazyk C), popř. při psaní jader operačních systémů.

Ukážeme jednoduchý příklad zápisu části programu, který odečte od čísla v paměťové buňce procesoru (registru) AX číslo v registru BX, porovná jej s nulou; pokud je výsledek nulový, začne se vykonávat kód pro (nějaký) výpočet počítej. Zkratky instrukcí jsou pro procesor Intel.

SUB AX, BX   ; sub - subtraction - odečte od AX BX a výsledek uloží do AX
CMP AX, 0    ;cmp - compare - porovnej hodnotu AX (tj. výsledek) s 0
JZ pocitej   ;jz - jump zero - pokud je výsledek 0,  skočí na funkci pocitej, jinak pokračuje dále

Program zapsaný v imperativním jazyku (např. Cobol, Pascal, Ada, C/C++, Basic, Java, Javascript, php, Python) je založen na zápisu algoritmu posloupností příkazů (zahrnující také cykly a větvení), využívají se proměnné. Část programu odečítající dvě čísla (předchozí příklad v assembleru) bychom v imperativním jazyce C napsali pomocí podmínky if a dvou proměnných a,b:

a = a-b; // odečti proměnnou b od a, výsledek ulož (přiřaď) do proměnné a 
if (a==0) pocitej(); // je-li a rovno 0, zavolej funkci pocitej

Mezi funkcionální jazyky patří např. Lisp (jehož varianta AutoLISP je součástí AutoCADu). Program ve funkcionálním jazyku je vlastně množina (ne posloupnost!) funkcí, většinou neexistují proměnné, místo nich se pracuje se seznamy dat.

V logickém jazyku je program zpravidla tvořen množinou nějakých odvozovacích pravidel, např. logických formulí. Logické jazyky se využívají zejména v umělé inteligenci, v expertních systémech. Typickým představitelem logického jazyka může být Prolog (logický jazyka vestavěný do databází a odvozený od Prologu je Datalog).
Ukážeme si zápis programu v Prologu jako množinu pravidel, který umí řešit problémy vztahů mezi členy rodiny.

Definujeme klauzule:

rodic(jana,lenka).
rodic(jana,petr). 
rodic(petr,eva).
muz(petr). 
zena(jana).
zena(eva).
zena(lenka).

Definujeme odvozovací pravidla:

syn(Y,X) :- rodic(X,Y), muz(Y). % Y je syn X, když X je rodič Y a Y je muž; čárka znamená logickou spojku „a“
dcera(Y,X) :- rodic(X,Y), zena(Y). % Y je dcera X, když X je rodič Y a Y je žena
prarodic(X,Z) :- rodic(X,Y), rodic(Y,Z). % X je prarodič Z, když X je rodič Y a Y je rodič Z
potomek(Y,X) :- syn(Y,X);dcera(Y,X). % Y je potomek X, když Y je syn X nebo Y je dcera X; středník znamená logickou spojku „nebo“

Pak můžeme klást dotazy:

?-rodic(A,Petr)
?-prarodic(Jana,Eva)

Systém odpoví na první dotaz A=Jana a na druhý yes.

V Prologu lze psát i výpočty.

Uvedený příklad ke stažení ve formě souboru: priklad.pl

Syntaxe a sémantika

Příklad: Syntaxe jazyka C říká, že cyklus s podmínkou na začátku se zapisuje:

while (podmínka) příkaz;

Sémantika (význam) takto zapsaného cyklu je: příkaz se provádí opakovaně tak dlouho, dokud je splněna podmínka.

Kompilační a interpretované jazyky

U interpretovaných jazyků není výsledkem procesu zpracování zdrojového kódu samostatně spustitelný soubor (nedochází vůbec k překladu). Abychom program spustili, musíme mít také speciální program, který se nazývá interpret. Vstupem interpretu je také zdrojový kód. Rozdíl je, že interpret přečte jeden řádek zdrojového kódu, provede syntaktickou kontrolu a ihned zajistí jeho provedení (vykonání). Na chyby v zápise programu se tedy přijde až při běhu programu (běh programu se v tomto případě přeruší). Příkadem interpretovaných jazyků je Basic, Python, JavaScript (interpret je přímo zabudován v internetovém prohlížeči), Visual Basic Script, Tcl, neimperativní jazyky.

Každý z obou přístupů má své výhody a nevýhody. Výhoda kompilačního jazyka je, že se provede syntaktická kontrola celého textu, výsledný program je možné spustit samostatně bez nutnosti mít speciální programové prostředí. Běžící samostatný program je rychlejší než v případě interpretovaného jazyka. Nevýhodou je, že při jakékoliv změně programu (zdrojového kódu) je nutné provést znovu překlad.
Hlavní nevýhodou programů zapsaných pomocí interpretovaného jazyka je jejich pomalý běh. Pokud se změní zdrojový kód, není potřeba jej překládat, nový program se spustí pomocí interpretu. Pokud existují interprety pro různé operační systémy, pak je snadná distribuce nových verzí programů uživatelům.

Několik moderních programovacích jazyků spojuje oba principy. Zdrojový kód syntakticky kontroluje překladač a provádí překlad jako u kompilačních jazyků. Výsledkem není samostatně spustitelný soubor, ale speciální soubor obsahující jakýsi „mezijazyk“ (vnitřní formu, virtuální strojový kód). Tato vnitřní forma je pak interpretována interpretem (kterému se také říká virtuální počítač či virtuální stroj). Výhoda tohoto přístupu je zřejmá - interpretace vnitřní formy je rychlejší než v případě klasického intepretačního jazyka, protože je při překladu provedena kompletní syntaktická kontrola a vnitřní forma může být optimalizována. Intepretace je samozřejmě ale pomalejší než při běhu samostatného kódu. Výhodou přístupu je, že mezijazyk může být intepretován stejně na různých platformách, pokud je k dispozici příslušný interpret.
Typickým zástupcem této technologie je jazyk Java. Zdrojový kód (soubory s příponou .java) jsou přeloženy do souboru s příponou .class (což je zmíněná vnitřní forma, v Javě nazývaná bytecode). Bytecode je pak interpretován programem, který se nazývá JVM (Java Virtual Machine). JVM je součástí internetových prohlížečů a interpretuje tzv. applety vložené do webových stránek.
Firma Microsoft představila vývojový systém .NET (Dot Net), který implementuje tento princip. Zdrojové kódy mohou být v zapsány v jazyce Visual Basic NET, Visual C NET, C# (C Sharp) NET. Vnitřní formu nazývá firma Microsoft zkratkou MSIL (Microsoft Intermediate Language), interpret této vnitřní formy se nazývá CLR (Common Language RunTime).

Poznámka k překladu: Každý programový balík překladače obsahuje soubory s programovými moduly nazývané knihovny (libraries). Jedná se o soubory s příponami .lib nebo .obj.Názorným příkladem knihovny je matematická knihovna. Procesory běžně nemají instrukci pro výpočet např. hodnoty funkce sin, logaritmu, odmocniny aj. Hodnoty se musí spočítat programově (např. součtem řady, přibližnými vzorci). Aby běžný programátor nemusel tyto výpočty zbytečně programovat sám, dodává výrobce překladače tyto funkce ve formě hotového strojového kódu právě v modulech zvaných knihovny.
A nyní konečně detailně k překladu. Překlad zpravidla probíhá dvoufázově. V první fázi, která se skutečně nazývá překlad a provádí ji překladač, se provede syntaktická kontrola. Výsledkem překladu není ještě samostatně spustitelný program, ale zatím jeho „polotovar“ Polotovar se nazývá object code a bývá uložen v souboru s příponou .obj, v operačních systémech Unixového typu typicky mají soubory příponu .o. Soubor s obj kódem obsahuje již části kódu s běžnými instrukcemi (např. sčítání). Pokud obsahuje zdrojový kód volání knihovních funkcí (např. sin), je v kódu pouze odkaz na volání funkce sin. Další fáze překladu je sestavení (neboli linkování) a provádí jej sestavovací program (linker). Vstupem sestavovacího program je object kód a potřebné knihovny. Sestavovací program vybere z knihoven kódy funkcí použitých v programu, připojí je k object kódu a teprve výsledkem sestavení je hotový spustitelný program.

Ukázku programu v interpretovaném jazyce Javascript, který je prováděn prohlížečem webových stránek, si můžete také stáhnout (je nutné uložit webovou stránku i soubor s kódem obsah.js a otevírat soubor vypocet_obsahu.html): vypocet_obsahu.html, obsah.js

Ukázku programu v jazyce C zatím nezveřejňujeme, bude náplní dalších cvičení, až se naučíme ovládat překladač jazyka C.