Funkcionální programování: Porovnání verzí
Smazaný obsah Přidaný obsah
→Striktní, nestriktní a líné vyhodnocení:
opraven překlep a "efektnější -> efektivnější" značka: editace z Vizuálního editoru |
opravy, vagnosti a nepresnosti zbyvaji v mnozstvi vetsim nez malem značka: editace z Vizuálního editoru |
||
Řádek 1:
'''Funkcionální programování''' je [[deklarativní programování|deklarativní]] programovací [[Programovací paradigma|paradigma]], které chápe výpočet jako vyhodnocení [[Funkce (matematika)|matematických funkcí]]. Funkcionální programování má své kořeny v [[Lambda kalkul|lambda-kalkulu]], formálním systému vyvinutém v 30. letech k vyšetřování definicí funkcí, jejich aplikace a rekurze. Mnoho funkcionálních programovacích jazyků může být považováno za rozšíření lambda kalkulu.
Výpočtem funkcionálního programu je tedy posloupnost vzájemně ekvivalentních výrazů, které se postupně zjednodušují. Výsledkem výpočtu, pokud se k němu podaří dospět, je výraz v dále
V praxi je rozdíl mezi matematickou funkcí a představou funkce použité v [[Imperativní programování|imperativním programování]]. [[Turingův_stroj#Subrutiny|Imperativní funkce]] mohou mít [[Vedlejší účinek|vedlejší účinky]], které mění stav programu. Z toho důvodu postrádají [[referenční transparentnost]]: Stejné volání může vést k různým návratovým hodnotám v závislosti na stavu vykonávaného programu. Oproti tomu ve funkcionálním kódu návratové hodnoty funkcí záleží pouze na argumentech funkce, a tudíž dvě volání téže funkce se stejnými argumenty vrací vždy stejnou hodnotu. Eliminace vedlejších účinků může zjednodušit analýzu a pochopení chodu programu, což je jednou z klíčových motivací pro vývoj funkčního programování.
Řádek 15:
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 [[Rozhodnutelnost|nerozhodnutelná]].
[[Lambda kalkul]] poskytuje teoretickou
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.
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
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 (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í.
Řádek 35:
=== Higher-order funkce ===
Funkce jsou higher-order
=== Čistě funkcionální ===
Řádek 66:
=== 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.
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ýt 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.
<code>
f:=x^2+x+1
Řádek 88:
f(g(1, 4)) → g(1,4)^2+g(1,4)+1 → (1+4)^2+(1+4)+1 → 5^2+5+1 → 31</code>
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 efektivnější. Ve striktním výpočtu je argument počítán jednou, zatímco v "blbě implementovaném" 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 (programovací jazyk)|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í|čistě funkcionálními]] jazyky jako je [[Miranda (programovací jazyk)|Miranda]], [[Clean]] a [[Haskell (programovací jazyk)|Haskell]].
Řádek 102:
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ů.
Zatím ani slovo o anonymních funkcích, tzv. lambda funkcích.
=== 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ády (funkcionální programování)|monád]],
=== Záležitosti efektivity ===
|