Funktionell programmering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 februari 2022; kontroller kräver 2 redigeringar .

Funktionell programmering  är ett programmeringsparadigm där beräkningsprocessen tolkas som beräkningen av värdena för funktioner i den matematiska förståelsen av de senare (i motsats till funktioner som subrutiner i procedurprogrammering ).

I kontrast till paradigmet imperativ programmering , som beskriver beräkningsprocessen som en successiv förändring av tillstånd (i en mening som liknar automatteorin ). Vid behov, i funktionell programmering, representeras hela uppsättningen av sekventiella tillstånd av beräkningsprocessen explicit, till exempel som en lista .

Funktionell programmering handlar om att beräkna resultaten av funktioner från indata och resultaten av andra funktioner, och innebär inte explicit lagring av programmets tillstånd. Följaktligen innebär det inte heller förändringar i detta tillstånd (till skillnad från imperativet , där ett av de grundläggande koncepten är en variabel som lagrar dess värde och låter dig ändra det när algoritmen exekveras ).

I praktiken är skillnaden mellan en matematisk funktion och begreppet "funktion" i imperativ programmering att imperativa funktioner kan förlita sig inte bara på argument, utan också på tillståndet hos variabler utanför funktionen, samt ha bieffekter och förändringar. externa variablers tillstånd. Således, i imperativ programmering, när du anropar samma funktion med samma parametrar, men i olika stadier av algoritmexekveringen, kan du få olika utdata på grund av påverkan av variabeltillståndet på funktionen. Och i ett funktionellt språk, när vi anropar en funktion med samma argument, får vi alltid samma resultat: utdata beror bara på input. Detta gör det möjligt för funktionella språkkörtider att cacha resultaten av funktioner och anropa dem i en ordning som inte definieras av algoritmen, och parallellisera dem utan något extra arbete från programmerarens sida (som ger funktioner utan biverkningar - rena funktioner ) .

Lambdakalkylen är grunden för funktionell programmering, många funktionella språk kan betraktas som ett "tillägg" över den [1] .

Funktionella programmeringsspråk

De mest kända funktionella programmeringsspråken är :

Ännu inte fullt fungerande initiala versioner av både Lisp och APL gav ett särskilt bidrag till skapandet och utvecklingen av funktionell programmering. Senare versioner av Lisp, som Scheme , såväl som olika varianter av APL, stödde alla funktioner och koncept för ett funktionellt språk [3] .

Som regel har intresset för funktionella programmeringsspråk, särskilt rent funktionella, varit mer vetenskapligt än kommersiellt. Men anmärkningsvärda språk som Erlang , OCaml , Haskell , Scheme (efter 1986) såväl som det specifika R (statistik), Wolfram (symbolisk matematik), J och K (finansiell analys) och XSLT ( XML ) fann deras väg in i den kommersiella programmeringsindustrin. . Utbredda deklarativa språk som SQL och Lex / Yacc innehåller vissa delar av funktionell programmering, till exempel, använder inte variabler. Kalkylarksspråk kan också anses fungera, eftersom kalkylbladsceller innehåller en rad funktioner som vanligtvis bara beror på andra celler, och om du vill modellera variabler måste du tillgripa funktionerna hos ett imperativt makrospråk.

Historik

Lambdakalkylen har blivit den teoretiska grunden för att beskriva och beräkna funktioner. Eftersom det är en matematisk abstraktion , inte ett programmeringsspråk , har det legat till grund för nästan alla funktionella programmeringsspråk idag. Ett liknande teoretiskt koncept, kombinatorisk logik , är mer abstrakt än λ-kalkylen och skapades tidigare. Denna logik används i vissa esoteriska språk som Unlambda . Både λ-kalkylen och den kombinatoriska logiken utvecklades för att tydligare och mer exakt beskriva matematikens principer och grunder [4] .

Det första funktionella språket var Lisp , skapat av John McCarthy vid MIT i slutet av femtiotalet och implementerat initialt för IBM 700/7000 [5] . Lisp var den första som introducerade många funktionella språkbegrepp, även om språket använder mer än bara det funktionella programmeringsparadigmet [6] . Lisp utvecklades vidare av språk som Scheme och Dylan .

Informationsbehandlingsspråket [ , IPL definieras ibland som det allra första maskinfunktionella språket [7] . Det är ett assemblerspråk för att arbeta med en lista med symboler. Det hade konceptet med en "generator" som använde en funktion som ett argument, och eftersom det är ett språk på assemblynivå kan det också placeras som ett språk som har funktioner av högre ordning. Men i allmänhet betonar IPL användningen av imperativa begrepp [8] .

Kenneth Iverson utvecklade APL-språket i början av sextiotalet och dokumenterade det i sin bok A Programming Language ( ISBN 978-0-471-43014-8 ) [9] . APL hade ett betydande inflytande på språket FP skapat av John Backus . I början av 1990-talet skapade Iverson och Roger Hui APL:s efterträdare , programmeringsspråket I mitten av nittiotalet skapade Arthur Whitney , som tidigare hade arbetat med Iverson, språket K , som senare användes kommersiellt i finansbranschen.

Robin Milner skapade ML- språket vid University of Edinburgh på 1970 -talet , och David Turner startade SASL vid University of St. Andrews och senare Miranda vid University of Kent. I slutändan skapades flera språk baserade på ML, bland vilka de mest kända är Objective Caml och Standard ML . Även på sjuttiotalet utvecklades ett programmeringsspråk baserat på principen om Scheme (implementering av inte bara ett funktionellt paradigm), vilket beskrevs i det berömda verket "Lambda Papers", såväl som i boken om det åttiofemte året " Struktur och tolkning av datorprogram ".

1972 skapade Per Martin-Löf intuitionistisk typteori (även kallad konstruktiv). I denna teori fick funktionell programmering ett konstruktivt bevis på vad som tidigare kallades beroende typ. Detta gav en kraftfull impuls till utvecklingen av interaktiva satsbevisande och till det efterföljande skapandet av många funktionella språk.

Haskell skapades i slutet av 1980-talet i ett försök att kombinera många av idéerna från forskning om funktionell programmering [3] .

Begrepp

Vissa begrepp och paradigm är specifika för funktionell programmering och mestadels främmande för imperativ programmering (inklusive objektorienterad programmering ). Men programmeringsspråk är vanligtvis en hybrid av flera programmeringsparadigm, så "oftast imperativa" programmeringsspråk kan använda vilket som helst av dessa begrepp [10] .

Funktioner av högre ordning

Funktioner av högre ordning är funktioner som kan ta som argument och returnera andra funktioner. [11] . Matematiker kallar ofta en sådan funktion för en operator , till exempel derivatoperatorn eller integrationsoperatorn.

Funktioner av högre ordning tillåter användningen av currying  - omvandlingen av en funktion från ett par argument till en funktion som tar sina argument ett i taget. Denna förvandling är uppkallad efter Haskell Curry .

Rena funktioner

Rena funktioner är de som inte har I/O- och minnesbiverkningar ( de beror bara på deras parametrar och returnerar endast resultatet). Rena funktioner har flera användbara egenskaper, varav många kan användas för att optimera din kod:

Tack vare memoisering, om funktionen senare anropas med samma argument, kan dess resultat tas direkt från värdetabellen utan att beräknas (kallas ibland referenstransparensprincipen). Memoisering, till priset av en liten minnesförbrukning, kan avsevärt öka prestandan och minska tillväxtordningen för vissa rekursiva algoritmer.

Medan de flesta kompilatorer av imperativa programmeringsspråk känner igen rena funktioner och tar bort vanliga underuttryck för rena funktionsanrop, kan de inte alltid göra det för förkompilerade bibliotek, som i allmänhet inte tillhandahåller denna information. Vissa kompilatorer, som gcc , förser programmeraren med rena funktionsnyckelord för optimeringsändamål [12] . Fortran 95 låter dig beteckna funktioner som "rena" (rena) [13] .

Rekursion

I funktionella språk är en loop vanligtvis implementerad som en rekursion. Strängt taget finns det inget sådant som en loop i det funktionella programmeringsparadigmet. Rekursiva funktioner kallar sig själva, vilket gör att operationen kan utföras om och om igen. En stor stack kan krävas för att använda rekursion , men detta kan undvikas med svansrekursion . Svansrekursion kan kännas igen och optimeras av kompilatorn till kod som är resultatet av kompilering av en liknande iteration i ett imperativt programmeringsspråk. [14] Scheme-språkstandarderna kräver att svansrekursion identifieras och optimeras. Svansrekursion kan optimeras genom att konvertera programmet till stilen att använda fortsättningar när du kompilerar det, som ett av sätten. [femton]

Rekursiva funktioner kan generaliseras till funktioner av högre ordning, genom att till exempel använda katamorfism och anamorfism (eller "faltning" och "expansion") [16] . Funktioner av detta slag spelar rollen som ett sådant koncept som en cykel i imperativa programmeringsspråk [17] .

Argumentutvärderingsmetod

Funktionella språk kan klassificeras efter hur funktionsargument hanteras under utvärdering. Tekniskt sett ligger skillnaden i uttryckets denotationssemantik . Till exempel, med en strikt metod för att utvärdera ett uttryck:

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

utgången kommer att vara ett fel, eftersom det tredje elementet i listan innehåller division med noll. Med ett icke-strikt tillvägagångssätt kommer uttryckets värde att vara 4, eftersom strängt taget värdena på dess element inte är viktiga för att beräkna längden på listan och kanske inte beräknas alls. Med strikt (tillämplig) utvärderingsordning, är värdena för alla argument förberäknade innan själva funktionen utvärderas. Med ett icke-strikt tillvägagångssätt (normal utvärderingsordning) utvärderas inte argumentens värden förrän deras värde behövs när funktionen utvärderas [18] .

Som regel implementeras ett icke-strikt tillvägagångssätt i form av grafreduktion. Icke-strikt utvärdering är standard i flera rent funktionella språk, inklusive Miranda och Haskell [19] .

På icke-funktionella språk

I princip finns det inga hinder för att skriva program i funktionell stil på språk som inte traditionellt anses fungera, precis som objektorienterade stilprogram kan skrivas på strukturella språk. Vissa imperativa språk stöder konstruktioner som är typiska för funktionella språk, såsom funktioner av högre ordning och listförståelse, vilket gör det lättare att använda den funktionella stilen i dessa språk, i synnerhet är detta tillvägagångssätt flitigt använt i utövandet av Python-språket . Ett annat exempel är Ruby -språket , som har förmågan att skapa både anonyma funktioner med hjälp av bundna variabler (λ-objekt) och möjligheten att organisera anonyma funktioner av högre ordning genom ett block med hjälp av yield. I C kan funktionspekare som argumenttyper användas för att skapa funktioner av högre ordning. Funktioner av högre ordning och uppskjuten liststruktur implementeras i C++-biblioteken . I Java 8 och senare, och C# 3.0 och senare, kan du använda λ-funktioner för att skriva ett program i en funktionell stil.

Programmeringsstilar

Imperativa program tenderar att betona sekvenser av steg för att utföra vissa åtgärder, medan funktionella program tenderar att betona arrangemanget och sammansättningen av funktioner, ofta inte anger den exakta sekvensen av steg. Ett enkelt exempel på två lösningar på samma problem (med samma Python-språk ) illustrerar detta.

# imperativ stilmål = [] # skapa en tom lista för objekt i källlistan : # för varje element i källlistan trans1 = G ( objekt ) # tillämpa G() funktion trans2 = F ( trans1 ) # tillämpa F() funktionsmål . append ( trans2 ) # lägg till det konverterade elementet i listan

Den funktionella versionen ser annorlunda ut:

# funktionell stil # FP-språk har ofta compose() inbyggd i compose2 = lambda A , B : lambda x : A ( B ( x )) target = map ( compose2 ( F , G ), source_list )

Till skillnad från imperativstilen, som beskriver stegen som leder till uppnåendet av ett mål, beskriver den funktionella stilen det matematiska förhållandet mellan data och målet.

Mer exakt finns det fyra steg i utvecklingen av funktionell stil, i fallande ordning efter datas roll i program:

I det första fallet bestäms hela strukturen av programmet av datastrukturen, i det senare fallet finns inte data som sådan i källkoden alls, de antyds endast vid ingången. Vissa språk stöder ett antal stilar: till exempel låter Haskell dig skriva i både applikativa, kombinatoriska och prickfria stilar.

Funktioner

Huvuddragen i funktionell programmering, som avgör både fördelarna och nackdelarna med detta paradigm, är att det implementerar en tillståndslös datormodell. Om ett imperativt program i något skede av exekveringen har ett tillstånd, det vill säga en uppsättning värden av alla variabler, och ger biverkningar, så har ett rent funktionellt program inget tillstånd vare sig i sin helhet eller delar och producerar inte biverkningar effekter. Det som görs i imperativa språk genom att tilldela värden till variabler uppnås i funktionella språk genom att skicka uttryck till funktionsparametrar. Den omedelbara konsekvensen är att ett rent funktionellt program inte kan ändra de data det redan har, utan bara kan generera nya genom att kopiera eller utöka gamla. Konsekvensen av detsamma är förkastandet av cykler till förmån för rekursion.

Styrkor

Förbättra kodtillförlitlighet

Den attraktiva sidan av tillståndslös datoranvändning är den ökade tillförlitligheten hos koden på grund av tydlig strukturering och frånvaron av behovet av att spåra biverkningar. Alla funktioner fungerar bara med lokal data och fungerar alltid med dem på samma sätt, oavsett var, hur och under vilka omständigheter den kallas. Omöjligheten av datamutation när du använder dem på olika platser i programmet eliminerar uppkomsten av svårupptäckta fel (som till exempel att av misstag tilldela ett felaktigt värde till en global variabel i ett imperativt program).

Enkelt att organisera enhetstestning

Eftersom en funktion i funktionell programmering inte kan ge bieffekter, kan objekt inte ändras både inom scopet och utanför (till skillnad från i imperativa program, där en funktion kan ställa in någon extern variabel som läses av den andra funktionen). Den enda effekten av att utvärdera en funktion är resultatet den returnerar, och den enda faktorn som påverkar resultatet är värdet på argumenten.

Således är det möjligt att testa varje funktion i ett program genom att helt enkelt utvärdera den från olika uppsättningar av argumentvärden. I det här fallet behöver du inte oroa dig för att anropa funktioner i rätt ordning, eller om den korrekta bildningen av externt tillstånd. Om någon funktion i programmet klarar enhetstester kan du vara säker på kvaliteten på hela programmet. I imperativa program är det inte tillräckligt att kontrollera returvärdet för en funktion: funktionen kan modifiera det externa tillståndet, vilket också måste kontrolleras, vilket inte är nödvändigt i funktionsprogram [20] .

Kompilatoroptimeringsalternativ

Den traditionellt nämnda positiva egenskapen med funktionell programmering är att den låter dig beskriva programmet i den så kallade "deklarativa" formen, när en stel sekvens av att utföra många operationer som krävs för att beräkna resultatet inte är explicit specificerad, utan bildas automatiskt i processen att beräkna funktioner. Denna omständighet, såväl som frånvaron av stater, gör det möjligt att tillämpa ganska komplexa metoder för automatisk optimering på funktionella program.

Samtidighetsfunktioner

En annan fördel med funktionsprogram är att de ger de bredaste möjligheterna till automatisk parallellisering av beräkningar. Eftersom frånvaron av biverkningar är garanterad är det i alla funktionsanrop alltid tillåtet att utvärdera två olika parametrar parallellt - ordningen i vilken de utvärderas kan inte påverka resultatet av samtalet.

Lokal kod läsbarhet

När man analyserar koden för ett imperativt program är det viktigt att veta "var vi är nu." Utan förståelse för miljön är det svårt att göra ändringar i koden, så innan du gör ändringar måste du först förstå den allmänna kontexten för exekveringen, eller åtminstone inom den redigerade modulen. Inom funktionell programmering kan kod däremot läsas och redigeras lokalt, utan rädsla för att detta ska leda till några oväntade konsekvenser. Detta gör att deltagare med olika åtkomstnivåer kan arbeta tillsammans i programmet utan extra kostnader för att säkerställa kodmodularitet.

Nackdelar

Nackdelarna med funktionell programmering härrör från samma funktioner. Frånvaron av tilldelningar och deras ersättning med generering av nya data leder till behovet av konstant tilldelning och automatisk frigivning av minne, därför är det obligatoriskt i exekveringssystemet för ett funktionellt programsophämtare blir en komponent . Den icke-strikta beräkningsmodellen leder till en oförutsägbar ordning av funktionsanrop, vilket skapar problem i I/O, där ordningen på operationerna är viktig. Uppenbarligen är indatafunktioner i sin naturliga form (till exempel från standard Cgetchar() -biblioteket ) inte rena, eftersom de kan returnera olika värden för samma argument, och vissa knep krävs för att eliminera detta.

För att övervinna bristerna med funktionella program inkluderade även de första funktionella programmeringsspråken inte bara rent funktionella verktyg, utan också mekanismer för imperativ programmering (tilldelning, loop, "implicit PROGN" fanns redan i Lisp). Att använda sådana verktyg löser en del praktiska problem, men innebär att man går bort från idéerna (och fördelarna) med funktionell programmering och att skriva imperativa program på funktionella språk. I rena funktionella språk löses dessa problem på andra sätt, till exempel i Haskell implementeras I/O med hjälp av monader  , ett begrepp lånat från kategoriteorin.

Anteckningar

  1. ↑ A. Field, P. Harrison Funktionell programmering: Per. från engelska. - M .: Mir, 1993. - 637 s., ill. ISBN 5-03-001870-0 . Sida 120 [Kapitel 6: Matematiska grunder: λ-kalkyl].
  2. ↑ 1 2 Paul Hudak Utformning, utveckling och tillämpning av funktionella programmeringsspråk  (engelska)  // Association for Computing Machinery Computing Surveys: tidskrift. - 1989. - September ( vol. 21 , nr 3 ). - s. 359-411 . - doi : 10.1145/72551.72554 . Arkiverad från originalet den 5 juni 2013.
  3. ↑ Roger Penrose . Kapitel 2: Kyrkans Lambdakalkyl // Kungens nya sinne. Om datorer, tänkande och fysikens lagar = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. - Redaktionell URSS, 2003. - ISBN 5-354-00005-X . + återutgivning av ISBN 978-5-382-01266-7 ; 2011
  4. ↑ McCarthy, John History of Lisp  // In Association for Computing Machinery SIGPLAN History of Programming Languages ​​Conference. - 1978. - Juni. - S. 217-223 . - doi : 10.1145/800025.808387 . Arkiverad från originalet den 7 juni 2008.
  5. ↑ J. Harrison, 1997 , Ch. 3. λ-kalkyl som programmeringsspråk.
  6. ↑ I sin memoarbok Herbert Simon (1991), Models of My Life s.189-190 ISBN 0-465-04640-1 uppger att hans, Al. Newell och Cliff Shaw som "ofta kallas för artificiell intelligenss fäder" för att ha skrivit programmet Logic Theorist som automatiskt bevisar teorem från Principia Mathematica . För att uppnå detta var de tvungna att komma på ett språk och ett paradigm som i efterhand kan ses som funktionell programmering.
  7. ↑ Historia för programmeringsspråk: IPL (nedlänk) . Hämtad 15 april 2012. Arkiverad från originalet 1 november 2006. 
  8. ↑ XIV. APL-session // Programmeringsspråkets historia / Richard L. Wexelbblat. - Academic Press, 1981. - S.  661 -693. — 749 sid. — ISBN 0-12-745040-8 .
  9. ↑ Evgeny Kirpichev. Element av funktionella språk  // Övning av funktionell programmering. - 2009. - December ( nummer 3 ). — ISSN 2075-8456 . Arkiverad från originalet den 3 september 2017.
  10. ↑ Ladda ner PDF: "Tekniker för funktionell programmering, V. A. Potapenko" s. 8 "Funktioner av högre beställningar" . Datum för åtkomst: 10 januari 2009. Arkiverad från originalet den 30 juni 2009.
  11. ↑ GCC, Deklarera funktioners attribut . Hämtad 28 augusti 2012. Arkiverad från originalet 18 augusti 2012.
  12. ↑ XL Fortran för AIX, V13.1 > Språkreferens, rena procedurer (Fortran 95)
  13. ↑ Optimering av svansanrop . Datum för åtkomst: 31 juli 2012. Arkiverad från originalet den 1 augusti 2012.
  14. ↑ Reviderad5 rapport om det algoritmiska språkschemat, 3.5. Korrekt svansrekursion . Datum för åtkomst: 31 juli 2012. Arkiverad från originalet den 5 januari 2007.
  15. ↑ Meijer, Erik ; Fokkinga, Maarten; Paterson, Ross (1991). Funktionell programmering med bananer, linser, kuvert och taggtråd (PDF) . Konferens om funktionella programmeringsspråk och datorarkitektur (FPCA). Springer. pp. 124-144. CiteSeerX  10.1.1.41.125 . ISBN  3-540-54396-1 . Arkiverad (PDF) från originalet 2017-07-09 . Hämtad 2020-03-03 . Utfasad parameter används |deadlink=( hjälp )
  16. ↑ Fågel, Richard. Pärlor av funktionell  algoritmdesign . - Cambrigde : University Press , 2010. - 277 s. - ISBN 978-0-521-51338-8 . Arkiverad 8 mars 2022 på Wayback Machine
  17. ↑ N. A. Roganova Funktionell programmering: Lärobok för studenter vid högre utbildningsanstalter - M .: GINFO, 2002. - 260 sid. Sida 14 s. 3.1. Lat och ivrig datoranvändning
  18. ↑ Lata utvärdering - en översikt | ScienceDirect-ämnen . www.sciencedirect.com . Hämtad: 23 mars 2021.
  19. ↑ Ahmechet V. "Funktionell programmering för alla" . Tillträdesdatum: 11 januari 2009. Arkiverad från originalet den 2 februari 2009.

Litteratur

  • Gorodnyaya LV Grunderna i funktionell programmering. Föreläsningskurs - M .: Internet University of Information Technologies, 2004. S. 280. ISBN 5-9556-0008-6
  • Dushkin R. V. Funktionell programmering i Haskell. — M.: DMK Press, 2006. S. 608. ISBN 5-94074-335-8
  • Fält A., Harrison P. Funktionell programmering = Funktionell programmering. — M .: Mir, 1993. — 637 sid. — ISBN 5-03-001870-0 .
  • N. A. Roganova Funktionell programmering: Lärobok för studenter vid högre utbildningsanstalter - M .: GINFO, 2002. - 260 sid.
  • John Harrison. Funktionell programmering. Föreläsningskurs = Funktionell programmering . — 1997.
  • A. M. Mironov. Teorin om funktionella program.

Länkar

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk