Skip to content

Instantly share code, notes, and snippets.

@jiribenes
Created March 31, 2022 14:14
Show Gist options
  • Save jiribenes/00e741edf14d185c4da22bb2d74d8da7 to your computer and use it in GitHub Desktop.
Save jiribenes/00e741edf14d185c4da22bb2d74d8da7 to your computer and use it in GitHub Desktop.
Cvičení z Neprocedurálního programování - 7

Lambda kalkul

Na začátku cvičení jsem připomněl lambda kalkul, což je výpočetní model, který obsahuje tři typy výrazů:

E ::= \x. E   "lambda abstrakce / defnice funkce"
    | E E     "aplikace funkce"
    | x       "proměnná"

a jedno výpočetní pravidlo: (\x. E) F se spočítá dosazením F za všechna x v E, symbolicky F [ x := E ].

Haskell

Pracovali jsme s Haskellem s pomocí Haskell Language Serveru ve VSCode. Samotný zdrojový kód může být interpretován pomocí GHCi, či kompilován pomocí GHC.

Příklad použití:

shell# ghci mujsoubor.hs
ghci> 1 + 1
2
ghci> :reload
soubor reloadnut (načteny změny)
ghci> 1 + ctyricetDva
43
-- jednořádkový komentář
{-
více
řádkový
komentář
-}
-- Výrazy se v Haskellu píšou s malým písmenkem na začátku.
-- Na levé straně je jméno hodnoty. Používáme =, abychom definovali výraz pod nějakým jménem jako:
ctyricetDva = 42
pozdrav = "Ahoj"
-- Funkce jsou v Haskellu také hodnoty
prictiJednicku = \x -> x + 1
-- Ekvivalentní zápisy z jiných jazyků:
-- Python: prictiJednicku = lambda x: x + 1
-- C#: Func<int, int> prictiJednicku = x => x + 1;
-- C++: auto prictiJednicku = [](auto x) -> auto { return x + 1 }
-- Funkce více argumentů můžeme udělat tak, že uděláme funkci,
-- která vrátí funkci
prictiJednickuASecti = \x -> (\y -> prictiJednicku x + prictiJednicku y)
-- Poznámka: Tahle ^ závorka není nutně potřeba!
dvakrat = \x -> x * 2
-- Aplikace funkce je _zleva_ asociativní a má velmi vysokou precedenci:
-- >>> dvakrat (prictiJednicku 42)
-- C++> dvakrat(prictiJednicku(42))
-- 86
-- >>> dvakrat prictiJednicku 42
-- to samé jako
-- >>> ((dvakrat prictiJednicku) 42)
-- C++> (dvakrat(prictiJednicku))(42)
-- (tady nedává smysl)
-- Definice funkce je tak častá, že Haskell má i syntaktický cukr
-- tedy místo `dvakrat = \x -> x * 2` stačí napsat:
dvakrat' x = x * 2
-- Podobně pro další funkce:
prictiJednicku' x = x + 1
prictiJednickuASecti' x y = prictiJednicku x + prictiJednicku y
-- Obecně:
-- >>> foo x y = ...
-- je syntaktický cukr pro
-- >>> foo = \x -> \y -> ...
-- Tedy definice funkce vypadá takhle:
-- <název funkce> <arg1> <arg2> ... <argN> = <tělo funkce>
-- Funkce se vyhodnocují stejně jako v lambda kalkulu.
-- Více viz předchozí cvičení (hezky jsem to tam rozepsal...)
ctyricetCtyri = prictiJednicku (prictiJednicku ctyricetDva)
{-
Příklad vyhodnocení:
ctyricetCtyri = (\x -> x + 1) (prictiJednicku ctyricetDva) [ vložíme definici `prictiJednicku` ]
= ((prictiJednicku ctyricetDva) + 1) [ dosadíme x := prictiJednicku ctyricetDva ]
= (((\x -> x + 1) ctyricetDva) + 1) [ vložíme definici `prictiJednicku` ]
= ((ctyricetDva + 1) + 1) [ dosadíme x := ctyricetDva ]
-}
-- Obvod obdélníku:
obvod a b = 2 * (a + b)
-- Obsah obdelniku
obsah a b = a * b
-- Každý operátor je funkce, pokud jej uzávorkujeme
foo = 5 + 10
foo' = (+) 5 10
-- Naopak z binárních funkcí můžeme udělat binární operátory
-- pomocí backticků (znaku `)
bar = mod 10 3 -- funkce mod je modulo
bar' = 10 `mod` 3
-- Typicky se tahle notace používá pro funkce `mod` (modulo)
-- a funkci `div`.
{-
Každé funkci můžeme dát jen menší počet argumentů než požaduje.
Pokud má funkce N argumentů a my ji zavoláme s K argumenty,
pak dostaneme novou funkci, která bere (N - K) argumentů.
-}
-- N = 3
sectiTri x y z = x + y + z
-- Vzpomeňte si, že tohle je jen syntaktický cukr pro:
sectiTri' = \x -> \y -> \z -> x + y + z
-- K = 2
-- tahle funkce bere (N - K) = 1 argument
prictiJednicku = sectiTri 0 1
{-
prictiJednicku = sectiTri 0 1
= (\x -> \y -> \z -> x + y + z) 0 1 [ vložení definice sectiTri ]
= (\x -> (\y -> \z -> x + y + z)) 0 1 [ uzávorkování ]
= (\y -> \z -> 0 + y + z) 1 [ dosazení x := 0 ]
= (\y -> (\z -> 0 + y + z)) 1 [ uzávorkování ]
= (\z -> 0 + 1 + z) [ dosazení y := 1 ]
-}
-- Každá funkce bere jen jeden argument.
-- Jen potenciálně vrací další funkci... :)
tri = prictiJednicku 2
{-
tri = (\z -> 0 + 1 + z) 2
= 0 + 1 + 2
= 3
-}
-- Občas si chceme pořídit pomocné definice:
-- `let` <promenna> = <výraz> `in` <výraz>
sectiTri x y z =
let tmp = x + y
in tmp + z
-- Tahle ^ varianta je sama o sobě výraz (má hodnotu).
-- Dá se tedy psát i něco jako
-- >>> 2 * (let a = 42 in a + 10) + 7
-- alternativně
sectiTri' x y z = tmp + z
where
tmp = x + y
-- Osobně spíš doporučuji druhý způsob :)
-- Haskell je jazyk se statickými typy.
-- Nicméně je ale schopen pro každý výraz najít nejobecnější typ i bez naší pomoci!
-- Typy mají velké písmenko na začátku.
-- Pokud se chcete zeptat GHCi na typ, použijte `:type <výraz>`.
-- Pokud vám GHCi vrátí moc složitý typ (tj. obsahuje, napište `:type +d <výraz>`
pozdrav :: String
pozdrav = "Ahoj!"
-- Pokud se zeptáte GHCi, tak vám řekne typ `pozdrav`u
-- >>> :t pozdrav
-- String
ctyricetDva :: Int
ctyricetDva = 42
--- >>> :t ctyricetDva
-- Int
-- `prictiJednicku` je funkce, která vezme Int a vrátí Int
prictiJednicku :: Int -> Int
prictiJednicku = \x -> x + 1
-- `sectiTri` je funkce, která vezme Int a vrátí (Int -> (Int -> Int))
sectiTri :: Int -> (Int -> (Int -> Int))
sectiTri x y z = x + y + z
-- Z příkladu výše jde vidět, že šipka `->` je _zprava_ asociativní!
-- Tedy se její typ dá zapsat bez závorek jako:
sectiTri' :: Int -> Int -> Int -> Int
sectiTri' x y z = x + y + z
-- Zpravidla píšeme typy pro top-level funkce a deklarace
-- jako formu dokumentace. :)
-- Samozřejmě to není potřeba, protože je Haskell natolik chytrý,
-- že ty typy odvodí i sám, ale dokumentace se hodí.
-- Navíc často se v Haskellu programuje tak, že nejdříve napíšete všechny typy
-- a až potom to naprogramujete...
-- Dvojice (pairs) se píšou v Haskellu následovně:
-- Každý prvek dvojice může mít různý typ!
dvojice = (42, "Ahoj!")
-- >>> :t dvojice
-- (Int, String)
-- Následující příklad ukazuje základní použití všech věcí, které jsme si zatím ukazovali:
-- | Vyřeší kvadratickou rovnici tvaru `ax^2 + bx + c = 0`,
-- vrací obě řešení jako pár (dvojici)
vyresKvadratickouRovnici :: Double -> Double -> Double -> (Double, Double)
vyresKvadratickouRovnici a b c = (reseni (+), reseni (-))
where
diskriminant = b^2 - 4 * a * c
-- `reseni` je funkce, která bere další funkci jako svůj argument
reseni op = (-b `op` sqrt diskriminant) / (2 * a)
-- Cvičení: Podívejte se na funkci výše a pochopte jak funguje.
-- Nápovědou vám budiž všechny předchozí soubory!
% Tento soubor obsahuje jednoduchý typový systém
% pro lambda kalkul (takzvaný STLC) s inty a booly navíc.
% https://en.wikipedia.org/wiki/Simply_typed_lambda_calculus
% Je to takový zjednodušený základ pro typový systém Haskellu.
?- set_prolog_flag(occurs_check, true).
% ^ Tahle vlajka zařídí to, že Prolog selže při unifikaci druhu `X = f(X)`.
% To se nám hodí, aby se Prolog nesnažil najít řešení pro rovnici typu `A = A -> B`
% (To by se mohlo stát u výrazu jako `\x -> x x`)
% Vyhledávání v asociovaném seznamu
% to jest seznamu, který v sobě má (key, value) dvojice
lookup([(X,A)|_], X, A).
lookup([(Y,_)|T], X, A) :- \+ X = Y, lookup(T, X, A).
% `typ/4` najde typ daného výrazu
% a prochází až do hloubky dané Fuel
% což je číslo v Peanově aritmetice
% typ(+LookupDictionary, ?Expression, ?Type, +Fuel)
% aplikace E na F má typ B pokud
% ... E má typ A -> B
% ... F má typ A
typ(G, app(E, F), B, s(N)) :-
typ(G, E, A -> B, N),
typ(G, F, A, N).
% funkce \x -> E má typ A -> B pokud
% ... E má typ B v prostředí, ve kterém má x typ A
typ(G, lam(var(X), E), A -> B, s(N)) :-
typ([(X, A) | G], E, B, N).
% x má typ A, pokud má tento typ v prostředí
typ(G, var(X), A, s(_)) :-
lookup(G, X, A).
% čísla mají typ int
typ(_, X, int, s(_)) :-
integer(X).
% konstanty fls, tru mají typ bool
typ(_, fls, bool, s(_)).
typ(_, tru, bool, s(_)).
% A + B má typ int, pokud
% ... A má typ int
% ... B má typ int
typ(_, A + B, int, s(N)) :-
typ(G, A, int, N),
typ(G, B, int, N).
% Cvičení: Přidejte si ifzero(X, Then, Else), která má typ A, pokud:
% ... X má typ int
% ... Then má typ A
% ... Else má také typ A
% Překonvertuje Prologovská čísla na Peanova
into_peano(0, z).
into_peano(N, s(P)) :-
N > 0,
N1 is N - 1,
into_peano(N1, P).
% Vyrobí výraz dle typu, omezeno hloubkou dle Fuel
synth(Expr, Type, Fuel) :-
into_peano(Fuel, N),
typ([], Expr, Type, N).
% Zjisti typ pro daný výraz
infer(Expr, Type) :-
into_peano(10000, N), %
typ([], Expr, Type, N).
%
% P Ř Í K L A D Y :
%
% najdi všechny výrazy hloubky < 4 typu int
% > synth(E, int, 4).
%
% zjisti typ T pro \x -> 2 + x
% > X = var(x), infer(lam(X, 2 + X), T).
%
% najdi všechny výrazy hloubky < 5 a typu bool -> bool -> int
% > synth(E, bool -> bool -> int, 5).
-- Dále jsme si ukazovali "součtové typy":
-- Barva je buď červená, nebo zelená, nebo modrá
data Barva = Cervena | Zelena | Modra
barvaToString :: Barva -> String
barvaToString barva =
case barva of -- rozeber možnosti `barva`
Cervena -> "Cervena" -- ... pokud je červená
Zelena -> "Zelena" -- ... pokud je zelená
Modra -> "Modra" -- ... pokud je modrá
-- >>> barvaToString Modra
-- "Modra"
jeBarvaCervena :: Barva -> Bool
jeBarvaCervena barva =
case barva of
Cervena -> True
_ -> False -- default = False
-- >>> jeBarvaCervena Zelena
-- False
-- Pattern matching v argumentu funkce
-- jde udělat i na top-level úrovni!
barvaToString' :: Barva -> String
barvaToString' Cervena = "Cervena"
barvaToString' Zelena = "Zelena"
barvaToString' Modra = "Modra"
jeBarvaCervena' :: Barva -> Bool
jeBarvaCervena' Cervena = True
jeBarvaCervena' _ = False -- default = False
-- Intuitivně si můžeme představovat, že:
-- data Int = ... | -2 | -1 | 0 | 1 | 2 | ...
-- data Char = 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | ...
-- data Bool = True | False
-- [Poznámka: Bool je takhle _fakt_ definován :D]
fibonacci :: Int -> Int
fibonacci 1 = 0
fibonacci 2 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)
-- >>> fibonacci 10
-- 34
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment