Líně, čistě, funkcionálně

Práce SOČ, obor 18: Informatika

Jan Špaček

Programovací jazyky

  • C
  • C++
  • Java
  • Python
  • Fortran
  • CoffeeScript
  • JavaScript
  • Perl
  • Scala
  • Ruby
  • C#
  • Pascal
  • Befunge
  • PHP

Imperativní

Imperativní jazyky

Výpočty se provádí vykonáváním operací, které mění stav programu (uložený v paměti).

Algoritmy jsou sekvence kroků.

Euklidův algoritmus

Určení největšího společného dělitele dvou čísel — menší číslo odečítáme od většího dokud se nedostaneme k nule.

Nestrukturovaný jazyk

10 INPUT A,B
20 IF B=0 THEN GOTO 80
30 IF A>B THEN GOTO 60
40 LET B=B-A
50 GOTO 20
60 LET A=A-B
70 GOTO 20
80 OUTPUT A
90 END

Strukturovaný jazyk (C)

int gcd(int a, int b)
{
  while(b != 0) {
    if(a > b) {
      a = a - b;
    } else {
      b = b - a;
    }
  }
  return a;
}
.

Alternativy

Imperativní přístup k programování je dnes dominantní, není ale jediný.

Haskell

Výpočty se provádí vyhodnocováním výrazů.

Algoritmy jsou vyjádřeny pomocí funkcí.

Funkce, která zdvojnásobí argument:

double x = x + x
double 3 = 6

Řešení kvadratické rovnice:

quadratic a b c
 | d < 0     = []
 | d == 0    = [-b/(2*a)]
 | otherwise = [(-b+sqrt d)/(2*a),(-b-sqrt d)/(2*a)]
 where d = b^2 - 4*a*c
 
 quadratic 2 14 24 = [-3.0,-4.0]

Funkce jsou hodnoty, lze je tedy předávat jiným funkcím nebo vracet jako výsledek: funkce vyššího řádu.

map double [2,3,-4,1] = [4,6,-8,2]
filter odd [0,4,1,6,3] = [1,3]

Skládání funkcí

(f . g) x = f (g x)
map (negate . abs) [5,0,-3,2] = [-5,0,-3,-2]

Mezi nejčastěji používané datové typy patří seznamy

[1,2,3] = 1:2:3:[] = 1:(2:(3:[]))
['Ž', 'e', 'l', 'v', 'a'] = "Želva"

[1..5] = [1,2,3,4,5]
[3,5..11] = [3,5,7,9,11]
map f [] = []
map f (x:xs) = f x : map f xs

map double [1,2,3] =
  map double (1:(2:(3:[]))) =
  double 1 : map double (2:(3:[])) =
  double 1 : double 2 : map double (3:[]) =
  double 1 : double 2 : double 3 : map double [] =
  double 1 : double 2 : double 3 : [] =
  2 : 4 : 6 : [] =
  [2,4,6]

Každá funkce má právě jeden argument — funkce s více argumenty jsou curryfikované.

max 5 4 = 5
(max 5) 4 = 5

max :: Int -> Int -> Int
max 5 :: Int -> Int
max 5 4 :: Int

Funkce tedy můžeme částečně aplikovat — zavolat je s menším množstvím argumentů a získat tak novou funkci.

map (max 5) [-2,8,-6,3,7] = [5,8,5,5,7]
map (max 5 . abs) [-2,8,-6,3,7] = [5,8,6,5,7]

Operátory jsou funkce:

5 + 4 = 9
(+) 5 4 = 9
map ((+) 3) [1,0,2] = [4,3,5]
(* 2) 3 = 6
(12 /) 3 = 4
map (/ 3) [3,12,6] = [1,4,2]
filter ((< 40) . (^2)) [2,5,7,3,9] = [2,5,3]

Všechny hodnoty jsou neměnné.

Výsledek funkce závisí pouze na jejích argumentech.

Jediný efekt, který funkce má, je získání výsledku.

Referenční transparentnost

Zavoláme-li stejnou funkci dvakrát se stejným argumentem, dostaneme stejný výsledek.

Nezávisí na pořadí vyhodnocování.

V imperativních jazycích funkce nejsou referenčně transparentní, protože můžou mít vedlejší efekty:

def double(x)
  x + x
end

ary = [1,2,3]
double ary.pop != ary.pop + ary.pop

Pořadí vyhodnocování je zásadní.

Líné vyhodnocování

Hodnoty výrazů se zjišťují až když jsou zapotřebí.

O pořadí vyhodnocování se tedy stará jazyk, nikoli programátor.

Je snadné používat nekonečné struktury:

take 6 [1,3..] = [1,3,5,7,9,11]
takeWhile (< 100) (map (^2) [1..]) = [1,4,9,16,25,36,49,64,81]

Fibonacciho posloupnost:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

fn = fn-1 + fn-2

Fibonacciho posloupnost jako seznam:

fibs = 1:1:zipWith (+) fibs (tail fibs)
fibs = [1,1,2,3,5,8,13,...

Funkce zipWith a tail ze standardní knihovny:

zipWith (*) [2,3,4] [-1,2,0] = [-2,6,0]
tail [1,2,3,4] = [2,3,4]
fibs =
zipWith (+)
<
>

Prvočísla

Číslo x je prvočíslo právě tehdy, pokud pro všechna prvočísla p, p2 ≤ x, je zbytek po dělení x / p nenulový.

primes = 2:filter isPrime [3,5..]
isPrime x = all ((/= 0) . (mod x)) ps
  where ps = takeWhile ((< x) . (^2)) primes
primes = [2,3,5,7,9,11,13,17,19,23,25,29,31,37...

Silný typový systém

Haskell je staticky typovaný, většinu typů ale odvozuje.

Typování v imperativních jazycích je obvykle statické nebo dynamické.

Staticky typovaný jazyk (C++)

Programátor u všech proměnných a funkcí uvádí typy.

std::vector<int> selectLarger(std::vector<int>& xs, int limit)
{
  std::vector<int>::const_iterator end = xs.end();
  std::vector<int> result;

  for(std::vector<int>::const_iterator it = result.begin();
    it != end; ++it) {
      if(*it > limit) {
        result.push_back(*it);
      }
  }

  return result;
}
  • + Kompilátor odhalí velkou část chyb při překladu
  • - Programátor musí psát všechny typy
  • - Polymorfismus je netriviální (šablony, ...)

Dynamicky typovaný jazyk (Ruby)

Typy (třídy) jsou přiřazeny hodnotám, nikoli proměnným.

def select_larger(ary, limit)
  result = []
  ary.each do |elem|
    if elem > limit
      result.push elem
    end
  end
  return result
end

Tato metoda bude fungovat pro všechny hodnoty (objekty), které poskytují požadované metody.

  • + Polymorfismus (kachní typování)
  • + Není třeba deklarovat typy
  • - Typové chyby se projeví až za běhu

Haskell je staticky typovaný — typy se kontrolují při překladu.

  • + Typové chyby se odhalí včas
  • + Kompilátor může optimalizovat
  • + Typy slouží jako dokumentace

Naprostou většinu typů ale odvodí

  • + Programátor zapisuje jen důležité typy
  • + Odvozené typy jsou vždy „nejlepší“ (nejobecnější)
  • + Typový systém má za sebou propracovanou teorii
map :: (a -> b) -> [a] -> [b]
filter :: (a -> Bool) -> [a] -> [a]
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
(.) :: (b -> c) -> (a -> b) -> (a -> c)
max :: Ord a => a -> a -> a
(+) :: Num a => a -> a -> a
max :: Ord a => a -> a -> a
max 4.53 1.09 = 4.53
max 'e' 'x' = 'x'
max "nekalý" "nekalost" = "nekalý"
filter :: (a -> Bool) -> [a] -> [a]
isUpper :: Char -> Bool
even :: Integral a => a -> Bool

filter isUpper "Středoškolská Odborná Činnost" = "SOČ"
filter even [2,3,5,10,4,-3] = [2,10,4]
'a' + 3
max "šalba" 42
filter odd [1.3,2.45,-0.3]

Typový systém zaručuje typovou bezpečnost programu.

Žádné Segmentation fault, NullPointerException ani NoMethodError.

Přeložený program obvykle funguje napoprvé.

Funkcionální jazyk

  • + Elegantní vyjádření algoritmů
  • + Znovupoužitelnost kódu
  • + Dokazování správnosti funkcí

Líné vyhodnocování

  • + O pořadí výpočtů se stará jazyk
  • + Snadná práce s nekonečnými daty
  • + Zvýšená modularita

Typový systém

  • + Nejsilnější typový systém
  • + Absolutní typová bezpečnost
  • + Polymorfismus

Líně, čistě, funkcionálně

Užití funkcionálního programovacího jazyka Haskell k řešení úloh Ústředních kol ČR Soutěže v programování

Řešené úlohy

  1. Krunimír — želví grafika
  2. Bílá paní — hledání cesty v bludišti

Krunimír

Želva se pohybuje po písku podle uživatelem dodaného programu a kreslí za sebou stopu.

define square(side) {
  pen(1)
  repeat(4) {
    forward(side) right(90)
  }
  pen(0)
}

define row() {
  repeat(4) {
    square(114) forward(163) 
  }
  forward(-652) right(90)
  forward(163) left(90)
}

forward(301) left(90)
forward(301) right(180)
repeat(4) { row() }
define koch(n) {
  if(n) {
    koch(n-1)
    left(60) koch(n-1)
    right(120) koch(n-1)
    left(60) koch(n-1)
  }
  if(1-n) {
    forward(2)
  }
}

pen(0) forward(-175) 
left(90) forward(250) 
pen(1)
right(120) koch(5)
right(120) koch(5)
right(120) koch(5)

Bílá paní (Banshee)

Hledání nejkratší cesty v bludišti, je potřeba projít co nejméně zdmi a bílá paní se musí vyhnout všem zvědům.

<
>

Cíl práce

Cílem práce bylo demonstrovat použití Haskellu na netriviálních úlohách a dokázat, že funkcionální jazyk lze použít i v prostředí, kde se počítá s jazykem imperativním.

Výsledek

?
Jan Špaček Wichterlovo gymnázium, Ostrava-Poruba http://honzasp.github.com/funsp
?