% cv. 2 ; 1.3.2017 ; Jan Hric
% cv. 2+3, 5.3.2018
% update 28.2.2018
% v. 1.3.2
% .. 2021

% Opakovani terminologie:
% predikat/procedura, klauzule, fakt, hlava, telo, cil, dotaz,
% predikatovy symbol, funkcni symbol.

% Rodinne vztahy:
% kontext p/2: p(Predek, Potomek).
% 	m/1: m(Muz).
%	z/1: z(Zena).


% Zapiste:
% prarodic/2, babicka/2, (nevlastni) sourozenec/2, vlSourozenec/2
% bratranecNSestrenice
% teta
% - hodi se: X=Y   % X a Y jsou stejne, (nebo, v obecnosti, se zunifikuji)
%	X\=Y	% X a Y nejsou stejne


% data:
p(a,b1).
p(a,b2).
  p(b1,c1).
  p(b1,c3).
  p(b1,c4).
  p(b2,c2).
  p(b2,c3).
  p(b2,c5).
    p(c1,d1).
    p(c3,d2).
    p(c3,d3).
    p(c5,d5).
      p(d2,e2).

% p(+virtualni_genealogie, +predek, -potomek). 1. arg. pro rozliseni dat

% potomek(+,-)/2
potomek1(X,X).
potomek1(X,Y):-p(X,P),potomek1(P,Y).

potomek2(X1,X0):-p(X1,X0).
potomek2(X1,X0):-p(X1,X2),potomek2(X2,X0).

% nezacykli se, pokud genealogie je konecny DAG
potomek3(X,Y):-p(X,P),potomek3(P,Y).
potomek3(X,X).

% ! z logickeho hlediska je ruzne poradi cilu (spojenych 'and') 
%     a klauzuli (spojenych 'or') irelevantni, ale:
% ! ruzne zpusoby zapsani maji vliv na efektivitu a nekdy i konecnost vypoctu
% - pokud podspecifikujeme zamyslene "vstupni" argumenty (tj. argument 
%     je volna promenna tam, kde jsme predpokladali term), tak krome 
%      koncove podminky se casto splni i rekurzivni klauzule.

% testy:
ta1(X):-potomek1(a,X).
ta2(X):-potomek2(a,X).
ta3(X):-potomek3(a,X).
ta4(X):-potomek1(X,e2).
ta5(X):-potomek2(X,e2).

ta6(X):- allSol(potomek1(a),X).

% runtime magie
allSol(Pred,X):- call(Pred,X), write([X]), fail.


% struktury: nerekurzivni i rekurzivni
% dvojice
% datumy ... : datum/3, a samostatne rozbor variant
% komplexni cisla: rect/2, polar/2 - pravouhle a polarni zadani
% numeraly: s/1, 0/0 ; pripadne predchudce p/1
% :-) seznamy
%       asociacni seznamy
% binarni stromy, a binarni haldy: t/3, void/0 (nebo nil/0)
% 2-3 stromy: t2/3, t3/5, nil3/0 (at se to neplete)
% Reg. vyrazy: seq/2, */1, +/2, lambda/0, empty/0, p/1 - pismena
% Vyrokove formule: and/2, or/2, non/1, imp/2, ekv/2, xor/2, true/0, false/0, p/1 - promenne

% příklady rek. struktur:
% numeral 2: 
data(nat2, s(s(0)) ).
data(bstrom1, t(t(t(nil,1,nil),2,nil),3,nil) ).	% nepříjemnost: hromadění závorek na konci termu
data(fle1, and(p(x),or(not(p(x)),p(y))) ). 	% x and (not x or y), prefixně
  % infix:  p(x) and (not p(x) or p(y))
data(rv1, *(+(lambda, seq(p(a),p(b))))).		% RV: (lambda|ab)*
% Pozn/bude: správnost "typu" termu se dá skontrolovat (rekurzivně) ; v HS budou typy
% Pozn: (velká) testovací data můžeme generovat 

% prava rotace
% mody: rotR(+,-) nebo rotR(-,+)
rotR(t(t(A,X,B),Y,C), t(A,X,t(B,Y,C)) ).

t21(S,V):- data(bstrom1,S), rotR(S,V). 

/*

datova struktura pro datum:
20180305	% cislo (1)
'05032018'	% atom	(2)
"05032018"	% retezec (3)
datum(5,brezen,2018)  %	(4)
datum(5,3,2018)	      %	(5)
datum(den(5),mes(3),rok(2018))	% (6)
datum([den(5),mes(3),rok(2018)])	% seznamy (7)
datum([den-5,mes-3,rok-2018])	% operator -/2, neinterpretovany (8)
datum([5,3,2018])	% (9)
[5,3,2018]		% (10)
*/

% Zviditelneni: display/1 z přednášky
tb99:- display( datum([5,3,2018]) ).
tb98:- display( datum([den-5,mes-3,rok-2018]) ).

% DOPLNIT:
% interface k datumu: make, set, get, ...
mk_datum(_D,_M,_R, _Datum).	% vytvoreni, konstruktor ; mod (+,+,+,-), taky (-,-,-,+)
get_den(Datum, _D):- Datum = Datum.
set_mes(Datum, _M, Datum0) :- Datum0=Datum.	% mod (+,+,-)
%
% s vyuzitim mk_datum/4
get_den1(Datum,D):- mk_datum(D,_,_,Datum).
set_mes1(Datum,M,Datum0) :- mk_datum(D,_M1,R,Datum), mk_datum(D,M,R,Datum0).
  % konstrukce nove struktury v Datum0

% Strukturalni rekurze:
% - rekurzivni termy na vstupu lze casto primocare zpracovat tak, ze term rozebereme  
%     a na podterm(y) volame rekurzi 
% - viz dale: zahrnuje to i idiom 'strukturalni rekurze' i idiom 'akumulator'
% - jsou i jine zpusoby rekurze nez strukturalni, napr. v mergesortu a FFT delime 
%     vstupni seznam na dva stejne dlouhe seznamy, nikoli na hlavu seznamu a telo seznamu

% numeraly: (tj. unarni reprezentace cisel)
% strukturalni rekurze: pro kontrolu typu ; funktory 0/0, s/1
prirozene_cislo(0).
prirozene_cislo(s(X)) :- prirozene_cislo(X).
% pozn.: v typovanem jazyce by toto pohlidal typovy system

tb0 :- prirozene_cislo( s(s(s(0))) ).
tb0a:- prirozene_cislo( _X ).	% cykli
tb0b(X):- prirozene_cislo( X ).	% cykli
tb0c :- prirozene_cislo( s(s(s(nula))) ). % fail/false

% plus1(+,+,-)/3
% programatorsky idiom: skladani substituci; 
%   rekurze podle 1. a 3. arg.
plus1(  0, Y,  Y).
plus1(s(X),Y,s(Z)) :- plus1(X,Y,Z).

% debug:
plus1a(  0, Y,  Y) :- write([konec,0,Y,Y]),nl.
plus1a(s(X),Y,s(Z)):- write([do___,X,Y,Z]),nl,  % na puvodni 1. a 3. arg nemame pristup
						% nelze je vypsat
                      plus1a(X,Y,Z),
                      write([ven__,X,Y,Z]),nl.

% Idiom: akumulator (nebo stav)
plus2(  0, Y,  Y).
plus2(s(X),Y,  Z) :- plus2(X,s(Y),Z).

% debug:
plus2a(  0, Y,  Y) :- write([konec,0,Y,Y]),nl.
plus2a(s(X),Y,  Z) :- write([do___,X,Y,Z]),nl,
                      plus2a(X,s(Y),Z),
                      write([ven__,X,Y,Z]),nl.

% ladeni: - vypis je rychlejsi nez trasovani
% - kontrola relaci, obecnejsi nez Unit testy
% - metoda dvou interface 

% minus1/3, minus1(+X,+Y,-Z) ~ plus1(+Y,-Z,+X)  ; vlastne interfaceovy predikat
% rekurze podle puvodniho tretiho arg. plus1/3
minus1(X,Y,Z):-plus1(Y,Z,X).

% Q: Jak to dopadne, kdyz odcitame vetsi cislo od mensiho?
tb96(V) :- testovaciNumeral(2,X2), testovaciNumeral(3,X3), write(ok),
	minus1(X2,X3,V).
% 

%minus2(X,Y,Z):-plus2(Y,Z,X). % ?
% T:-

% mensi/2 z prednasky
mensi(0, s(_X)).
mensi(s(X),s(Y)):- mensi(X,Y).

% Pr: upravte mensi/2 na mensi2/3, aby vždy uspělo a vracelo ve třetím arg. explicitně konstanty true, false .
%
mensi2(0,s(_X), true).
mensi2(_, _,   false ).
mensi2(s(X),s(Y),V):- mensi2(X,Y,V).

% minus s kontrolou, mene efektivni
%   X a Y prochazime 2x
minus3(X,Y, Z) :- mensi(X,Y), Z=0.
minus3(X,Y, Z) :- plus1(Y,Z,X).

% krat/3
krat1(0,_Y,0).
krat1(s(X),Y,Z):- % preprocesing: A1=s(X)
  krat1(X,Y,Z1),  % neni tail-rekurzivni
  plus1(Y,Z1,Z).  % postprocesing

% DCx: krat2/3 akumulatorem
% hint: potrebujeme dalsi argument pro stav 
%  a interfaceovou klauli pro jeho inicializaci
%   <- uzivatel dostane klasicky interface
krat2(X,Y,Z):-krat2a(X,Y,0,Z).	% interfejsova klauzule, zavadi Acc = 0 jako Arg3
krat2a(  0 ,_Y,  Z,Z).
krat2a(s(X), Y,Acc,Z):-
  plus2(Y,Acc,Acc2),
  krat2a(X,Y,Acc2,Z). % invariant: X*Y+Acc2=Z

% DC: divMod(X,Y,Div,Mod) :- ...


% testovaciData/2
testovaciNumeral(2,s(s(0)) ).
testovaciNumeral(3,s(s(s(0))) ).

tb1(V):- plus1(s(s(0)), s(s(0)), V). % ! vsechny vysledky
% spravnost vuci nedeterminizmu (tj. rekurzi): nevyda nespravny vysledek pozdeji

tb2(V):- 
  testovaciNumeral(3,N3),
  plus1a(N3,N3,V).

tb3(V):- plus2(s(s(0)), s(s(0)), V). % ! vsechny vysledky

tb4(V):- 
  testovaciNumeral(3,N3),
  plus2a(N3,N3,V).

tb5(V):- 
  testovaciNumeral(3,N3),
  testovaciNumeral(2,N2),
  krat1(N3,N2,V).

tb6(_V):- 
  testovaciNumeral(3,N3),
  testovaciNumeral(2,N2),
  krat1(N2,N3,V23),
  krat1(N3,N2,V32),
  plus1(N2,N3,P23),
  plus1(N3,N2,P32),
  minus1(N3,N2,M32),
  write([krat,V23*V32,plus,P23+P32,minus,M32]),
  true.  % minuly radek se lehce zakomentuje

tb7(V):-
  minus1(s(0),s(s(0)),V). 	% neuspech

tb8([X,Y]):-
  minus1(X,Y,s(s(s(0)))).	% vic reseni, OK

tb9([X,Y]):-
  minus2(X,Y,s(s(s(0)))).	% vic reseni, cyklus?


% CV: mensi(+X,+Y) :- pro numeraly: uspeje, pokud X je mensi nez Y
% ... a varianty: mensiRovno/2 vetsi/2

% Bool se "vraci" jako uspech/neuspech ; pouzitelne v testech  

%%%%

% seznamy
% prefix/2, sufix/2, 
% prefixy/2, sufixy/2...



/*
%----------
vypust(X,[X|Xs],Xs).
vypust(X,[Y|Ys],[Y|Zs]):-vypust(X,Ys,Zs).

vloz(X,Xs,Ys) :- vypust(X,Ys,Xs).

otocAk(Xs,Ys) :- otocAk(Xs,[],Ys).
otocAk([],A,A).
otocAk([X|Xs],A,Ys):-otocAk(Xs,[X|A],Ys).

k.
*/

