Funktionell programmering

Funktionell programmering som begrepp

Som vi beskriver i Funktionell programmering som paradigm har terminologin "funktionell" programmering sitt ursprung i matematiska funktioner, som t.ex. sin(x) och sqrt(x). Läs det avsnittet först!

Funktionell programmering och sidoeffekter

Matematiska funktioner beräknar alltså värden men har inga sidoeffekter. Det vill säga, om vi beräknar sin(x) i en matematisk formel, kan detta inte orsaka att parametern x byter värde, att en orelaterad variabel z byter värde, eller några andra effekter överhuvudtaget -- vi får helt enkelt tillbaka ett uträknat värde från vårt "anrop" till sin().

Med andra ord, funktionen sin är något som ger ett värde tillbaka utan att i övrigt påverka sin omgivning överhuvudtaget -- att "påverka" eller "ändra" finns inte i matematiken.

I funktionell programmering arbetar vi på liknande sätt, utan sidoeffekter. Vill vi programmera funktionellt får vi alltså inte göra så här:

def find_smallest(seq):
    seq.sort()  # ändrar i seq
    return seq[0]

Varför inte? Jo, här ändrar ju find_smallest värdet på sin inparameter. Så kan inte matematiska funktioner göra. Däremot är följande tillåtet:

def find_smallest(seq):
    return sorted(seq)[0]

Här har vi inga sidoeffekter! Vi använder oss inte heller av några globala variabler eller någon information utöver den som vi har fått via parametrar, som detta skulle ha gjort:

id = 0
def next_id():
    global id
    id += 1
    return id

>>> next_id()
1
>>> next_id()  # Får vi samma värde som förra identiska anropet?  Nej!
2
>>> next_id()
3
>>> id=4710  # Vi kan påverka den utifrån!
>>> next_id()
4711

Att använda funktionell programmering får ett antal konkreta konsekvenser:

• Det spelar ingen roll om vi anropar en "ren" funktion 1 gång eller 100; vi får samma resultat varje gång. Anroparen kan lugnt förlita sig på detta (till skillnad från next_id, som är en "Python-funktion" men inte funktionell då den både har sidoeffekter och returnerar värden som beror på externa, globala variabler).

• Om vi vet att find_smallest(seq)==14, så vet vi alltså att vårt nästa anrop till find_smallest(seq) också skulle returnera 14, så länge som inte vi har ändrat i seq. Det gör att en bra kompilator (i vissa språk) kan optimera bort beräkningar åt oss på ett sätt som inte skulle gå om koden inte var funktionellt skriven.

• Anroparen kan lugnt förutsätta att seq har samma värde även efter anropet, utan att fundera på hur funktionsanropet kan tänkas ha modifierat seq -- i ren funktionell programmering kan detta inte hända. Ett funktionellt skrivet program saknar därmed vissa felkällor som man måste vara noga att se upp med i andra typer av program ("oj, har seq inte samma värde som det hade nyss?").

• Om vi vill beräkna minsta elementet i 1 miljard listor kan vi tryggt dela upp detta på 100 CPU-kärnor utan att riskera att något blev beräknat "i fel ordning". Funktionen beror ju bara på sina indata, inte på några andra värden som vi kan råka hantera på fel sätt. En bra kompilator skulle till och med kunna dela upp arbetet på det sättet helt automatiskt.

De här fördelarna kan vara mer eller mindre viktiga beroende på det program man skriver och beroende på hur man själv programmerar. Funktionell programmering kan också ha vissa nackdelar, vilket diskuterades i det tidigare avsnittet.

Funktionell programmering i TDDE23-24

I den här kursen kommer vi att titta på olika aspekter av funktionell programmering.

En sådan viktig aspekt är just avsaknaden av sidoeffekter. Detta är inte något som vi kommer att använda genomgående genom kursen, inte något som vi kommer att kräva överallt; vi programmerar trots allt inte i ett "rent" funktionellt språk. Däremot är det något man kan ha nytta av att använda på de ställen där det passar. Sidoeffekter ger oss hela tiden mer att hålla reda på -- inte bara "vad returnerar funktionen?" utan också "hur påverkar den sin omgivning på andra sätt?". I många fall är det väl värt att undvika dessa komplikationer även när man programmerar i t.ex. Python eller Java. I andra fall är det fullständigt befogat att använda sig av sidoeffekter i Python.

En annan viktig aspekt av funktionell programmering är att kunna programmera med hjälp av funktioner som är "första ordningens objekt", vilket innebär att en funktion inte är något magiskt begrepp utan är ett sorts värde som kan hanteras som andra typer av värden. Python har fullt stöd för detta och låter oss till exempel göra så här:

if condition:
    fun = sin
else:
    fun = cos

y = fun(x)

Här ser vi en variabel fun vars värde är en funktion.

I nästa steg kan vi använda detta för att skapa funktioner som tar funktioner som parametrar, liksom funktioner som returnerar funktioner. Detta kallas högre ordningens funktioner, eftersom det är funktioner som i sig använder funktioner som värden (inte t.ex. "heltalsfunktioner" utan "funktionsfunktioner" eller "funktionsfunktionsfunktioner", fast det låter så löjligt så vi sammanfattar det som "högre ordningens funktioner"). Detta är ett väldigt kraftfullt verktyg som vi kan ha mycket nytta av. I resten av avsnittet är det just detta vi ska titta vidare på.

Exempel på funktionell programmering

För att visa några fördelar hos funktionell programmering kommer vi först att gå genom två rekursiva funktioner som inte använder sig av högre ordningens funktioner. Nedan har vi t.ex. två funktioner:

• Den första, increment5, går igenom en lista och ökar (eng. increment) alla element med 5.
• Den andra, first_element, returnerar en lista som består av de första elementet från alla "andra-nivå"-listor.

def increment5(seq):
    """ Returns a new list where every element in seq is incremented by 5 """
    if not seq:
        return []
    else:
        return [5 + seq[0]] + increment5(seq[1:])


def first_element(seq):
    """ Creates a list with the first element of every second-level list in seq """
    if not seq:
        return []
    else:
        return [seq[0][0]] + first_element(seq[1:])

>>> increment5([5, 10, 15, 20])
[10, 15, 20, 25]
>>> first_element([['q', 'w', 'e', 'r'], [2, 3, 5, 7, 11]])
['q', 2]

Även utan funktionell programmering kan vi generalisera detta på följande sätt:

def incrementX(seq, inc):
    """ Returns a new list where every element in seq is incremented by inc """
    if not seq:
        return []
    else:
        return [inc + seq[0]] + increment5(seq[1:])


def nth_element(seq, n):
    """ Creates a list with nth first element of every second-level list in seq """
    if not seq:
        return []
    else:
        return [seq[0][n]] + first_element(seq[1:])

Nu har vi inte bundit fast oss till att öka med just 5, eller till att hitta just det första elementet i varje underlista. Så här långt kan vi lätt komma utan högre ordningens funktioner, eftersom parametrarna inc och n var "vanliga" värden (i detta fall heltal). Med hjälp av inc kan vi nu addera precis vilket tal som helst -- men hur skulle vi göra om vi ville kunna beräkna vilken funktion av seq[0] som helst, t.ex. multiplicera element med 5?

Vi kommer snart att se fyra alternativa sätt att göra detta på med hjälp av olika tekniker som förekommer i funktionell programmering.

Alternativ 1 - Högre ordningens funktioner

Högre ordningens funktioner går alltså ut på att använda funktioner som in- och utdata och bygger på det faktum att funktioner räknas som första ordningens objekt.

def with_all(func, seq):
    """ Applies func to every element in the sequence """
    if not seq:
        return []
    else:
        return [func(seq[0])] + with_all(func, seq[1:])


def i5(n):
    return n + 5

def fe(s):
    return s[0]

def increment5(seq):
    return with_all(i5, seq)

def first_element(seq):
    return with_all(fe, seq)

Notera att with_all implementerar en generell funktionalitet som kan parametriseras genom att man talar om vilken funktion func den ska använda! Både increment5 och first_element kunde nu implementeras med hjälp av detta, så vi slipper upprepa rekursionskoden och kan programmera på en högre nivå.

def mul5(n):
    return n * 5

def multiply5(seq):
    return with_all(mul5, seq)

Nu kunde vi också implementera multiplikation med 5 genom att anropa with_all. Genom att vi skickar med en funktion kan vi implementera vilken transformation som helst på elementen och uttrycka den utan att upprepa rekursionskoden. Och detta är viktigare än man kanske kan tro: Dels kan det i andra fall vara väldigt mycket kod som man slipper upprepa (inte bara 4-5 rader som i with_all), dels bygger programmering i väldigt hög grad på att man bryter ner koden i förståeliga delar som skapar nya begrepp att använda sig av.

Alternativ 2 - Lambda-funktioner

Små funktioner som endast består av ett uttryck, likt i5 och fe ovan, kan ersättas med så kallade lambda-funktioner. De är temporära funktioner utan namn som typiskt används som argument till högre ordningens funktioner.

Dokumentation

def with_all(func, seq):
    """ Applies func to every element in the sequence """
    if not seq:
        return []
    else:
        return [func(seq[0])] + with_all(func, seq[1:])

def increment5(seq):
    return with_all((lambda n: n + 5), seq)

def first_element(seq):
    return with_all((lambda s: s[0]), seq)

Detta har fördelen att man inte behöver skapa nya namn för små och enkla uttryck som man ändå hade skrivit direkt i koden om man inte hade använt högre ordningens funktioner.

Mer om högre ordningens funktioner

Vi vill ha en funktion combine som kan gå igenom en lista av tal och kombinera dem parvis med hjälp en funktion som vi skickar in. Några exempel på vad vi vill kunna göra är:

• 0 + 1 + 2 + 3 + 4 = 10
• 0 - 1 - 2 - 3 - 4 = -10
• 0 * 1 * 2 * 3 * 4 = 0

def combine(func, seq):
    """ Combines all the elements in the sequence by using func """
    result = seq[0]
    for element in seq[1:]:
        result = func(result, element)
    return result

>>> combine((lambda x, y: x - y), range(5))
-10

Detta var det svar som vi ville ha. Men hur skulle det fungera om vi vänder ordning på argumenten till den inskickade funktionen?

Alltså att istället för result = func(result, element) så har vi result = func(element, result). Vi testar och ser att vi får fel svar:

>>> combine((lambda x, y: x - y), range(5))
2

Varför?

• Med func(result, element) beräknar vi ((((0 - 1) - 2) - 3) - 4)
• Med func(element, result) beräknar vi (4 - (3 - (2 - (1 - 0))))

I den här typen av beräkningar gäller det alltså att hålla reda på beräkningsordningen!

Men kan vi göra combine rekursiv istället? Vi måste då bearbeta i omvänd ordning eftersom vi börjar med en hel lista och för varje rekursionssteg minskar den.

def combine(func, seq):
    """ Combines all the elements in the sequence by using func """
    if not seq[1:]:
        return seq[0]
    else:
        return func(combine(func, seq[:-1]), seq[-1])

>>> combine((lambda x,y: x-y),range(5)) 
-10

Att tänka på vid combine-liknande funktioner

Det gäller att hålla koll på i vilken ordning de enskilda elementen kombineras. Om funktionen vi skickar in är både kommutativ och associativ kan vi i princip kombinera hur som helst, men om den saknar någon av dessa egenskaper är ordningen viktig. Definitionerna av dessa egenskaper:

• Kommutativ: a + b = b + a
• Associativ: (a + b) + c = a + (b + c)

Exempel:

• Addition är både kommutativ och associativ.
• Subtraktion är varken kommutativ eller associativ.
• Konkatenering (sammanslagning av strängar eller listor) är associativ men inte kommutativ.

Funktioner som utdata

Vi har sett funktioner som indata, i både combine och with_all, men vi kan även använda funktioner som utdata. Detta kan man göra med redan definierade funktioner som sin och cos:

def get_function(i):
    if i % 0 == 1:
        return sin
    else:
        return cos

Man kan också skapa en funktion inuti en funktion, och sedan returnera den. Det fungerar både med lambdafunktioner och namngivna funktioner.

def get_function(i):
    if i % 0 == 1:
        return (lambda n: n+1)
    else:
        # Vi kan faktiskt definiera en intern funktion inuti en annan funktion...
        def twice(n):
            return 2*n
        # ... och använda den och/eller returnera den. 
        return twice

En anledning till att skapa en intern funktion kan vara att man vill ha en s.k. closure. I funktionen nedan används detta för att låta den returnerade funktionen (next_num) ha ett sorts "minne" som finns kvar mellan anropen. Som man kan se "minns" den:

• Parametern length, som den får från anropet till create_counter. Den inre funktionen använder det värde som length hade fått i anropet. I körexemplet är detta 3 och som man kan se går räknaren "runt" innan den kommer till 3.

• Variabeln i, som deklarerades i length. Denna ändras sedan inuti varje anrop till next_num men har en längre livslängd -- den bevaras mellan anropen.

  Verkar detta underligt? Man kan tänka sig det som ett mellanting mellan en helt global variabel (som bara har en enda kopia och "alltid" finns kvar under hela programkörningen) och en helt lokal variabel (som skapas på nytt vid varje metodanrop). Just i deklareras i create_counter, så det blir en ny instans för varje anrop till create_counter men denna delas mellan anropen till den inre funktionen next_num.

Exempel:

def create_counter(length):
    """ Returns a circular counter function """
    i = 0
    def next_num():
        # Eftersom vi tilldelar ett värde till i måste vi deklarera
        # den "nonlocal", annars får vi en egen lokal variabel... 
        nonlocal i
        i = i + 1
        # Vi kan använda "length" utifrån, utan att deklarera nonlocal,
        # eftersom vi inte tilldelar length ett nytt värde i inre funktionen
        if i >= length:
            i = 0
        return i
    return next_num

>>> c = create_counter(3)
>>> c
<function next at 0x0000025067C8>
>>> c()
1
>>> c()
2
>>> c()
0

Det som händer här är alltså att funktionen create_counter returnerar ett closure, ungefär ett funktionsobjekt som även innehåller information om lokala variabler.

Alternativ 3 - Pythons egna iteratorfunktioner

Den generella funktionen with_all har redan en motsvarighet i Python i funktionen map. Denna returnerar dock inte listan direkt.

Dokumentation

>>> range(5)
range(0, 5)

>>> list(range(5))
[0, 1, 2, 3, 4]

>>> map((lambda x: x*x), range(5))
<map object at 0x00000000024C83C8>

>>> list(map((lambda x: x*x), range(5)))
[0, 1, 4, 9, 16]

Det som funktionerna range och map returnerar kallas iteratorer. De är värden/objekt som vet hur man får fram ett element i taget. Iteratorer kan användas för att plocka ut element från en existerande "färdig" lista, men när det gäller range och map (och många andra fall) har iteratorn helt enkelt information om hur man räknar ut nästa element.

En iterator kan ses alltså som en slags automat ur vilken man kan få ett element i taget. Den i princip enda operationen man kan göra på en iterator är next() som ger nästa element, om det finns.

Varför vill man göra så? Jo, i många fall skulle det ta för mycket mycket tid och minne att räkna ut alla element i förväg -- om vi skapar list(range(1000000000)) skulle det resultera i en faktisk lista med en miljard värden, vilket kunde ta mycket mer minne än vi har i datorn. Men vi kan istället använda iteratorn direkt, t.ex. i en for-loop:

sum = 0
for i in range(1000000000):
    sum += i

Här behöver vi bara ett element i taget, så allt som behövs är att range-iteratorn kan hålla reda på var den är i beräkningen. För detta behöver vi ju inte skapa hela listan med en miljard element.

Även map fungerar på detta sätt. Vi kan iterera över de beräknade värdena utan att man behöver skapa hela listan av värden på en gång:

for val in map((lambda x: x*x), range(5)):
    print(val)

Det kan till och med hända att man aldrig tittar på vissa element, som i detta fall:

for val in map((lambda x: x*x), range(1000000000)):
    print(val)
    if val > 100:
        break

Resultat:

0
1
4
9
16
25
36
49
64
81
100
121

Här plockades bara värdena 0 till 11 ut ur map-iteratorn. Sedan avbröts loopen. Att räkna ut kvadraten på alla tal upp till 1 miljard hade då varit slöseri med tid och minne.

Om vi trots allt vill ha just en lista med alla värden som man får ut från en iterator kan vi använda funktionen list.

def increment5(seq):
    return list(map((lambda n: n + 5), seq))

def first_element(seq):
    return list(map((lambda s: s[0]), seq))

Mer om iteratorfunktioner

Några andra fräna saker som har med iteratorer att göra:

>>> s = [3, 1, 4, 2]
>>> min(s), max(s), sum(s)
(1, 4, 10)

>>> sorted(s)
[1, 2, 3, 4]

>>> list(reversed(s))
[2, 4, 1, 3]

>>> list(filter((lambda x: x%2==0), s))
[4, 2]

>>> list(enumerate(s))
[(0, 3), (1, 1), (2, 4), (3, 2)]

>>> list(zip(s, ['a', 'b', 'c', 'd']))
[(3, 'a'), (1, 'b'), (4, 'c'), (2, 'd')]

Alternativ 4 - Listbyggare

Listbyggare (eng. list comprehensions) är ett mer kompakt alternativ till funktionen map. Man får en lista direkt och behöver således inte använda funktionen list.

Dokumentation

list(map(lambda variabel: uttryck), sekvens)

Blir med hjälp av listbyggare:

[uttryck for variabel in sekvens]

Här har vi funktionerna som vi stötte på tidigare skrivna med listbyggare:

def increment5(seq):
    return [n +5 for n in seq]

def first_element(seq):
    return [s[0] for s in seq]

Mer exempel på listbyggare

>>> [len(x) for x in ['spam', 'ham']]
[4, 3]

## Likt filter
>>> [x*x for x in range(5) if x > 0 and x % 2 == 0]
[4, 16]

## Flera listor
>>> [(x, y) for x in range(3) for y in range(4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2),
(1, 3), (2, 0), (2, 1), (2, 2), (2, 3)]

## Text-filter
>>> [line.rstrip() for line in open("poetry.txt")]
['Roses are red', 'Violets are blue', 'Spam and eggs']

>>> people = [('Eve',37,'manager'), ('Dave',45,'technician'), ('Alice',49,'CEO')]

## Projicering
>>> [age for (name,age,job) in people]
[37, 45, 49]

Ett lite klurigare exempel

Nedan ser vi en funktionell implementation av: summan av f(x) för alla tal 0 <= x <= n. Det är en utmärkt lösning som är tydlig och enkelt skriven, men finns det andra sätt att göra det på med hjälp av vad vi har sett idag?

def sum1(f, n):
    """ Returns the sum of f(n), f(n-1),..., f(0). """ 
    if n < 0:
        return 0
    else:
        return f(n) + sum1(f, n - 1)

Principskiss

Låt oss säga att argumenten som skickas in ska ge upphov till:

Hur skulle det kunna se ut?

Detta i kod blir då:

from functools import reduce

def sum2(f, n):
    return reduce((lambda x, y: x + y), \
        [f(x) for x in range(n + 1)])

Sammanfattning

• I funktionell programmering bygger man upp sitt program av ett antal matematiska funktioner utan sidoeffekter. Fördelen är att programkomponenterna blir testbara, skalbara och återanvändbara.
• Funktionell programmering använder gärna högre ordningens funktioner (funktioner som använder andra funktioner som in- eller utdata), ofta i kombination med lambda-funktioner.
• Python har ett flertal iteratorer inbyggda, som kan hjälpa oss att t.ex. utföra en operation på alla element.
• Listbyggare är en ännu mer kompakt och flexibel metod att konstruera sekvenser.

Tillhörande quiz

Finnes här