No title

Programovací jazyky Ing. Marek Běhálek Katedra informatiky FEI VŠB-TUO A-1018 / 597 324 251 http://www.cs.vsb.cz/behalek [email protected]

Obsah Co je to programovací jazyk Vývoj programovacích jazyků Paradigma programování a různá paradigmata programování Specifikace programovacích jazyků Překladače Klasifikace jazyků a méně tradiční přístupy k programování Studijní program „Informační a komunikační technologie“ ZPP - Programovací jazyky

2

Programovací jazyk Popis výpočtů, obvykle ve tvaru, jenž umožňuje provedení elektronickým počítačem (program) Standardizovaný nástroj pro komunikaci s počítačem S jakými daty má počítač pracovat? Jak se tato data budou ukládat a přenášet? Které akce a kdy se mají provést? ZPP - Programovací jazyky

3

Proč používáme programovací jazyky? Zjednodušují přenos určitého typu informace Noty v hudbě Matematické formule Elektrotechnická schémata

Vyznačují se velkou přesností vyjádření Přirozené jazyky – vynechávání, gramatické chyby, víceznačnost

Jsou obvykle proveditelné na počítači Značkovací jazyky (HTML) – data, ne program Specifikační jazyky (λ-kalkul) – teoretický výzkum ZPP - Programovací jazyky

4

Historie – Teoretické začátky Alonzo Church 30. léta - lambda-kalkul jako základ teorie vyčíslitelnosti Alan Turing ukázal, že stroj může řešit problémy "programování ve strojovém kódu omezuje rychlost a snadnost programování počítačů„ John von Neumann pojem paměti základní model většiny současných počítačů návrh zkratek pro Mark I ZPP - Programovací jazyky

5

Historie – První jazyky kolem 1946 Konrad Zuse – Plankalkul použit také pro šachy rukopis publikován až v roce 1972, nebyl nikdy implementován 1949 John Mauchly - Short Code první počítačový jazyk skutečně použitý na elektronickém zařízení určen pro zadávání rovnic "ručně kompilovaný" jazyk 1951 Grace Murray Hopper prosazovala vytvoření vyšších jazyků pracovala na návrhu prvního překladače zavedla pojem "počítačový virus" ZPP - Programovací jazyky

6

Historie - Úrovně jazyků Strojově orientované jazyky instrukce, adresy přímo závislé na konkrétním procesoru náročný vývoj aplikací

Jazyky vyšší úrovně Delší doba překladu a generování cílového kódu Větší nároky na čas a paměť v době běhu programu Přenositelnost - podstatně menší závislost programů na konkrétním technickém vybavení Čitelnost Prostředky abstrakce - abstrakce dat a operací Kontrola a detekce chyb - ještě před spuštěním programu ZPP - Programovací jazyky

7

Historie – První překladače Výraz "kompilátor" poč. 50. let - Grace Murray Hopper překlad jako 'kompilace posloupnosti podprogramů z knihovny' “automatické programování“ - kompilace v dnešním slova smyslu, považovalo se za nemožné 1954-57 FORTRAN (FORmula TRANslator) John Backus, IBM problémově orientovaný, strojově značně nezávislý, optimalizace prokázala se vhodnost kompilovaných jazyků vysoké úrovně ad hoc struktury - komponenty a technologie se vymýšlely během výstavby překladače překladače se chápaly jako něco tajemného, složitého a drahého (18 člověkoroků - jeden z největších projektů v té době) ZPP - Programovací jazyky

8

Historie – FORTRAN C C C

10

Vypocet funkce faktorial INTEGER FUNCTION FACT(N) IMPLICIT NONE INTEGER N, I, F F = 1 DO 10 I = 1,N F = F * I CONTINUE FACT = F END PROGRAM P1 IMPLICIT NONE INTEGER N, F, FACT READ(*,*) N F = FACT(N) WRITE(*,*) "Fact = ", F END ZPP - Programovací jazyky

9

Historie – Vyšší jazyky (1) 1958-59 LISP 1.5 (List Processing) John McCarthy, M. I. T. první funkcionální jazyk - implementace lambda-kalkulu možnost imperativního stylu programování 1958-60 ALGOL 60 (Algorithmic Language) J. Backus, P. Naur bloková struktura, složené příkazy, rekurze syntax poprvé popsána formálně gramatikou (BNF) koncem 60. let se stal nejpopulárnějším jazykem v Evropě základ mnoha dalších programovacích jazyků

ZPP - Programovací jazyky

10

Historie – ALGOL 60 begin integer N; ReadInt(N); begin real array Data[1:N]; real sum, avg; integer i; sum:=0; for i:=1 step 1 until N do begin real val; ReadReal(val); Data[i]:=if val<0 then -val else val end; for i:=1 step 1 until N do sum:=sum + Data[i]; avg:=sum/N; PrintReal(avg) end end ZPP - Programovací jazyky

11

Historie – Vyšší jazyky (2) 1960 COBOL (Common Business Oriented Language) pro vytváření rozsáhlých programů k vládním a obchodním účelům formalizovaný anglický text, čitelný pro manažery zavedl propracované záznamové struktury 1964 BASIC (Beginners All-Purpose Symbolic Instruction Code) John G. Kemeny, Thomas E. Kurz, Dartmouth University 1975 Tiny BASIC běží na mikropočítači s 2KB RAM 1975 Bill Gates, Paul Allen prodávají firmě MITS 1963-64 PL/I (Programming Langugage I) kombinace jazyků COBOL, FORTRAN, ALGOL 60, snaha, aby obsahoval "všechno pro všechny" => příliš složitý zavedl konstrukce pro souběžné zpracování a výjimky ZPP - Programovací jazyky

12

Historie – Vyšší programovací jazyka (2) Strukturované programování 1968-71 Pascal Niklaus Wirth, ETH Zurich jednoduchý jazyk, určen pro výuku programování P-kód – instrukce virtuálního procesoru specializované procesory pro P-kód 1972 C Dennis Ritchie určen částečně pro návrh přenositelných operačních systémů

Modulární programování 1980 Modula-2 1980-83 Ada ZPP - Programovací jazyky

13

Historie – Objektově orientované programování (1) 1964-67 SIMULA 67 1972 Smalltalk Alan Kay, Xerox - původně pouze experimentální jazyk čistě objektově orientovaný - vše je objekt, předávání zpráv první jazyk podporující GUI s okny 1982-85 C++ Bjarne Stroustrup, AT&T Bell Labs odvozen z jazyka C => mnoho nebezpečných vlastností, např. dynamické přidělování paměti bez GC, aritmetika s ukazateli 1997 ISO a ANSI standard 1984-85 Objective C 1994-95 Java James Gosling, Sun Microsystems původně pro vestavná zařízení, později široké použití v rámci WWW, strojově nezávislý binární kód (Java bytecode), použití just-in-time překlad 2000-02 C# Anders Hejlsberg, Microsoft, základní jazyk architektury .NET ZPP - Programovací jazyky

14

Historie – Jazyk a architektura počítače Omezení jazyku na to, co lze efektivně implementovat na současných procesorech. Von Neumannova architektura Model klasických procesorů Základ klasických jazyků

Funkcionální jazyky Backus (1978, Turing Adward) – kritika přístupu „od architektury k jazyku“ Funkcionální jazyky jsou efektivnější než imperativní Lze dokazovat vlastnosti programů Jednoduše je lze paralelizovat Založeno na algebraických pravidlech Malá efektivita implementace – možné optimalizace ZPP - Programovací jazyky

15

Paradigmata programování Úvod Paradigma programování určuje styl programování. Paradigma programování reprezentuje a definuje jakým způsobem vnímá programátor vykonávání programu. Například objektově orientované paradigma programování definuje program jako kolekci komunikujících objektů. Různé programovací jazyky implementují různá paradigmata programování. Jazyk může být založen na jednom, ale klidně i na více paradigmatech. Často není striktní – jazyk obsahuje více paradigmat a záleží na programátorovi, jaký kód vyprodukuje (strukturovaný program v C++). Jednotlivé paradigmata mají většinou určité specifické vlastnosti.

Existuje celá řada paradigmat pro programování Vznikají stále nové. ZPP - Programovací jazyky

16

Paradigmata programování – Různá paradigmata (1) Annotative programming (as in Flare language) Aspect-oriented programming (as in AspectJ) Attribute-oriented programming (might be the same as annotative programming) (as in Java 5 Annotations, pre-processed by the XDoclet class; C# Attributes ) Class-based programming, compared to Prototype-based programming (within the context of object-oriented programming] Concept-oriented programming is based on using concepts as the main programming construct. Constraint programming, compared to Logic programming Data-directed programming Dataflow programming (as in Spreadsheets) Flow-driven programming, compared to Event-driven programming Functional programming Imperative programming, compared to Declarative programming Intentional Programming Logic programming (as in Mathematica)


17

Paradigmata programování – Různá paradigmata (2) Message passing programming, compared to Imperative programming Object-Oriented Programming (as in Smalltalk) Pipeline Programming (as in the UNIX command line) Policy-based programming Procedural programming, compared to Functional programming Process oriented programming a parallel programming model. Recursive programming, compared to Iterative programming Reflective programming Scalar programming, compared to Array programming Component-oriented programming (as in OLE) Structured programming, compared to Unstructured programming Subject-oriented programming Tree programming Value-level programming, compared to Function-level programming ZPP - Programovací jazyky

18

Specifikace programovacích jazyků - Co chceme popsat? Jak má vypadat správně napsaný program? SYNTAXE Formální jazyky, gramatiky, automaty

Co má program dělat? SÉMANTIKA Predikátový počet, lambda kalkul, atributové gramatiky ZPP - Programovací jazyky

19

Specifikace programovacích jazyků Syntaxe - struktura jazykových konstrukcí Textové jazyky (C, Pascal, Java) Grafické jazyky (vývojové diagramy, UML) a > 10 ano x := x + 5

ne

if

a > 10 then begin x := x + 5;

end


20

Specifikace programovacích jazyků - Popis syntaxe Syntaktický diagram if

podmínka

then

příkaz

else

příkaz

Gramatika příkaz → if podmínka then příkaz zbytek zbytek → else příkaz | ε ZPP - Programovací jazyky

21

Specifikace programovacích jazyků – Standardy Backus-Naur Form (BNF) <decl>

-> ‘DEF’ ‘=‘ <expr> <expr1> | ‘TYPE’ ‘=‘ <expr1> -> ‘;’ <expr> <expr1> | e Příklad: DEF a = 1;

Extended Backus-Naur Form (EBNF) Doplněny operátory pro regulární výrazy <decl> -> ‘DEF’ ‘=‘ <expr> ( <expr> )* | ‘TYPE’ ‘=‘ ZPP - Programovací jazyky

22

Specifikace programovacích jazyků Sémantika – význam jazykových konstrukcí Statická sémantika – v době překladu Dynamická sémantika – v době běhu

Příklad: Co znamená X + 1 ? X je celé číslo: Přičti k hodnotě proměnné X jedničku. X je řetězec: Převeď konstantu 1 na řetězec a připoj na konec řetězce uloženého v proměnné X. X je objekt: Zavolej metodu "operator +“ s parametrem 1. X je reálné číslo: Převeď 1 na reálné číslo 1.0 a přičti k hodnotě proměnné X. ZPP - Programovací jazyky

23

Specifikace programovacích jazyků - Metody popisu sémantiky Slovní popis Nepřesný

Formální popis Axiomatická sémantika Vyjádření významu programu pomocí tvrzení (predikátová logika, specifikační jazyky, …) {P} while R do S {Q ∧ ¬R} Operační sémantika Vyjádření významu programu posloupností přechodů mezi stavy Denotační sémantika Vyjádření významu programu pomocí funkcí E : Expr → (String → Int) → Int ZPP - Programovací jazyky

24

Překladač Analýza zdrojového textu, vyhledání chyb Základní stavební prvky – identifikátory, čísla, řetězce, operátory, oddělovače, … Programové konstrukce – deklarace, příkazy, výrazy Kontextové vazby – definice/užití, datové typy

Syntéza cílového programu / Interpretace Strojový jazyk (nebo JSI) Jazyk virtuálního procesoru (JVM, CLR) ZPP - Programovací jazyky

25

Typy překladače Kompilační překladač

Interpretační překladač


26

Typy překladače Rozdíly mezi kompilátorem a interpretem

Interpret je mnohem pomalejší než kompilátor Je potřeba analyzovat zdrojový příkaz pokaždé, když na něj program narazí. Interpret je 10 x až 100 x pomalejší.

Interpret má ale i výhody. Nezávislost na platformě. Snadnější ladění – v době chyby máme k dispozici všechny informace. Možnost měnit program za běhu - Smaltalk. ZPP - Programovací jazyky

27

Typy překladače Inkrementální překlad Umožňuje po drobné opravě přeložit jen změněnou část Možnost provádění drobných změn během ladění programu

Just-in-time překlad Generování instrukcí virtuálního procesoru (Java VM - .class, .NET CLR – jazyk IL) Překlad až v okamžiku volání podprogramu Optimalizace podle konkrétního procesoru ZPP - Programovací jazyky

28

Překlad C++


29

Klasifikace jazyků (1) Imperativní - programy jsou posloupnosti základních příkazů (nejčastěji přiřazení) s odpovídajícími řídicími strukturami (např. cykly), jež určují, které příkazy se budou provádět a v jakém pořadí. C, Pascal, Fortran, JSI Objektově orientované - programy jsou kolekcí komunikujících objektů. Často se s těmito jazyky spojuje dědičnost a polymorfismus. Simula, Smalltalk-80, C++, Java, C# ZPP - Programovací jazyky

30

Klasifikace jazyků (2) Deklarativní jazyky – popisujeme, co se má vypočítat, ne jak.

Logické - programy jsou kolekcemi tvrzení v konkrétní logice (nejčastěji predikátové) Prolog, Goedel Funkcionální - programy se popisují jako soustavy rovností s aplikacemi funkcí na hodnoty. FP, LISP, Scheme, ML, Haskell ZPP - Programovací jazyky

31

Klasifikace jazyků (3) Paralelní – programy jsou kolekcemi komunikujících nebo jinak kooperujících procesů. Některé verze jazyka Modula-2, Ada V současné době paralelizace řešena spíše „knihovními“ funkcemi – MPI, PVM

Skriptovací – jsou určeny jako podpora pro větší programovací jazyk. Lze kombinovat s libovolným z předcházejících modelů. ZPP - Programovací jazyky

32

Rozdíly mezí imperativními a deklarativními jazyky Imperativní jazyky Program má implicitní stav, který se modifikuje konstrukcemi programovacího jazyka. Explicitní pojem „pořadí“ příkazů Vyjadřuje, jak se má program vyhodnocovat

Vychází z aktuální (Von Neummanovy) architektury počítačů Jednoduchá a efektivní realizace

Deklarativní jazyky Program nemá implicitní stav. Program je tvořen výrazy, ne příkazy. Popisujeme co se má spočítat, ne jak. Není dáno pořadí příkazu.

Efektivní implementace vyžaduje komplexní optimalizace. Funkcionální jazyky x Relační (logické) jazyky ZPP - Programovací jazyky

33

Funkcionální programování – Funkcionální programovací jazyky (1) Vycházejí z λ-kalkulu – základním modelem výpočtu je matematický pojem funkce aplikované na argument a vypočítávající deterministicky její výsledek. Program je složen s funkcí bez vedlejších efektů. Funkce jsou brány jako běžné hodnoty („first-class values“). Funkcionální jazyky mají lepší mechanismus abstrakce Možnost abstrahovat chování pomocí funkcí vyššího řádu. Program je budován z funkcí jejich kompozicí. Většinou mnohem stručnější programy

Funkcionální programovací jazyky neobsahují přiřazení, příkazy, cykly atd. Opakování je řešeno pomocí rekurze. Přiřazení má „matematický“ význam. Proměnná má v daném kontextu vždy tutéž hodnotu – referenční transparence.


34

Funkcionální programování – Funkcionální programovací jazyky (2) Umožňují nové algebraické přístupy Lazy evaluation ( x eager evaluation) Možnost používat potencionálně nekonečné struktury.

Možnost oddělení dat od řízení – nemusíme se starat o to, jak proběhne vyhodnocení.

Umožňuje nové přístupy k vývoji programů Možnost dokazovat programy Možnost transformovat program na základě algebraických vlastností

Umožňuje lepší využití paralelního provádění programů Jednoduchá dekompozice programů na části, které lze vyhodnocovat paralelně. Potencionálně příliš mnoho paralelismů.

Možnost kompozice dvou paralelních úloh jednoduchou kompozicí funkcí. ZPP - Programovací jazyky

35

Funkcionální programování –

Příklady Vytvoření seznamu druhých mocnin dm [] = [] dm (x:xs) = sq x : dm xs where sq x = x * x

Seřazení seznamu (quicksort) qs [] = [] qs (x:xs) = let ls = filter (< x) xs rs = filter (>=x) xs in qs ls ++ [x] ++ qs rs ZPP - Programovací jazyky

36

OOP – Smalltalk (1) Existují i jiné objektově orientované jazyky než Java… "When I invented the term 'object-oriented' I did not have C++ in mind." -- Alan Kay Jedním z „jiných“ objektově orientovaných jazyků je jazyk Smalltalk Ve skutečnosti neexistuje jazyk Smalltalk. Existuje celá řada „variant“ jazyků obsahujících Smalltalk v jejich názvu. Obvykle je pod pojemem Smalltalk rozuměn jazyk Smalltalk-80. ZPP - Programovací jazyky

37

OOP – Smalltalk (2) Smalltalk je čistě objektově orientovaný jazyk. Koncepce tříd a objektů Základní myšlenkou je, že vše je objekt a objekty spolu komunikují prostřednictvím zpráv Objekty mohou v jazyce Smalltalk provádět právě tři činnosti Udržovat stav (reference na další objekty) Přijímat zprávy od sebe a nebo od jiných objektů V rámci reakce na zprávu posílat zprávy jiným objektům. Vše v jazyce Smalltalk je objekt. Každý objekt je instancí nějaké třídy. Třídy jsou také objekty. Každá třída je instancí nějaké metatřídy. Metatřídy jsou všechny instancí třídy Metaclass. Blok zdrojového kódu je taky objekt Například tělo metody – zprávy ZPP - Programovací jazyky

38

OOP – Smalltalk (3) Jazyk Smaltalk integruje kompletní mechanismus reflexe. Obvykle realizuje „image-based persistence“ Prostředí pro jazyky jako Java oddělují zdrojový kód od stavu programu. Zdrojový kód je nahrán při startu aplikace. Po ukončení jsou ztraceny všechny data kromě těch, které byly explicitně uloženy. V jazyce Smalltalk je vše objektem, tedy například i třídy, a vše je uloženo jako jeden „image“. Ten může být snadno „obnoven“. Vývojové prostředí je obvykle součástí prostředí. Není využíván žádný „externi“ nástroj. ZPP - Programovací jazyky

39

OOP – Smalltalk – Řídicí struktury (2) Cykly typu „while“ | a | a := 100 atRandom. [ a = 42 ] whileFalse: [ a := 100 atRandom ].

Cyklus typu „for“ 100 timesRepeat: [ Transcript show: 'Hello world.'; cr ].

Na závěr Hello world program (omlouvám se, že nebyl někde na začátku☺): Transcript show: 'Hello, world!'. ZPP - Programovací jazyky

40

Studijní program „Informační a komunikační technologie“ Úvod do programování (Java) Programování v C/C++ Programování v C# Programovací techniky Programovací jazyky a překladače Seminář z programování Funkcionální a logické programování ZPP - Programovací jazyky

41

No title

Recommend Documents