jiribenes/1-jsonparser.prolog Secret

## 1-jsonparser.prolog
% Občas se nám stává, že náš program komunikuje s okolním světem.
% Parsery jsou dobrým prostředkem, jak jednoduše a rychle načíst nějaký string.

% Chceme nejdříve naparsovat následující gramatiku:
% A = λ             (prázdný string)
% A = a | A
% Tedy A je jazyk obsahující všechna slova { a^n | n číslo }

% V Prologu se to dá zapsat jako:
as --> [].
as --> [a], as.

% Reálně Prolog přidá automaticky dva argumenty takovýmto funkcím
% - jeden pro "z čeho chceme parsovat"
% - druhý pro "co nám zbývá naparsovat"
% Tedy výše uvedené `as` se dá napsat jako:
as_([], []).
as_(Znaky, ZbyleZnaky) :-
  Znaky = [ a | NoveZnaky ],
  as_(NoveZnaky, ZbyleZnaky).


% Takhle by vypadal parser pro nějaký počet mezer...
pwhitespace --> [].
pwhitespace --> [' '], pwhitespace.

% Tak si udělejme parser pro JSON! :)

% Top-level funkce vezme string a vrátí hodnotu
json_parse(String, V) :-
    % Převede String na seznam znaků
    string_chars(String, SeznamZnaku),

    % zavolá "naparsuj JSON" tak, aby ti nezbyly znaky.
    pjson(V, SeznamZnaku, []).

% JSON = Null | Bool | Seznam | String | Int
pjson(V) -->
    pnull(V);
    pbool(V);
    pseznam(V);
    pstring(V);
    pint(V).

% Null = n u l l
pnull(nic) --> [n, u, l, l].

% Bool = t r u e | f a l s e
pbool(ano) --> [t,r,u,e].
pbool(ne) --> [f,a,l,s,e].

% Seznam = [ ]
% Seznam = [ Hodnoty ]
% Hodnoty = Json
% Hodnoty = Json , Hodnoty
pseznam([]) --> ['[', ']'].
pseznam(V) --> ['['], pmanyvalues(V), [']'].

pmanyvalues([V]) --> pjson(V).
pmanyvalues([V|Vs]) -->
    pjson(V),
    [','],
    pmanyvalues(Vs).

% String = " Chary "
pstring(str(Chars)) --> ['"'], pchars(Chars), ['"'].

% Chary = ''
% Chary = Char Chary    (kde Char není dvojitá uvozovka)
pchars('') --> [].
pchars(V)  -->
    [C],
    { C \= '"' },              % tady pomocí `{ výraz }` voláme obyčejnou Prologovou funkci
    pchars(Cs),
    { atom_concat(C, Cs, V) }. % spojí dohromady atomy

% Inty
pint(int(V)) -->
    [Digit],
    { atom_number(Digit, AtomDigit) }, % Převede znak na číselný atom
    pint2(V, AtomDigit).

% Tady používáme akumulátor A na udržování mezivýsledku
pint2(A, A) --> [].
pint2(V, A) -->
    [Digit],
    {
      atom_number(Digit, AtomDigit),
      A1 is A * 10 + AtomDigit
    },
    pint2(V, A1).

% Pozor, že parser neřeší whitespace.
% Pokud chcete, aby jej řešil, použijte ve vhodných místech `pwhitespace`.

## 2-arithparser.prolog
% Parser aritmetických výrazů

% pInteger naparsuje číslo
% víceméně stejné jako v předchozím případě.

pInteger(I) --> pIntegerInner(I, 0).

pIntegerInner(I, A) --> pIntegerAtLeastOne(I, A); { I = A }.
pIntegerAtLeastOne(I, A) --> pNextDigit(I, A).

pNextDigit(I, A) -->
    [Digit],
    {
      atom_number(Digit, N),
      A1 is 10 * A + N
    },
    pIntegerInner(I, A1).

% Top-level parser pro výrazy
% Expr = Add
pExpr(V) --> pAdd(V).

% Sčítací výrazy mají následující gramatiku:
% Add = Mul + Add
% Add = Mul - Add
% Add = Mul
pAdd(M + A) --> pMul(M), ['+'], pAdd(A).
pAdd(M - A) --> pMul(M), ['-'], pAdd(A).
pAdd(A) --> pMul(A).

% Násobící výrazy mají následující gramatiku:
% Mul = Simple * Mul
% Mul = Simple / Mul
% Mul = Simple
pMul(A * B) --> pSimple(A), ['*'], pMul(B).
pMul(A / B) --> pSimple(A), ['/'], pMul(B).
pMul(A) --> pSimple(A).

% Jednoduché výrazy mají následující gramatiku
% Simple = ( Expr )
% Simple = Integer
pSimple(V) --> pInteger(V).
pSimple(V) --> ['('], pExpr(V), [')'].

% Pro zajímavost, takhle vypadá `pSimple` v "obyčejné" Prologové notaci...
% pSimple(V, SeznamCharu, ZbyleChary) :-
%     SeznamCharu = ['(' | NovySeznamCharu],
%     pExpr(V, NovySeznamCharu, ZbyleCharyZExpr),
%     ZbyleCharyZExpr = [ ')' | ZbyleChary ].

% Touto funkcí můžeme naparsovat aritmetický výraz
expr_parse(String, Repr) :-
    string_chars(String, Chars),
    pExpr(Repr, Chars, []).

## 3-lambda.md

      
    Raw
  

              3-lambda.md
            
          
    Lambda kalkul

Jednoduchý výpočetní model, který je Turingovsky úplný.
Má jen tři konstrukty:

proměnné -- a, b, c, ...
aplikace výrazů -- (E F) (pozor, je zleva asociativní)
lambda abstrakci (vytvoření nové funkce) -- (\x. E)
Dále budu označovat proměnné malými písmenky a výrazy velkými písmenky...

K tomu má jedno vyhodnocovací pravidlo ⇝:
(\x. E) F ⇝ E [ x := F ]

Slovy: pokud aplikujeme funkci s argumentem x vracející E na výraz F,
dostaneme výraz E, ve kterém všechny výskyty x nahradíme za F.
Dodejme, že funkce jsou ekvivalentní, pokud jen stačí přejmenovat proměnné,
aby byly identické.
Příklad vyhodnocení

Konstanta dosazená do funkce

Zkusme vyhodnotit následující výraz:
(\x. x) c

pro nějakou konstantu c.
Očividně je ta funkce vlevo identita --- vrátí přímo to, co dostane.
Naše intuice nám tedy napovídá, že bychom měli dostat zpátky zase c.
Použijeme tedy vyhodnocovací pravidlo výše:
(\x. E) F

(\x. x) c

a máme dostat E [x := F], což je v našem případě x [x := c].
Tedy nám vyjde c a jsme spokojeni :)
Funkce dosazená do funkce

Mějme identitu aplikovanou na identitu:
(\x. x) (\y. y)

Použijeme vyhodnocovací pravidlo výše:
(\x. E)    F

(\x. x) (\y. y)

a máme dostat E [x := F], což je v našem případě x [x := (\y. y)].
Tedy nám vyjde (\y. y).
Jak si pořídit funkce více argumentů?

Všimněte si, že máme jen funkce s jedním argumentem.
Co kdybychom chtěli argumentů víc?
Funkci dvou argumentů můžeme vyrobit následovně:
Vezmeme funkci s jedním argumentem x, která vrátí funkci s jedním argumentem y,
která teprve vrátí "tělo" funkce E: \x. (\y. E).
Často se díky této vlastnosti píše dle výrazu výše jen zkráceně jako \x y. E.
Aplikace je asociativní zleva

Abychom mohli psát hezky f x y s významem f(x, y),
pak dle výše uvedeného musí být aplikace nutně asociativní zleva!
Tedy nejprve se aplikuje f na x a až potom se výsledek aplikuje na y.
Zapsáno znaky: f x y == (f x) y.
Reprezentace v Prologu

Například:
% term(+LambdaKalkulovyTerm) určuje, jestli je daný lambda kalkulový term validní
term(var(X)).
term(lam(X, E)) :- term(E).
term(app(A, B)) :- term(A), term(B).
Výraz (\x. x) (\y. y) pak můžeme napsat jako app(lam(x, var(x)), lam(y, var(y))) :)
Reprezentace čísel

Tohle je jen bonus!
Čísla můžeme reprezentovat podobně jako v Prologu / v Teorii množin.
Jako nulu prohlásíme výraz (\s. (\z. z)), ve zkrácené notaci tedy (\s z. z)
Jako jedničku výraz (\s. (\z. s z)), ve zkrácené notaci (\s z. s z).
Jako dvojku výraz (\s z. s (s z)) a tak dále...
Matematicky je číslo n funkce, která vezme funkce s a z
a aplikuje funkci s n-krát na funkci z.
Vypadá to skoro, jako kdyby z = 0 a s = (+1) (přičtení jedničky).
Také jsme si ukazovali funkci (\n. (\s z. s (n s z))), která k danému číslu přičte jedničku
(reálně je to successor funkce/funkce vracející následníka daného čísla)
a zkoušeli jsme ji zavolat na jedničku a ukázali jsme si, že to je dvojka.
Pokud tedy jako ⟦0⟧ označím nulu a jako S označím funkci následníka výše, pak:
    ⟦0⟧ = λ s z . z
    
    ⟦1⟧ = ⟦S0⟧
    = (λ n . λ s z . s (n s z))(λ s′ z′ . z′)
    ⇝ λ z s . s ((λ s′ z′ . z′) s z)
    ⇝ λ z s . s ((λ z′ . z′) z)
    ⇝ λ z s . s z
    
    ⟦2⟧ = ⟦SS0⟧
    = (λ n . λ s z . s (n s z))((λ n′ . λ s′ z′ . s′ (n′ s′ z′))(λ s″ z″ . z″))
    ⇝ (λ n . λ s z . s (n s z))(λ s′ z′ . s′ ((λ s″ z″ . z″) s′ z′))
    ⇝ (λ n . λ s z . s (n s z))(λ s′ z′ . s′ z′)
    ⇝ λ z s . s ((λ s′ z′ . s′ z′) s z)
    ⇝ λ z s . s (s z)

Cvičení: Naprogramujte součet dvou čísel!
Rozmyslete si jak to děláte induktivně v Prologu a jen to převeďte do lambda kalkulu :)
Tedy rozmyslete si, že musí platit:
m + 0 = m
m + Sn = S(m + n)

a napište funkci PLUS, která vezme dvě čísla a sečte je.
Obecně se podobně dají reprezentovat i jiné konstrukce jako if a booleany, nebo spojové seznamy,
nebo dvojice. Více detailů se dá najít na wiki: https://en.wikipedia.org/wiki/Church_encoding
Něčím podobným se ale budeme zabývat příště rovnou v Haskellu...

  
## 4-callbywhat.md

      
    Raw
  

              4-callbywhat.md
            
          
    Vyhodnocovací strategie

Mějme v Pythonu následující kus kódu:
def square(x):
  return x * x

vysledek = square(1 + 2)
Obecně jsou dva způsoby jak vyhodnotit výsledek:

vyhodnotit nejdříve argumenty, pak funkci
vyhodnotit nejdříve funkci, pak argumenty

Call-by-value

Python standardně vyhodnocuje nejdříve argumenty:
vysledek ⇝ square(1 + 2) # vyhodnotíme argument 
         ⇝ square(3)     # dosadíme definici `square`
         ⇝ 3 * 3         # roznásobíme
         ⇝ 9

Call-by-name

Ale mohli bychom vyhodnocovat i nejdříve funkci jako takovou:
vysledek ⇝ square(1 + 2)      # dosadíme definici `square`
         ⇝ (1 + 2) * (1 + 2)  # sečteme vlevo  
         ⇝ 3 * (1 + 2)        # sečteme vpravo
         ⇝ 3 * 3              # roznásobíme

K čemu se může hodit call-by-name?

Tohle asi vypadá, že k ničemu není, ale uvažte následující funkci:
def vyhodError():
  raise ValueError("ohno, error")

def vratDruhyArgument(x, y):
  return y
a zavolejme vratDruhyArgument(vyhodError(), 42).
Call-by-value

vratDruhyArgument(vyhodError(), 42) ⇝ <vyhodí error> # vyhodnocení levého argumentu

Tohle vždycky vyhodí error!
Call-by-name

vratDruhyArgument(vyhodError(), 42) ⇝ 42 # z definice `vratDruhyArgument`

Ale tohle ten error nevyhodí nikdy, ani si jej vlastně nevšimne! :O
	% Občas se nám stává, že náš program komunikuje s okolním světem.
	% Parsery jsou dobrým prostředkem, jak jednoduše a rychle načíst nějaký string.

	% Chceme nejdříve naparsovat následující gramatiku:
	% A = λ (prázdný string)
	% A = a \| A
	% Tedy A je jazyk obsahující všechna slova { a^n \| n číslo }

	% V Prologu se to dá zapsat jako:
	as --> [].
	as --> [a], as.

	% Reálně Prolog přidá automaticky dva argumenty takovýmto funkcím
	% - jeden pro "z čeho chceme parsovat"
	% - druhý pro "co nám zbývá naparsovat"
	% Tedy výše uvedené `as` se dá napsat jako:
	as_([], []).
	as_(Znaky, ZbyleZnaky) :-
	Znaky = [ a \| NoveZnaky ],
	as_(NoveZnaky, ZbyleZnaky).


	% Takhle by vypadal parser pro nějaký počet mezer...
	pwhitespace --> [].
	pwhitespace --> [' '], pwhitespace.

	% Tak si udělejme parser pro JSON! :)

	% Top-level funkce vezme string a vrátí hodnotu
	json_parse(String, V) :-
	% Převede String na seznam znaků
	string_chars(String, SeznamZnaku),

	% zavolá "naparsuj JSON" tak, aby ti nezbyly znaky.
	pjson(V, SeznamZnaku, []).

	% JSON = Null \| Bool \| Seznam \| String \| Int
	pjson(V) -->
	pnull(V);
	pbool(V);
	pseznam(V);
	pstring(V);
	pint(V).

	% Null = n u l l
	pnull(nic) --> [n, u, l, l].

	% Bool = t r u e \| f a l s e
	pbool(ano) --> [t,r,u,e].
	pbool(ne) --> [f,a,l,s,e].

	% Seznam = [ ]
	% Seznam = [ Hodnoty ]
	% Hodnoty = Json
	% Hodnoty = Json , Hodnoty
	pseznam([]) --> ['[', ']'].
	pseznam(V) --> ['['], pmanyvalues(V), [']'].

	pmanyvalues([V]) --> pjson(V).
	pmanyvalues([V\|Vs]) -->
	pjson(V),
	[','],
	pmanyvalues(Vs).

	% String = " Chary "
	pstring(str(Chars)) --> ['"'], pchars(Chars), ['"'].

	% Chary = ''
	% Chary = Char Chary (kde Char není dvojitá uvozovka)
	pchars('') --> [].
	pchars(V) -->
	[C],
	{ C \= '"' }, % tady pomocí `{ výraz }` voláme obyčejnou Prologovou funkci
	pchars(Cs),
	{ atom_concat(C, Cs, V) }. % spojí dohromady atomy

	% Inty
	pint(int(V)) -->
	[Digit],
	{ atom_number(Digit, AtomDigit) }, % Převede znak na číselný atom
	pint2(V, AtomDigit).

	% Tady používáme akumulátor A na udržování mezivýsledku
	pint2(A, A) --> [].
	pint2(V, A) -->
	[Digit],
	{
	atom_number(Digit, AtomDigit),
	A1 is A * 10 + AtomDigit
	},
	pint2(V, A1).

	% Pozor, že parser neřeší whitespace.
	% Pokud chcete, aby jej řešil, použijte ve vhodných místech `pwhitespace`.
	% Parser aritmetických výrazů

	% pInteger naparsuje číslo
	% víceméně stejné jako v předchozím případě.

	pInteger(I) --> pIntegerInner(I, 0).

	pIntegerInner(I, A) --> pIntegerAtLeastOne(I, A); { I = A }.
	pIntegerAtLeastOne(I, A) --> pNextDigit(I, A).

	pNextDigit(I, A) -->
	[Digit],
	{
	atom_number(Digit, N),
	A1 is 10 * A + N
	},
	pIntegerInner(I, A1).

	% Top-level parser pro výrazy
	% Expr = Add
	pExpr(V) --> pAdd(V).

	% Sčítací výrazy mají následující gramatiku:
	% Add = Mul + Add
	% Add = Mul - Add
	% Add = Mul
	pAdd(M + A) --> pMul(M), ['+'], pAdd(A).
	pAdd(M - A) --> pMul(M), ['-'], pAdd(A).
	pAdd(A) --> pMul(A).

	% Násobící výrazy mají následující gramatiku:
	% Mul = Simple * Mul
	% Mul = Simple / Mul
	% Mul = Simple
	pMul(A * B) --> pSimple(A), ['*'], pMul(B).
	pMul(A / B) --> pSimple(A), ['/'], pMul(B).
	pMul(A) --> pSimple(A).

	% Jednoduché výrazy mají následující gramatiku
	% Simple = ( Expr )
	% Simple = Integer
	pSimple(V) --> pInteger(V).
	pSimple(V) --> ['('], pExpr(V), [')'].

	% Pro zajímavost, takhle vypadá `pSimple` v "obyčejné" Prologové notaci...
	% pSimple(V, SeznamCharu, ZbyleChary) :-
	% SeznamCharu = ['(' \| NovySeznamCharu],
	% pExpr(V, NovySeznamCharu, ZbyleCharyZExpr),
	% ZbyleCharyZExpr = [ ')' \| ZbyleChary ].

	% Touto funkcí můžeme naparsovat aritmetický výraz
	expr_parse(String, Repr) :-
	string_chars(String, Chars),
	pExpr(Repr, Chars, []).