Haskell a funkcionální programování (1)

Peter Almásy 26. 9. 2001

Funkcionální programování je zajímavou alternativou k programování v klasických jazycích, jako jsou C nebo Pascal. Haskell, jazyk založený na matematické teorii lambda kalkulu, je jedním z představitelů tohoto odlišného přístupu.

Jak už název prozrazuje, tento článek se bude zabývat funkcionálním programovacím jazykem nazvaným Haskell. (Matematik Haskell Brooks Curry vypracoval teoretické základy pro funkcionální programovací jazyky. Jeho vliv je patrný i na tom, že jistému typu funkcí se říká curried). Dovolím si čtenáře předem upozornit, že mým cílem není psát učebnici funkcionálního programování v Haskellu (takových učebnic je na síti dostupných několik a já na nošení dříví do lesa moc nejsem …), pouze bych chtěl poukázat na to, že existuje (podle mého názoru zajímavá) alternativa ke klasickým programovacím jazykům. Pokud budu citovat ze stránek věnovaných tomuto jazyku, dal by se Haskell popsat jako polymorfně typový, líný, čistě funkcionální počítačový programovací jazyk podstatně odlišný od většiny jiných programovacích jazyků … Než se však dostanu k samotnému Haskellu, dovolil bych si menší teoretický výklad k tomu, co to vůbec jsou funkcionální jazyky.

Kód v klasickém programovací jazyce (jako C, Pascal, Perl, Java atd.) je tvořen posloupností příkazů (přiřazení, volání funkce/metody, zaslání zprávy objektu …), které jsou vykonávány v přesně daném pořadí. Program má tedy implicitní stav, který se modifikuje standardními konstrukcemi daného jazyka. V tomto kontextu se klasické jazyky (a ty tvoří drtivou většinu) nazývají imperativní. Jejich přístup je založen na architektuře klasického počítače (tzv. von Neumannova typu).

Menší skupina jazyků, nazvaná deklarativní, používá jiný přístup. Program nemá implicitní stav a stavové informace se udržují explicitně. Opakované provádění se nevyjadřuje iteracemi (tj. cykly), ale rekurzí. Deklarativní jazyky lze dále rozdělit na funkcionální (sem patří Haskell, FP, Miranda, Lisp, Scheme atd.) a relační (Prolog, Goedel). Jazyky patřící do skupiny funkcionální přistupují k programu jako k (matematickému) výrazu. Provádění programu spočívá v deterministickém vyhodnocování výrazů. Program tedy popisuje, co chceme vypočíst, a to, jak se výpočet bude provádět, není podstatné. Podobný přístup můžeme vidět např. u SQL dotazů nebo ještě lépe u tabulkových kalkulátorů (spreadsheet) – buňka obsahuje výraz, který popisuje její vztah k ostatním buňkám. Uživatele nezajímá, v jakém pořadí kalkulátor vyhodnotí obsahy jednotlivých buněk, ale potřebuje, aby byly dodrženy jednotlivé závislosti. Alokace paměti je také ponechána na kalkulátoru – tabulka je tvořena (teoreticky) nekonečnou rovinou buněk, ale místo se alokuje, až když je daná buňka potřebná. Shrnutím tedy je, že pro funkcionální jazyky je podstatné, co se má dělat, a nikoli, jakým způsobem se to provede.

Proč se vlastně zabývat něčím, jako je funkcionální programování? Skoro klasickou odpovědí je ukázka implementace algoritmu QuickSort (jak jinak než v jazyce Haskell), takže proč ji tady nepoužít :-)

qsort []     = []
qsort (x:xs) = qsort mensi ++ [x] ++ qsort vetsi_rovno
        where
            mensi  = [ y | y <- xs, y < x]
            vetsi_rovno  = [ y | y <- xs, y >= x]

Pokusím se uvedený příklad trochu osvětlit. Zjednodušeně řečeno, program v Haskellu sestává z definic funkcí. Definice funkce má dvě části – jméno funkce a případné parametry a tělo funkce (za rovnítkem). Jednu funkci může popisovat i více rovnic. U naší funkce qsort první řádek říká, že setříděním prázdného seznamu (o seznamech bude řeč za chvíli) získáme prázdný seznam. Druhá rovnice je trochu komplikovanější. Můžeme ji popsat asi takto: výsledkem třídění seznamu, jehož první prvek je x a zbytek xs, je seznam, který vznikne spojením (operace ++) setříděného seznamu mensi, prvku x a setříděného seznamu vetsi_rovno. Seznam mensi získáme ze seznamu xs výběrem takových prvků y, které jsou menší než x. Seznam vetsi_rovno získáme obdobně výběrem prvků větších nebo rovných x. Jak vidíme, je při definici funkce qsort použita rekurze, která je pro funkcionální programování typická.

V porovnání například s kódem v jazyce C je ihned jasná první přednost – funkcionální programy bývají obvykle kratší (2 až 10 krát) než jejich imperativní ekvivalenty. Další, velmi užitečnou vlastností, kterou u imperativních jazyků nenalezneme, je tzv. líné vyhodnocování (lazy evaluation). Princip spočívá v tom, že při výpočtu se výrazy vyhodnocují, až když je jich zapotřebí. Může tedy dojít k situaci, kdy některé výrazy nemusí být vyhodnoceny nikdy.

Nelze mluvit o funkcionálních jazycích a nezmínit se o seznamech. Základními kameny pro práci se seznamy jsou prázdný seznam (v Haskellu []) a přidání prvku do seznamu (operátor : ). Větší seznamy se tvoří postupným přidáváním prvků. Například výraz

1:2:3:4:5:[]

je v Haskellu seznam celých čísel 1,2,3,4,5. Z prak­tického hlediska nemusí být uvedená konstrukce příliš přehledná, a proto lze použít i další způsob zápisu seznamu (který je ale ekvivalentní s předchozím)

[1,2,3,4,5]

Speciálním případem seznamu jsou řetězce. Ty lze zapisovat jednak již uvedeným způsobem

['l','a','m','b','d','a']

a nebo klasicky v uvozovkách

"lambda"

Haskell nabízí opravdu velké množství různých funkcí pracujících se seznamy, jelikož značná část výpočtů je založena právě na nich. (např. při implementaci dříve uvedeného QuickSortu byl použit tzv. generátor seznamů)

Vlastností známou i z imperativních programovacích jazyků je polymorfismus. Náš příklad s tříděním pomocí QuickSort bude fungovat na celá čísla, znaky, čísla s plovoucí řádovou čárkou i na seznamy seznamů. Obecně je možné setřídit libovolné seznamy, pro jejichž prvky jsou definovány operace porovnávání. Funkcionální jazyky obecně poskytují vysokou míru abstrakce. Jedním z mechanismů abstrakce jsou funkce vyššího řádu. Haskell umožňuje pracovat s funkcemi jako s běžnými hodnotami – funkce může být parametrem jiné funkce, může být vrácena jako výsledek nebo uložena v datové struktuře (seznamy, …)

Z hlediska programátora je velmi užitečný také systém modulů – možnost rozčlenit zdrojový kód na logické celky uložené v samostatných souborech. V neposlední řadě je podstatná i automatická správa paměti (garbage collector).

widgety

Funkcionální programování ale samozřejmě není všelék. Vysoká míra abstrakce je sice z hlediska vývoje aplikace výhodnější, ale také něco stojí. U aplikací, kde hraje rychlost provádění výsledného kódu hlavní roli, bude asi vždy lepší použít jazyk jako C. Na druhou stranu, takových aplikací není až takové množství (o tom může svědčit například i rozmach Javy, která je koneckonců interpretovaná …) a překladače Haskellu jsou již schopný generovat optimalizovaný a rychlý kód. O tom, že funkcionální programování nepatří pouze do oblasti teoretické, svědčí i to, že jej používají i velké firmy jako například Ericsson.

To by bylo pro dnešek o funkcionálním programování všechno. Pokud někoho tolik teorie nudilo, můžu slíbit, že příště se už podíváme na praktičtější věci – zmíním se o několika překladačích jazyka Haskell (nejen) pro Linux a podrobněji se zaměřím na interpret nazvaný Hugs.

Našli jste v článku chybu?
DigiZone.cz: Další programatické formáty

Další programatické formáty

Vitalia.cz: Tradiční čínská medicína a rakovina

Tradiční čínská medicína a rakovina

Vitalia.cz: Antibakteriální mýdla nepomáhají, spíš škodí

Antibakteriální mýdla nepomáhají, spíš škodí

DigiZone.cz: Digi Slovakia zařazuje stanice SPI

Digi Slovakia zařazuje stanice SPI

Vitalia.cz: 5 důvodů, proč jet na výlov rybníka

5 důvodů, proč jet na výlov rybníka

DigiZone.cz: Wimbledon na Nova Sport až do 2019

Wimbledon na Nova Sport až do 2019

Vitalia.cz: Tesco nabízí desítky tun jídla zdarma

Tesco nabízí desítky tun jídla zdarma

DigiZone.cz: Technisat připravuje trojici DAB

Technisat připravuje trojici DAB

Lupa.cz: Cimrman má hry na YouTube i vlastní doodle

Cimrman má hry na YouTube i vlastní doodle

Vitalia.cz: dTest odhalil ten nejlepší kečup

dTest odhalil ten nejlepší kečup

Vitalia.cz: Nová vakcína proti chřipce se aplikuje nosem

Nová vakcína proti chřipce se aplikuje nosem

Vitalia.cz: Jak Ondra o astma přišel

Jak Ondra o astma přišel

Vitalia.cz: Vodárny varují: Ve vodě z kohoutku jsou bakterie

Vodárny varují: Ve vodě z kohoutku jsou bakterie

Lupa.cz: Jak se prodává firma za miliardu?

Jak se prodává firma za miliardu?

120na80.cz: Co je padesátkrát sladší než cukr?

Co je padesátkrát sladší než cukr?

DigiZone.cz: Parlamentní listy: kde končí PR...

Parlamentní listy: kde končí PR...

DigiZone.cz: Nova opět stahuje „milionáře“

Nova opět stahuje „milionáře“

Lupa.cz: Proč jsou firemní počítače pomalé?

Proč jsou firemní počítače pomalé?

Podnikatel.cz: Nemá dluhy? Zjistíte to na poště

Nemá dluhy? Zjistíte to na poště

Lupa.cz: Jak levné procesory změnily svět?

Jak levné procesory změnily svět?