Functioneel programmeren

In de informatica is functioneel programmeren een programmeerstijl en een programmeerparadigma. Hierbij wordt de informatieverwerking in de vorm van functies uitgedrukt, vergelijkbaar met wiskundige functies. Bij deze stijl dienen (liefst alle) wijzigingen van variabelen buiten de functie (de zogenaamde "neveneffecten") en het opslaan van programmatoestand en wijzigbare variabelen vermeden te worden. Variabelen voor onder meer een accumulator, teller, globale of controlevariabele zijn uit den boze.
Voorbeelden van meer of minder zuivere programmeertalen voor functioneel programmeren zijn APL, Erlang, F#, Haskell, Lisp, ML, Scala en Scheme, waarvan Haskell de puurste is.

Een hoger concept van berekening

Imperatief programmeren

Een computer voert een berekening uit volgens een vastgelegd patroon van stappen; iedere stap in dit patroon is een kleine, simpele deelberekening. Het beschouwen van een berekening als een serie kleine stappen is een mogelijk model voor het uitvoeren van een berekening.

Functioneel programmeren

Een ander model – dat zich richt op een hoger niveau van denken, begrijpen en berekenen – is het model van de lambdacalculus van Alonzo Church en Stephen Cole Kleene. In dit model vindt een berekening plaats door het toepassen van functies op argumenten: "als ik functie ${\mathfrak {f}}$ toepas op argument $a$ krijg ik als antwoord $b$ ". Hoe de toepassing van ${\mathfrak {f}}$ op $a$ precies tot $b$ leidt, doet er niet toe – het gaat erom dat $b$ het antwoord is. In puur functionele programmeertalen kunnen functies dan ook geen zogenaamde neveneffecten veroorzaken. Dit zijn effecten die invloed hebben op meer dan het resultaat van de functie, zoals het veranderen van een globale variabele. Het veranderen van zo'n variabele wordt een destructieve re-assignment genoemd.

Abstractie en applicatie

De twee belangrijkste mechanismen binnen de lambdacalculus om tot een berekening te komen zijn de abstractie en de applicatie.

Voor het programmeren komt abstractie neer op het definiëren van een functie: "bij iedere term A met de eigenschappen die bij A horen, hoort een antwoord B die op deze-en-deze manier afhangt van wat A precies is". Bijvoorbeeld de functie

{\mathfrak {f}}:\mathbb {R} \mapsto \mathbb {R}

{\mathfrak {f}}(x)=x^{2}-2x+3

Deze functie ${\mathfrak {f}}$ definieert een verbinding tussen twee waarden uit de verzameling $\mathbb {R}$ . Deze verbinding kan toegepast worden op ieder element van $\mathbb {R}$ en levert dan ook weer een ander, bijbehorend element van $\mathbb {R}$ op. Hoe dat gebeurt en wat een computer (of mens) ervoor moet doen om dat bijbehorende element te vinden doet er niet toe, het gaat erom dat de verbinding bestaat en toegepast kan worden.

Naast abstractie is er ook de applicatie. Voor programmeerdoeleinden komt dit neer op het toepassen van een functie op een argument. Bijvoorbeeld:

{\mathfrak {f}}(7)\mapsto 38

Toepassing van een functie op een specifiek argument dat voldoet aan de algemene beschrijving van argumenten voor die functie, levert een antwoord op. Hoe en waarom doet er weer niet toe, het gaat er alleen om dat het antwoord geproduceerd wordt.

Referentiële transparantie

Veel functies in functionele programmeertalen zijn referentieel transparant. Dit houdt in dat een expressie vervangen kan worden door zijn waarde zonder de werking van het programma te veranderen. Een voorbeeld hiervan zijn rekenkundige bewerkingen, zoals 1 + 1; dit kan vervangen worden door 2 zonder het programma te veranderen. Veel wiskundige functies zijn ook referentieel transparant, zoals sin(x) (deze levert voor een gegeven x altijd dezelfde waarde op).

Recursie

Een ander, belangrijk aspect van de lambdacalculus is dat functies gedefinieerd kunnen worden in termen van andere functies (tenminste, voor zover het voor het programmeren in functionele talen van belang is) – inclusief in termen van zichzelf. Dit betekent dat de lambdacalculus een enorme reikwijdte heeft wat betreft de definities die gegeven kunnen worden. Zover zelfs dat de lambdacalculus model staat voor het geheel van alle berekenbare problemen die er zijn. Functionele talen kunnen dus alles berekenen wat berekend kan worden.

Een voorbeeld van een definitie in termen van functies (specifiek, een recursieve definitie) is de volgende:

{\mathit {fact}}:\mathbb {N} \mapsto \mathbb {N}

{\mathit {fact}}(n)=\left\lbrace {\begin{array}{ccl}n=0&\rightarrow &1\\n>0&\rightarrow &n*{\mathit {fact}}(n-1)\end{array}}\right.

Hogere-ordefuncties

Een belangrijk kenmerk van een functionele taal is dat een functie ook een andere functie als argument kan meekrijgen. Dit worden hogere-ordefuncties genoemd. Zo bestaat in Haskell en andere functionele talen de functie map. De functie map past een andere functie F op alle elementen uit een lijst L. De argumenten van functie map zijn dus de functie F en de lijst L.

Functioneel model naar functionele taal

Een dergelijk hoog-niveau model van berekening is natuurlijk mooi en vooral eenvoudig, maar het is niet direct toe te passen op de hardware zoals die voorkomt in moderne computers. Functionele talen leunen dan ook sterk op geavanceerde en vooral complexe compilers en interpreters die de vertaalslag maken van functietoepassing naar het stap-voor-stapmodel van de processor.

Deze vertaalslag is veel groter dan bij de imperatieve talen, wat zijn weerslag heeft gevonden in de (vaak beperkte) snelheid waarmee veel functionele programma's uitgevoerd werden (zeker in de eerste generaties van ontwikkelomgevingen voor deze talen was dit een aanzienlijk probleem). Dit heeft zijn weerslag gehad in de populariteit van functionele talen buiten de onderzoeksomgevingen van universiteiten.

Tegenwoordig neemt de populariteit van functionele talen sterk toe. Zij zijn namelijk door de afwezigheid van neveneffecten veel beter dan imperatieve talen in staat om berekeningen geparallelliseerd uit te voeren. De berekening wordt dan uitgevoerd door meerdere processoren van één computer tegelijkertijd of zelfs door meerdere computers tegelijkertijd. Vanaf ongeveer 2005 zijn computers met meerdere processoren sterk in prijs gedaald en is de belangstelling voor functioneel programmeren toegenomen.

Onderscheid met andere soorten programmeertalen

Het grootst merkbare onderscheid is ongetwijfeld tussen de functionele programmeertalen en de imperatieve talen. Maken functionele talen gebruik van het hoog-niveau model van de lambdacalculus, de imperatieve talen zijn geheel geënt op het berekeningsmodel van de onderliggende processor: stap voor kleine stap, iedere stap letterlijk in het imperatieve programma opgenomen als een individuele opdracht. Is een functie in een functionele taal een programma op zich, in een imperatieve taal wordt iedere functie onderverdeeld in deze kleine, losse stappen. Ook een groot verschil is dat in de puur functionele talen geen sprake is van expliciete variabelendeclaratie of geheugenreservering. Dit zorgt voor transparante, compacte code. Het is mede daardoor ook makkelijk om over deze code te redeneren, en bijvoorbeeld correctheid te bewijzen. Sterker nog, omdat je precies weet wanneer er wat met een waarde gebeurt (iets wat in de imperatieve wereld zeer moeilijk bereikt kan worden door de mogelijkheid van neveneffecten), kan je automatisch uitzoeken wanneer bepaalde functies parallel kunnen worden uitgevoerd.

Daarnaast onderscheiden de functionele talen zich van de logische talen. In deze taalcategorie draait het niet om functies en functie-toepassingen maar om bewijsobjecten en predicatenlogica. De logische en functionele talen lijken echter veel op elkaar in het opzicht dat ze een hoog-niveau abstractie als model kiezen en staan daarin samen lijnrecht tegenover de imperatieve talen; om deze reden worden functionele en logische talen samen ook wel de declaratieve paradigma genoemd.

Ten slotte is er veel onenigheid over de positie van objectgeoriënteerde programmeertalen in dit geheel; deze talen verdelen een berekening in verschillende onderdelen, waarbij ieder onderdeel de verantwoordelijkheid is van een opzichzelfstaand programma-object. Deze objecten op zich worden intern echter weer opgesteld aan de hand van één (of meer) van de bovengenoemde modellen, dus de vraag blijft of dit model als een geheel afzonderlijk model gezien kan worden.

Websites

(en) Akhmechet, Slava, defmacro - Functional Programming For The Rest of Us (19 juni 2006).
(en) Dijkstra, Edsger Wybe, How Computing Science created a new mathematical style (4 maart 1990).
(en) Ford, Neal, Functional Thinking (13 januari 2012). Videopresentatie over functioneel programmeren in Java

IBM Functional Thinking Series: (en) Ford, Neal, Functional thinking: Thinking functionally, Part 1. IBM developerWorks (3 maart 2011).; (en) Ford, Neal, Functional thinking: Thinking functionally, Part 2. IBM developerWorks (31 mei 2011).; (en) Ford, Neal, Functional thinking: Thinking functionally, Part 3. IBM developerWorks (28 juni 2011).; (en) Ford, Neal, Functional thinking: Immutability. IBM developerWorks (27 juli 2011).; (en) Ford, Neal, Functional thinking: Coupling and composition, Part 1. IBM developerWorks (30 augustus 2011).; (en) Ford, Neal, Functional thinking: Coupling and composition, Part 2. IBM developerWorks (4 oktober 2011).; (en) Ford, Neal, Functional thinking: Functional features in Groovy, Part 1. IBM developerWorks (12 november 2011).; (en) Ford, Neal, Functional thinking: Functional features in Groovy, Part 2. IBM developerWorks (20 december 2011).; (en) Ford, Neal, Functional thinking: Functional features in Groovy, Part 3. IBM developerWorks (31 januari 2012).; (en) Ford, Neal, Functional thinking: Functional design patterns, Part 1. IBM developerWorks (6 maart 2012).; (en) Ford, Neal, Functional thinking: Functional design patterns, Part 2. IBM developerWorks (3 april 2012).; (en) Ford, Neal, Functional thinking: Functional design patterns, Part 3. IBM developerWorks (15 mei 2012).; (en) Ford, Neal, Functional thinking: Functional error handling with Either and Option. IBM developerWorks (12 juni 2012).; (en) Ford, Neal, Functional thinking: Either trees and pattern matching. IBM developerWorks (10 juli 2012).; (en) Ford, Neal, Functional thinking: Rethinking dispatch. IBM developerWorks (21 augustus 2012).; (en) Ford, Neal, Functional thinking: Tons of transformations. IBM developerWorks (25 september 2012).; (en) Ford, Neal, Functional thinking: Transformations and optimizations. IBM developerWorks (16 oktober 2012).; (en) Ford, Neal, Functional thinking: Laziness, Part 1. IBM developerWorks (20 november 2012).; (en) Ford, Neal, Functional thinking: Laziness, Part 2. IBM developerWorks (19 december 2012).; (en) Ford, Neal, Functional thinking: Why functional programming is on the rise. IBM developerWorks (29 januari 2013).