Václav Končický

Funkcionální programování

Uvažme nyní programování, kde všechny objekty, se kterými pracujeme, jsou matematické funkce nebo konstanty. Zkusme si nejprve říct, co od takových funkcí budeme vyžadovat.

Chtěli bychom, aby tyto funkce byly čisté. Čistá funkce závisí pouze na parametrech, které dostane a vždy vrátí stejný výsledek pro stejné parametry. Vnější stav nevidí ani nemění. Tudíž čistá funkce nemá žádné vedlejší efekty.

Čisté funkce mají mnoho výhod. Protože závisí pouze na parametrech, můžeme si kešovat výsledky funkce (příkladem je dynamické programování). Taktéž můžeme libovolně paralelizovat a prohazovat pořadí výpočtů, protože závislosti tvoří strom.

Ukážeme, že takový princip programování je turingovsky úplný, tudíž má smysl takové programování uvažovat. Ukážeme si nejprve nejjednodušší systém této síly a pak jej postupně vyvineme v programovací jazyk Haskell.

Lambda kalkulus

Nejjednodušší abstraktní model, který již má sílu turingova stroje, se běžně nazývá lambda kalkulus. Ten má pouze tři konstrukce. Tou první jsou proměnné. Ty označují libovolný (neznámý) objekt. Budeme je značit slovy začínající malým písmenem: x, y, var.

Dále máme Lambdy, což jsou funkce s jedním parametrem. Jejich definice se skládá z hlavy, tedy vázané proměnné x reprezentující parametr, a těla definujícího obraz funkce, jenž může být libovolný výraz lambda kalkulu. Lambdy budeme značit (jak jinak) lambdou, za kterou máme hlavu a tělo oddělené tečkou: λx.F(x). Lambda může v těle obsahovat i volné proměnné, které jsme nespecifikovali hlavou.

Nakonec uvažujeme aplikace. Ta vezme funkci F a libovolný jiný výraz lambda kalkulu L a značí vyhodnocení F(L). Tu budeme značit mezerou: F L.

Aplikace vážou silněji, než lambdy. Zatímco aplikace jsou zleva asociativní, tak lambdy jsou asociativní zprava. Abychom správně určili rozsah těla lambdy nebo vnoření aplikací, máme k dispozici též závorky.

λx.λy.x = (λx.(λy.x))
a b c = ((a b) c)

λx.x a = (λx.(x a))
(λx.x) a = ((λx.x) a)

S lambda kalkulem si můžeme zkusit počítat online.

Vyhodnocování programu v lambda kalkulu je pak redukce aplikací: kdykoliv narazíme na aplikaci (λx.F(x)) y, nahradíme ji výrazem F(y). Taktéž můžeme libovolně přejmenovávat parametr lambdy a dvě různé lambdy nikdy nesdílejí vázanou proměnnou.

Užití redukce budeme značit šipkou →, přejmenování parametru lambdy rovnítkem. Ukažme si to na jednoduchých příkladech:

-- Aplikace identity
> (λx.x) y → y
-- Nahrazení volnou proměnnou
> (λx.z) y → z
-- Vnořená funkce
> (λx.(λy.x)) z a → (λy.z) a → z
-- Přejmenovávání
> (λx.x y) ((λx.x) z) = (λx.x y) ((λx1.x1) z) → (λx.x y) z → z y

Samozřejmě nám nic nebrání na funkci aplikovat jinou funkci. Naopak, toto je velmi důležitá vlastnost lambda kalkulu i celého funkcionálního programování.

> (λx.(x w)) (λy.(z y)) → ((λy.z y) w) → z w

Přestože lambda bere nejvýše jeden parametr, můžeme si nepřímo pořídit funkce více proměnných. Tu můžeme udělat snadno zřetězením více lambd za sebou:

> (λx.λy.λz.x y z) a b c → (λy.λz.a y z) b c → (λz.a b z) c → a b c

Takovou funkci pak můžeme reprezentovat zkratkou λx y z.x y z. Této technice vytváření funkce více proměnných pomocí funkcí jedné proměnné se říká currying podle matematika Haskell Curry.

Může se nám též stát, že vyhodnocení nikdy neskončí, což odpovídá nekonečné rekurzi.

> (λx.x x) (λy.y y) → (λy.y y) (λy.y y) = (λx.x x) (λy.y y) -- cyklus

Líné vyhodnocování

Existuje mnoho způsobů, v jakém pořadí vyhodnotit aplikace. Každý má své výhody a nevýhody. Ukážeme si dva takové způsoby, a pak z nich sestavíme jiné, které bude spojovat výhody obou. Hranatými závorkami budeme značit, kterou redukci jsme udělali.

První způsob je postupovat zevnitř ven. Pokud narazíme na složený výraz, podíváme se nejprve dovnitř, zda obsahuje nějakou aplikaci a tu vyhodnotíme. Tudíž nejprve vyhodnocujeme vnitřní aplikace, a až potom redukujeme vnějši aplikace na ně:

> (λx.f x x) ((λx.λy.z) a b)
(λx.f x x) (｢(λx.λy.z) a｣ b)
→ (λx.f x x) (｢(λy.z) b｣)
→ ｢(λx.f x x) z｣
→ f z z

Tento způsob má zásadní problém. Můžeme se snadno zacyklit, pokud se pokusíme vyhodnotit vnitřní mezivýsledek skrývající nekonečnou rekurzi. Ten však ve vnější aplikaci můžeme zahodit, takže jej možná nebylo třeba vyhodnotit.

> (λx.λy.y) ((λx.x x) (λx.x x))
(λx.λy.y) (｢(λx.x x) (λx.x x)｣)
→ (λx.λy.y) (｢(λx.x x) (λx.x x)｣) -- ouha

Nabízí se tedy jiný postup. Tentokráte budeme postupovat zvnějšku. Prohlížíme program zleva doprava, vezmeme nejlevější aplikaci a tu redukujeme. Takto funkce vyhodnotíme zvnějšku dovnitř a nikdy nevyhodnotíme vnitřek funkce před tím, než na ní použijeme aplikaci. Tentokrát nám předchozí příklad vyjde bez zacyklení:

> (λx.λy.y) ((λx.x x) (λx.x x)) → λy.y
｢(λx.λy.y) ((λx.x x) (λx.x x))｣ → λy.y

Naopak nevýhodou je, že tento postup může být neefektivní. Jelikož nevyhodnocujeme vnitřek, může se nám kopírovat a pak jej budeme muset vyhodnotit častěji:

> (λx.f x x) ((λx.λy.z) a b)
｢(λx.f x x) ((λx.λy.z) a b)｣
→ f (｢(λx.λy.z) a｣ b) ((λx.λy.z) a b)
→ f (｢(λy.z) b｣) ((λx.λy.z) a b)
→ f z (｢(λx.λy.z) a｣ b)
→ f z (｢(λy.z) b｣)
→ f z z

Oběma problémům se můžeme však vyhnout, a to použitím líného vyhodnocování. V líném vyhodnocováním postupujeme z vnějšku. Kromě toho ale navíc všechny výskyty stejné aplikace nahradíme stejnou redukcí. Tak provedeme vyhodnocení jen jednou a jen, pokud to je potřeba. Efektivně jsme si tak nakeškovali výsledek a každý parametr je vyhodnocený nejvýše jednou.

> (λx.λy.y) ((λx.x x) (λx.x x)) → λy.y
｢(λx.λy.y) ((λx.x x) (λx.x x))｣ → λy.y

> (λx.f x x) ((λx.λy.z) a b)
｢(λx.f x x) ((λx.λy.z) a b)｣
→ f (｢(λx.λy.z) a｣ b) (｢(λx.λy.z) a｣ b)
→ f (｢(λy.z) b｣) (｢(λy.z) b｣)
→ f z z

Tudíž líné vyhodnocování může pracovat s potenciálně nekonečnými strukturami, ale je stále velmi efektivní. V případě, že takovou nekonečnou strukturu máme, ale ve skutečnosti potřebujeme jen její konečnou část, tak opravdu jen tuto část vyhodnotíme. Právě tento líný způsob vyhodnocování používá jazyk Haskell.

To má pro nás příjemný důsledek. Jak jsme na začátku slíbili, pořadí vyhodnocování, narozdíl od procedurálních jazyků, se nyní může zvolit automaticky tak, aby bylo co nejefektivnější. Při samotném psaní programu se tak pořadí vyhodnocování stane nedůležitým.

Tento fakt lze přirovnat k tomu, když se poprvé v jazyce přidal Garbage Collection. Do té doby byla alokace paměti důležitou součástí programu, ale přidání GC jej udělal nedůležitým.

Booleovská logika

Zkusme nyní vybudovat jednoduchou booleovskou logiku pomocí lambda kalkulu. Vzhledem k tomu, že máme k dispozici velmi málo, nemáme žádné přímé konstanty. Musíme tudíž použít pouze to, co máme, a to lambdy.

Pravdivou a nepravdivou hodnotu budeme reprezentovat funkcemi o dvou parametrech, kde pravda vrací první parametr a nepravda ten druhý. Pak můžeme vyhodnotit pravdivost dvěma aplikacemi určitých proměnných, kterým přiřadíme sémantický význam.

Slova velkými písmeny budeme využívat jako syntaktické zkratky za funkce a při vyhodnocení je substitujeme za jejich definici.

T = λx.λy.x = λx y.x
F = λx.λy.y = λx y.y

> T t f = (λx.λy.x) t f → (λy.t) f → t
> F t f = (λx.λy.y) t f → (λy.y) f → f

Pomocí této definice funkcí si nyní nadefinuje pomocnou funkci IF. Tato funkce bere tři parametry b, t, f a provede prostou aplikaci t a f na b. Tudíž IF vrátí t (první parametr), pokud b = T, a pro b = F vrací f (druhý parametr). Pak pomocí této funkce můžeme nadefinovat obvyklé spojky NOT, AND, OR.

IF = λb t f.b t f = λb.λt.λf.b t f
NOT = λa.IF a F T
AND = λa b.IF a b F
OR = λa b.IF a T b

> OR T F = (λa.λb.(λb1.λt.λf.b1 t f) a (λx.λy.x) b) (λx.λy.x) (λx.λy.y)
 → (λa.λb.a (λx.λy.x) b) (λx.λy.x) (λx.λy.y)
 → (λb.(λx.λy.x) (λx.λy.x) b) (λx.λy.y)
 → (λx.λy.x) (λx.λy.x) (λx.λy.y)
 → (λy.(λx.λy.x)) (λx.λy.y)
 → λx.λy.x = T

Cvičení: Zkuste zkombinovat tyto spojky a vytvořit XOR, implikaci, ekvivalenci.

Přídání typů

V lambda kalkulu nám něco zásadně chybí, a to jakékoliv rozlišování typů parametrů. Vše je jen jednoho typu. Pojďme tedy do lambda kalkulu přidat typy.

Každá proměnná nyní bude mít svůj přiřazený typ. Konkrétní typy budou začínat velkým písmenem a typ budeme značit čtyřtečkou (x::A).

Jakého typu budou funkce? V obecném případě funkce bere parametr nějakého typu A a v těle vrací jiný parametr nějakého typu B. Typ takové funkce budeme psát jako A -> B. Taková funkce může například být (λx::A . y::B) :: A -> B. Šipka v značení typu je, stejně jako samotná lambda, zprava asociativní.

Aplikace pak kontroluje, že pravá strana je stejného typu jako typ parametru funkce. Typ aplikace je pak typ těla aplikované lambdy. Pokud tomu tak není, jedná se o chybu a program je neplatný.

Jakmile máme nějaký typovaný Lambda program, můžeme se podívat na strukturu jeho typu. To budeme značit aplikací na speciální funkci :t (toto je mimochodem zapůjčeno z jazyka Haskell):

> :t (λx::A . (λy::B . x))
(λx::A . (λy::B . x)) :: A -> B -> A

> :t (λx::A . (λy::B . x)) a::A
((λx::A . (λy::B . x)) a::A) :: B -> A

> :t (λx::A . (λy::B . x)) a::A b::B
((λx::A . (λy::B . x)) a::A b::B) :: A

Takto je ale náš typový systém příliš krkolomný a explicitní. Často vůbec není třeba definovat typ parametru ve funkci a lze jej odvodit podle toho, jak používáme aplikace. Proto zavedeme i "typové proměnné", které budeme značit malým písmenem. Pokud někde neuvedememe typ explicitně, implicitně se doplní nová typová proměnná.

> :t x
x :: a
> :t (λx.y)
(λx.y) :: a -> b
> :t (λx.y::B)
(λx.y::B) :: a -> B

Jak ale s typy pracovat, když máme ve výrazu kombinace typů a typových proměnných? Vraťme se k Prologu, kde máme stejný problém, když máme v predikátu kombinaci proměnných a termů. Ten jsme řešili unifikací. A přesně tu stejnou unifikaci využijeme i zde.

> :t (λx.x)
(λx.x) :: a -> a
-- původně (a -> b), ale b se zunifikovalo na a; x v těle je typu a

> :t (λx.λy.x) c::T
((λx.λy.x) c::T) :: b -> T
-- původně (a -> b -> c), kde c = a, a = T, plus aplikace

Jestliže narazíme na aplikaci, můžeme při unifikaci odvodit, že levá strana musí být lambda. Nezapomeňme, že lambda je zprava asociativní.

> :t (λx.λy.x y)
(λx.λy.x y) :: (a -> b) -> a -> b
-- aplikace (x y) implikuje, že proměnná x je funkce typu (a -> b)
-- pak y v těle je typu a, vracíme typ b

> :t x y z
(x y z) :: d 
-- x musí být typu (a -> b) kvůli aplikaci y a b = (c -> d) kvůli aplikace z
-- pak x::(a -> c -> d), y::a, z::c a výsledek je typu d

> :t (λx.λy.x y) (λz::Z . z)
((λx.λy.x y) (λz::Z . z)) :: Z -> Z
-- typ (a -> b) je v tomto případě kvůli pravé straně aplikace (Z -> Z)

Odvození typu výrazu můžeme provést tak, že jej nejprve redukujeme, a potom odpovíme typem redukce. Vyplývá to z toho, jak jsme nadefinovali typ aplikace.

> (λx.λy.x y) (λa.λb::B . a)
 → (λy.(λa.λb::B . a) y)
 → (λy.λb::B . y)
-- vyhodnotili jsme výraz

> :t (λy.λb::B . y)
(λy.λb::B . y) :: y -> B -> y
-- redukovaná forma je snažší na vysvětlení typu
> :t (λx.λy.x y) (λa.λb::B . a)
((λx.λy.x y) (λa.λb::B . a)) :: y -> B -> y
-- při zjištění typu proběhla implicintě redukce

Může se též stát, že unifikace typů nebude možná. Pak vyhodnocení selže.

Přidání aritmetiky

Přidejme si do našeho typovaného lambda kalkulu nyní speciální typ, a to Int odpovídající přirozeným číslům. Dále mějme operace plus, minus, mul, div značící aritmetické operace na těchto číslech. Všechny tyto funkce jsou typu Int -> Int -> Int.

V době vyhodnocování tyto funkce budou dělat přesně to, co bychom od nich čekali, vrátí výsledek aritmetické operace. Nyní můžeme zkoušet vyhodnocovat Lambda programy s touto přidanou aritmetikou:

> :t plus (mul 2 3)
(plus (mul 2 3)) :: Int -> Int

> plus (mul 2 3) 5
 → plus 6 5
 → 11

> plus mul
Error: Couldn't match expected type 'Int'
                   with actual type 'Int -> Int -> Int'
-- první parametr plus musí být Int, ale mul je funkce

> :t (λx y z.plus (mul x y) z)
(λx y z.plus (mul x y) z) :: Int -> Int -> Int -> Int

> (λf x.f x x) plus
 → (λx.plus x x)

> :t (\f x.f x x)
((λf x.f x x)) :: (a -> a -> b) -> a -> b

> :t (λf x.f x x) plus
((λf x.f x x) plus) :: Int -> Int
-- V tomto případě je a = b = Int

Cvičení: Napište funkce succ(x) = x + 1, half(x) = x / 2.

Od lambda kalkulu k Haskellu

Jazyk Haskell z principů typovaného lambda kalkulu vychází, dokonce si z něj půjčuje část syntaxe. Tudíž si pomocí Haskellu, po mírných úpravách, můžeme pořídit lambda kalkulus. Musíme si však dát pozor na to, že zatímco Lambda kalkulu nevadí volné proměnné, Haskell si bude stěžovat.

Proměnné i funkce v Haskellu zůstavají jako slova, která začínají malým písmenem. Aplikace se stále znázorňuje mezerou. Pouze se liší syntaxe psaní lambdy, speciálně λ se nahrazuje \ a . je psaná jako ->.

My budeme používat GHC implementaci Haskellu, která má interaktivní mód schovaný pod příkazem ghci. Programy v jazyku Haskell mají příponu .hs. Načtení programu pak můžeme dělat, podobně jako u Prologu, dvěma způsoby.

První způsob je v interaktivním módu zavolat funkci :load s názvem souboru v uvozovkách. Druhý způsob je přidat název souboru jako parametr při spouštění interaktivního módu.

Standardní knihovna

Samozřejmě Haskell není tak holý, aby se s ním nedalo pořádně pracovat. Standardní knihovna Haskellu nám rovnou přidává základní typy a funkce, se kterými můžeme pracovat.

Ukažme si nejprve, jaké důležité typy máme k dispozici (seznam neobsahuje vše):

Pro číselné typy máme k dispozici standardní aritmetické a relační operátory. Pro typ Bool máme booleovské funkce. Pro uspořádané dvojce máme funkce fst a snd vracející první nebo druhý prvek. Seznamy mají standardních funkcí podstatně více, ty probereme později.

> 2 + 3
5

> True && False
False

> (5 * (6 - 2) + 1) * 2
42

> 5 : [1,4,6]
[5,1,4,6]

> 3 > 7
False

> (\x y -> 2 * x + y) 4 7
15

> fst (3, False)
3

Pojmenovanou funkci si v Haskellu můžeme vytvořit snadno, místo \ u lambdy napíšeme název a -> nahradíme =. Nepovinně taktéž můžeme před tím, než definujeme tělo funkce, definovat její typ. Může to pomoci najít chyby v programu.

double :: Integer -> Integer
-- tyto definice jsou si ekvivalentní:
double x = 2 * x -- přímočaré
double x = (*) 2 x -- syntaxe operátoru jako funkce
double = (\x -> 2 * x) -- stejná definice přes lambdu
double = (*) 2 -- částečná aplikace, zbývá jeden parametr

nonzero :: Integer -> Bool
nonzero x = x /= 0

> double 4
8

> nonzero (double 0)
False

> double (nonzero 3)
Error:
    • Couldn't match expected type ‘Integer’ with actual type ‘Bool’
    • In the first argument of ‘double’, namely ‘(nonzero 3)’
      In the expression: double (nonzero 3)
      In an equation for ‘it’: it = double (nonzero 3)

Syntaxe Haskellu nám umožňuje napsat definici funkce vícekrát, kde můžeme u parametrů být různě specifičtí. Haskell si pak při vyhodnocování zvolí tu nejspecifičtější variantu. Pokud jsou nejednoznačné, dostaneme vynadáno.

Na parametrech v definici funkce můžeme podobně, jako v Prologu, použít Pattern matching.

f :: Integer -> Integer
-- více definic podle specifičnosti parametru
f 0 = 10
f 1 = 5
f x = 20 + x

-- rekurzivní funkce
triangle :: Integer -> Integer
triangle 0 = 0
triangle x = x + triangle (x-1)

-- prohodíme pořadí prvků ve dvojici
swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

-- rozbal dvojici jako dva parametry pro funkci dvou parametrů a tu zavolej
paramsFromPair :: (a -> b -> c) -> (a, b) -> c
paramsFromPair f (x, y) = f x y
-- alternativně bez Pattern Matchingu
-- paramsFromPair f p = f (fst p) (snd p)

addFirst2 :: [Integer] -> Integer
-- použití pattern matching na rozbalení seznamu
addFirst2 (a:b:_) = a + b

-- Funkce, co bere jinou funkci
doFirst2 :: (Integer -> Integer -> Integer) -> [Integer] -> Integer
doFirst2 f (a:b:_) = f a b

-- nespecifikujeme typ, doplní se automaticky
-- nekonečný cyklus
nekonecne = 1 + nekonecne

> f (f 0)
30

> triangle 6
21

> paramsFromPair (-) (5, 3)
2

> paramsFromPair (-) (swap (3, 5))
2

> addFirst2 [3,6,7,2]
9

> addFirst2 [0]
*** Exception: Non-exhaustive patterns in function addFirst2
-- nedefinovali jsme pro krátké seznamy

> addFirst2 [1,1,nekonecne]
2
-- líné vyhodnocování nikdy nešáhne na nekonecne

> doFirst2 (*) [3,7]
21
-- f = násobení

> :t doFirst2 (*)
(doFirst2 (*)) :: [Integer] -> Integer
-- redukovaná aplikace

Cvičení: Napište sčítání jako rekurzivní funkci, kde použijeme pouze přičtení nebo odečtení o 1.

Cvičení: Napište funkci plati :: [Integer] -> Boolean, která vezme první tři prvky seznamu a, b, c a zkontroluje, že a + b == c.

Cvičení: Napište funkci platiObecne :: (Integer -> Integer -> Integer) -> (Integer -> Integer -> Boolean) -> [Integer] -> Boolean, která vezme funkce operace a relace, a první tři prvky seznamu a, b, c; a zkontroluje, že platí relace (operace a b) c. Pak pomocí platiObecne napište plati.

Dále ke specifikaci funkce můžeme použít stráže. Stráž umožňuje vybrat způsob vyhodnocení podle funkce vracející Boolean. K tomuto účelu existuje funkce otherwise = True pro syntaktický cukr. Ukažme si její použití na příkladu:

-- signum(x) = -1 pro záporná, 0 pro nulu a 1 pro kladná
signum :: Integer -> Integer
signum x | x < 0     = -1
         | x > 0     = 1
         | otherwise = 0

> signum 5
1

V jazyku Haskell, podobně jako v Pythonu, závisí na odsazení řádku. Všechny stráže na nových řádcích musí být odsazené. Nejlepší je pro čitelnost je zarovnávat pod sebou.

Cvičení: Napište funkci faktorial :: Integer -> Integer která počítá faktoriál.

Cvičení: Napište funkci nonempty :: [a] -> Bool, která pro seznam odpovídá, zda obsahuje nějaký prvek.