Domov › Internet › Funkční programování pro každého. Funkcionální programovací jazyky

Funkční programování pro každého. Funkcionální programovací jazyky

Funkční programování zahrnuje výpočet výsledků funkcí ze vstupních dat a výsledků jiných funkcí a nezahrnuje explicitní ukládání stavu programu. Neznamená to tedy 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 ji měnit během 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 vůči 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 algoritmu, můžete získat různá výstupní data v důsledku vlivu stavu proměnných 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 modulům funkčního jazyka ukládat výsledky funkcí do mezipaměti a volat je v pořadí, které není určeno algoritmem, a paralelizovat je bez jakékoli další akce ze strany programátora (viz níže).

Funkcionální programovací jazyky

LISP - (John McCarthy,) a mnoho z jeho dialektů, z nichž nejmodernější jsou:
Erlang - (Joe Armstrong, ) funkční jazyk s podporou procesů.
APL je předchůdcem moderních vědeckých výpočetních prostředí, jako je MATLAB.
(Mezi aktuálně používanými dialekty jsou známy Robin Milner, Standard ML a Objective CAML).
- funkční jazyk rodiny ML pro platformu .NET
Miranda (David Turner, který později vyvinul jazyk Haskell).
Nemerle je hybridní funkcionální/imperativní jazyk.
Haskell je čistě funkční. Pojmenováno po Haskell Currym.

Původní verze Lisp a APL, které ještě nebyly plně funkční, 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 vlastnosti a koncepty funkcionálního jazyka.

Zájem o funkcionální programovací jazyky, zejména ty čistě funkcionální, byl zpravidla spíše vědecký než komerční. Nicméně významné jazyky jako Erlang, OCaml, Haskell, Scheme (po roce 1986) a specifické (statistika), Mathematica (symbolická matematika) a K (finanční analýza) a XSLT (XML) našly uplatnění v komerčním programování. průmysl. Široce používané deklarativní jazyky jako SQL a Lex/Yacc obsahují některé prvky funkcionálního programování, například si dávají pozor, aby nepoužívaly 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.

Příběh

Prvním funkčním jazykem byl Lisp, vytvořený Johnem McCarthym během své práce na konci padesátých let a implementovaný původně pro IBM 700/7000. (Angličtina) ruština

. Lisp zavedl mnoho konceptů funkcionálního jazyka, i když nevyznával pouze paradigma funkcionálního programování. Dalším vývojem Lisp se staly jazyky jako Scheme a Dylan.

Koncepty

Některé koncepty a paradigmata jsou specifické pro funkcionální programování a jsou do značné míry cizí imperativnímu 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ů.

Funkce vyššího řádu

Funkce vyššího řádu jsou funkce, které mohou vzít jiné funkce jako argumenty a vrátit je. Matematici často nazývají takovou funkci operátorem, například derivační operátor nebo integrální operátor.

Funkce vyššího řádu vám umožňují používat currying – transformaci funkce z dvojice argumentů na funkci, která přebírá své argumenty jeden po druhém. Tato transformace byla pojmenována po H. Currym.

Čisté funkce

Pokud se nepoužije výsledek čisté funkce, lze jej odstranit, aniž by došlo k poškození jiných výrazů.
Výsledek čistého volání funkce lze uložit do paměti, to znamená uložit do tabulky hodnot spolu s argumenty volání. Pokud je funkce později volána se stejnými argumenty, lze její výsledek převzít přímo z tabulky, aniž by byl vyhodnocen (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ů.
Pokud mezi dvěma čistými funkcemi neexistuje žádná datová závislost, lze pořadí jejich výpočtu změnit nebo paralelizovat (jinými slovy, výpočet čistých funkcí splňuje principy zabezpečení vláken)
Pokud celý jazyk neumožňuje vedlejší účinky, lze použít jakoukoli politiku hodnocení. To dává kompilátoru svobodu kombinovat a reorganizovat vyhodnocování výrazů v programu (například odstranění stromových struktur).

Ačkoli 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í, nemohou to udělat vždy pro předkompilované knihovny, které obvykle tyto informace neposkytují. Některé kompilátory, jako je gcc, poskytují programátorovi klíčová slova k označení čistých funkcí pro účely optimalizace. Fortran 95 umožňuje funkce označit jako „čisté“.

Rekurze

Rekurzivní funkce lze zobecnit funkcemi vyšších řádů, například pomocí katamorfismu a anamorfismu (neboli „konvoluce“ a „rozvinutí“). Funkce tohoto druhu hrají roli takového konceptu jako smyčka v imperativních programovacích jazycích.

Přístup k hodnocení argumentů

Funkční jazyky lze klasifikovat podle toho, jak jsou argumenty funkce zpracovávány během jejího vyhodnocování. 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 pro výpočet délky seznamu nejsou hodnoty jeho prvků, přísně vzato, důležité a nemusí se vůbec vypočítat. S přísným (aplikativním) pořadím hodnocení jsou hodnoty všech argumentů vypočteny předem před vyhodnocením samotné funkce. V nestriktním přístupu (normální pořadí hodnocení) se hodnoty argumentů nevyhodnocují, dokud není jejich hodnota potřebná při vyhodnocování funkce.

Nestriktní přístup je zpravidla realizován formou redukce grafu. Nepřísné hodnocení je výchozí v několika čistě funkčních jazycích, včetně Miranda, Clean a Haskell.

FP v nefunkčních jazycích

V zásadě neexistuje žádná překážka 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, což usnadňuje použití funkčního stylu v těchto jazycích. Příkladem může být funkcionální programování v Pythonu.

Styly programování

Imperativní programy mají tendenci zdůrazňovat posloupnost kroků k provedení nějaké akce a funkční programy mají tendenci zdůrazňovat uspořádání a složení funkcí, často bez uvedení přesné posloupnosti kroků. Ilustruje to jednoduchý příklad dvou řešení stejného problému (pomocí stejného jazyka Python).

# imperativní styl cíl = # vytvořte prázdný seznam pro položku v source_list: # pro každý prvek původního seznamu trans1 = G(položka) # použít funkci G(). trans2 = F(trans1) # použít funkci F() target.append(trans2) # přidat převedený prvek do seznamu

Funkční verze vypadá jinak:

#funkční styl # Jazyky FP mají často vestavěnou funkci 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.

Zvláštnosti

Hlavním rysem funkcionálního programování, který určuje výhody i nevýhody tohoto paradigmatu, je jeho implementace bezstavový výpočetní model. 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á kopírováním a/nebo rozšiřováním starých. Důsledkem toho samého je opuštění smyček ve prospěch rekurze.

Silné stránky

Zlepš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ší efekty. 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 mutovat data při použití na různých místech v programu eliminuje výskyt těžko odhalitelných chyb (jako je například náhodné přiřazení špatné hodnoty globální proměnné v imperativním programu).

Snadná organizace testování jednotek

Protože funkce ve funkcionálním programování nemůže vyvolat vedlejší efekty, nelze objekty měnit ani uvnitř rozsahu, ani vně (na rozdíl od imperativních programů, kde jedna funkce může nastavit nějakou externí proměnnou, která je čtena druhou funkcí). Jediným účinkem vyhodnocení funkce je výsledek, který vrátí, a jediným faktorem, který výsledek ovlivňuje, jsou hodnoty 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í nebo o správné vytvoření externího stavu. Pokud některá funkce v programu projde jednotkovými testy, můžete si být jisti kvalitou celého programu. V imperativních programech kontrola návratové hodnoty funkce nestačí: funkce může upravit externí stav, což je také potřeba zkontrolovat, což není nutné provádět ve funkčních programech.

Možnosti optimalizace kompilace

Tradičně zmiňovanou pozitivní vlastností funkcionálního programování je, že umožňuje popsat program 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í rozsáhlé možnosti pro automatickou paralelizaci výpočtů. Vzhledem k tomu, že je zaručena absence vedlejších efektů, je při libovolném volání funkce vždy možné paralelně vyhodnocovat dva různé parametry – pořadí, v jakém se vyhodnocují, nemůže ovlivnit výsledek volání.

Nedostatky

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 nutnosti neustálého přidělování a automatického uvolňování paměti, proto se v systému provádění funkčního programu stává vysoce účinný garbage collector povinnou součástí. Volný výpočetní model má za následek nepředvídatelné 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ě (jako je getchar ze standardní knihovny jazyka) nejsou čisté, protože jsou schopny vracet různé hodnoty pro stejné argumenty a k odstranění jsou vyžadovány některé triky.

K překonání nedostatků funkcionálních programů již první funkcionální programovací jazyky obsahovaly nejen čistě funkční nástroje, ale také imperativní programovací mechanismy (přiřazení, smyčka, „implicitní PROGN“ již v LISPu byly). Použití takových nástrojů může vyřešit některé praktické problémy, ale znamená to opustit myšlenky (a výhody) funkcionálního programování a psát imperativní programy ve funkcionálních jazycích. V čistě funkcionálních jazycích se tyto problémy řeší jinými prostředky, například v Haskellu se I/O implementuje pomocí monád, což je netriviální koncept vypůjčený z teorie kategorií.

viz také

Anamorfismus
Katamorfismus

Poznámky

A. Field, P. Harrison Funkční programování: Přel. z angličtiny - M.: Mir, 1993. - 637 s., ill. ISBN 5-03-001870-0. Strana 120 [Kapitola 6: Matematické základy: λ-kalkul].
Tiobe Programming Community Index
Pavel Hudák (Angličtina) ruština (září 1989). „Koncepce, vývoj a aplikace funkcionálních programovacích jazyků“ (PDF). 21 ACM Computing Surveys
(3): 359-411. DOI:10.1145/72551.72554. 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
+ reedice ISBN 978-5-382-01266-7; 2011 McCarthy, John (červen 1978). "Historie Lisp" . V konferenci ACM SIGPLAN Historie programovacích jazyků
: 217–223. DOI:10.1145/800025.808387.
, Ch. 3. λ-kalkul jako programovací jazyk Ve svých pamětech Herbert Simon (1991), Modely mého života (Angličtina) s.189-190 ISBN 0-465-04640-1 uvádí, že jeho, Al. Newell a Cliff Shaw, kteří jsou „často nazýváni rodiči umělé inteligence“ za napsání programu Logic Theorist ruština (Angličtina) automatickým důkazem věty z Principia Mathematica
ruština
. Aby toho dosáhli, museli přijít s jazykem a paradigmatem, které lze zpětně považovat za funkcionální programování.
Historie programovacích jazyků: IPL
XIV. APL Session // Historie programovacího jazyka / Richard L. Wexelbblat. - Academic Press, 1981. - s. 661-693. - 749 str.
Stáhnout PDF: „Techniky funkčního programování, V. A. Potapenko“ strana 8 „Funkce vyšších řádů“.
GCC, Deklarace atributů funkcí

XL Fortran pro AIX, V13.1 > Jazyková reference, čisté postupy (Fortran 95) Optimalizace ocasního volání Jazyky podobné funkčním používají méně striktní koncept. Funkce v matematice nemůže měnit prostředí, které ji volá, a pamatovat si výsledky své práce, ale poskytuje pouze výsledek výpočtu funkce. Programování pomocí matematického konceptu funkce způsobuje určité potíže, takže funkcionální jazyky v té či oné míře poskytují také imperativní schopnosti, což zhoršuje návrh programu (například možnost bezbolestných dalších změn). Dalším rozdílem od imperativních programovacích jazyků je deklarativní povaha popisů funkcí. Texty programů ve funkcionálních programovacích jazycích popsat sled akcí pro řešení. Prvním navrženým funkčním jazykem byl Lisp. Varianta tohoto jazyka je široce používána v systému počítačově podporovaného navrhování AutoLISP.

Za hlavní vlastnosti funkcionálních programovacích jazyků jsou obvykle považovány následující:

stručnost a jednoduchost;
silné psaní;
modularita;
funkce jsou objekty výpočtu;
odložené (líné) výpočty.

Některé funkcionální programovací jazyky

Miranda (jaká rodina?)

Odkazy

http://roman-dushkin.narod.ru/fp.html - Kurz přednášek o funkcionálním programování, pořádaný na MEPhI od roku 2001.

Nadace Wikimedia. 2010.

Podívejte se, co je „Funkční programovací jazyk“ v jiných slovnících:

Programovací jazyk, který umožňuje specifikovat program jako sadu definic funkcí. Ve funkcionálních programovacích jazycích: funkce si mezi sebou vyměňují data bez použití mezilehlých proměnných a přiřazení;... ... Finanční slovník

funkční jazyk- Programovací jazyk, ve kterém jsou akce s daty vyjádřeny jako volání funkčních procedur. [GOST 19781 90] Předměty podpory. zpracovatelské systémy informace software EN funkční jazyk... Technická příručka překladatele

Ruby Semantics: multi-paradigm Typ provedení: interpret Rok vydání: 1995 Autor(ři): Yukihiro Matsumoto Nejnovější verze: 1.9.1 ... Wikipedia

Funkční jazyk- 37. Funkční jazyk Funkční jazyk Programovací jazyk, ve kterém jsou akce s daty vyjádřeny ve formě volání funkčních procedur Zdroj: GOST 19781 90: Softwarová podpora systémů zpracování informací. Podmínky a...... Slovník-příručka termínů normativní a technické dokumentace

Erlang Soubor:Erlang logo.png Sémantika: multiparadigma: kompetitivní, funkční programování Datum vydání: 1987 Autoři: Typování dat: přísné, dynamické Hlavní implementace: E ... Wikipedia

Schéma Sémantika: funkční Typ provedení: interpret nebo kompilátor Rok vydání: 1970 Autor(ři): Guy Steele a Gerald Sussman Typování dat ... Wikipedia

Tento termín má jiné významy, viz Miranda . Miranda je funkcionální programovací jazyk vytvořený v roce 1985 Davidem Turnerem jako standardní funkcionální jazyk. Má přísný systém polymorfního typu, ... ... Wikipedie

Hope je funkcionální programovací jazyk vyvinutý na počátku 80. let; je předchůdcem jazyků Miranda a Haskell. Časopis Byte, srpen 1985, poprvé publikoval průvodce jazykem Hope. Příklad výpočetního programu... ... Wikipedie

Tento termín má jiné významy, viz SASL. SASL je plně funkční programovací jazyk vyvinutý Davidem Turnerem na University of St Andrews v roce 1972, založený na aplikační podmnožině ISWIM. V roce 1976... ... Wikipedie

Tento termín má jiné významy, viz Scala. Scala Jazyková třída: Multi-paradigma: func... Wikipedie

knihy

Programování v Clojure. Praxe používání Lisp ve světě Java, Emerick Ch., Carper B., Grand K.. Proč si mnoho lidí vybírá Clojure? Jedná se o funkční programovací jazyk, který nejen umožňuje používat Java knihovny, služby a další prostředky JVM, ale také konkuruje...

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 vůči funkci, a také mají vedlejší účinky a mění 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 algoritmu, můžete získat různá výstupní data v důsledku vlivu stavu proměnných 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 pro programy ve funkčních jazycích ukládat do mezipaměti výsledky funkcí a volat je v pořadí, které není určeno algoritmem, a paralelizovat je bez jakékoli další akce ze strany programátora (což zajišťují funkce bez vedlejších účinků - čisté funkce).

Encyklopedický YouTube

1 / 5

Co je funkcionální programování

Matematika a konstanty / Úvod do programování Lekce 4 (JavaScript ES6)

Reaktivní programování a moderní webová rozhraní

Alexander Chirtsov o matematice ve fyzice

Anna Andreeva. Řešení olympijských úloh v matematice

titulky

Funkcionální programovací jazyky

Původní verze Lispu i APL, které dosud nebyly plně funkční, 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 vlastnosti a koncepty funkcionálního jazyka.

Zájem o funkcionální programovací jazyky, zejména ty čistě funkcionální, byl obvykle spíše vědecký než komerční. Nicméně pozoruhodné jazyky jako Erlang, OCaml, Haskell, Scheme (po roce 1986) a specifické (statistiky), Wolfram (symbolická matematika) a (finanční analýza) a XSLT (XML) našly využití v komerčním programovacím průmyslu. . Široce používané deklarativní jazyky jako SQL a Lex/Yacc obsahují některé prvky funkcionálního programování, například si dávají pozor, aby nepoužívaly 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.

Příběh

Prvním funkčním jazykem byl Lisp, vytvořený Johnem McCarthym během své práce na konci padesátých let a implementovaný původně pro IBM 700/7000. (Angličtina) automatickým důkazem věty z. Lisp poprvé představil mnoho konceptů funkcionálního jazyka, ačkoli jazyk nepoužívá pouze paradigma funkcionálního programování. Další vývoj Lisp zahrnoval jazyky jako Scheme a Dylan.

. Lisp zavedl mnoho konceptů funkcionálního jazyka, i když nevyznával pouze paradigma funkcionálního programování. Dalším vývojem Lisp se staly jazyky jako Scheme a Dylan.

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

Některé koncepty a paradigmata jsou specifické pro funkcionální programování a jsou do značné míry cizí imperativnímu 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ů.

Funkce vyššího řádu jsou funkce, které mohou vzít jiné funkce jako argumenty a vrátit je. Matematici často nazývají takovou funkci operátor, například derivační operátor nebo integrační operátor.

Funkce vyššího řádu vám umožňují používat currying – transformaci funkce z dvojice argumentů na funkci, která přebírá své argumenty jeden po druhém. Tato transformace získala své jméno na počest H. Curryho.

Funkce vyššího řádu vám umožňují používat currying – transformaci funkce z dvojice argumentů na funkci, která přebírá své argumenty jeden po druhém. Tato transformace byla pojmenována po H. Currym.

Čisté funkce jsou takové, které nemají vedlejší efekty I/O nebo 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:

Pokud není použit výsledek čisté funkce, lze její volání odstranit, aniž by došlo k poškození jiných výrazů.
Výsledek čistého volání funkce lze uložit do paměti, to znamená uložit do tabulky hodnot spolu s argumenty volání. Pokud je funkce později volána se stejnými argumenty, lze její výsledek převzít přímo z tabulky, aniž by byl vyhodnocen (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ů.
Pokud mezi dvěma čistými funkcemi neexistuje žádná datová závislost, lze pořadí jejich výpočtu změnit nebo paralelizovat (jinými slovy, výpočet čistých funkcí splňuje principy zabezpečení vláken)
Pokud celý jazyk neumožňuje vedlejší účinky, lze použít jakoukoli politiku hodnocení. To dává kompilátoru svobodu kombinovat a reorganizovat vyhodnocování výrazů v programu (například odstranění stromových struktur).

Rekurze

Přístup k hodnocení argumentů

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

Nestriktní přístup je zpravidla realizován formou redukce grafu. Nepřísné hodnocení je výchozí v několika čistě funkčních jazycích, včetně Miranda, Clean a Haskell. [ ]

FP v nefunkčních jazycích

Styly programování

# imperativní styl cíl = # vytvořte prázdný seznam pro položku v source_list: # pro každý prvek původního seznamu trans1 = G(položka) # použít funkci G(). trans2 = F(trans1) # použít funkci F() cílová. připojit (trans2) # přidat převedený prvek do seznamu

Funkční verze vypadá jinak:

#funkční styl # Jazyky FP mají často vestavěnou funkci 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 vývoje funkčního stylu v sestupném pořadí podle role dat v programech:

Refal (pro tuto kategorii, reprezentovanou jedním jazykem, neexistuje žádný obecně uznávaný název);
Aplikativní (Lisp, Tcl, Rebol);
Kombinatorické (APL / / , FP/FL);
Bez teček (čisté zřetězení) (Joy, Cat, Factor, podmnožina PostScriptu).

V prvním případě je celá struktura programu určena datovou strukturou, ve druhém se data jako taková ve zdrojovém kódu vůbec nevyskytují, 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 a beztečkovém stylu.

Zvláštnosti

Silné stránky

Zlepšení spolehlivosti kódu

Snadná organizace testování jednotek

Možnosti optimalizace kompilace

Souběžné schopnosti

Nedostatky

K překonání nedostatků funkcionálních programů již první funkcionální programovací jazyky obsahovaly nejen čistě funkční nástroje, ale také imperativní programovací mechanismy (přiřazení, smyčka, „implicitní PROGN“ byly již v Lisp). Použití takových nástrojů může vyřešit některé praktické problémy, ale znamená to opustit myšlenky (a výhody) funkcionálního programování a psát imperativní programy ve funkcionálních jazycích. V čistě funkcionálních jazycích se tyto problémy řeší jinými prostředky, například v Haskellu se I/O implementuje pomocí monád, což je netriviální koncept vypůjčený z teorie kategorií.

Funkce jsou abstrakce, ve kterém jsou detaily implementace nějaké akce skryty za samostatným názvem. Dobře napsaná sada funkcí umožňuje jejich mnohonásobné použití. Standardní knihovna Python přichází s množstvím předpřipravených a odladěných funkcí, z nichž mnohé jsou dostatečně univerzální, aby zvládly širokou škálu vstupů. I když určitá část kódu není použita vícekrát, ale z hlediska vstupních a výstupních dat je zcela autonomní, lze ji bezpečně oddělit do samostatné funkce.

Tato přednáška je více orientována na praktické úvahy spíše než na teorii funkcionálního programování. V případě potřeby však budou použity a vysvětleny příslušné termíny.

Dále se podrobně podíváme na popis a použití funkcí v Pythonu, rekurzi, předávání a vracení funkcí jako parametrů, sekvenční zpracování a iterátory a také na koncept generátoru. Bude ukázáno, že v Pythonu jsou funkce objekty (a proto mohou být předány jako parametry a vráceny jako výsledek provádění funkcí). Kromě toho si povíme, jak můžete implementovat některé mechanismy funkcionálního programování, které nemají přímou syntaktickou podporu v Pythonu, ale jsou rozšířené ve funkcionálních programovacích jazycích.

Co je funkcionální programování?

Funkcionální programování je programovací styl, který používá pouze složení funkcí. Jinými slovy, toto programování spíše ve výrazech než v rozkazovacích příkazech.

Jak zdůrazňuje David Mertz ve svém článku o funkcionálním programování v Pythonu, „funkční programování - programování ve funkcionálních jazycích (LISP, ML, OCAML, Haskell, ...), jejichž hlavní atributy jsou:

„Přítomnost prvotřídních funkcí“ (funkce, stejně jako jiné objekty, lze přenášet uvnitř funkcí).
Rekurze je hlavní řídicí struktura v programu.
Zpracování seznamů (sekvencí).
Zákaz vedlejších efektů ve funkcích, což znamená především absenci přiřazení (v „čistých“ funkčních jazycích)
Operátoři jsou zakázáni a důraz je kladen na výrazy. Místo operátorů je celý program ideálně jeden výraz s doprovodnými definicemi.
klíčová otázka: Co je třeba počítat, ne Jak.
Použití funkcí vyšších řádů (funkce nad funkcemi nad funkcemi).

Funkční program

V matematice funkce zobrazuje objekty ze stejné sady ( sady definic funkcí) jinému ( sada funkčních hodnot). Matematické funkce (tzv čistý) „mechanicky“, jednoznačně vypočítají výsledek z daných argumentů. Čisté funkce by mezi dvěma hovory neměly ukládat žádná data. Můžete si je představit jako černé skříňky, o kterých víte jen to, co dělají, ale vůbec ne jak.

Programy funkčního stylu jsou navrženy jako složení funkcí. V tomto případě jsou funkce chápány téměř stejně jako v matematice: mapují jeden objekt na druhý. V programování jsou „čisté“ funkce ideálem, který není v praxi vždy dosažitelný. Praktické užitečné funkce obvykle mají vedlejším účinkem: Uložení stavu mezi hovory nebo změna stavu jiných objektů. Je například nemožné si představit I/O funkce bez vedlejších účinků. Ve skutečnosti se takové funkce používají kvůli těmto „efektům“. Matematické funkce navíc snadno pracují s objekty, které vyžadují nekonečné množství informací (například reálná čísla). Obecně počítač

Funkcionální programování

1. Úvod

Programy v tradičních programovacích jazycích jako C, Pascal, Java atd. Skládají se z posloupnosti úprav hodnot určité sady proměnných, která se nazývá stav. Pokud neuvažujeme I/O operace a také nebereme v úvahu skutečnost, že program může běžet nepřetržitě (tj. bez zastavení, jako v případě serverových programů), můžeme provést následující abstrakci. Než se program začne vykonávat, má stav nějakou počáteční hodnotu σ0, která představuje vstupní hodnoty programu. Po ukončení programu má stav novou hodnotu σ0, která zahrnuje to, co lze považovat za „výsledek“ programu. Během provádění každý příkaz změní stav; proto stav prochází nějakou konečnou posloupností hodnot:

σ = σ0 → σ1 → σ2 → · · · → σn = σ0

Stav se upravuje pomocí přiřazovacích příkazů zapsaných jako v=E nebo v:=E, kde v je proměnná a E je nějaký výraz. Tyto příkazy následují jeden po druhém; Příkazy jako if a while umožňují změnit pořadí, ve kterém jsou tyto příkazy prováděny v závislosti na aktuální hodnotě stavu. Tento styl programování se nazývá imperativní nebo procedurální.

Funkční programování představuje paradigma, které se zásadně liší od výše uvedeného modelu. Funkční program je výraz (v matematickém smyslu); spustit program znamená vypočítat hodnotu tohoto výrazu.1 S přihlédnutím k výše uvedenému zápisu, uvážíme-li, že výsledek prac.

1 Použití termínu „výpočet“ neznamená, že program může pracovat pouze s čísly; Výsledkem výpočtu mohou být řetězce, seznamy a obecně libovolné datové struktury povolené v daném jazyce.

imperativní program je zcela a jednoznačně určen svým zadáním, můžeme říci, že konečný stav (nebo jakýkoli meziprodukt) je nějaká funkce (v matematickém smyslu) výchozího stavu, tzn. a0 = f(σ). Funkcionální programování používá tento úhel pohledu: program je výraz odpovídající funkci f. Funkcionální programovací jazyky podporují konstrukci takových výrazů a poskytují široký výběr odpovídajících jazykových konstrukcí.

Při porovnávání funkcionálního a imperativního přístupu k programování si můžete všimnout následujících vlastností funkcionálních programů:

Funkční programy nepoužívají proměnné v tom smyslu, že se toto slovo používá v imperativním programování. Funkční programy zejména nepoužívají operátor přiřazení.

V důsledku předchozího bodu neexistují žádné smyčky ve funkčních programech.

Provádění posloupnosti příkazů ve funkčním programu nemá smysl, protože jeden příkaz nemůže ovlivnit provádění dalšího.

Funkční programy využívají funkce mnohem složitějšími způsoby. Funkce mohou být předány jiným funkcím jako argumenty a vráceny jako výsledek, a dokonce obecně provádět výpočty, jejichž výsledkem je funkce.

Namísto smyček funkční programy široce využívají rekurzivní funkce.

Funkční přístup k programování se na první pohled může zdát zvláštní, neobvyklý a málo užitečný, ale je třeba vzít v úvahu následující úvahy.

Za prvé, imperativní styl v programování není pevně zakódovaná nutnost. Mnoho charakteristik imperativních programovacích jazyků vyplývá z abstrakce od detailů implementace počítače na nízké úrovni, od strojového kódu přes jazyky assembleru až po jazyky jako Fortran a tak dále. Není však důvod se domnívat, že takové jazyky odrážejí nejpřirozenější jazyk

způsob, jakým může člověk sdělit své záměry stroji. Možná správnější přístup je, že programovací jazyky se rodí jako abstraktní systémy pro psaní algoritmů a poté jsou přeloženy do imperativního počítačového jazyka.

Kromě toho má funkční přístup oproti imperativnímu řadu výhod. Za prvé, funkční programy přímo odpovídají matematickým objektům, a proto umožňují přesné uvažování. Nastavte hodnotu imperativního programu, tzn. funkce, kterou implementuje, může být poměrně obtížné vyhodnotit. Naproti tomu význam funkčního programu lze odvodit téměř přímo.

Zvažte například následující program Haskell:

faktoriál n = pokud n == 0, pak 1 jinak n * faktoriál (n - 1)

Téměř okamžitě vidíte, že tento program odpovídá následující dílčí funkci:

f(n) = n! n ≥ 0

(Zde symbol znamená, že funkce není definována, protože program nekončí pro záporné hodnoty argumentu.) U programu C však tato shoda není zřejmá:

int x = 1; zatímco (n > 0)

x = x * n; n = n - 1;

Je třeba si také povšimnout používání termínu „funkce“ v jazycích jako C, Java atd. V matematickém smyslu nejsou „funkce“ jazyka C funkcemi, protože:

Jejich význam může záviset na více než jen na argumentech;

Výsledek jejich realizace může být různývedlejší efekty(například změna hodnot globálních proměnných)

Dvě volání stejné funkce se stejnými argumenty mohou přinést různé výsledky.

Přitom funkce ve funkcionálních programech jsou skutečně funkcemi ve smyslu, v jakém se tomu rozumí v matematice. Výše uvedené připomínky se jich tedy nevztahují. Z toho vyplývá, že vyhodnocení jakéhokoli výrazu nemůže mít žádné vedlejší účinky, a proto pořadí, ve kterém jsou jeho podvýrazy vyhodnocovány, neovlivňuje výsledek. Funkční programy lze tedy snadno paralelizovat, protože jednotlivé složky výrazů lze vyhodnocovat současně.

2 Základy lambda kalkulu

Stejně jako je teorie Turingova stroje základem imperativních programovacích jazyků, lambda kalkul slouží jako základ a matematický „základ“, na kterém jsou založeny všechny funkcionální programovací jazyky.

Lambda počet byl vynalezen na počátku 30. let 20. století logikem A. Churchem, který doufal, že jej použije jako formalismus k ospravedlnění matematiky. Brzy byly objeveny problémy, které znemožňovaly jeho použití v této funkci (nyní existuje důvod se domnívat, že to není tak úplně pravda) a lambda kalkul zůstal jedním ze způsobů, jak formalizovat koncept algoritmu.

V současné době je lambda kalkul hlavní takovou formalizací používanou ve výzkumu souvisejícím s programovacími jazyky. To je pravděpodobně způsobeno následujícími faktory:

Toto je jediná formalizace, kterou, i když s určitými nepříjemnostmi, lze ve skutečnosti přímo použít k psaní programů.

Lambda kalkul poskytuje jednoduchý a přirozený model pro důležité koncepty, jako je rekurze a vnořená prostředí.

Většinu konstrukcí v tradičních programovacích jazycích lze víceméně přímo mapovat na konstrukci lambda kalkul.

Funkcionální jazyky jsou v podstatě vhodnou formou syntaktické notace pro konstrukty různých variant lambda kalkulu. Některé moderní jazyky (Haskell, Clean) mají

100% soulad jeho sémantiky se sémantikou implikovaných konstrukcí lambda kalkulu.

V matematice, když je potřeba mluvit o funkci, je zvykem tuto funkci pojmenovat a následně ji použít, jako například v následujícím výroku:

Nechť f: R → R je definováno následujícím výrazem:

	(x2 hřích (1/x2),

Potom f0 (x) není integrovatelné na intervalu .

Mnoho programovacích jazyků také umožňuje definovat funkce pouze tím, že jim přiřadíte nějaké názvy. Například v jazyce C musí mít funkce vždy jméno. Zdá se to přirozené, ale protože se funkce ve funkcionálním programování používají všude, může tento přístup vést k vážným problémům. Představte si, že musíme vždy pracovat s aritmetickými výrazy podobným stylem:

Nechť x = 2 a y = 4. Pak xx = y.

Lambda notace umožňuje definovat funkce se stejnou lehkostí jako jiné matematické objekty. Lambda výraz budeme nazývat konstrukci formuláře

kde E je nějaký výraz, případně pomocí proměnné x.

Příklad. λx.x2 je funkce, která umocňuje svůj argument na druhou.

Použití lambda notace nám umožňuje jasně oddělit případy, kdy výrazem ve tvaru f(x) rozumíme samotnou funkci f a její hodnotu v bodě x. Kromě toho vám lambda notace umožňuje formalizovat téměř všechny typy matematických notací. Pokud začnete s konstantami a proměnnými a sestavíte výrazy pouze pomocí výrazů lambda a aplikací funkcí na argumentech, můžete si představit velmi složité matematické výrazy.

Aplikaci funkce f na argument x budeme označovat jako f x, tedy na rozdíl od zvyku v matematice nebudeme používat závorky2. Z důvodů, které budou zřejmé později, budeme předpokládat, že aplikace funkce na argument je ponechána asociativní, tzn. f x y

2 Všimněte si, že v matematice se výrazy jako sin x píší bez závorek.

znamená (f(x))(y). Jako zkratku pro výrazy tvaru λx.λy.E použijeme zápis λx y.E (podobně pro větší počet argumentů). Budeme také předpokládat, že „rozsah“ výrazu lambda sahá co nejvíce doprava, tj. například λx.x y znamená λx.(x y), a nikoli (λx.x)y.

Na první pohled se zdá, že musíme zavést speciální zápis pro funkce několika argumentů. Existuje však operace curry 3, která vám umožňuje psát takové funkce v běžné notaci lambda. Cílem je použít výrazy ve tvaru λx y.x + y. Takový výraz lze považovat za funkci R → (R → R), tzn. pokud je aplikován na jeden argument, výsledkem je funkce, která pak přebírá další argument. Tím pádem:

(λx y.x + y) 1 2 = (λy.1 + y) 2 = 1 + 2.

Proměnné ve výrazech lambda mohou být volné nebo vázané. Ve výrazu tvaru x2 + x je proměnná x volná; jeho hodnota závisí na hodnotě proměnné x a obecně nemůže být

Pokud změníte zápis j, význam výrazu se nezmění.

Je třeba si uvědomit, že v jakémkoli podvýrazu může být proměnná volná (jako ve výrazu pod integrálem), ale v celém výrazu je vázána nějakým variabilní operace vazby, jako je operace sčítání. Zavolá se část výrazu, která je "uvnitř" operace vazby rozsah variabilní.

V lambda počtu jsou výrazy λx.E[x] a λy.E[y] považovány za ekvivalentní (toto se nazývá α-ekvivalence a proces konverze mezi takovými páry se nazývá α-transformace). Samozřejmě je nutné uložit podmínku, že y není volná proměnná v E[x].

3 z příjmení slavného logika Haskell Curry, po kterém je pojmenován programovací jazyk Haskell

3 Lambda kalkul jako formální systém

Lambda počet je založen na formálním zápisu lambda termínu, složeného z proměnných a nějaké pevné množiny konstant pomocí operace aplikace funkcí a lambda abstrakce. To znamená, že všechny výrazy lambda lze rozdělit do čtyř kategorií:

1. Proměnné: jsou označeny libovolnými řetězci složenými z písmen a číslic.

2. Konstanty: označují se také řetězce; určíme rozdíl od proměnných z kontextu.

3. Kombinace: , tzn. aplikace funkce S na argument T; a S a T mohou být libovolné členy lambda. Kombinace je napsána jako S T.

4. Abstrakce libovolného lambda členu S vzhledem k proměnné x, označované jako λx.S.

Termín lambda je tedy definován rekurzivně a jeho gramatiku lze definovat jako následující Backus-Naurův tvar:

Exp = Var| Const| Exp Exp| λVar. Exp

Podle této gramatiky jsou termíny lambda reprezentovány spíše jako syntaktické stromy než jako sekvence znaků. Z toho vyplývá, že shody o asociativitě operace aplikace funkce, ekvivalenci výrazů tvaru λx y.S a λx.λy.S, nejednoznačnosti v názvech konstant a proměnných pramení pouze z potřeby reprezentovat členy lambda v a forma vhodná pro lidi a nejsou součástí formálního systému.

3.1 Volné a vázané proměnné

V V této části formalizujeme dříve danou intuitivní myšlenku volných a vázaných proměnných. Spousta volných

proměnné F V (S) lambda člen S lze rekurzivně definovat takto:

Podobně je množina souvisejících proměnných BV (S) definována pomocí následujících vzorců:

BV(x) =

BV(c) =

BV (ST) = BV (S) BV (T)

BV(λx.S) = BV(S)(x)

Zde se předpokládá, že c je nějaká konstanta.

Příklad. Pro člen S = (λx y.x) (λx.z x) lze ukázat, že F V (S) = (z) a

BV(S) = (x, y).

3.2 Náhrady

Intuitivně, aplikace termínu λx.S jako funkce na argument T vede k termínu S, ve kterém jsou všechny volné výskyty x nahrazeny T . Formalizace této intuice kupodivu není snadná.

Operaci dosazení členu S za proměnnou x v jiném členu T označíme jako T. Stejně jako v definici volných a vázaných proměnných lze pravidla substituce definovat také rekurzivně. Potíž je v tom, že musí být zavedena další omezení, aby se zabránilo konfliktním názvům proměnných.

3.3 Konverze

Lambda kalkul je založen na třech převodních operacích, které vám umožňují přejít z jednoho termínu na jiný, který je mu ekvivalentní. Podle ustálené tradice se tyto převody označují řeckými písmeny α, β a η. Jsou definovány takto:

α-konverze: λx.S −→ λy.S za předpokladu, že y / F V (S).

Například λu.u v −→ λw.w u.

β-konverze: (λx.S) T −→ S.

β-konverze je pro nás nejdůležitější, protože odpovídá výpočtu hodnoty funkce argumentu. α-konverze je pomocný mechanismus pro změnu názvů vázaných proměnných a η-konverze je zajímavá hlavně při zvažování lambda kalkulu spíše z logického než z programovacího hlediska.

3.4 Rovnost termínů lambda

Pomocí zavedených převodních pravidel můžeme formálně definovat pojem rovnosti lambda termínů. Dva členy jsou si rovny, pokud jeden může přejít od jednoho z nich k druhému pomocí konečné sekvence převodů. Definujme pojem rovnosti následujícími výrazy, ve kterých je třeba vodorovné čáry chápat jako „pokud je splněno tvrzení nad čarou, platí i tvrzení

pod tím":

Pojem rovnost, definovaný těmito formulemi, je nutné odlišit od pojmu syntaktické ekvivalence, který budeme označovat speciálním symbolem ≡. Například λx.x 6≡λy.y, ale λx.x = λy.y. Často je možné uvažovat o syntaktické ekvivalenci termínů až po α-konverze. Takovou ekvivalenci budeme označovat symbolem ≡α. Tento vztah je definován stejným způsobem jako rovnost členů lambda, s tou výjimkou, že ze všech konverzí jsou povoleny pouze α-konverze. Tedy λx.x ≡α λy.y.

3.5 Extenzionalita

η-konverze v lambda kalkulu vyjadřuje princip extenzionality. V obecném filozofickém smyslu se říká, že dvě vlastnosti jsou extenzivně ekvivalentní, pokud patří přesně stejným objektům. V matematice se např. přejímá extenzivní pohled na množiny, tzn. dvě sady jsou považovány za stejné, pokud obsahují stejné prvky. Podobně říkáme, že dvě funkce jsou si rovny, pokud mají stejnou doménu, a pro všechny hodnoty argumentu v této doméně počítají stejný výsledek.

Oblíbené v kategorii: