Nahoru
 

Funkcionální programování

V komunitě programátorů jsou určitě známy jazyky jako C#, C++ nebo Java. Tyto jazyky si jsou svým zápisem podobné. Existují však i velice odlišné jazyky a styly programování. Mezi tyto méně známé styly patří i funkcionální programování. Dost často programátoři nevědí, jak něco takového funguje, pojďme se na to tedy podívat.

Funkcionální programování je programovací paradigma založené na pouhém volání funkcí. Na rozdíl od imperativního programování, pod který spadají jazyky C, C++, C#, Java nebo JavaScript, zde nenajdeme žádné deklarace proměnných ani cykly. Jediné, co máme k dispozici, jsou funkce. Nejsilnějším nástrojem pro vytváření algoritmů se stává rekurze.

Funkce ve funkcionálním programování jsou tzv. vyššího řádu. Znamená to, že funkce můžeme používat i jako parametry nebo naopak funkce může vracet jinou funkci. Jedná se o důležitou vlastnost v právě zmíněné rekurzi. Funkce ve funkcionálním programování, na rozdíl od například imperativního, vždy vrací stejný výsledek na stejné vstupy. Není možné změnit výpočetní proces. Stromy volání funkcí jsou pro stejné vstupy vždy ekvivalentní.

Teoretickým základem a matematickým modelem funkcionálního programování je lambda kalkul, který vznikl v roce 1930. Dá se chápat jako velice jednoduchý programovací jazyk. Každý výraz v lambda kalkulu popisuje funkci. Dokonce i čísla máme zakódována ve funkcích. Výpočet pro jednotlivé algoritmy se provádí tzv. vyhodnocováním (jednoduše řečeno se jedná o dosazování jedné funkce do druhé). Pomocí lambda kalkulu dokážeme vyřešit jakýkoliv problém, který zvládne vyřešit Turingův stroj. Výpočetně jsou si tyto dva matematické modely ekvivalentní. To mimo jiné znamená, že cokoliv naprogramujeme v imperativním jazyku (C, C++, C#, Java) lze naprogramovat i ve funkcionálním jazyku.

Ukázka logiky v lambda kalkulu
Obrázek č. 1: Ukázka logiky v lambda kalkulu

Pokud byste zkusili v praxi vyhodnocovat jakýkoliv algoritmus s dosazenou hodnotou, tak byste rychle zjistili, že lambda kalkulus je sice velice jednoduchý jazyk, avšak velice „upovídaný“. Například při dosazení trojky do funkce, jež vypočítává faktoriál, byste určitě popsali celý papír A4, než byste funkci vyhodnotili.

Jako nejbližší funkčně implementovanou verzi lambda kalkulu můžeme považovat programovací jazyk Lisp. Mezi další funkcionální jazyky patří Haskell nebo F# . Vývojáři těchto jazyků však přidali i některé prvky klasických imperativních jazyků, ale základní myšlenka zůstává stejná.

Nejčastěji se funkcionální jazyky uplatní na akademické půdě, díky svému elegantnímu matematickému zápisu, ale mají své místo i v komerčním světě. Například již zmíněný Lisp používají aplikace jako Grammarly, AutoCad nebo textový editor Emacs.

Jak vypadá takové použití funkcionálního programování v praxi? Pro ukázku uvedu příklad jednoduchého algoritmu, jehož úkolem je obrátit pořadí prvků v seznamu (poli). Tedy pro seznam [1, 2, 3, 4] nám vrátí výsledek [4, 3, 2, 1].

V jazyce C# by implementace reverzního algoritmu pomocí cyklu mohla vypadat takto:

List<int> Reverse(List<int> list)
{
    List<int> newList = new List<int>();
    for (int i = list.Count() - 1; i >= 0; i--)
        newList.Add(list[i]);
    return newList;
}

Algoritmus v cyklu projíždí zadaný seznam odzadu a postupně přidává prvky do nového seznamu. Jak bychom toto naprogramovali pomocí funkcionálního programování, kde nelze použít cykly ani deklarace proměnných?

Pro jednoduchost se nejprve zbavíme cyklů v C#. Musíme vymyslet, jak bychom daný algoritmus řešili pomocí rekurze. Myšlenka je následující: Ze zadaného seznamu postupně „ukusujeme“ první prvky, kde se při každém odtrhnutí prvku zanoříme hlouběji do rekurze. Jakmile je seznam prázdný, začneme se z rekurze vynořovat a prvky, jež jsme odtrhli budeme přidávat na konec seznamu.

V C# by rekurzivní verze funkce Reverse mohla vypadat následovně:

List<int> ReverseRec(List<int> list)
{
    if (list.Count() == 0)
        return new List<int>();

    int first = list.First();
    list.RemoveAt(0); // vymaze prvni prvek ze seznamu
    List<int> newList = ReverseRec(list);  // zde probehne zanoreni
    newList.Add(first);
    return newList;
}

Průběh algoritmu pro vstup [1, 2, 3, 4] popisuje následující obrázek.

Průběh rekurzivního algoritmu pro obrácení pořadí seznamu - Strom rekurzivních volání
Obrázek č. 1: Průběh rekurzivního algoritmu pro obrácení pořadí seznamu

Po zbavení se cyklů a pomocných proměnných už se vlastně jedná o funkcionální řešení. Ve funkcionálních jazycích je navíc syntaxe uzpůsobena psaní rekurzí, takže se zápis ještě více zkrátí. Zde je ukázka stejného algoritmu ve funkcionálním jazyce Lisp:

(defun reverse (list)
    (if (null list)
        nil
        (append (reverse (cdr list)) (car list))
    )
)

Jaké jsou výhody funkcionálního programování? Za velkou výhodu můžeme považovat kratší a elegantnější zápis různých algoritmů (hlavně z matematického hlediska). Může se zdát, že zakázáním cyklů jsme se připravili o zápis skutečně složitých algoritmů, což není pravda. Jakýkoliv algoritmus napsaný pomocí cyklů lze přepsat do rekurzivního tvaru a obráceně. Za další výhodu znalosti jakéhokoliv funkcionálního jazyka považuji i to, že se programátor „otrká“ v používání rekurze. Spousta vývojářů se ji aktivně vyhýbá, protože se zpočátku zdá těžko uchopitelná. Jakmile se však rekurzi naučíme, stává se pro nás silným nástrojem, jež můžeme využít v každodenním programátorském životě.

Abychom pochopili rekurzi, musíme nejprve pochopit rekurzi.

Stephen Hawking

Naopak nevýhodou funkcionálního programování je těžké pochopení napsaných programů. Málokdo si dokáže rychle a přesně představit, jak se zanořuje rekurze. Navíc člověk musí věnovat hodně času procvičení, aby se ji pořádně naučil. Někdy také rekurzivně psané algoritmy ztrácí na efektivitě, jelikož si musí pamatovat návratové pozice při zanoření do rekurze. Tomu se dá vyhnout, pokud algoritmus přepíšeme do koncové rekurze, kterou umí kompilátor optimalizovat.

Funkcionální programování pracuje pouze s funkcemi, kde hlavní síla výpočtu leží na bedrech rekurze. Daný zápis algoritmu se oproti imperativním jazykům (C, C++, …) daleko více podobá matematickým ideálům a často bývá kratší. Na druhou stranu pochopit takový zápis nebývá jednoduché a člověk musí rekurzi věnovat čas, aby ji dokázal správně využít.