Hlavní navigace

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).

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?

5. 2. 2006 9:26

Jerry (neregistrovaný)
Ale asm si musí optimalizovat programátor. V C optimalizuje překladač. A kdo je v tom asi lepší :-)???

19. 12. 2005 18:56

Neřeší to oprava zveřejněná autorem v druhém prastarém dílu seriálu? :-D
Root.cz: Telegram spustil anonymní blog Telegraph

Telegram spustil anonymní blog Telegraph

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

Přehledná titulka, průvodci, responzivita

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

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

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

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

120na80.cz: Vitaminová abeceda

Vitaminová abeceda

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

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

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

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č?

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

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

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

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

ČRo rozšiřuje DAB do Berouna

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

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

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

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

DigiZone.cz: Sat novinky: Fransat UHD Demo

Sat novinky: Fransat UHD Demo

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

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

Vitalia.cz: I církev dnes vyrábí potraviny

I církev dnes vyrábí potraviny

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte