Hlavní navigace

Mercury: Typové třídy

Ondřej Bojar 8. 4. 2004

Závěrečný díl krátkého představení jazyka Mercury přináší úvodní vysvětlení k typovým třídám. Typové třídy poslouží při definici a implementaci datové struktury nad čímkoli, co však splňuje určité předpoklady.

K čemu slouží typové třídy

Dosud jsme se seznámili s abstraktními datovými typy („datové struktury nad čímkoli“; množina něčeho, strom něčeho, halda něčeho, regulární výraz nad něčím, zobrazení něčeho na něco). Pro vybudování a zpracovávání datové struktury nebylo vůbec třeba vědět, jak elementární prvek ve struktuře vypadá. Pro některé datové struktury je však nezbytné, aby elementární prvek sám splňoval některé vlastnosti, přesněji řečeno: pro práci s datovou strukturou potřebujeme na elementárních prvcích vykonávat určité operace.

Uveďme jednoduchý příklad přímo z dokumentace Mercury. Chceme definovat datovou strukturu hashovací tabulky pro cokoli. Na to, abychom však byli schopni vkládaný prvek (třeba autobus) do tabulky vložit, potřebujeme získat hashovací klíč pro tento konkrétní autobus (musíme vědět, na které pozici v tabulce by měl tento konkrétní autobus sedět). Můžeme sice náš modul s hashovací tabulkou připravit tak, že bude umět hashovat řetězce, čísla a jiné základní datové typy, ale těžko připravíme naši hashovací tabulku tak, aby uměla hashovat obecně cokoli, třeba zmíněný autobus. Řešení je prosté: s naším zákazníkem (uživatelem modulu hashovací tabulky) se dohodneme, že poskytujeme hashovací tabulku na cokoli, ale že zákazník sám dodá návod, jak se pro tohle cokoli zjistí hodnota hashovacího klíče, tj. preferovaná pozice v tabulce.

:- typeclass hashable(T) where [func hash(T) = int]. 

Seznam vyžadovaných operací jsme shrnuli pod názvem hashable, hashovatelné. Hashovatelné je cokoli typu T, nad čím je definována (uživatel dodá) funkce hash. Tato funkce, ať už pracuje na autobusech jakkoli, autobus vezme a vrátí jeho preferovanou pozici v tabulce, tj. integer.

Nyní můžeme přistoupit k definici typu hashovací tabulky a operací nad hashovací tabulkou.

:- type hash_table(T).
% abstraktní datový typ, jak tabulku uděláme,
% je uživateli jedno

:- func init(hash_table(T))
% Vyrob prázdnou tabulku. Na to typicky není třeba
% umět něco hashovat.

:- pred insert(hash_table(T), T, hash_table(T)) <= hashable(T).
:- mode insert(in, in, out) is semidet.
% Vlož do tabulky prvek (a selži, pokud už tam byl).
% Tento predikát už potřebuje umět pro daný prvek
% zjistit preferovanou pozici v tabulce. Proto je
% u definice typu parametrů uveden požadavek:
% Umím sice vkládat cokoli, ale potřebuji, aby to
% cokoli bylo hashovatelné. 

Díky explicitnímu požadavku na hashovatelnost je nyní možné v implementaci insert/3 používat funkci hash/1, ať už tou funkcí bude později cokoli. Pokud vám to nápadně připomíná virtuální metody z objektově orientovaného programování, nemýlíte se. Jde o stejnou myšlenku, jen zavedenou při pohledu „od funkcí a typů objektů“ a nikoli při pohledu „od objektů tj. hodnot“.

Jak učinit něco hashovatelným

Nyní se musíme podívat na úkoly uživatele našeho modulu hashovací tabulky. Aby směl používat hashovací tabulku autobusů, musí oznámit, jak vypadá funkce, která z autobusu určí jeho hashovací klíč. Toto oznámení se provádí definicí instance typové třídy:

:- type autobus.
% autobus může být reprezentován jakkoli, do toho
% nic tvůrcům hashovací tabulky není

:- instance hashable(autobus) where [func(hash/1) is hashuj_autobus].

:- func hashuj_autobus(autobus) = int. 

V implementační části pak můžeme hashovací klíč autobusu vypočíst třeba jako součin vzdálenosti, kterou má urazit, a typické obsazenosti spoje.

Pro naše pohodlí mohl už sám autor modulu hashovací tabulky připravit (abstraktní, protože implementace je utajena) instance typové třídy hashable potřebné pro hashování základních datových typů:

:- instance hashable(int).
:- instance hashable(string). 

Jakou funkcí hashování realizoval, už nám může být jedno, ze zvědavosti však můžeme do implementace instancí nahlédnout:

:- implementation.

:- instance hashable(int) where [func(hash/1) is hash_int].
:- instance hashable(string) where [func(hash/1) is hash_string].

:- func hash_int(int) = int.
hash_int(X) = X.
% hashovací klíč čísla je číslo samo, žádná velká práce

:- func hash_string(string) = int.
hash_string(S) = H :-
  string__hash(S, H).
% hashovací klíč řetězce je už obtížnější stanovit
% tak, aby málo řetězců mělo klíč stejný, určitým
% standardním způsobem hashovací klíč vypočte knihovní
% funkce string__hash/2, tak ji prostě použijeme 

Příklad typových tříd pro matematické struktury

Pro příznivce algebry je v dokumentaci Mercury uvedena definice typové třídy okruhu, já ji uvedu spíše proto, aby byla zřejmá syntaxe definice typové třídy požadující více operací.

:- typeclass ring(T) where [
  func zero = (T::out) is det,               % prvek identity pro '+'
  func one = (T::out) is det,                % prvek identity pro '*'
  func plus(T::in, T::in) = (T::out) is det, % '+'/2
  func mult(T::in, T::in) = (T::out) is det, % '*'/2
  func negative(T::in) = (T::out) is det     % '-'/1
]. 

Okruh celých čísel pak definujeme instancí typové třídy okruhu pro typ int:

:- instance ring(int) where [
        zero = 0,
        one = 1,
        plus(A, B) = A+B,
        mult(A, B) = A*B,
        negative(A) = -A
].

Jiným příkladem je částečně uspořádaná množina (kterou lze pěkně vykreslit acyklickým orientovaným grafem, anglicky stručně nazývaným lattice). Osobně se mi vykreslování výsledků kdejakých experimentů ve formě lattice velmi zalíbilo (zvláště s použitím vynikajícího automatického kreslítka GraphViz. Připravil jsem si proto velmi obecný modul lattice. Modul definuje abstraktní datový typ pro uchovávání částečně uspořádané množiny. Základní operací je pak „přidej nový prvek do množiny“, přičemž tato operace zajistí, že prvek dostane jasné místo v acyklickém grafu reprezentujícím množinu a uspořádání. (Algoritmus v grafu ukládá pouze netranzitivní kostru uspořádání.) Modul pak používám tak, že sbírané výsledky prostě házím do částečně uspořádané množiny a nakonec vítězoslavně poprosím modul: a teď mi množinu pěkně částečně uspořádanou vykresli.

Příklad množiny množin celých čísel uspořádaných relací inkluze. Postupně jsem do lattice naházel prvky {1,3,5,7}, {1,2}, atd., bez ohledu na pořadí. Obrázek vykreslil počítač:

Obrázek částečně uspořádané množiny

Co tedy potřebujeme při definici a implementaci modulu lattice?

:- type lattice(T).

:- typeclass partially_ordered(T) where [
    pred lower_than(T::in, T::in) is semidet.
    % Predikát musí uspět, právě tehdy když první
    % prvek je v uspořádání striktně menší než druhý
    % prvek. (Predikát tedy musí selhat, pokud jsou
    % si dané prvky v uspořádání rovny.)
  ].

:- func init = lattice(T).

:- pred insert(lattice(T), T, lattice(T)) <= partially_ordered(T).
:- mode insert(in, in, out).

:- func to_graphviz_source(lattice(T)) = string.
% Naplněnou lattice exportujeme jako zdrojový kód
% pro vykreslovací program. 

A pro konkrétní použití pro náš příklad uspořádání množin relací inkluze je třeba definovat instanci typové třídy partially_ordered:

:- instance partially_ordered(set(T)) where [
    pred(lower_than/2) is set_strictly_included
  ].

:- pred set_strictly_included(set(T)::in, set(T)::in) is semidet.
set_strictly_included(A, B) :-
  set__subset(A, B), % Množina A musí být podmnožinou
  A \= B.            % množiny B a množiny se nesmí rovnat. 

Shrnutí

Cílem této krátké série článků bylo představit vám programovací jazyk s velmi silným typovým systémem, deklarativní sémantikou a abstrakcí nad algoritmy (programování vyššího řádu). Cílem nebylo přesvědčit vás, že máte od zítřka programovat právě v Mercury. Je však vhodné občas pohlédnout i do budoucnosti vývoje masově užívaných programovacích jazyků a koncepty, na nichž Mercury stojí, rozhodně do této budoucnosti patří.

Z praktického hlediska mohu Mercury jako nástroj doporučit vždy, když potřebujete budovat komplikované datové struktury (ideálně s použitím rekurze) a chcete užívat pohodlí a jistotu typové kontroly. Všechny části vašeho programu budou ještě v době kompilace prověřeny a chybné (ve smyslu „odporující definici“) užití datové struktury je vyloučeno. Díky tomuto rysu je i velmi bezpečné definici datové struktury při vývoji programu měnit, případnou typovou nekonzistenci kompilátor najde a konkrétně upozorní, která místa programu nové definici neodpovídají.

Abstrakci nad algoritmy přijde člověk na chuť buď pokud implementuje formálně popsané algoritmy (kde je právě takový způsob popisu zvykem), nebo delší praxí v programovacím jazyce, který to podněcuje. Výsledný kód je často o stupeň stručnější a konzistentnější, protože člověk nemusí mírné obměny algoritmů provádět explicitním kopírováním kódu, ale může alternativní část algoritmu vkládat jako parametr.

Našli jste v článku chybu?

14. 4. 2004 15:19

Ondřej Bojar (neregistrovaný)

http://www.cs.mu.oz.au/research/mercury/

8. 4. 2004 21:48

Charon (neregistrovaný)

Když jsem si veškeré texty a příspěvky pročítal, nějak jsem nenarazil na místo, kde by se dal Mercury compilátor stáhnou a tudíž prezentované věci vyzkoušet. Můžete mne prosím nasměrovat ?
Díky
Charon



Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?