Jazyky a překladače - 6 (sémantika a typy 1)

11. 10. 2006 | Michal Vyskočil | Programování | 7473×

Sémantika je trochu tajuplný pojem, přesto je při překladu velice důležitá. Syntaxe, kterou jsme se zabývali do minulého dílu, definovala, jak bude program vypadat. Sémantika určuje, co to vlastně znamená. S ní úzce souvisí i problematika typů. Na startovní čáru se nám tak postavily jazyky Smalltalk, Python, Javascript, Pascal, trocha Basicu, něco v PHP nebo PL/SQL a v shellu a v neposlední řadě C++ a Java.

Obsah

• Princip překladače
• Sémantická analýza
• Typové systémy
  • Statické typování
  • Dynamické typování
• Závěr

Varování: tento článek není o Javě, přesto, že se někomu může zdát, že je v něm až příliš kódu v Javě. Klidně si za ni dosaďte třeba C++ a s malými odchylkami (rozhraní, reflexe) bude platit to stejné. Stejně tak není o Pythonu - ten jsem zvolil jako zástupce dynamických OOP jazyků. Přestože jsou pokročilejší jazyky (například Smalltalk), z Pythonu toho umím více.

Princip překladače

Překladač je program, který (velice zjednodušeně řečeno) postupně prochází kód v nějakém programovacím jazyce a z něj generuje spustitelný soubor (nebo bytecode). Samotný překlad se sestává z několika fází a třetí je:

Sémantická analýza

Ovšem jak lexikální, tak ani syntaktická analýza není vše. Následující kód je z hlediska scanneru, tak i parseru naprosto v pořádku:

" program ve Smalltalku "
n := 10.
s := 'Hello, world!'.
[n = 10] if:
	[ Transcript show: n, s; cr. ]

No, nejen z hlediska scanneru, ale i z hlediska většiny lidí, kteří ve Smalltalku neprogramují (tímto děkuji Pavlu Křivánkovi za to, že mě donutil si nainstalovat Squeak a ten příklad si taky spustit a opravit :-)). Řekněme to takhle: syntaxe je správně, ovšem program stejně nejde spustit. Při pokusu o jeho spuštění ve Squeaku nám virtuální stroj nabídne řešení problému, že selektor zprávy #if není znám.

Po opravení všech tří chyb, které jsem napáchal, získáme zdrojový kód, který je platný nejen po syntaktické, ale i sémantické stránce.

" program ve Smalltalku "
n := 10.
s := 'Hello, world!'.
(n = 10) ifTrue:
	[ Transcript show: s; cr. ]

Formálně rozlišujeme tři druhy sémantik:

• Denotační sémantika popisuje sémantiku programovacího jazyka pomocí funkcí. Ty přiřazují sémantické hodnoty syntaktickým zápisům.
• Axiomatická sémantika popisuje účinek, který má provedení při různých podmínkách. Tedy takové, které jsou platné před provedením příkazu (vstupní) nebo po jeho provedení (výstupní).
• Operační sémantika ukazuje, jak je libovolný program vykonán na stroji, jehož činnost je definována (například Turingův stroj). Sémantika potom určuje, jak tento stroj program zpracovává.

Zanecháme teoretické informatiky a formálních definic a přejdeme na příklad. Následující operace mají (v podstatě) stejnou sémantiku a to, že provedou konkatenaci řetězců a a b, přičemž výsledek uloží do proměnné c — concat.tar.gz.

/*C*/
strcat(c, a);
strcat(c, b);
//C++
std::string c = a + b;
okno + "titulek";
#shell
c=$a$b
#PHP, Perl
$c = $a . $b;
--Oracle PL/SQL
c := a || b;
#Python
c = a + b
"Smalltalk"
c := a, b.
;Common Lisp
(setq c (concatenate 'string a b))

Jak vidíme, tak jazyky se docela dost liší v syntaxi zápisu operace, která má nakonec (prakticky) stejný výsledek. V C nejsou řetězce, a tak se problém řeší dvojitým voláním funkce strcat(). V shellu stačí napsat dvě proměnné vedle sebe a jejich obsah se pouze expanduje. V PHP, Perl a PL/SQL mají pro konkatenaci speciální operátor, což je pravděpodobně nejlepší způsob. V Pythonu a C++ se používá operátor +. V obou jazycích se jedná o volání speciální metody, které provádí vlastní sčítání. Tento způsob ovšem nezachovává komutativnost operátoru +. Protože pro řetězce neplatí vztah a + b = b + a, který platí pro čísla (zanedbáme omezení vyjádření čísel v počítačích), takže z matematického hlediska je lepší používat jiný znak. Smalltalk se také vydal cestou speciálního operátoru (znalci vědí, že , není operátor, ale selektor zprávy a podobně jako v Pythonu se nakonec jedná o volání příslušné metody). A nakonec implementace v Lispu se podobá jazyku C, kdy se pro konkatenaci volá funkce (pro větší podobnost by stačilo definovat funkci char* concatenate(const char* ch1, const char* ch2)).

Mezi příklady se nám objevil jeden, který má sémantiku odlišnou. Je to proslavený přetížený operátor +, který nastavuje titulek okna v jednom nejmenovaném toolkitu, což je častý argument odpůrců přetěžování operátorů. Tato konstrukce má odlišnou sémantiku a takové použití operátorů není správné. Překladače obvykle nemají možnost rozpoznat a odmítnout uživatelsky definovaný operátor se špatnou sémantikou (výjimkou je třeba Prolog), proto je důležité, aby programátoři svoje nadšení pro operátory krotili a používali je pouze na vhodných místech. Nicméně ani to nepovažuji za argument proti přetěžování operátorů, protože pokud by dotyčný programátor zvolil pro nastavení titulku metodu add(), byl by to potom argument proti metodám? Anebo spíš ukázka špatně zvoleného jména.

Typové systémy

Pojem typ proměnné je v každém programovacím jazyce velice důležitý. Když jsem se učil programovat v Basicu, proměnné a funkce se znakem $ na konci byly řetězce (moje oblíbená funkce INPUT$) a ostatní byly čísla. V některých implementacích (třeba Atari Basicu) nebylo více konstrukcí - jako procedury, které nahrazoval příkaz GOSUB (a GOTO pro skutečné programátory). Když jsem potom přišel k Pascalu, musel jsem se naučit deklarovat typy tímto způsobem:

var
	i, j, k : integer;
	errMsg  : string[20];

Což způsobovalo mojí oblíbenou chybovou hlášku tajp mišmaš (type mismatch). V té době jsem nerozuměl, proč Pascal nedokáže přiřadit integer z typu real a proč to prostě neořízne, jako to fungovalo v Basicu. Ovšem záhy jsem poznal, že různé jazyky řeší problematiku typů různými způsoby.

Statické typování

Statické typování velice dobře známe z jazyků jako je Pascal, C, C++, Java nebo třeba Haskell. Při programování v těchto jazycích musíte explicitně deklarovat typy proměnných. Příkladem je

//staticke typovani v jazyce Java
NejakaTrida foo = new NejakaTrida();

Deklarujeme proměnnou typu NejakaTrida, kterou ihned inicializujeme konstruktorem patřičné třídy. V těchto jazycích je tedy typová informace explicitní a nezávislá na proměnné. Při deklaracích hlaviček funkcí/metod je tedy nutné uvádět typy, který musí parametry splňovat. Tohoto faktu velice silně využívá C++ při tzv. přetěžování funkcí, kdy má jedna funkce několik implementací, které se vybírají na základě datových typů parametrů. C++ přineslo celou řádku nových datových typů, které mají usnadnit právě psaní přetěžovaných funkcí.

void spam(unsigned int i);
void spam(signed int i);

Při překladu statického jazyka dojde ke kontrole sémantiky (a s tím související typové kontrole) jazyka, což znamená, že jsou typy do programu (až na některé výjimky) zadrátovány natvrdo. Na druhou stranu mnoho jazyků nabízí prostředky k obcházení typového systému, protože jsou situace, kdy je statické typování omezující. Jazyk C nabízí ukazatel void*, C++ má navíc šablony. V Javě pro tento účel používáme typ Object a od verze 1.5 také šablony.

Ovšem ani statické typování není všemocné a existuje mnoho věcí, které v době kompilace vůbec ošetřit nejde. Oblíbené přetečení zásobníku v C je jenom hezkým důkazem toho, že bez runtime kontrol nejde zabezpečit přístup do paměti. Ostatně oblíbené výjimky jazyka Java (a jiných) nejsou nic jiného, než běhové kontroly.

Dynamické typování

Dynamické typování je odlišným způsobem. Přestože bude mnoho programátorů, kteří používají staticky typované jazyky, tvrdit opak, dynamické typování neznamená slabé, nebo dokonce žádné typování. Naopak, mnoho dynamicky typovaných jazyků je silně typovaných. Odlišnosti oproti statickému jsou dvě.

1. Typy se explicitně nedeklarují, jsou uloženy v runtime jazyka.
2. S tím souvisí, že se při překladu dynamických jazyků neprovádí typová kontrola. Typy se vyhodnocují v době běhu programu a ne v době překladu.

Pokud nevěříte, tak následuje ukázka:

// Java Integer i = new Integer(15);

# Python i = 15 type(i) <type int>

; Common Lisp (type-of 15/2) RATIO

Takže zatímco ve staticky typovaných jazycích je nutné proměnné deklarovat a typovost uvádět explicitně (a třeba v Javě dokonce dvakrát), u dynamických tomu tak není. Proměnné jsou reference na interní reprezentaci objektu a její nedílnou součástí je i typ proměnné. To znamená, že z hlediska jednoznačnosti typových informací jsou na tom jak statické, tak dynamické jazyky naprosto stejně (vynecháme problematiku slabě typovaných jazyků jako třeba shellu). Hlavním rozdílem je tedy místo uložení typové informace, zda je v runtime, nebo ve zdrojovém kódu.

Jenom poukáži na častou výhradu, která se v této souvislosti objevuje. Následující kód

Object x = (Object) new Foo();

nedává u dynamických jazyků vůbec smysl. Prostě se vytvoří instance třídy Foo a pokud podporuje potřebné metody (rozumí daným zprávám), není žádný důvod přemýšlet nad něčím takovým, jako je přetypování. Ostatně, dynamické jazyky operátory přetypování nenabízejí. Tedy pokud za ně nepovažujeme konverzní funkce, třeba pro převod z čísla na řetězec.

Jedná se o velice podstatné změny programátorova myšlení, a i proto jsou dynamicky typované jazyky často odmítány. Při překladu dynamického jazyka prakticky nedochází k sémantické kontrole, ta se dělá až za běhu programu. Tedy v té době, kdy se vyhodnocují typy. Hezký příklad jednoho ze základních principů používaných v dynamických (OOP) jazycích nabízí Java (ano, opravdu Java) — viz její definice metody System.out.println:

public void println(Object x)

Tato metoda dokáže vytisknout libovolný objekt. Nevěříte?

public class PrintableHW {
	public PrintableHW() {}
	public String toString() {
	return "Hello, world!";
	}
};
....
//uplne jina class a jina metoda 
System.out.println(new PrintableHW());

A výstupem je Hello, world!. Toto je klasický případ situace, kdy nás absolutně nezajímá typ daného objektu. Zajímá nás, zda podporuje metodu toString(), kterou zavoláme.

Co se to tu vlastně stalo? Za prvé jsme trochu ošidili typový systém Javy (protože je PrintableHW potomkem třídy Object, obešla se akce bez explicitního přetypování) a díky reimplementaci metody toString() třídy Object se zavolala naše metoda a ne ta implicitní. Kód potenciálně složité metody toString se nám potom rozpadá na něco jako

public void println(Object x) {
	"vytiskni_retezec"(x.toString());
	"vytiskni_retezec"(EOL);
}

Ovšem, jak jsem už napsal. Java není dynamicky typovaný jazyk (přestože obsahuje některé jejich rysy) a podobné vlastnosti nabízí pouze při přetěžování metod třídy Object. V okamžiku, kdy si řekneme, že by se nám podobná vymoženost hodila i u jiných metod, musíme začít dědit, anebo vytvořit nějaké rozhraní, které musí implementovat všechny třídy, které chceme podobným způsobem používat.

Takže hlavním rozdílem mezi staticky a dynamicky typovanými jazyky je okamžik, kdy se zjišťuje, zda daný objekt podporuje danou metodu. Ve staticky typovaných jazycích kontrola probíhá ve fázi překladu, v dynamicky typovaných v době běhu. Dynamický styl programování bývá také nazýván jako duck typing, kde se k objektům přistupuje pomocí kachního testu:

If it walks like a duck and quacks like a duck, it must be a duck.
Pokud to chodí jako kachna a kváká jako kachna, potom to musí být kacha.

Což přesně vystihuje rozdíl. Staticky typovaný jazyk se zeptá — je daný objekt typu kachna? Pokud ano, zavolej metodu quack(). Dynamický jazyk funguje odlišně — má daný objekt metodu quack()? Pokud ano, zavolej ji. Je zřejmé, že není žádný problém podstrčit dynamickému jazyku například syntetizátor, který shodou okolností obsahuje metodu quack() :-). Podobná granularita až na úrovni jednotlivých metod je sice možná i ve staticky typovaných jazycích, ale nárůst počtu abstraktních tříd či rozhraní bude enormní.

Závěr

Příště si provedeme podrobnější porovnání statických a dynamických jazyků, protože se jedná o téma, které je velice zajímavé. Dojde i na šablony, přičemž zjistíme, že jde pouze o další import dynamičnosti do statických jazyků. V tomto díle nám zbývá jenom ukázat slíbený obrázek prvních tří fází překladu:

Na závěr bych chtěl poděkovat Pavlu Křivánkovi za článek Statická vs. dynamická typová kontrola, který mě inspiroval k sepsání tohoto (dvoj)dílu o statických a dynamických typových systémech.

       

Komentáře

[freshmouse]

Super seriál! Michal Vyskočil na hrad!

[thingie]

No, mohlo by to být trochu teoretičtější (abych z toho měl aspoň iluzi, že z toho něco mám ).

[freshmouse]

Já tomu taky nerozumím (resp. ne všemu). Ale je z toho vidět, že tomu rozumí alespoň autor (nebo nerozumí, ale umí to podat tak, aby to vypadalo, že tomu rozumí). A kromě toho je to psáno hezkým slohem + je to zajímavé téma. Víc takových článků.

[thingie]

Já tomu právě rozumím, v tomto konkrétním dílem jsem se třeba nedozvěděl víceméně nic nového :-/

[freshmouse]

To ovšem mění situaci.

[Josef Kufner]

Podobný pocit jsem měl u některých předchozích dílů, ale ten následující díl tomu vždy dal hlavu a patu. Je to moc hezký seriál, jen tak dál.

[David Watzke]

Nemělo by být místo:

/*C*/
strcat(c, a);
strcat(c, b);

tohle:

/*C*/
strcpy(c, a);
strcat(c, b);

? Sice to funguje stejně, ale k čemu by pak bylo strcpy, kdyby to ani nebylo zapotřebí?

[Michal Vyskočil]

Taky možnost, ale v konečném výsledku obojí dělá to samé, takže je to jedno . Ale díky za upozornění.

[Bubak]

Neni to tak uplne pravda v pripade, ze nemas retezec, na nejz odkazuje c, vynulovany.

[Michal Hocko]

Priklady funguju rovnako, iba ak

*c == '\0'

v opacnom pripade sa a prilepi za prvu '\0' v c, co by mohol byt celkom problem (pretecenie).

strcpy kopiruje vzdy na zadanu adresu ako prvy parameter (to len na doplnenie).

[Nikola Pajkovský]

strcpy radeji se tomu vyhybat je to nebezpecne protoze muze dojit k preteceni. bezpecnejsi je strncpy(c, a, sizeof(a) );

[Michal Kubeček]

1. V tom je ovšem mezi strcpy() a strcat() obrovský rozdíl, že? :-)

2. To, co jste napsal, dělá úplně něco jiného, než jste chtěl.

3. Kdybyste použil strlen() místo sizeof() (což jste patrně měl na mysli), bude vaše konstrukce dělat přesně totéž co strcpy(c,a)

[Michal Vyskočil]

Nechce se mi věřit, že by autoři standardní knihovny strcpy implementovali nějak takto

while (*a++ = *b++);

[Nikola Pajkovský]

ten tvuj cyklus by nikdy neskoncil a havaroval by

while( *b++ != '\0' )
{
    *a++ = *b++;

}

je to jenom pro ilustraci bude to napsane urcite lepe

[Michal Kubeček]

Ale skončil, je to zcela korektní implementace strcpy(), na rozdíl od té vaší, která kopíruje jen každý druhý znak a i když se náhodou trefí do koncové značky, stejně ji nezkopíruje.

Měl byste si nastudovat aspoň základy, všechno, co jste sem zatím napsal, bylo úplně špatně. Idiom

  while (*s++ = *t++);

je už v Kernighanovi a Ritchiem…

[Michal Kubeček]

Já bych naopak řekl, že nejspíš ano, ono to dost dobře (v céčku) ani jinak napsat nejde, jen se to dá zapsat přehledněji. Při použití čtyřkového gcc už je to ale asi jedno, protože to má podobné funkce implementované jako builtin.

[Tom.š Ze.le.in]

Hezký článek, jako obvykle.

Jen k jednomu bodu:

Ostatně, dynamické jazyky operátory přetypování nenabízejí. Tedy pokud za ně nepovažujeme konverzní funkce, třeba pro převod z čísla na řetězec.

Obecně mi není jasné, proč by přetypování nemělo mít u dynamických jazyků smysl (když se podle typu řídí např. výběr metody).

Pokud by na přetypování někdo trval, tak change-class v CL existuje, ale je fakt, že to může být chápáno jako na pomezí konverze a přetypování.

[Pavel Křivánek]

Při statickém přetypování se vytváří něco jako jiný pohled na objekt, což u dynamických jazyků většinou není potřeba. Pokud ano, pak je zde otázka, jestli od tohoto nového "pohledu" vyžadujeme stejnou identitu. Pokud ne, je na místě konverzní metoda. Pokud potřebujeme typ objektu změnit globálně, pak se použije konverzní metoda a záměna identity. Aby si objekt sám sobě za běhu měnil třeba strukturu instančních proměnných a množinu akceptovaných zpráv je u některých jazyků možné (třeba v Selfu), ale obecně se obtížně udržuje atomicita takové operace. Jinak příjde na řadu lokální proxy objekt.

[Jiří (BoodOk) Kadeřávek]

Super, diky, aplaus!

[Zdenek]

Hezké, ovšem zásadní chyba je že mícháte vše dohromady, aniž by autor dělil koncepty na dobré a špatné (s chvalitebnou výjimkou kritiky přetěžování operátorů v C++). Takhle žádnou zajímavou flamewar nevyvoláte, což je hrozná škoda.

[Robert Krátký]

Právě jsme se s Michalem bavili o tom, že kdyby článek nepojmenoval nudným "Jazyky a překladače", ale třeba "Java stojí za prd!", určitě by se počet čtenářů zvýšil...

[Michal Vyskočil]

Ovšem já přetěžování operátorů nekritizuji, naopak, mě se tato vlastnost C++ líbí. To, co kritizuji je jedno konkrétní použití, které je špatné.

Navíc, nevěřím na dobré a špatné koncepty. Statické i dynamické typování má svoje výhody a nevýhody a těžko šmahem odsuzovat jedno, nebo druhé.

Jediné, co je pravda je, že je titulek málo úderný, ale to už napsal Robert

[Kyosuke]

Ano, pravda. Že Java stoji za prd, mělo připomenout. Škoda, žádný flejmwar nebude …

[Kyosuke]

s/mělo/se mělo/

[Pavel Křivánek]

No já zírám. Rádo se stalo

[ava]

Priklad se smalltalkem a selektorem #if: mi prijde trosku nestastny, program totiz LZE prelozit i spustit, a az za behu je pri odesilani zpravy #if: vyvolana vyjimka, ze ani trida Block ani jeji nadtridy teto zprave nerozumi. Program lze opravit take tim zpusobem, ze tride Block pridam metodu #if:, potom program zacne "magicky" fungovat beze zmeny uvedeneho kodu. Pokud bude semantika #if: stejna jako #ifTrue:, bude program dokonce delat to same. Jinak pekny clanek.

[Pavel Křivánek]

Faktem je, ze on je spustitelny za urcitych okolnosti i ve Squeaku a nahradni selektor nenabizi virtualni stroj, ale prekladac, ktery tam soucasti VM neni. Tento prikald je pro Michala takove male Waterloo

[neviem]

Existuje nejaka superhyper knizka o semantikach (samozrejme okrem mannu)? By ste mohli ku nie beznym veciam pridat aj nejake tie zoznamy lit.

[Mintaka]

Co třeba "Konstrukce překladačů" "ISBN 80-01-02028-2" autoři: Melichar, Češka, Ježek, Richta vydavatelství: ČVUT. Superhyper to asi nebude, ale zábavku na pár zimních večerů to poskytne.