Funkcionální programování

Z Multimediaexpo.cz

Aktuální verze z 14. 8. 2022, 14:51

Funkcionální programování patří mezi deklarativní programovací principy. Alonzo Church vytvořil formální výpočtový model nazvaný \(\lambda\)-kalkul. Tento model slouží jako základ pro funkcionální jazyky. Funkcionální jazyky dělíme na:

• typované – Haskell
• netypované – Lisp, Scheme

Výpočtem funkcionálního programu je posloupnost vzájemně ekvivalentních výrazů, které se postupně zjednodušují. Výsledkem výpočtu je výraz v normální formě, tedy dále nezjednodušitelný. Program je chápán jako jedna funkce obsahující vstupní parametry mající jediný výstup. Tato funkce pak může být dále rozložitelná na podfunkce.

Funkcionální programování

Funkcionální programování je paradigmatické programování, které zachází s výpočtem jako s vyhodnocením matematických funkcí. Zaměřuje se na aplikaci složenou z funkcí, na rozdíl od imperativního programování, které se zaměřuje na změny stavu. Jinými slovy imperativní jazyky se orientují na popis toho, jak se má provádět výpočet, a jazyky deklarativní jsou naopak zaměřené na to, co se má vypočítat. Funkcionální jazyky zahrnují APL, Erlang, Haskell, Lisp, ML, Oz a Scheme. V případě funkcionálních jazyků, jak již jejich název napovídá, je základním modelem výpočtu matematický pojem funkce aplikované na argumenty a vypočítávající deterministicky jediný výsledek. Tyto jazyky vycházejí z teorie funkcí – lambda-kalkulu, který vytváří základ pro většinu modelů funkcionálních programů. V praxi se můžeme setkat jak s čistě funkcionálními jazyky, které striktně vycházejí z teorie (např. FP, Haskell, Miranda, Hope), tak i s hybridními jazyky, které mohou obsahovat i prvky, které jsou se základními principy funkcionálního programování v rozporu. Například často citovaný „typicky“ funkcionální jazyk Lisp je ve skutečnosti jazykem hybridním, neboť umožňuje modifikovat hodnoty již definovaných proměnných. Mezi hybridní jazyky patří rovněž jazyk Standard ML a jazyk Scheme.

Použití

Funkcionální programovací jazyky, hlavně čistě funkcionální, se používají spíše v akademických kruzích, než v komerčním softwarovém vývoji. Nicméně funkční programovací jazyky používané v průmyslu a komerčních aplikacích zahrnují Erlang, R (statistický), Matematika (symbolická matematika), Haskell, ML, J a K (finanční analýza) a domain-specific programovací jazyky jako XSLT. Dále jsou funkcionální programovací jazyky důležité pro některá odvětví informatiky, například zabývající se umělou inteligencí, formální specifikací, modelováním nebo rychlým prototypováním.

Historie

Prvopočátky funkcionálních jazyků najdeme již ve 30. letech 20. století. Tehdy profesor matematiky a filosofie na Princeton University Alonzo Church (1903-1995) vytvořil netypovaný lambda kalkul jako matematickou teorii funkcí. K nejznámějším Churchovým vědeckým přínosům patří také tzv. Church-Turingova teze o tom, že algoritmus je ekvivalentní pojmu funkce a Churchův teorém z roku 1936 o tom, že aritmetika je nerozhodnutelná. Lambda kalkul poskytuje teoretickou konstrukci pro popis funkcí a jejich vyhodnocení. Ačkoliv je to více matematická abstrakce než programovací jazyk, vytváří dnes základy téměř všech funkcionálních jazyků. Kombinatorická logika je variace lambda kalkulu, kde jsou lambda výrazy nahrazeny omezenou sadou primitivních funkcí - kombinátorů. Vytvořil ji Mores Schöfinkel a Haskell Brooks Curry . Původně ji vytvořili k dosažení čistšího přístupu k základům matematiky. Kombinační logika je obecně chápána víc abstraktně něž Lambda kalkul a ve vývoji ji předběhla. Jeden z prvních jazyků, který v sobě zahrnoval funkcionální část byl LISP, vytvořený Johnem McCarthym pro IBM série 700/7000 vědeckých počítačů na konci 50. LET. LISP představil spoustu vlastností, které můžeme najít v nynějších funkcionálních jazycích, ačkoliv LISP je technicky multi-paradigmatický jazyk. Scheme a Dylan byly pozdější pokusy zjednodušit a vylepšit LISP. Informační procesní jazyk IPL je někdy uváděn jako první počítačový funkcionální jazyk. Je to jazyk pro manipulaci se seznamem znaků. Má svůj generátor funkcí, který se stará o to aby funkce mohla přijmout funkci jako argument a vzhledem k tomu že je to assembly-level jazyk, kód může být použit jako data, takže IPL může být považován za higher-order funkční. Každopádně hodně závisí na měnící se struktuře seznamu a podobných přímých vlastnostech. Keenen E. Iverson vyvinul programovací jazyk APL na začátku 60. let a popsal ho roku 1962 ve své knize “A programming Language”. APL měl hlavní vliv na programovacím jazyku FP Johna Backuse. Na začátku 90. let, vytvořil Iverson a Roger Hui nástupce APL, J programing. Uprostřed let 90. Artur Whitney, který pracoval s Iversonem, vytvořil K programovací jazyk, který se používá v komerčním a finančním průmyslu. John Backus představil programovací jazyk FP v roce 1977 v jeho přednášce Can Programming Be Liberated From the von Neuman Style za niž obdržel Turingovu cenu, která se uděluje za významný technický přínos pro oblast výpočetní techniky. Definoval funkcionální programy tak, že následují principy kompozice. Backusovy noviny popularizovaly výzkum funkcionálního programování, přestože zdůrazňovali functional-level programming spíše než lambda kalkul, který byl spojován s funkcionálním programováním. V 70. letech vytvořil Robin Milner na universitě v Edinburgu programovací jazyk ML, a David Turner vyvinul jazyk Miranda na universitě v Kentu. ML byl poté pozměněn do několika dialektů, z nichž jsou nyní nejběžnější Objektive Caml a Standard ML. Programovací jazyk Haskell byl uvolněn na konci osmdesátých let jako pokus skloubit dohromady odlišné přístupy, které byly objeveny v průběhu výzkumu funkcionálního programování.

Koncepty

Spousta konceptů a paradigmat jsou vlastní funkcionálnímu programování a cizí imperativnímu programování (včetně objektově orientovaného programování). Nicméně programovací jazyky jsou často hybridy několika programovacích paradigmat, takže programátoři používající hlavně imperativní mohou též používat některý z konceptů funkcionálního programování.

Higher-order funkce

Funkce jsou higher-order ve chvíli, kdy můžou převzít druhou funkci jako argument a navrátit ji jako výsledek. (Derivace a antiderivace jsou toho příkladem). Higher-order funkce jsou blízce příbuzné s funkcemi první třídy v tom, že obě dovolují funkci jako argument a výsledek jiné funkce. Rozdíl mezi těmito funkcemi je tento: higher-order popisuje matematický koncept funkce aplikovanou na jinou funkci, přičemž First class je počítačově-vědní termín, který popisuje programové jazykové entity, které nemají žádné omezení v jejich použití (tudíž first class funkce se může objevit kdekoliv v programu, stejně jako jiné first class entity, jako například čísla, včetně použití jako argument funkce nebo návratová hodnota funkce). Higher-order funkce aktivují currying, což je technika, v které je funkce používána na vlastní argument najednou, přičemž při každém použití navrátí další higher-order funkci, která přijme další argument.

Čistě funkcionální

Čistě funkcionální programy nemají žádné vedlejší efekty. To činí jejich chování jednodušší na jejich pochopení. Například výsledek použití čisté funkce na čistý argument nezávisí na pořadí vyhodnocení. V důsledku jazyk, který nemá žádné nečisté funkce (čistě funkcionální jako například Haskell), může použít evaluaci call-by-need. Nicméně ne všechny funkcionální jazyky jsou čisté. Jazyky z rodiny Lispu nejsou čisté, protože způsobují vedlejší efekty. Od té doby, co čisté funkce neupravují sdílené proměnné, může být paralelně sdíleno více čistých funkcí, aniž by se navzájem ovlivňovaly. Čisté funkce jsou proto vláknově bezpečné, a to umožňuje interpretům a kompilerům používat evaluaci call-by-future. Čistě funkcionální programovací jazyky typicky vyžadují referenční průhlednost, což znamená, že pokud dva výrazy mají stejné hodnoty, může být jeden dosazen za druhý v jakémkoliv výrazu bez ovlivnění výsledku. Například:

y = f(x) * f(x);

Pokud je funkce f(x) čistá, může kompilátor kód převést a transformovat program takto:

z  = f(x);
y = z * z;

a eliminuje druhé vyhodnocení (pravděpodobně zbytečného volání funkce f(x)). Tato optimalizace se nazývá eliminace společného podvýrazu (common subexpression elimination). Nicméně jestliže má funkce vedlejší efekt, volání funkce nemůže být eliminováno. Podívejte se na následující program:

y  = random() * random();

Druhé volání random nemůže být eliminováno, protože návratová hodnota se může lišit od předchozího volání. Podobně

y  = printf(“x”) * printf(“x”);

nemůže být optimalizováno, i kdyby printf vrátil stejnou hodnotu v obou případech, chybějící druhé volání by způsobilo změnu ve výstupu programu. Většina kompilerů pro imperativní programovací jazyky detekuje čisté funkce a provádí obecnou eliminaci podvýrazu pro volání čistých funkcí. Předkompilované knihovny většinou nevyhodnocují tuto informaci a tím zabraňují optimalizaci externí funkce. Některé kompilery, jako například gcc, přidávají extra výraz pro programátora, aby explicitně označil externí funkce jako čisté, takže mohou být optimalizovány i za přítomnosti předkompilovaných knihoven.

Rekurze

Opakování je ve funkcionálních jazycích obvykle provedeno pomocí rekurze. Rekurzivní funkce vyvolávají samy sebe, čímž dovolují opakování programu. Konec rekurze může být rozpoznán a optimalizován kompilerem do stejného kódu, který se používá na implementaci opakování u imperativních jazyků. Programovací jazyk Scheme standardně vyžaduje další implementaci k rozpoznávání těchto funkcí. Obecné vzory rekurzí mohou být změněny za použití higher order funkcí, catamorphismus a anamorphismus jsou toho nejzřejmější příklady. Takové higher order funkce hrají obvykle roli podobnou vestavěným kontrolním strukturám, jako jsou smyčky v imperativních programovacích jazycích.

Striktní, Nestriktní a líné vyhodnocení

Funkcionální jazyky mohou býk kategorizovány podle toho, používají-li striktní nebo nestriktní vyhodnocení, což jsou koncepty, které říkají jak budou zpracovány argumenty funkce při vyhodnocování výrazu. Pro ilustraci se podívejte na následující dvě funkce f a g.

f:=x^2+x+1
g:=x+y

Následující výraz bude vyhodnocen jednou z těchto cest.

f(g(1, 4))

Výpočet vnitřnější funkce g jako první.

f(g(1, 4))   →   f(1+4)   →   f(5)   →   5^2+5+1   →   31

Výpočet vnější funkce f jako první.

f(g(1, 4))   →   g(1,4)^2+g(1,4)+1   →   (1+4)^2+(1+4)+1   →   5^2+5+1   →   31

V prvním případě se jedná o striktní výpočet, argumenty funkce jsou vyhodnoceny před voláním funkce; vedle toho druhý případ je příklad nestriktního vyhodnocení, kde jsou argumenty přenechány ve funkci nevyhodnocené a volání funkce určuje kdy budou argumenty vyhodnoceny. Striktní vyhodnocení je efektnější. Ve striktním výpočtu je argument počítám jednou, zatímco v nestriktním může být počítán vícekrát, jak můžete vidět v příkladu nahoře, kde je funkce g vypočítána vícekrát. Striktní výpočet je také jednodušší implementovat, pokud argumenty předané datové funkci jsou datové hodnoty, v nestriktním výpočtu mohou být argumenty výrazy. A ve výsledku první funkcionální jazyky jako LISP, ISWIM a ML spolu s hodně novými funkcionálními jazyky používají striktní výpočet. Nicméně jsou tu důvody preferovat nestriktní výpočet. Lambda kalkul poskytuje silnější teoretické základy pro jazyky, které používají nestriktní výpočet. Nestriktní výpočet používají nejvíce definiční jazyky. Například podporuje nekonečné datové struktury jako seznam všech kladných proměnných typu integer nebo všech prvočísel. S nestriktním výpočtem jsou tyto struktury vypočítány pouze v kontextu, kde je vyžadována konečná délka. To vedlo k vývoji líného výpočtu, což je typ nestriktního výpočtu, kde výsledek počátečního výpočtu kteréhokoliv argumentu může být sdílen přes výpočtovou sekvenci. Ve výsledku není argument spočítán nikdy více než jednou. Líný výpočet je používán hlavně línými moderními čistě funkcionálními jazyky jako je Miranda, Clean a Haskell.

Funkcionální programování v nefunkcionálních jazycích

Je možné používat funkcionální styl programování i v jazycích, které nejsou považovány za funkcionální. Některé nefunkcionální jazyky si od funkcionálních jazyků půjčily některé rysy jako higher-order funkce a zpracování seznamů. To dělá jednodušší používání tohoto stylu v těchto jazycích. Funkcionální struktury jako higher-order funkce a zpracování seznamů můžeme implementovat v C++ pomocí knihoven. V C můžeme použít ukazatele na funkce, abychom získali některé z efektů higher-order funkcí, například můžeme implementovat běžnou funkci mapování za použití funkčních ukazatelů. Deklarativní specifické jazyky jako SQL a Lex/Yacc, které nejsou Turing-kompletní, používají některé elementy funkcionálního programování, hlavně při vyvarování se nestálých hodnot.

Porovnání funkcionálního a imperativního programování

Funkcionální programování je velmi odlišné od imperativního programování. Nejvýraznější rozdíl je v tom, že funkcionální programování zabraňuje vedlejším efektům, které jsou používané v imperativním programování k implementování stavů vstupů a výstupů. Čistě funkcionální programování zakazuje vedlejší efekty. Zakázání vedlejších efektů zajišťuje referenční průhlednost, která ulehčuje verifikaci, optimalizaci a paralelizaci programů a ulehčuje psaní automatických nástrojů k provedení těchto procesů. Higher-order funkce jsou zřídka používány ve starších imperativních jazycích. Kde by tradiční imperativní programování nejspíše použilo smyčku k prozkoumání seznamu, funkcionální styl by často použil higher-order funkci mapování, která převezme jako argument funkci a seznam, aplikuje funkci na každý element seznamu a vrátí seznam výsledků

Simulování stavu

Některé úlohy se zdají být většinou implementovány pomocí stavu. Čistě funkcionální programování provádí tyto úlohy a vstupně výstupní úlohy (jako je třeba přijmutí uživatelského vstupu a výstup na obrazovku) jinou cestou. Čistě funkcionální jazyk, jako je Haskell, je implementuje za použití monád, odvozených od teorie kategorií. Monády jsou extrémně silné a nabízí intuitivní cestu jak modelovat stav (a jiné vedlejší efekty jako například vstupy a výstupy) v imperativním stylu bez ztráty čistoty. Zatímco existující monády jsou jednoduché na použití, pro spoustu lidí je těžké definovat novou monádu (která je občas potřebná pro určité typy knihoven). Alternativní metody jako třeba Hoareho logika a unikátnost byly vytvořeny pro sledování vedlejších efektů v programu. Některé moderní vývojové jazyky používají efektní systém k jednoznačnému zjištění vedlejších efektů.

Záležitosti efektivity

Funkcionální programovací jazyky mají automatické spravování paměti s garbage collection, v kontrastu se staršími programovacími jazyky jako je C a Pascal, které používají explicitní spravování paměti. Funkcionální programovací jazyky jsou náročnější na systémové prostředky. Nicméně spousta imperativních programovacích jazyků jako Java, Perl, Python, Ruby mají také automatickou správu paměti. Efektivita funkcionálních programovací jazyků se v poslední době zlepšila. Programy, které provádí náročné numerické výpočty ve funkcionálních jazycích jako OCaml a Clean, jsou stejně rychlé jako v C. Pro programy, které pracují s velkými maticemi a vícerozměrnými databázemi, byly vymyšleny a rychlostně optimalizovány array-funkcionální jazyky (jako J a K). Přestože čistě funkcionální jazyky jsou obecně považovány za pomalejší, jakýkoliv imperativní algoritmus se dá vyjádřit v těchto jazycích, přinejhorším s logaritmickým zpomalením. Navíc neměnnost dat může v mnoha případech vést k větší efektivitě díky tomu, že kompilátor může provádět předpoklady, které by byly v imperativních jazycích nejisté.

Programovací styly

Imperativní jazyky směřují k sérii kroků, vykonané programem při provádění akce, kdežto funkcionální programy směřují ke kompozici a poskládání funkcí často bez upřesňujících explicitních kroků. Jednoduchý příklad dvou řešení stejného problému za použití multiparadigmatického jazyka (Python):

# imperative style
target = []               # create empty list
for item in source_list:  # iterate over each thing in source
    trans1 = G(item)      # transform the item with the G() function
    trans2 = F(trans1)    # second transform with the F() function
    target.append(trans2) # add transformed item to target

Ve funkcionální verzi to vypadá jinak

# functional style
# FP-oriented languages often have standard compose()
compose2 = lambda F, G: lambda x: (F(G(x))
target = map(compose2(F,G), source_list)

V kontrastu k imperativnímu stylu, který popisuje kroky potřebných k vytvoření položky target, funkcionální styl popisuje matematický vztah mezi položkami source_list a target.

Související články

• Function-level programování
• Čistě funkcionální
• Imperativní programování
• Procedurální programování
• Deklarativní programování
• Logické programování