Den funktionelle programmering er en programmeringsparadigmetype af deklarativ, der betragter beregningen som en evaluering af matematiske funktioner.
Da tilstandsændringen og mutationen af data ikke kan repræsenteres ved funktionsevalueringer, accepterer funktionel programmering dem ikke, tværtimod understreger den anvendelsen af funktioner i modsætning til den bydende programmeringsmodel , der understreger, før tilstanden ændres.
Et funktionelt sprog er derfor et programmeringssprog, hvis syntaks og egenskaber tilskynder funktionel programmering. Mens oprindelsen af funktionel programmering kan findes i lambda-calculus , er det ældste funktionelle sprog Lisp , oprettet i 1958 af McCarthy . Lisp fødte varianter som Scheme ( 1975 ) og Common Lisp ( 1984 ), der ligesom Lisp ikke eller kun er let skrevet . Senere funktionelle sprog som ML ( 1973 ), Haskell ( 1987 ), OCaml , Erlang , Clean and Oz , CDuce , Scala ( 2003 ), F # eller PureScript ( 2013 ), Agda (en) er stærkt skrevet.
Funktionel programmering frigøres radikalt fra bivirkninger (eller bivirkninger) ved at forbyde enhver tildelingshandling.
Det funktionelle paradigme bruger ikke en statsmaskine til at beskrive et program, men en sammenlåsning af funktioner, der fungerer som "sorte bokse", der kan indlejres i hinanden. Hver kasse har flere parametre i input, men kun en output, den kan kun output en mulig værdi for hver tuple af værdier præsenteret i input. Funktionerne introducerer således ikke bivirkninger. Et program er derfor en applikation i matematisk forstand, som kun giver et resultat for hvert sæt inputværdier. Denne måde at tænke på, meget forskellig fra tilgangen til imperativ programmering, er en af hovedårsagerne til den vanskelighed, som programmører, der er uddannet i tvingende sprog, har med at nærme sig funktionel programmering. Imidlertid udgør det generelt ikke særlige vanskeligheder for begyndere, der aldrig har været udsat for tvingende sprog. En vigtig fordel ved funktioner uden bivirkninger er den lethed, at vi har til at teste dem individuelt. Desuden forenkler den udbredte anvendelse af automatisk hukommelsesstyring ved hjælp af en affaldssamler programmørens opgave.
I praksis af effektivitetsårsager, og fordi nogle algoritmer let udtrykkes med en tilstandsmaskine, tillader nogle funktionelle sprog bydende programmering ved at tillade at specificere, at visse variabler kan tildeles (eller ændres i henhold til det sædvanlige navn), og derfor muligheden af lokalt introducerende kanteffekter . Disse sprog er grupperet under navnet urene funktionelle sprog .
Såkaldte rent funktionelle sprog tillader ikke tvingende programmering. Faktisk er de blottet for bivirkninger og beskyttet mod problemer med samtidig håndhævelse . Vi kan for eksempel se, hvad der er gjort inden for rammerne af Erlang- sproget .
Implementeringen af funktionelle sprog gør sofistikeret brug af stakken, fordi de for at overvinde behovet for at gemme midlertidige data i arrays er stærkt afhængige af rekursion (inklusive opkaldet til en funktion i sin egen definition). Én teknisk multipel for at lave kompilering af den mest effektive rekursion er en teknik kaldet tail recursion (på engelsk : tail-recursion ), som består i at akkumulere de midlertidige resultater i en hukommelsescelle i stakken og passere som en parameter i det rekursive opkald . Dette gør det muligt at undgå at stable rekursive opkald i stakken ved at erstatte dem med en simpel rækkefølge efter spring. Koden genereret af compileren svarer derefter til den, der genereres af en tvingende sløjfe. Nogle sprog som Scheme , OCaml og Anubis optimerer automatisk rekursive opkald på denne måde.
Ufravigelige programmering er baseret på modellen af statens maskiner (se også Turing maskine og Von Neumann arkitektur ), med en central hukommelse og instruktioner, som ændrer sin tilstand gennem successive udsendelser. Et sådant program er repræsenteret af en tilstandsmaskine (se tællemaskine ), der repræsenterer de successive tilstande i hukommelsen. Dette kræver, at programmøren til enhver tid har en nøjagtig model af tilstanden for den hukommelse, som programmet ændrer.
For at reducere kompleksiteten af denne opgave reducerer mange teknikker antallet af variabler, der skal styres på samme tid, de fleste af dem falder ind under struktureret programmering og datakapsling :
Disse variabler er derefter beregnet til at blive omlokaliseret af compileren eller tolken, umiddelbart ved afslutningen af proceduren eller via en affaldssamler .
Det sker dog, at det design , som programmereren vælger, får ham til at ændre "delte" variabler eller hukommelsesområder, som ikke er strukturelt relevante for proceduren, i visse procedurer, frivilligt eller ej. Det viser sig, at disse ”perifere” modifikationer, der er betegnet under den generiske betegnelse for bivirkninger (eller bivirkninger ), i tvingende programmering er de facto mere reglen end undtagelsen og komplicerer i høj grad forståelsen af programmerne, derfor er de kilden til mange vanskeligheder og bugs : Hvis vi glemmer at opdatere visse delte data, eller tværtimod, ændrer vi dem uden at måle alle data. , hvis den kronologiske rækkefølge af tildelinger fra de forskellige softwarekomponenter er utilstrækkelig, eller hvis et hukommelsesområde er fordelt på det forkerte tidspunkt, ender programmet i en uforudset, inkonsekvent eller endda ustabil tilstand, og programmøren er ofte ude af stand til at opdage oprindelsen af fejlen, og hvis den lykkes, koster den tung programinstrumentering .
En anden egenskab ved funktionelle sprog er referentiel gennemsigtighed . Dette udtryk dækker det enkle princip, at resultatet af programmet ikke ændres, hvis du erstatter et udtryk med et udtryk af samme værdi . Dette princip er krænket i tilfælde af bivirkningsprocedurer, da en sådan procedure, ikke kun afhængig af dens inputargumenter, ikke nødvendigvis opfører sig identisk i to givne øjeblikke af programmet.
Lad os tage et eksempel. I C , hvis n betegner en global variabel, der indeholder et heltal, der skal inkrementeres (derfor en hukommelsescelle, der er synlig for hele programmet), og hvis inc (k) er en funktion, der øger værdien af n med størrelsen k :
int n = 2; int inc(int k) { /* incrémentation par effet de bord */ n = n + k; return n; } f(inc(1) + inc(1));I dette eksempel returnerer funktionen inc (i) ikke den samme værdi under de to opkald: et af argumenterne for funktionen f vil være 2 + 1 = 3 og det andet 3 + 1 = 4 værd . Det er derfor umuligt at erstatte inc (i) + inc (i) med 2 * inc (i), fordi værdien af inc (i) er forskellig for hvert opkald. Denne adfærd er grundlæggende forskellig fra en matematisk funktion. På en stor programskala betyder det, at udskiftning af en funktion med en anden kan kræve ændringer andetsteds i programmet, og det kan være nødvendigt at teste hele systemet igen., Fordi der ikke er nogen garanti for, at en sådan udskiftning ikke har ændret dets samlede opførsel. Efterhånden som systemets kompleksitet øges, øges omkostningerne ved en ændring. Omvendt sikrer den referencegennemsigtige egenskab, at udskiftning af en funktion med en anden ækvivalent ikke risikerer at ændre programmets samlede opførsel. Med andre ord er de matematisk lige. Denne egenskab letter softwarevedligeholdelse. Det gør det også muligt automatisk at anvende dokumentation for drift. Endelig har det en anden fordel ved væsentligt at reducere betydningen af ordren til udførelse, hvilket sikres ved rækkefølgen af opkaldsfunktioner en konsekvens er, at paralleliseringen af et funktionelt program kan udføres automatisk, og at de optimeringer, som kompilatorer kan udføre, er lettere at implementere.
Funktionelle sprog anvender datatyper og strukturer på højt niveau som f.eks. Udvidelige lister. Det er således generelt muligt let at udføre operationer såsom sammenkædning af lister eller anvendelse af en funktion til en liste - listen søges rekursivt - i en enkelt kodelinje.
En kraftfuld mekanisme for funktionelle sprog er brugen af højere ordensfunktioner . En funktion siges at være af højere orden, når den kan tage funktioner som argumenter (også kaldet callbacks ) eller returnere en funktion som et resultat. Vi siger også, at funktioner er førsteklasses objekter, hvilket betyder, at de kan håndteres lige så let som grundlæggende typer. Programmerne eller funktionerne, der manipulerer funktioner, svarer i matematik til funktionaliteter . To enkle eksempler er aflednings- og integrationsoperationer. Funktioner af højere orden blev undersøgt af Alonzo Church og Stephen Kleene i 1930'erne , startende fra formalismen af lambda-calculus , som påvirkede designet af flere funktionelle sprog, især Haskells . Den teori om lukkede kartesiske kategorier er en anden tilgang til at karakterisere funktioner, ved hjælp af begrebet universelt problem . Anubis- sproget er baseret på denne teori.
I begyndelsen af 2000'erne begyndte funktionel programmering at dukke op fra den akademiske verden. I det industrielle miljø anvendes Erlang- sprogene (udviklet af Ericsson til konkurrencedygtige programmeringsbehov og robusthedsimperativer), Common Lisp , OCaml og Scheme . Men udviklingen af funktionelle sprog er begrænset af manglen på kommercielle kvalitetsværktøjer og biblioteker og frem for alt af manglen på uddannede programmører. Bemærk også F # -sprog udviklet af Microsoft Research er tilgængeligt under gratis softwarelicens i 2010.
Selvom diagrammerne for (i) konkurrencen ICFP viser det modsatte, lider de funktionelle sprog i første kvartal af XXI E århundrede af et ry for langsomhed i dag fuldstændig uberettiget : visse compilers- ordning , som kompilatorerne Stalin eller Bigloo, kompilatorerne til Common Lisp , sprog i slægten af ML , såsom OCaml , Haskell eller CDuce, producerer eksekverbare filer, hvis gennemsnitlige ydeevne er sammenlignelig med hensyn til udførelsestid og plads til dem, der produceres af C eller C ++ kompilatorer . En kode uden bivirkninger, der er meget mere robust og lettere at vedligeholde, vi foretrækker den frem for et program, hvis hukommelsesstyring og forudsigelse af adfærd vil være vanskelige at mestre, selvom det betyder at miste lidt i effektivitet. Derudover skal det også bemærkes Chris Okasakis arbejde med rent funktionelle datastrukturer, der konkurrerer med ændrede strukturer i effektivitet og langt overstiger dem, når det kommer til robusthed.
Uden for universiteter og specifikke industrisektorer kan XSLT være et middel til at popularisere det funktionelle paradigme. Dedikeret til XML- behandling tillader det en programmør at beholde sine tvingende sprog eller objektsprog , mens han opdager en anden programmeringslogik.
Ligeledes Scala og OCaml sprog, som er beregnet til at være funktionelle sprog, tillader programmøren, der har behov for det for at forblive i en bydende nødvendigt programmering logik.