Hlavní navigace

Mercury: Typová čistota

Ondřej Bojar

Druhý díl stručného úvodu do jazyka Mercury představí systém modulů a typový polymorfismus. Typový polymorfismus prakticky vzato dělá totéž, o co se pokoušejí šablony v C++ nebo obecné typy (generic types), žhavý to výkřik Javy. Na rozdíl od objektově orientovaných programovacích jazyků není typový systém Mercury komplikován objekty a podstata abstraktních typů zřetelněji vynikne. Chcete-li zvládnout javovské generické typy, možná vám pomůže i tento článek z jiného světa.

Moduly jako záruka zapouzdření (enkapsulace)

Stavebním kamenem objektově orientovaných jazyků jsou objekty, a jedním z jejich základních rysů je zapouzdření: jen autor třídy objektů rozhoduje, do čeho smějí uživatelé třídy strkat prsty a co je jim už zatajeno. V Mercury se ke stejnému účelu užívají moduly.

Podívejme se na zjednodušený příklad jednoho ze základních knihovních modulů. Modul map slouží k uchovávání zobrazení (tabulky klíčů a hodnot, hashovací tabulky, chcete-li):

:- module map.
:- interface.
% Následuje seznam typů a predikátů, které modul
% exportuje, dává k dispozici ostatním.

:- type map(Key, Value).

:- func map__init = map(K, V).
:- mode map__init = uo is det.

:- pred map__search(map(K,V), K, V).
:- mode map__search(in, in, out) is semidet.

:- pred map__insert(map(K,V), K, V, map(K,V)).
:- mode map__insert(in, in, in, out) is semidet.

:- implementation.

% Implementaci přenechme jinému, na té stejně nám
% uživatelům nezáleží.

V části interface jsme deklarovali, jaké predikáty a funkce má uživatel modulu k dispozici. Zároveň jsme zavedli abstraktní typ map/2, abstraktní proto, že uživatelé modulu nemají žádnou možnost zjistit, jak je hodnota typu map/2 reprezentována. Za pozornost však stojí skutečnost, že na druhou stranu autor modulu map nemá tušení, jakého typu budou klíče a hodnoty, které si bude uživatel v tabulce uchovávat. Autor modulu map pouze říká: zavádím typ parametrizovaný dvěma typovými proměnnými: první (Key) zastupuje typ klíčů do tabulky, druhá (Value) zastupuje typ hodnot v tabulce.

Typový polymorfismus v praxi

Jak přesně kompilátor rozumí typovým proměnným, pochopíte snadno při pohledu na deklaraci predikátu search/3. (Dvojice podtržítek je oddělovač názvu modulu od názvu predikátu, map__search je tedy predikát search/3 v modulu map. Nově je doporučeno užívat jako oddělovač tečku, ale názvy s podtržítky jsou poměrně čitelnější, např. string__to_int ap.)

:- pred map__search(map(K,V), K, V).
:- mode map__search(in, in, out) is semidet.

Predikát search v prvním parametru přijímá hodnotu typu zobrazení z něčeho do něčeho. Ve druhém parametru přijímá jednu hodnotu stejného typu K, jako jsou klíče v zobrazení. Ve třetím parametru pak vrací nějakou hodnotu stejného typu V, jako jsou hodnoty v daném zobrazení. (Predikát může nenajít žádnou hodnotu, která by odpovídala danému klíči, může tedy selhat, proto semidet.)

Podobně je snadné porozumět predikátu insert/4: vezme zobrazení z klíčů typu K do hodnot typu V, vezme daný nový klíč a novou hodnotu (samozřejmě odpovídajících typů K a V), a pokud pro daný klíč není v zobrazení žádná hodnota, přidá zadanou dvojici (jinak selže). Výstupem predikátu je zase zobrazení z klíčů typu K do hodnot typu V, které navíc umí zobrazit nově přidaný klíč.

Jednoduchý příklad ukáže, jak modul map použít, zároveň si procvičíme deklarativní uvažování:

:- import_module map.
:- import_module string, int.

:- pred vloz_a_vyhledej is semidet.

vloz_a_vyhledej :-
  PrazdnaTabulka = map__init,
  map__insert(PrazdnaTabulka, "ahoj", 1, TabulkaSAhoj),
  map__insert(TabulkaSAhoj, "nazdar", 2, TabulkaSAhojANazdar),
  map__search(TabulkaSAhojANazdar, "nazdar", TohleByMelaBytDvojka),
  TohleByMelaBytDvojka = 2. 

Predikát vloz_a_vyhledej otestuje funkčnost modulu, uspěje, pokud modul map správně vloží dva klíče a po vyhledání jednoho z nich vrátí stejnou hodnotu, jako jsme vložili. K selhání může dojít buď při vkládání některého z klíčů, při vyhledávání, nebo při závěrečné unifikaci; pokud by k selhání došlo, už se při této implementaci zvenku nedozvíme, kde přesně to bylo.

Unifikaci se nebudu více věnovat a odkáži vás raději na nějakou úvodní učebnici Prologu, stručně lze říci, že rovnítko značí unifikaci a používá se jak pro přiřazení, tak pro test shody (dvojité rovnítko se užívá pro definici typů, viz níže). Pokud je kterákoli z proměnných už naplněna a druhá není, proměnné se ztotožní („Pointry ukáží na stejné místo“, chcete-li mluvit ošklivě.). Jsou-li naplněny obě proměnné, provede se test rovnosti obsahů. Unifikace je semideterminis­tická, může selhat, pokud se dvě naplněné proměnné neshodují.

Podívejme se ale na typy proměnných. Přestože jsme nikde neřekli, že proměnná TohleByMelaByt­Dvojka je typu int, kompilátor to snadno odvodil, stejně jako odvodil, že PrazdnaTabulka má typ map(string, int). Odvození se opřelo o uvedené konstanty: je evidentní, že „ahoj“ má typ string, a je evidentní, že 1 má typ int. Podle deklarace predikátu map__insert tedy musí být proměnné PrazdnaTabulka iTabulkaSAhoj typu map(string, int). Při druhém vkládání už kompilátor typ proměnné TabulkaSAhojANazdar nejen odvozuje, ale také prověřuje typovou korektnost: Do proměnné TabulkaSAhoj, která je typu map(string, int), například nesmíme chtít vložit klíč 5 a hodnotu „osel“, protože klíč 5 má typ int místo string a hodnota „osel“ má typ string místo int.

Postupné zaplňování proměnných probíhá obdobně jako v Prologu, na rozdíl od Prologu však kompilátor dopředu ověřil, že nebudete míchat jablka s hruškami. Unifikace se vždy bude provádět jen na proměnných stejného typu.

Zapomeňte na přetypování

V Mercury není možné žádnou proměnnou či hodnotu přetypovat. Jak jste jistě správně odpověděli na domácí úkol z minulého dílu, v Mercury není vlastně vůbec možné obsah proměnné změnit, jakmile je do něj jednou něco přiřazeno. Je však samozřejmě možné použít vhodnou funkci, která vezme např. hodnotu typu int a vrátí hodnotu typu string:

:- func int_to_string(int) = string.
:- mode int_to_string(in) = uo is det.

„Přetypování“ pak provedete snadno:

main(!IO) :-
  Cislo = 42,
  CisloJakoRetezec = int_to_string(Cislo),
  io__write_string(CisloJakoRetezec).

Rozdíl proti přetypování v C ap. je zásadní: V C musíte napřed proměnnou alokovat (třeba na zásobníku) a při alokaci určit, jaký „základní“ typ má proměnná mít (a kolik místa v paměti je tedy na hodnotu této proměnné potřeba), a pak se můžete na hodnotu uloženou v proměnné dívat jinými brýlemi. V Mercury typ proměnné v naprosté většině případů neurčujete explicitně, kompilátor ho za vás odvodí podle toho, do jakých predikátů proměnnou předáváte. Typ proměnné je pak určen jednou provždy a kompilátor najde všechny vaše prohřešky. (Tomuto způsobu typování proměnných se říká statické, protože ještě v době kompilace umožňuje zcela přesně zkontrolovat, že všechny proměnné mají právě jeden jasně daný typ.)

Jedna výhoda statického typování je zřejmá: v Mercury nemusíte např. pochybovat o tom, jak bude vypočten výsledek dělení dvou čísel (v prakticky všech ostatních jazycích můžete být velmi často překvapeni, že se kompilátor rozhodl dělit celočíselně, když vy potřebujete dělení s plovoucí desetinnou tečkou, nebo naopak). V Mercury jsou totiž zavedeny dvě naprosto odlišné funkce ve dvou odlišných modulech:

:- module int.
:- interface.
:- type int.
:- func int / int = int.

a

:- module float.
:- interface.
:- type float.
:- func float / float = float.

Každá z těchto funkcí však pracuje nad hodnotami jiného typu. Pokud máte dvě hodnoty typu int, můžete použít funkci dělení z modulu int. Pokud máte dvě hodnoty typu float, můžete použít dělení z modulu float. (Obecně platí, že název modulu nemusíte uvádět, pokud kompilátor dokáže jednoznačně definici typu, predikátu či funkce dohledat, většinou budete prostě psát stejné lomítko pro floaty jako pro inty. Dohledávání je tedy omezeno vzájemně: je-li znám typ, snadno se dohledá modul, je-li znám modul, snadno se dohledá typ.)

Pokud použijete lomítko mezi hodnotou typu int a hodnotou typu float, kompilátor vám řekne, že nenašel funkci, která by tuto kombinaci vstupu zpracovávala. Vám pak nezbude než z intu vyrobit float pomocí funkce:

:- func float(int) = float.

nebo naopak z floatu udělat int, což lze třemi rozumnými způsoby:

:- func ceiling_to_int(float) = int.
:- func floor_to_int(float) = int.
:- func round_to_int(float) = int.

Příklad „přetypování“ by tedy byl:

:- func vydel_float_intem_a_vrat_zaokrouhlene_dolu(float::in, int::in)
        = (int::out) is det.

vydel_float_intem_a_vrat_zaokrouhlene_dolu(Float, Int)
  = floor_to_int(Float/float(Int)). 

Vlastní typy (jak přece jen míchat jablka s hruškami)

Ve sterilním prostředí, kde všechny prvky v seznamu nebo všechny hodnoty v tabulce mají stejný typ, se člověk pohybuje málokdy. Například budeme implementovat funkci, která vykreslí tabulku HTML a bude umožňovat jednoduchou konfiguraci barev: pro pojmenované části tabulky bude možné určit barvu (záhlaví modré, nadpisy řádek černé, zápatí bílé). Pro pohodlí uživatele chceme umožnit zadat barvu buď jménem (string), nebo trojicí čísel (RGB).

Náš vykreslovací predikát bude mít pravděpodobně tuto signaturu:

:- pred vykresli_tabulku(data_v_tabulce::in, nastaveni_barev::in, html::out)
        is det. 

Musíme ovšem dodat definice typů:

:- type html == string.
   % html je jen pěkný název pro string
:- type data_v_tabulce == list(list(string)).
   % data do tabulky budeme dodávat jako jako
   % seznam řádek, kde každá řádkavje seznam
   % buněk, tedy jako seznam seznamů řetězců.
:- type nastaveni_barev == map(cast_tabulky, barva).
   % nastavení barev je podle naší představy
   % zobrazení z částí tabulky do barev. (Záměrně
   % říkám zobrazení a nikoli seznam dvojic část
   % tabulky-barva. V seznamu dvojic by se mohla
   % definice barvy pro některou část tabulky objevit
   % dvakrát a co pak s tím... Je na čase začít
   % o programech přemýšlet přesně, jednoznačně.)

:- type cast_tabulky --->
          zahlavi; titulky; zapati.
   % Takhle se v Mercury definuje výčtový typ,
   % středník značí "nebo".

:- type barva --->
          jmeno(string)
        ; rgb(int, int, int).
   % Tohle je definice složitějšího výčtového typu,
   % "discriminated union". Říká přesně, co jsme si
   % přáli v zadání: barva je buď dána jménem, které
   % má typ string, nebo je dána jako rgb,
   % reprezentována trojicí čísel.

Ať už budeme vykreslování tabulky provádět jakkoli, určitě budeme potřebovat funkci, která vezme naši barvu a vrátí kousek HTML, který přesně tu barvu popisuje.

:- func barva_do_html(barva::in) = (html::out) is det.
barva_do_html(Barva) = HTML :-
  Barva = jmeno(Jmeno),
    HTML = Jmeno
  ;
  Barva = rgb(R, G, B),
    HTML = "#"++hex(R)++hex(G)++hex(B).

:- func hex(int) = string.
% Funkce mají implicitně mód (in) = out is det,
% takže si můžeme ušetřit psaní.
hex(Int) = Hex :-
  if Int >= 0, Int < 16
  then Hex = "0"++int_to_base_string(Int, 16)
  else
    if Int >= 16, Int < 256
    then Hex = int_to_base_string(Int, 16)
    else error("Sila barevne slozky mimo rozsah.").

Ve dvou funkcích uvedených výše jsme se seznámili se dvěma základními logickými konstrukcemi: if-then-else a switch. Konstrukce if-then-else je dobře známá: pokud testovací predikát (zde konjunkce testů, čárka znamená logické and) uspěje, použije se část then, pokud neuspěje, použije se část else. (V Mercury není možné napsat jen poloviční větvičku if-then, to by bylo v rozporu s logickou jednoznačností programu. Žádná situace nesmí zůstat neošetřená.)

Switch je zajímavější. Oddělovačem mezi větvemi je středník (znamená logické nebo), a pokud je switch použit v deterministickém predikátu (barva_do_html is det), prověřuje kompilátor, že vždy nastane právě jedna z uvedených možností. Vstupní proměnná Barva je typu barva, takže opravdu může nabývat právě dvou uvedených „tvarů“ hodnot. Buď obsahuje řetězec Jmeno, a ten pak stačí přímo vrátit, nebo obsahuje tři čísla, která převedeme do šestnáctkové soustavy a předřadíme jim křížek. (Spojování řetězcůrealizuje funkce (++)/2.)

Popsaným způsobem se nám podařilo dosáhnout přesně kýženého: konfigurace barev je zobrazení z částí tabulky do „řetězců nebo trojic čísel“. Přitom je uvedený program typově zcela čistý a nám se nemůže stát, že bychom omylem názvu barvy předřadili křížek nebo zapomněli převést čísla do hexadecimálního vyjádření.

Nebojte se upravovat staré programy!

Každý ví, že do starého nebo cizího programu není radno šťourat. Na jednom místě přidáte potřebnou novou vlastnost, na druhém to správně ošetříte, na třetím dobře utajeném zůstane nová vlastnost neošetřená a program havaruje nebo vrátí nesmysl. S Mercury se tohoto problému bát nemusíte. Přidejme například třetí možnost specifikace barvy, rovnou pomocí trojice hexadecimálních čísel (protože praví webdesignéři znají nazpaměť všechny bezpečné barvy v šestnáctkové soustavě).

:- type barva --->
          jmeno(string)
        ; rgb(int, int, int)
        ; rgb_hex(string, string, string).

Místa v programu, kde všude jste zpracovávali hodnotu typu barva, nemusíte pracně hledat, stačí se pokusit modul zkompilovat:

barva.m:011: In `barva_do_html(in) = out':
barva.m:011:   error: determinism declaration not satisfied.
barva.m:011:   Declared `det', inferred `semidet'.
barva.m:013:   The switch on Barva does not cover barva.rgb_hex/3. 

A pokud by se pravý webdesignér spletl a napsal místo rgb_hex jen rgb, dostane pěknou chybovou hlášku také:

test :-
  Barva = rgb("aa", "bb", "cc").

barva.m:031: In clause for predicate `barva.test/0':
barva.m:031:   in argument 1 of functor `rgb/3':
barva.m:031:   type error in unification of argument
barva.m:031:   and constant `"aa"'.
barva.m:031:   argument has type `int',
barva.m:031:   constant `"aa"' has type `string'.
barva.m:031: In clause for predicate `barva.test/0':
barva.m:031:   in argument 2 of functor `rgb/3':
barva.m:031:   type error in unification of argument
barva.m:031:   and constant `"bb"'.
...

Kruh se uzavírá

Teď asi už tušíte, jak může být například definován abstraktní typ map(K, V).

:- type map(K, V) == list(pair(K, V)).
% Například jako seznam dvojic klíč a hodnota.
% Protože však uživatel modulu map nemůže do
% seznamu nevhodně zasáhnout, můžeme si být jisti,
% že nebudeme nikdy pro jeden klíč uchovávat více
% hodnot. Stačí to v našich dvou exportovaných
% predikátech hlídat.

Nebo chytřeji jako binární vyhledávací strom:

:- type map(K, V) --->
          leaf
        ; branch(map(K, V), K, V, map(K, V)).
% Prázdné zobrazení budeme reprezentovat symbolem
% leaf. Neprázdné zobrazení budeme reprezentovat
% jako větvičku, kde uprostřed uchováváme nějaký
% klíč a k němu příslušnou hodnotu. Pokud hledaný
% klíč odpovídá uloženému, vrátíme hodnotu. Pokud
% je hledaný klíč menší, pokusíme se hodnotu najít
% v levém podstromu, tj. v zobrazení uloženém v prvním
% argumentu branch/4. Pokud je hledaný klíč větší,
% pokusíme se hodnotu najít v pravém podstromu.

A nebo ještě chytřeji jako hashovací tabulku. Na implementaci uživatelům nezáleží a vyměnit jim ji můžete kdykoli pod prsty.

Poznámka k syntaxi

Ve výkladu by mírně rušilo poněkud nudné sdělení týkající se syntaktických specifik jazyka Mercury ve srovnání s tradičními jazyky: Proměnné musí začínat velkým písmenem nebo podtržítkem. (Proměnné uvozené podtržítkem se užívají tam, kde nás hodnota proměnné vůbec nezajímá, ale musíme nějakou proměnnou uvést proto, abychom vyhradili místo ve výrazu, který v jiném kontextu na tomto místě zajímavou informaci přináší.) Platí to pro obyčejné i pro typové proměnné.

Shrňme si dosavadní poznatky:

U programů napsaných v Mercury je díky statickému typování jasné, kolik místa v paměti která proměnná potřebuje. Kompilátor tedy může veškeré alokace provést za vás a vy nemáte šanci něco zkazit. Díky deklarovanému determinismu a vzájemné závislosti proměnných na sobě (napřed musíš mít PrazdnouTabulku, abys z ní vložením mohl vyrobit TabulkuSAhoj, pak už PrazdnouTabulku nikde dál nepotřebuješ) ví kompilátor přesně, kdy už proměnná není třeba a kdy ji tedy smí dealokovat.

Kombinace statického typování a determinismu umožňuje ještě v době kompilace ověřit, že programátor neopomněl možnost, která připadá v úvahu, nebo neuvedl některou možnost vícekrát (predikát by pak měl více řešení, byl by multi a ne det).

Typový polymorfismus a zapouzdření do modulů jsou ideálními pomocníky při implementaci abstraktních datových typů.

Příště nás čeká další silná zbraň: programování vyššího řádu.

Našli jste v článku chybu?

4. 3. 2004 12:59

Marek Paška (neregistrovaný)

Zajímavý článek. Jen malou poznámečku ke generickým typům - nejlepší generiky, co jsem viděl jsou v Adě 95. To, co je v C++ je více méně nepřehledný humus. Ovšem Javu 1.5 ani C# 2.0 jsem zatím nijak detailně nezkoumal.

Vůbec Mercury mi Adu ve své filozofii docela připomíná. Samozřejmě s tím rozdílem, že Ada je jen obyčejný imperativní jazyk, co používá prověřené koncepty s důrazem na bezpečnost :-).



Lupa.cz: Levný tarif pro Brno nebude, je to kartel

Levný tarif pro Brno nebude, je to kartel

DigiZone.cz: R2B2 a Hybrid uzavřely partnerství

R2B2 a Hybrid uzavřely partnerství

Vitalia.cz: To nejhorší při horečce u dětí: Febrilní křeče

To nejhorší při horečce u dětí: Febrilní křeče

Měšec.cz: Exekuční poradna: ptejte se online

Exekuční poradna: ptejte se online

Root.cz: Nová třída SD karet A1 s vysokým výkonem

Nová třída SD karet A1 s vysokým výkonem

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

Vitalia.cz: Jak vybrat ořechy do cukroví a kde mají levné

Jak vybrat ořechy do cukroví a kde mají levné

Podnikatel.cz: E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

Měšec.cz: Za palivo zaplatíte mobilem (TEST)

Za palivo zaplatíte mobilem (TEST)

Lupa.cz: Obchod budoucnosti je bez front, košíků i pokladen

Obchod budoucnosti je bez front, košíků i pokladen

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Vitalia.cz: Nejlepší obranou při nachlazení je útok

Nejlepší obranou při nachlazení je útok