Funktionellt perspektiv på programmering

Johan Kullbom [HiddenEMail]
2008 (senast uppdaterad 2008-06-30)

Valid XHTML 1.0 Transitional
Valid CSS!

Denna artikel är ett försök att utifrån ett praktiskt perspektiv och främst språket C# förmedla viss insikt i vad det som kallas funktionell programmering är för något.

1. Några begrepp

I en vanlig “variabeldeklaration” i C-liknade språk som C++, C# och Java återfinns tre fundamentala begrepp jag vill börja med att belysa:

int x = 5;

Vi har här ett objekt (eller instans) x av typen int och värdet 5. I imperativ och objektorienterad programmering är vi vana vid dessa begrepp när vi talar om instanser av klasser och värdetyper (value types). För att introducera en tydlig och mer universell notation för typer skriver vi:

x : int

I objektorienterade språk använder man i allmänhet inte begreppet funktion. Utgångspunkten här är klasser med (medlems-)fält och (medlems-)metoder.

En funktion från X till Y, f: XY, är en relation, R: X × Y, som till varje element x i X ordnar exakt ett element y i Y:

xX : ∃ yY (R(x, y) ∧ ∀ zY (R(x, z) → z = y))
??? (Kolla upp ordentligt)
(För alla (∀) x av typen (∈) X gäller att (:) det existerar minst ett (∃) y av typen Y sådant att om relationen R mellan x och y gäller och (∧) att för alla z av typen Y sådant att relationen R mellan x och z gäller impliceras att z är identiskt med y)

En metod anropas med ett objekt, en instans, av en specifik klass. Om metoden är statisk anropas den med klassens namn. Här finns en fundamental skillnad. Statiska metoder (och fält) är inte beroende av någon existerande instans och det klassnamn man använder kan ur de flesta perspektiv betraktas som en namnrymd (namespace) vilken som helst. En statisk metod är i allt väsentligt detsamma som en funktion.

public static int F(int x) {
    return x * x;
}

F är en funktion som från ett argument av typen int returnerar ett objekt av typen int. Vi skriver att F är av typen int → int:

F : intint

På samma sätt som int är en typsignatur för ett heltal är int → int en typsignatur för en funktion från ett heltal till ett annat heltal.

I C# kan vi (från och med version 3.5/2008) definiera F ovan på ett annat sätt som tydligare visar typen på definitionen:

public static Func<int, int> F = x => x * x;

Här använder jag C#'s lambda notation. Ett lambda är en funktion utan namn. Här är lambdat, x => x * x, en funktion som från en parameter, x, returnerar dess kvadrat, x * x.

Denna definition betyder tekniskt exakt detsamma som den ovan men semantiskt är F här inte en metod/funktion utan ett värde (som råkar vara just en funktion). F är någonting av typen Func<int, int> (Func<T> på MSDN) eller int → int, att detta är en funktionstyp ändrar inte att funktionen är just ett värde.

Med F definierat som ett värde är det naturligt att du kan anropa en annan funktion G med detta värde som argument. Om vi definierar G som:

public static int G(Func<int, int> function) {
    return function(5);
}

Eller ekvivalent:

public static Func<Func<int, int>, int> G = function => function(5);

G är en funktion av typen (int → int) → int som från ett argument av typen int → int (en funktion) returnerar en int (resultatet av att anropa funktionen med värdet 5).

När vi nu gått med på att funktioner kan betraktas som värden vilka som helst blir det också naturligt att lokala variabler av dessa typer kan deklareras:

public static int H() {
    Func<int, int> function = x => x * x;
    return function(5);
}

2. Förvirrande begrepp

Någonting som grumlar begreppet funktion för den som är van vid något av de stora objektorienterade språken är att man lärt sig dela in medlemmarna av en klass i väsentligen fyra sorter:

Vi har sett ovan att statiska metoder kan uttryckas som statiska fält genom att betrakta metoden som ett värde av funktionstyp (t.ex. int → int). I den meningen finns ingen anledning att semantiskt skilja statiska metoder från statiska fält.

(Instans-)Metoder i sin tur är inte någonting annat än en statisk metod där det första argumentet är underförstått (kallas ofta this eller self). I C# blir detta extremt tydligt i och med att man infört extension methods:

public static class ExtraMath {
    public static int MyPow(this int x) {
        return x * x; 
    }   
}

Med Extension methods definierar man nya (instans-)metoder för redan existerande klasser. Typiskt sådana klasser man inte har kontroll/källkoden till. I C# är syntaxen för definiera en extension method identiskt med en statisk metod bortsett från från nyckelordet this framför typen på första argumentet.

Extension methods kan anropas antingen som en statisk metod på den klass där den är definierad eller som instansmetod på objekt av den typ metoden har som första argument:

int d = 4;

int r1 = d.MyPow();
int r2 = ExtraMath.MyPow(d);

Eftersom en statisk metod (ekvivalent) kan skrivas som ett statiskt fält kan även en (instans-)metod skrivas som ett statiskt fält. I praktiken förlorar vi då .-syntaxen men inte någon semantik.

Det är alltså möjligt att reducera de fyra ursprungliga medlemmarna av en klass till två: (värde-/databärande) fält och statiska fält.

2.1 Operatorer

Ett annat vanligt men likväl förvirrande begrepp är operator. Oftast uppträder operatorn som en seqvens av mer eller mindre udda tecken mellan två primitiva uttryck. Vi tenderar att se dessa som en fundamental del av språkets kärna och även om vi vet att vi har rätt att definiera och omdefiniera dem låter vi bli.

Om operatorn + istället var en metod skulle det förändra viss syntax men inte någon sematik.

int x = 1 + 2;

int x = 1.+(2);

Operatorer behövs inte och är inte skilda från metoder. Operatorer är metoder - eller i förlängningen funktioner.

int x = +(1, 2);

I språk som LISP eller Scheme existerar inte begreppet operator. Enkla matematiska uttryck som (5 + 6) * (7 - 2) blir som vilket funktionsanrop som helst (* (+ 5 6) (- 7 2)) - eller med C-syntax: *(+(5, 6), -(7, 2)).

4. Funktionella koncept

4.1 Högre ordningens funktioner

Då man inte erkänner någon fundamental skillnad mellan värden och funktioner är det vanligt med funktioner som tar andra funktioner som argument eller returnerar funktioner. En sådan funktion kallar man en högre ordningens funktion (Higher-order function).

Ett vanligt exempel på en högre ordningens funktion är sort:

public static IEnumerable<T> Sort<T>(IEnumerable<T> sequence, Func<T, T, bool> comparison) {
    //...
}

Sort<T> : (IEnumerable<T>, (T, T) → bool) → IEnumerable<T>

Funktionen sort tar som argument en sekvens av T:n samt en funktion från två T:n till bool och returnerar en ny sekvens av T:n.

Vår sort är helt generell och kan användas för att sortera vilka objekt som helst enligt vilket kriterium som helst. Om vi vill sortera en sekvens av User:s efter efternamn skulle det kunna se ut så här:

IEnumerable<User> unsortedUsers = GetUnsortedUsers();

IEnumerable<User> sortedUsers = Sort(unsortedUsers, (user1, user2) => user1.Surname > user2.Surname);

Ett vanligt misstag i den objektorienterade världen är att låta klasser vara av en “sorterbar” typ t.ex. genom att de implementerar någon sorts interface. Även om man - säkert mycket noggrant - ser till att gömma implementationen av sin sorteringsalgoritm har man likväl - helt felaktigt - påstått att hur en viss sorts objekt skall sorteras är upp till den klassen att bestämma.

4.1.1 Closures

Då funktioner inte bara kan ta andra funktioner som argument utan också returnera funktioner kan vi konstruera funktioner utifrån värden (och andra funktioner). MakeAdder tar ett heltal delta och returnerar en funktion som från ett annat heltal x returnerar summan av delta och x:

public static Func<int, int> MakeAdder(int delta) {
    return x => x + delta; 
}

MakeAdder : int → (intint)

Anropar vi MakeAdder med 5 får vi en funktion som från en int returnerar summan av denna och 5.

Func<int, int> addFive = MakeAdder(5);

int r1 = addFive(3); // r1 = 8
int r2 = addFive(6); // r2 = 11
int r3 = addFive(1); // r3 = 6

Den funktion som returneras av MakeAdder kommer ihåg - har kapslat in - argumentet delta. Den returnerade funktionen är en closure över delta.

Closures delar många egenskaper med objektorienteringens objekt där de inkapslade argumenten motsvaras av fält. Vi kan konstruera en generator:

public static Func<int> MakeGenerator() {
    int currentValue = 0;
    return () => ++currentValue; 
}

MakeGenerator : () → (() → int)

Typer på formen () → x är funktionstyper utan argument som returnerar något av typen x.

Func<int> generator = MakeGenerator();

int r1 = generator(); // r1 = 1
int r2 = generator(); // r2 = 2
int r3 = generator(); // r3 = 3

MakeGenerator är en funktion - utan argument - som returnerar en funktion - också utan argument - som i sin tur returnerar konsekutiva tal från 0 och uppåt. Den returnerade funktionen kapslar in currentValue på ett sätt som är mycket likt medlemsfält i objektorientering.

Closures kapslar alltså inte in värden utan variabler.

4.1.2 Currying och komposition

Som vi har sett kan vi skriva funktioner som från sina argument skapar nya funktioner. Speciellt kan vi från alla funktioner med minst två argument skapa en ny där vissa argument är fastställda. Med följande definition av curry kan vi från alla funktioner av typen (int → int) → int generera en ny av typen int → int där första argumentet är “underförstått”:

public static Func<int, int> curry(Func<int, int, int> function, int firstArg) {
    return x => function(firstArg, x);
}

Begreppen currying och partiell applikation (partial application) används i allmänhet slarvigt och så även här. Currying är egentligen att omvandla funktioner på formen (a → b) → c till a → (b → c). Partiell applikation innebär att man vid anropet till en funktion ger den “för få” argument och får tillbaka en funktion (closure) som “väntar” på de återstående. Bl.a. Ocaml, Haskell, F# och Scala har direkt stöd för partiell applikation av funktioner i språket.

Min curry borde kanske snarare heta partialApply.

Vi kan t.ex. generera vår addFive.

Func<int, int, int> add = (x, y) => x + y; // General add/+ function
Func<int, int> addFive = curry(add, 5);

int r = addFive(4); // r = 9

Om vi med hjälp av generics generaliserar vår curry till att kunna göra detsamma oavsett argument- och returtyper får vi en helt generell mekanism för att från funktioner med två argument underförstå det första.

public static Func<T2, R> curry<T1, T2, R>(Func<T1, T2, R> function, T1 firstArg) {
    return x => function(firstArg, x);
}

Definierar vi curry för funktioner med fler argument också har vi en helt generell mekanism:

public static Func<T2, T3, R> curry<T1, T2, T3, R>(Func<T1, T2, T3, R> function, T1 firstArg) {
    return (x1, x2) => function(firstArg, x1, x2);
}

public static Func<T2, T3, T4, R> curry<T1, T2, T3, T4, R>(Func<T1, T2, T3, T4, R> function, T1 firstArg) {
    return (x1, x2, x3) => function(firstArg, x1, x2, x3);
}

// ...

För att underförstå det sista argumentet till funktioner istället för det första definierar vi rcurry på motsvarande sätt:

public static Func<T1, R> rcurry<T1, T2, R>(Func<T1, T2, R> function, T2 lastArg) {
    return x => function(x, lastArg);
}

public static Func<T1, T2, R> rcurry<T1, T2, T3, R>(Func<T1, T2, T3, R> function, T3 lastArg) {
    return (x1, x2) => function(x1, x2, lastArg);
}

public static Func<T1, T2, T3, R> rcurry<T1, T2, T3, T4, R>(Func<T1, T2, T3, T4, R> function, T4 lastArg) {
    return (x1, x2, x3) => function(x1, x2, x3, lastArg);
}

// ...

Vi har nu en mycket användbar, om än formellt slarvig, implementation av currying.

På motsvarande sätt kan vi generellt definiera funktionskomposition (function composition):

public static Func<T1, R> compose<T1, T2, R>(Func<T2, R> outerFunction, Func<T1, T2> innerFunction) {
    return x => outerFunction(innerFunction(x));
}

4.2 Explicita beroenden

Med undantag för MakeGenerator har alla exempel hittills varit så kallade rena funktioner (pure functions) där resultatet av funktionerna varit entydigt definierade och uteslutande beroende av sina argument.

Rena funktioner gör aldrig någonting. Detta innebär att det är oberoende av i vilken ordning de evalueras i förhållande till varandra. Ordning spelar bara roll i den mån resultatet av en funktion är argument till en annan. Alla beroenden är explicita.

resultat = a(b(1), c(2));

Att b och c behöver evalueras innan a är explicit i form av nästling. Mellan b och c finns inget ordningsberoende.

Jag utgår här ifrån språk med strikt evaluering (strict evaluation) till skillnad från lat evaluering (non-strict evaluation).

I strikt (lat) mening finns beroendet bara om a faktiskt behöver värdena av b och c för att kunna producera sitt resultat. Om resultat från en ren funktion inte används kan vi alltid låta bli att anropa den.

I allmänhet kan vi säga att man i funktionell programmering uttrycker evalueringsordning genom nästling av uttryck.

När vi i imperativ programmering uttrycker program/algoritmer i termer av gör först A sedan B bygger vi in ett underförstått beroende till evalueringsordning. Då varje imperativt uttryck (statement) kan modifiera något slags state - lokalt eller globalt kan vi inte se vilka ordningsberoenden som faktiskt finns.

Notera att alla operationer som gör något annat än att från argument leverera ett resultat är att betrakta som imperativa uttryck. Detta inkluderar input/output, anrop till andra språk (om det inte kan garanteras att funktionerna är rena) och all sorts tilldelning (av redan initialiserade variabler).

print("skriv först");
print("skriv sedan");
print("skriv sist");

Om vi tänker oss att alla funktioner som modifierar någon sorts state istället tog ett state-objekt som argument och returnerade ett nytt modifierat state-objekt skulle vi kunna uttrycka ordningsberoenden explicit:

State state1 = print(new State(), "skriv först");
State state2 = print(state1, "skriv sedan");
State state3 = print(state2, "skriv sist");

Eller:

print(print(print(new State(), "skriv först"), "skriv sedan"), "skriv sist");

Det är i sammanhanget av underordnad betydelse om vårt state-objekt innehåller något faktiskt state eller inte, det viktiga är att vi nu har gjort beroendet mellan de olika print-uttrycken explicit.

4.3 Evaluering istället för exekvering

Rena funktioner är direkt översättbara till matematiska förhållanden mellan argument och resultat och utgör därför en deklaration över ett förhållande vi tror på. Detta att jämföras med instruktioner om hur något skall utföras.

När vi talar om att ett imperativt program körs menar vi att alla uttryck, i tur och ordning, utförs tills de alla är klara. Ur ett funktionellt perspektiv är processen att “köra” ett program detsamma som att förenkla alla uttryck till sin enklaste form. Uttrycken evalueras istället för att exekveras.

Genom att betrakta program som en beskrivningar av relationer istället för en instruktioner datorer skall följa har vi både höjt abstraktionsnivån i kommunikationen med maskinen och samtidigt gjort det möjligt för den att göra det den är bra på - att snabbt ge oss resultat.

När vi från ett imperativt perspektiv skriver:

int x = 0;

if(myCondition)
    x = 5;
else
    x = 10;
    
...

Menar vi ur ett funktionellt perspektiv:

int x = mycondition ? 5 : 10;

I funktionella språk returnerar if-uttryck på precis samma sätt som en conditional operator-uttryck och man skulle istället skriva (något i stil med):

int x = if mycondition 5 else 10;

Varje uttryck returnerar någonting och värdet av variabler ändras inte över tid.