Skip to content

Instantly share code, notes, and snippets.

@jiribenes
Created February 24, 2022 14:34
Show Gist options
  • Save jiribenes/ac93fc5683b4a43a08e1416b81564892 to your computer and use it in GitHub Desktop.
Save jiribenes/ac93fc5683b4a43a08e1416b81564892 to your computer and use it in GitHub Desktop.
Cvičení z Neprocedurálního programování - 2
% Bavili jsme se o unifikaci a backtrackingu....
% `X = Y` v prologu znamená "unifikuj X a Y"
%
% například:
% ?- f(X, g(Y)) = f(g(z), X).
% X = g(z),
% Y = z.
%
% Všimněte si, že Prolog vrací nejobecnější možné dosazení :)
% Pak jsme se bavili o tom, že Prolog je vlastně jen DFS s backtrackingem + unifikace!
% Pokračování grafů z minulého cvičení:
%
% A ------> B ---> C
% \ \ /|
% \| \| /
% E----------->F
% \ /|
% \| /
% D /
% /| /
% / /
% G ---> H
edge(a, b).
edge(a, e).
edge(b, c).
edge(b, f).
edge(e, d).
edge(e, f).
edge(f, c).
edge(g, d).
edge(g, h).
edge(h, f).
% Chceme definovat 'path(U, V)', který značí jestli existuje orientovaná cesta z U do V
% Hranu z U do V značím jako U -> V
% Orientovanou cestu z U do V značím jako U ~~~> V
% Níže jsou definovány tři varianty:
% * `path` je verze z prvního cvičení - najde výsledek a nezacyklí se
% * `path2` je nová verze - sice najde výsledek, ale zacyklí se
% * `path3` je nová verze - jen se zacyklí
% Hlavně jsme řešili rozdíl mezi "deklarativní správností", cca "formule daná pravidlem je správně"
% versus "procedurální správností", cca "dá správný výsledek"
% funguje z minulého cvičení
path(U, U).
path(U, V) :- edge(U, W), path(W, V).
% najde výsledek a pak se zacyklí
path2(U, U).
path2(U, V) :- path2(W, V), edge(U, W).
% zacyklí
path3(U, V) :- edge(U, W), path3(W, V).
path3(U, U).
% Můžeme si vytvořit složené termy
% Nepotřebujeme dopředu definovat tvar takových termů,
% narozdíl od Céčka, kde bychom museli napsat `struct pair { int a; int b; }`
% Vrátí první, resp. druhý člen dvojice.
% `_` znamená "Vytvoř novou proměnnou, která je různá od
% všech již existujících proměnných"
first(pair(A, _), A).
second(pair(_, B), B).
%% unární reprezentace čísel
%% Taky se ji říká Peanova aritmetika (či Robinsonova)
% 0 značí nulu
% s(X) značí následníka čísla X, tedy X + 1
% nat: je něco číslo?
nat(0). % 0 je číslo
nat(s(X)) :- nat(X). % (X + 1) je číslo, pokud X je číslo
% Příklady čísel:
% zero = 0.
% one = s(0). % successor of 0
% two = s(s(0)).
% three = s(s(s(0))).
% Chceme zadefinovat sčítání:
% add(X, Y, Z)
% 0 + X = X
add(0,X,X) :- nat(X).
% (X + 1) + Y = (Z + 1) if X + Y = Z
add(s(X), Y, s(Z)) :-
nat(X), nat(Y), nat(Z),
add(X, Y, Z).
% Tracujeme ručně `add(1,2,A)`:
% add(1, 2, A)
% = add(s(0), s(s(0)), A)
% ~> basecase
% <~ no.
% ~> X = 0, Y = s(s(0)), A = s(Z)
% ~> add(0, s(s(0)), Z)
% ~> basecase: X' = s(s(0)), Z = X'
%
% X = 0, Y = s(s(0)), X' = s(s(0))
%
% A = s(Z) = s(X') = s(s(s(0))).
% Doporučuji si výše uvedené vytraceovat i v REPLu
% Cvičení: Zkuste jednu z proměnných dát volnou, co se stane?
% Co když dáte dvě proměnné volné?
% Konkrétně co se stane když dáte `add(X, Y, s(s(s(s(0)))))`? (to poslední číslo je 4)
% Ideálně by vám to vypsalo všechna X a Y taková, že X + Y = 4.
% Jenže ono se to po chvilce zacyklí -- proč?
% Násobení
% mult(X, Y, Z)
% basecase
mult(0,X,0).
% Rozmyslete si, že tenhle basecase vlastně není potřeba
mult(s(0),X,X).
% rekurzivní případ
% (X + 1) * Y = (X*Y) + Y = M + Y = Z
mult(s(X), Y, Z) :-
mult(X, Y, M), % X * Y = M
add(M, Y, Z). % M + Y = Z
% Cvičení: Vytvořte `less_equal(X, Y)`, který platí pokud X <= Y,
% kde X, Y jsou čísla zadaná v Peanově aritmetice
% Cvičení: Vytvořte dělení dvěma -- `divTwo(X, Y)`, tedy Y := X / 2 (celočíselně).
% Uměli byste i obecné celočíselné dělení -- `div(X, Y, Z)`?
% Dál jsme se vrhli na seznamy
% a rovnou jsme se rozhodli si vyrobit vlastní složené termy,
% které reprezentují seznam.
% nil .... prázdný seznam
% cons(X, Y) .... X je hlava seznamu [head]
% , Y je tělo (ocásek) [tail]
%
% Predikát `list(X)` značí jestli `X` je seznam.
list(nil). % prázdný seznam je seznam
list(cons(Head, Tail)) :- % dvojice (Head, Tail) je seznam iff Tail je seznam
list(Tail).
% příklad seznamu [1, 2, "test"]
% cons(1, cons(2, cons("test", nil)))
% `printlist(X)` vypíše obsah stringového seznamu.
% (To, že obsahuje stringy nikde nekontrolujeme)
printlist(nil).
printlist(cons(String, Tail)) :-
writeln(String),
printlist(Tail).
% Můžeme si představit, že Prolog uvnitř funguje následovně:
% (Opravdové seznamy v Prologu vs. ty naše custom seznamy)
%
% [] ~~~> nil
% [1, 2, 3] ~~~> cons(1, cons(2, cons(3, nil)))
% [Head|Tail] <~~~ cons(Head, Tail)
% `printlist`, jen pro seznamy se syntaktickým cukrem.
printlist2([]).
printlist2([String|Tail]) :-
writeln(String),
printlist2(Tail).
% Doopravdy to je tak, že Prolog podporuje operátory a má:
% * nulární operátor [] ... reprezentuje náš `nil`
% * binární operátor [X|Y] ... reprezentuje náš `cons(X, Y)`
%
% Potom následující notace jsou ekvivalentní:
% [1, 2, "test"]
% cons(1, cons(2, cons("test", nil))) ... pozor, tahle notace je jen naše, nebude fungovat na predikáty v Prologu
% [1|[2|["test"|[]]]] ... explicitně napsaný [1, 2, "test"] pomocí operátorů
% Tohle by mělo být `true`, je to takový důkaz, že nekecám. :)
stejny :- [1, 2, "test"] = [1|[2|["test"|[]]]].
% náleží prvek seznamu?
% standardně ve std knihovně jako `member/2`, tedy funkce `member`, která bere 2 argumenty
elem(X, [X|_]).
elem(X, [_|T]) :- elem(X, T).
% Tahle verze `elem` skáče po dvou prvcích
% elem(X, [X, _|_]).
% elem(X, [_, _|T]) :- elem(X, T).
% Jak namatchovat správný seznam:
% f([A, B]) ... uspěje pro seznamy délky 2
% f([A, B | Tail]) ... uspěje pro seznamy délky >=2
% Hádanka, co dělá tahle funkce?
foo([], X, X).
foo([H|T], Y, [H|R]) :- foo(T, Y, R).
% standardně se jmenuje append/3 ;)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment