Funkcionální programování

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. února 2022; kontroly vyžadují 2 úpravy .

Funkcionální programování  je programovací paradigma, ve kterém je proces výpočtu interpretován jako výpočet hodnot funkcí v matematickém chápání funkcí (na rozdíl od funkcí jako podprogramů v procedurálním programování ).

V kontrastu s paradigmatem imperativního programování , které popisuje proces počítání jako postupnou změnu stavů (v jistém smyslu podobném teorii automatů ). Pokud je to nutné, ve funkcionálním programování je celá množina sekvenčních stavů výpočetního procesu reprezentována explicitně, například jako seznam .

Funkční programování je o počítání výsledků funkcí ze vstupních dat a výsledků jiných funkcí a neznamená explicitní uložení stavu programu. Neznamená to tedy ani proměnlivost tohoto stavu (na rozdíl od imperativu , kde jedním ze základních pojmů je proměnná , která uchovává svou hodnotu a umožňuje vám ji měnit při provádění algoritmu ).

V praxi je rozdíl mezi matematickou funkcí a pojmem „funkce“ v imperativním programování v tom, že imperativní funkce se mohou spoléhat nejen na argumenty, ale také na stav proměnných vnějších k funkci, stejně jako mají vedlejší účinky a změny. stav vnějších proměnných. V imperativním programování tedy při volání stejné funkce se stejnými parametry, ale v různých fázích provádění algoritmu, můžete získat různá výstupní data v důsledku vlivu stavu proměnné na funkci. A ve funkcionálním jazyce při volání funkce se stejnými argumenty vždy dostaneme stejný výsledek: výstup závisí pouze na vstupu. To umožňuje běhovým prostředím funkčního jazyka ukládat do mezipaměti výsledky funkcí a volat je v pořadí, které není definováno algoritmem, a paralelizovat je bez jakékoli další práce na straně programátora (což poskytuje funkce bez vedlejších účinků - čisté funkce ) .

Lambda kalkul je základem pro funkcionální programování, mnoho funkcionálních jazyků lze považovat za jeho „doplněk“ [1] .

Funkční programovací jazyky

Nejznámější funkcionální programovací jazyky jsou :

Dosud ne zcela funkční počáteční verze Lispu a APL přispěly k vytvoření a rozvoji funkcionálního programování. Pozdější verze Lisp, jako je Scheme , stejně jako různé varianty APL, podporovaly všechny rysy a koncepty funkcionálního jazyka [3] .

Zájem o funkcionální programovací jazyky, zejména ty čistě funkcionální, byl zpravidla spíše vědecký než komerční. Pozoruhodné jazyky jako Erlang , OCaml , Haskell , Scheme (po roce 1986) a také specifické R (statistika), Wolfram (symbolická matematika), J a K (finanční analýza) a XSLT ( XML ) našly své cesta do komerčního programovacího průmyslu. Rozšířené deklarativní jazyky jako SQL a Lex / Yacc obsahují některé prvky funkcionálního programování, například nepoužívají proměnné. Tabulkové jazyky lze také považovat za funkční, protože buňky tabulkového procesoru obsahují řadu funkcí, které obvykle závisí pouze na jiných buňkách, a pokud chcete modelovat proměnné, musíte se uchýlit ke schopnostem jazyka imperativních maker.

Historie

Lambda kalkul se stal teoretickým základem pro popis a výpočet funkcí. Jelikož se jedná o matematickou abstrakci , nikoli o programovací jazyk , tvoří dnes základ téměř všech funkcionálních programovacích jazyků. Podobný teoretický koncept, kombinatorická logika , je abstraktnější než λ-počet a byl vytvořen dříve. Tato logika se používá v některých esoterických jazycích , jako je Unlambda . Jak λ-počet, tak kombinatorická logika byly vyvinuty k jasnějšímu a přesnějšímu popisu principů a základů matematiky [4] .

Prvním funkčním jazykem byl Lisp , vytvořený Johnem McCarthym na MIT koncem padesátých let a implementovaný původně pro IBM 700/7000 [5] . Lisp byl první, kdo představil mnoho konceptů funkcionálního jazyka, ačkoli jazyk používá více než jen paradigma funkcionálního programování [6] . Lisp byl dále vyvinut jazyky jako Scheme a Dylan .

Information Processing Language [ , IPL je někdy definován jako úplně první strojový funkční jazyk [7] . Je to assembler pro práci se seznamem symbolů. Měl koncept „generátoru“, který používal funkci jako argument, a také, protože jde o jazyk na úrovni assembleru, může být umístěn jako jazyk, který má funkce vyššího řádu. Obecně však IPL zdůrazňuje použití imperativních pojmů [8] .

Kenneth Iverson vyvinul jazyk APL na počátku šedesátých let a dokumentoval jej ve své knize Programovací jazyk ( ISBN 978-0-471-43014-8 ) [9] . APL mělo významný vliv na jazyk FP vytvořený Johnem Backusem . Na počátku 90. let Iverson a Roger Hui vytvořili nástupce APL, programovací jazyk V polovině devadesátých let vytvořil Arthur Whitney , který dříve spolupracoval s Iversonem, jazyk K , který byl následně komerčně využíván ve finančním průmyslu.

Robin Milner vytvořil jazyk ML na University of Edinburgh v 70. letech 20. století a David Turner založil SASL na University of St. Andrews a později Miranda na University of Kent. Nakonec bylo na ML vytvořeno několik jazyků, z nichž nejznámější jsou Objective Caml a Standard ML . Také v sedmdesátých letech byl vyvinut programovací jazyk založený na principu Scheme (implementace nejen funkčního paradigmatu), který byl popsán ve slavném díle „Lambda Papers“ i v knize z 85. „ Struktura a interpretace počítačových programů “.

V roce 1972 vytvořil Per Martin-Löf intuicionistickou teorii typů (nazývanou také konstruktivní). V této teorii získalo funkcionální programování konstruktivní důkaz toho, co bylo dříve známé jako závislý typ. To dalo silný impuls k rozvoji interaktivního dokazování teorémů ak následnému vytvoření mnoha funkcionálních jazyků.

Haskell byl vytvořen na konci 80. let ve snaze spojit mnoho nápadů z výzkumu funkčního programování [3] .

Koncepty

Některé koncepty a paradigmata jsou specifické pro funkcionální programování a většinou cizí pro imperativní programování (včetně objektově orientovaného programování ). Programovací jazyky jsou však obvykle hybridem několika programovacích paradigmat, takže „většinou imperativní“ programovací jazyky mohou používat kterýkoli z těchto konceptů [10] .

Funkce vyššího řádu

Funkce vyššího řádu jsou funkce, které mohou brát jako argumenty a vracet jiné funkce. [11] . Matematici často nazývají takovou funkci operátorem , například derivační operátor nebo integrační operátor.

Funkce vyššího řádu umožňují použití curryingu  – transformace funkce z dvojice argumentů na funkci, která bere své argumenty jeden po druhém. Tato transformace je pojmenována po Haskell Currym .

Čisté funkce

Čisté funkce jsou ty, které nemají vedlejší efekty I/O a paměti (závisí pouze na svých parametrech a vrací pouze svůj výsledek). Čisté funkce mají několik užitečných vlastností, z nichž mnohé lze použít k optimalizaci kódu:

Díky zapamatování, pokud je funkce později volána se stejnými argumenty, lze její výsledek převzít přímo z tabulky hodnot bez výpočtu (někdy nazývaný princip referenční průhlednosti). Memoizace za cenu malé spotřeby paměti může výrazně zvýšit výkon a snížit pořadí růstu některých rekurzivních algoritmů.

Zatímco většina kompilátorů imperativních programovacích jazyků rozpoznává čisté funkce a odstraňuje běžné podvýrazy pro čistě funkční volání, nemůže tak vždy učinit pro předkompilované knihovny, které obecně tyto informace neposkytují. Některé kompilátory, jako je gcc , poskytují programátorovi klíčová slova čistě funkční pro účely optimalizace [12] . Fortran 95 umožňuje označit funkce jako „čisté“ (čisté) [13] .

Rekurze

Ve funkcionálních jazycích je smyčka obvykle implementována jako rekurze. Přísně vzato, ve funkčním programovacím paradigmatu nic jako smyčka neexistuje. Rekurzivní funkce volají samy sebe, což umožňuje operaci provádět znovu a znovu. Pro použití rekurze může být vyžadován velký zásobník , ale tomu se lze vyhnout pomocí koncové rekurze . Koncová rekurze může být rozpoznána a optimalizována kompilátorem do kódu, který je výsledkem kompilace podobné iterace v imperativním programovacím jazyce. [14] Jazykové standardy schématu vyžadují rozpoznání a optimalizaci rekurze ocasu. Ocasní rekurzi lze optimalizovat převodem programu do stylu používání pokračování při jeho kompilaci, jako jednoho ze způsobů. [patnáct]

Rekurzivní funkce lze zobecnit na funkce vyšších řádů, například pomocí katamorfismu a anamorfismu (neboli „konvoluce“ a „expanze“) [16] . Funkce tohoto druhu hrají roli takového konceptu jako cyklus v imperativních programovacích jazycích [17] .

Přístup hodnocení argumentů

Funkční jazyky lze klasifikovat podle toho, jak se při vyhodnocování zachází s argumenty funkcí. Technicky rozdíl spočívá v denotační sémantice výrazu. Například s přísným přístupem k hodnocení výrazu:

tisk ( len ([ 2 + 1 , 3 * 2 , 1 / 0 , 5 - 4 ]))

výstup bude chybový, protože třetí prvek seznamu obsahuje dělení nulou. Při nestriktním přístupu bude hodnota výrazu 4, protože přísně vzato, hodnoty jeho prvků nejsou důležité pro výpočet délky seznamu a nemusí se vůbec vypočítat. Při přísném (aplikativním) pořadí vyhodnocování jsou hodnoty všech argumentů předem vypočteny před vyhodnocením samotné funkce. Při nestriktním přístupu (normální pořadí vyhodnocení) se hodnoty argumentů nevyhodnocují, dokud není jejich hodnota potřebná při vyhodnocování funkce [18] .

Zpravidla je implementován nestriktní přístup ve formě redukce grafu. Nepřísné hodnocení je výchozí v několika čistě funkčních jazycích, včetně Mirandy a Haskella [19] .

V nefunkčních jazycích

V zásadě neexistují žádné překážky pro psaní programů ve funkcionálním stylu v jazycích, které nejsou tradičně považovány za funkční, stejně jako programy v objektově orientovaném stylu lze psát ve strukturních jazycích. Některé imperativní jazyky podporují konstrukce typické pro funkcionální jazyky, jako jsou funkce vyššího řádu a porozumění seznamům, které usnadňují použití funkcionálního stylu v těchto jazycích, zejména tento přístup je široce používán v praxi jazyka Python . Dalším příkladem je jazyk Ruby , který má schopnost vytvářet jak anonymní funkce pomocí vázaných proměnných (λ-objektů), tak schopnost organizovat anonymní funkce vyššího řádu prostřednictvím bloku pomocí yield. V C lze ukazatele funkcí jako typy argumentů použít k vytvoření funkcí vyššího řádu. Funkce vyššího řádu a struktura odloženého seznamu jsou implementovány v knihovnách C++ . V Javě 8 a novějších a C# 3.0 a novějších můžete pomocí λ-funkcí napsat program ve funkčním stylu.

Styly programování

Imperativní programy mají tendenci zdůrazňovat sekvence kroků k provedení nějaké akce, zatímco funkční programy mají tendenci zdůrazňovat uspořádání a složení funkcí, často neoznačující přesnou sekvenci kroků. Jednoduchý příklad dvou řešení stejného problému (pomocí stejného jazyka Python ) to ilustruje.

# imperativní styl target = [] # vytvořit prázdný seznam pro položku v source_list : # pro každý prvek ve zdrojovém seznamu trans1 = G ( item ) # apply G() function trans2 = F ( trans1 ) # apply F() function target . append ( trans2 ) # přidat převedený prvek do seznamu

Funkční verze vypadá jinak:

# funkční styl # FP jazyky mají často zabudovanou compose() compose2 = lambda A , B : lambda x : A ( B ( x )) target = mapa ( compose2 ( F , G ), source_list )

Na rozdíl od imperativního stylu, který popisuje kroky vedoucí k dosažení cíle, funkční styl popisuje matematický vztah mezi daty a cílem.

Přesněji řečeno, existují čtyři fáze ve vývoji funkčního stylu, v sestupném pořadí podle role dat v programech:

V prvním případě je celá struktura programu určena datovou strukturou, ve druhém případě data jako taková ve zdrojovém kódu vůbec nejsou, jsou pouze implikována na vstupu. Některé jazyky podporují řadu stylů: například Haskell vám umožňuje psát v aplikačním, kombinatorickém i beztečkovém stylu.

Funkce

Hlavním rysem funkcionálního programování, který určuje výhody i nevýhody tohoto paradigmatu, je implementace bezstavového výpočetního modelu. Pokud má imperativní program v jakékoli fázi provádění stav, to znamená sadu hodnot všech proměnných, a produkuje vedlejší efekty, pak čistě funkční program nemá žádný stav ani jako celek, ani po částech a nevytváří vedlejší účinky. efekty. To, co se v imperativních jazycích dělá přiřazováním hodnot proměnným, se ve funkčních jazycích dosahuje předáváním výrazů parametrům funkce. Bezprostředním důsledkem je, že čistě funkční program nemůže měnit data, která již má, ale může pouze generovat nová zkopírováním nebo rozšířením starých. Důsledkem toho samého je odmítnutí cyklů ve prospěch rekurze.

Silné stránky

Zvýšení spolehlivosti kódu

Atraktivní stránkou bezstavového počítání je zvýšená spolehlivost kódu díky jasnému strukturování a absenci potřeby sledovat vedlejší účinky. Jakákoli funkce pracuje pouze s lokálními daty a pracuje s nimi vždy stejně, bez ohledu na to, kde, jak a za jakých okolností je volána. Nemožnost mutace dat při jejich použití na různých místech programu eliminuje výskyt těžko odhalitelných chyb (jako je například náhodné přiřazení nesprávné hodnoty globální proměnné v imperativním programu).

Snadná organizace testování jednotek

Vzhledem k tomu, že funkce ve funkcionálním programování nemůže vyvolat vedlejší efekty, nelze objekty měnit uvnitř rozsahu ani vně (na rozdíl od imperativních programů, kde jedna funkce může nastavit nějakou externí proměnnou čtenou druhou funkcí). Jediným účinkem vyhodnocení funkce je výsledek, který vrátí, a jediným faktorem, který výsledek ovlivňuje, je hodnota argumentů.

Je tedy možné otestovat každou funkci v programu pouhým vyhodnocením z různých sad hodnot argumentů. V tomto případě se nemusíte starat o volání funkcí ve správném pořadí, ani o správné vytvoření externího stavu. Pokud některá funkce v programu projde unit testy, pak si můžete být jisti kvalitou celého programu. V imperativních programech kontrola návratové hodnoty funkce nestačí: funkce může upravit vnější stav, což je také potřeba zkontrolovat, což ve funkčních programech není nutné [20] .

Možnosti optimalizace kompilátoru

Tradičně zmiňovanou pozitivní vlastností funkcionálního programování je, že umožňuje popis programu v tzv. „deklarativní“ podobě, kdy rigidní posloupnost provádění mnoha operací nutných k výpočtu výsledku není výslovně specifikována, ale je tvořena automaticky v proces výpočtu funkcí. Tato okolnost, stejně jako absence stavů, umožňuje aplikovat na funkční programy poměrně složité metody automatické optimalizace.

Souběžné schopnosti

Další výhodou funkčních programů je, že poskytují nejširší možnosti automatické paralelizace výpočtů. Vzhledem k tomu, že je zaručena absence vedlejších efektů, je při každém volání funkce vždy přípustné paralelně vyhodnocovat dva různé parametry - pořadí, v jakém jsou vyhodnocovány, nemůže ovlivnit výsledek volání.

Čitelnost místního kódu

Při analýze kódu imperativního programu je důležité vědět, „kde se nyní nacházíme“. Bez porozumění prostředí je obtížné provádět změny v kódu, takže před provedením změn musíte nejprve pochopit obecný kontext provádění nebo alespoň v rámci upravovaného modulu. Na druhou stranu ve funkcionálním programování lze kód číst a upravovat lokálně, bez obav, že to povede k nějakým neočekávaným následkům. To umožňuje účastníkům s různými úrovněmi přístupu spolupracovat na programu bez dalších nákladů na zajištění modularity kódu.

Nevýhody

Nevýhody funkcionálního programování pramení ze stejných vlastností. Absence přiřazení a jejich nahrazení generováním nových dat vede k potřebě neustálého přidělování a automatického uvolňování paměti, proto je v systému provádění funkčního programu povinné součástí se stává vysoce účinný garbage collector . Nepřísný výpočetní model vede k nepředvídatelnému pořadí volání funkcí, což vytváří problémy v I/O, kde je důležité pořadí operací. Také samozřejmě vstupní funkce ve své přirozené podobě (například ze standardní getchar()knihovny C ) nejsou čisté, protože jsou schopny vracet různé hodnoty pro stejné argumenty a k jejich odstranění jsou zapotřebí určité triky.

K překonání nedostatků funkcionálních programů obsahovaly i první funkcionální programovací jazyky nejen čistě funkcionální nástroje, ale také mechanismy pro imperativní programování (přiřazení, smyčka, „implicitní PROGN“ byly již v Lisp). Použití takových nástrojů řeší některé praktické problémy, ale znamená odklon od myšlenek (a výhod) funkcionálního programování a psaní imperativních programů ve funkcionálních jazycích. V čistě funkcionálních jazycích jsou tyto problémy řešeny jinými prostředky, například v Haskell je I/O implementován pomocí monád  , konceptu vypůjčeného z teorie kategorií.

Poznámky

  1. ↑ A. Field, P. Harrison Funkční programování: Per. z angličtiny. - M .: Mir, 1993. - 637 s., ill. ISBN 5-03-001870-0 . Strana 120 [Kapitola 6: Matematické základy: λ-počet].
  2. ↑ 1 2 Paul Hudák Koncepce, vývoj a aplikace funkcionálních programovacích jazyků  ​​(anglicky)  // Association for Computing Machinery Computing Surveys: journal. - 1989. - září ( roč. 21 , č. 3 ). - str. 359-411 . - doi : 10.1145/72551.72554 . Archivováno z originálu 5. června 2013.
  3. ↑ Roger Penrose . Kapitola 2: Church's Lambda Calculus // Králova nová mysl. O počítačích, myšlení a fyzikálních zákonech = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. - Editorial URSS, 2003. - ISBN 5-354-00005-X . + opětovné vydání ISBN 978-5-382-01266-7 ; 2011
  4. ↑ McCarthy, John Historie Lisp  // In Association for Computing Machinery SIGPLAN Historie programovacích jazyků ​​Konference. - 1978. - Červen. - S. 217-223 . - doi : 10.1145/800025.808387 . Archivováno z originálu 7. června 2008.
  5. ↑ J. Harrison, 1997 , Ch. 3. λ-kalkul jako programovací jazyk.
  6. ↑ Ve svých memoárech Herbert Simon (1991), Modely mého života s. 189-190 ISBN 0-465-04640-1 uvádí, že jeho, Al. Newell a Cliff Shaw, kteří jsou „často označováni jako otcové umělé inteligence“ za napsání programu Logic Theorist , který automaticky dokazuje teorémy z Principia Mathematica . Aby toho dosáhli, museli přijít s jazykem a paradigmatem, které lze zpětně vnímat jako funkcionální programování.
  7. ↑ Historie programovacích jazyků: IPL (downlink) . Získáno 15. dubna 2012. Archivováno z originálu 1. listopadu 2006. 
  8. ↑ XIV. APL Session // Historie programovacího jazyka / Richard L. Wexelbblat. - Academic Press, 1981. - S.  661 -693. — 749 s. — ISBN 0-12-745040-8 .
  9. ↑ Jevgenij Kirpichev. Prvky funkcionálních jazyků  // Praxe funkcionálního programování. - 2009. - Prosinec ( číslo 3 ). — ISSN 2075-8456 . Archivováno z originálu 3. září 2017.
  10. ↑ Stáhnout PDF: "Techniky funkcionálního programování, V. A. Potapenko" str. 8 "Funkce vyšších řádů" . Datum přístupu: 10. ledna 2009. Archivováno z originálu 30. června 2009.
  11. ↑ GCC, Deklarace atributů funkcí . Získáno 28. srpna 2012. Archivováno z originálu 18. srpna 2012.
  12. ↑ XL Fortran pro AIX, V13.1 > Jazyková reference, čisté postupy (Fortran 95)
  13. ↑ Optimalizace koncového volání . Datum přístupu: 31. července 2012. Archivováno z originálu 1. srpna 2012.
  14. ↑ Revised5 Report on the Algorithmic Language Scheme, 3.5. Správná rekurze ocasu . Datum přístupu: 31. července 2012. Archivováno z originálu 5. ledna 2007.
  15. ↑ Meijer, Erik ; Fokkinga, Maarten; Paterson, Ross (1991). Funkční programování s banány, čočkami, obálkami a ostnatým drátem (PDF) . Konference o funkčních programovacích jazycích a počítačové architektuře (FPCA). Springer. str. 124-144. CiteSeerX  10.1.1.41.125 . ISBN  3-540-54396-1 . Archivováno (PDF) z originálu dne 2017-07-09 . Staženo 2020-03-03 . Použitý zastaralý parametr |deadlink=( nápověda )
  16. ↑ Ptáček, Richard. Perly návrhu funkčních algoritmů  . - Cambrigde : University Press , 2010. - 277 s. - ISBN 978-0-521-51338-8 . Archivováno 8. března 2022 na Wayback Machine
  17. ↑ N. A. Roganova Funkcionální programování: Učebnice pro studenty vysokých škol - M .: GINFO, 2002. - 260 s. Strana 14 str. 3.1. Lazy and Eager Computing
  18. ↑ Líné hodnocení - přehled | Témata ScienceDirect . www.sciencedirect.com . Staženo: 23. března 2021.
  19. ↑ Ahmechet V. "Funkční programování pro každého" . Datum přístupu: 11. ledna 2009. Archivováno z originálu 2. února 2009.

Literatura

  • Gorodnyaya LV Základy funkcionálního programování. Průběh přednášek - M .: Internetová univerzita informačních technologií, 2004. S. 280. ISBN 5-9556-0008-6
  • Dushkin R. V. Funkční programování v Haskellu. — M.: DMK Press, 2006. S. 608. ISBN 5-94074-335-8
  • Field A., Harrison P. Funkční programování = Funkční programování. — M .: Mir, 1993. — 637 s. — ISBN 5-03-001870-0 .
  • N. A. Roganova Funkcionální programování: Učebnice pro studenty vysokých škol - M .: GINFO, 2002. - 260 s.
  • John Harrison. Funkcionální programování. Kurz přednášek = Funkcionální programování . — 1997.
  • A. M. Mironov. Teorie funkčních programů.

Odkazy

  Přejděte na položku Wikidata  Slovníky a encyklopedie