Skip to content

Instantly share code, notes, and snippets.

@jiribenes
Last active Apr 9, 2021
Embed
What would you like to do?
Cvičení z Neprocedurálního programování - 6
% 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, []).

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...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment