% cv. 1 ; 19.2.2018 ; Jan Hric
% Neproceduralni programovani, LS 2018, Po 10:40 SU2
% v. 1.1
% v. 1.2 2019/2002
%  cv: LS 19/2020 Pa 12:20 SW2

/* cv1 doplneno r.2018
- ukoly: 
-- stahnout tento soubor z meho webu, je ve forme prologovskeho zdrojaku (s .pl)
    http://ktiml.ms.mff.cuni.cz/~hric/vyuka/cv1_17.pl   tento soubor
    http://ktiml.ms.mff.cuni.cz/%7Ehric/vyuka/cv1_17.pl
    http://ktiml.mff.cuni.cz/~hric/vyuka.htm#Progr2   neprocedurální programování
    http://ktiml.mff.cuni.cz/~hric/vyuka.htm          výuka
-- premistit do defautniho prologovskeho adresare
    c:\users\students\downloads\prolog ?asi
-- spustit Prolog
 -> vyvojove nastroje -> SWI-Prolog
 - SWI prolog je doporuceny, je free a pro Win i Linux
  SWI-Prolog.org, kdyz uz instalujete: haskell.org 
 - interpretacni prostredi Prologu
-- natahnout soubor (prompt je "?-")
 ?- [cv1_17]. 
 nebo (s priponou, pak nutno v apostrofech)       
 ?- ['cv1_17.pl'].
 nebo        
 ?- ['c:/users/students/downloads/prolog/cv1_17.pl'].
 - procedura plnym jmenem: consult(cv1_17). 
  - mame interpretacni prostredi, nezajima nas, zda je to kompilator nebo interpret.  
-- klast programu v prologu otazky:
 ?- p(c1,d1).
   - overi platnost zakladniho dotazu (zakladni ~ bez promennych)
 ?- p(c1,X). 
   - najde hodnotu/-y promenne X, pro kterou dotaz plati
   - dalsi hodnoty pozadujeme strednikem (;)
-- editace: typicky v externim editoru
 - editor jde nastavit
 - lze editovat pres menu, i consult pres menu ... 
-- ukonceni prace: "halt." 
 ?- halt.
 
konvence a jine:
- tento text bez diakritiky (zatím)
- prolog: za % komentare do konce radku
    viceradkove komentare: zacatek: lomitko / hvezdicka * (mezera), konec: hvezdicka * lomitko / (mezera)
  - pozn.: Hs ma dvojucelovy text/zdrojak vyreseno moderneji: format Literate Haskell
- zde v textu i na tabuli: 3 druhy "kodu", ktere podle syntaxe nejdou rozeznat:
1. termy: bez tecky na konci
2. kusy kodu (klauzule, procedury): s teckou na konci
3. dotazy (pro interpret): uvedene "?-"
- prolog: promenne zacinaji velkym pismenem: X,Y,Z,X1,Xs
  - funkcni symboly, konstanty, relacni symboly (=jmena procedur): zacinaji malym pismenem
- prolog je beztypovy jazyk a f.s. vcetne cetnosti jsou urceny z programu
  - konvence: f/2 znamena funkcni nebo predikatovy symbol "f" se dvema argumenty
  - muzete mit soucasne f/2 i f/3, (ale nezunifikuji se) 
    - programatorsky: neni to dobry styl, error-prone (tj. nachylne k chybam)
  
- moodle: bude
   https://dl1.cuni.cz/
   https://dl1.cuni.cz/course/view.php?id=5223  tento kurz v moodlu
  -! klic pro prihlaseni dostanete/jste dostali na prednasce  
    
*/

% povinny program
ta0 :- write('Hello World!'), nl. 
ta0a :- write("Hello World!"), nl. % proc jsme pred chvili trochu upravili program
ta0b(_X) :- print('Hello World!'), print("Hello World!").
% - pouziti write a print neni typicke, procedury dostavaji vstupni argumenty a vraceji (pouze)
%     vystupni argumenty, bez side-efektu (...).   

% unifikace: ta z logiky, v Prologu staci unifikovat dva termy / atomicke formule (cil a hlavu/fakt) 
ta0c([X,Y]) :- X= f(g(Z),a,h(Z,U)), Y=f(V,W,h(W,V)),
  write([pred,X,Y]),nl,
  X=Y,
  write([po,X,Y]),nl,
  write([interni,Z,U,V,W]).
  
ta0d([X,Y]) :- write([bod1,X,Y]),nl,
  Y=g(X), write([bod2,X,Y]),nl, 
  X=Y,    write([bod3,X,Y]),nl.
 
/*  
% rezoluce: zopakovat
- fli ((a and b) -> c) piseme v prologu c <- a, b.
odpovida klauzuli: c or not a or not b.
- fakt a. je zkratka pro a <- true.
- dotaz ?- a,b. je zkratka pro  not a or not b.
  - negativni literal z dotazu muzeme rezolvovat pouze s (jedinym) kladnym 
  literalem klauzule, tj. hlavou (vlevo od sipky <-)
*/

% 1.0 navrhnete (pod)jazyk pro reprezentaci cisel pomoci termu. 
% - na rozehrani/rozcviceni: znate z logiky. 
% - dnes jen struktura, programy budou priste (a/nebo na prednasce)   

% 1. navrhnete (pod)jazyk (tj. funkcni symboly a konstanty) pro praci 
%     se sekvencemi ruzne/promenlive delky
%% abyste mohli resit napr. vyhledavani retezcu 
% - hodi se konstanta pro prazdnou sekvenci
% - nehodi se napr. f/7 pro 7-mi clennou sekvenci (pro dni v tydnu), 
%     protoze se nezunifikuje s posloupnosti jine delky
% - v Prologu jsou "preddefinovany" seznamy pro praci s posloupnostmi, maji specialni syntax
% - Prolog je sice beztypovy, ale zvolene f.s. muzeme pouzivat pouze pro tvoreni posloupnosti.

% ! rekurzivni data se dobre zpracovavaji rekurzivnimi programy

% reprezentace mnozin:
% - muzeme pouzit stejnou strukturu, ale sami udrzujeme posloupnost bez opakovani
% - napr. pri porovnavani mnozin musite pouzit vlastni proceduru, ne vestavene =/2, ktere 
%     porovnava (presneji/obecneji receno unifikuje) termy, tj. posloupnosti (na shodu)

% 2. navrhnete (pod)jazyk pro binarni stromy
% - neprazdny strom obsahuje Levy_podstrom, Hodnotu a Pravy_podstrom, (v danem  poradi)
% - a taky se hodi prazdny podstrom (dale tusim void)
% - jde to navrhnout vice zpusoby
% - pomoci termu reprezentujeme pouze strukturu stromu, ze strom je napr. vyhledavaci (BVS), 
%     je urceno zpusobem tvorby a udrzovanim invariantu
% -> stejnou strukturu muzete pouzit pro binarni haldu (pro heapsort)
%   - a kdyz si date trochu prace, tak bude i vyvazena (bude pozdeji)
% 2.1 zapiste podminky na spravne utvoreny BVS(S) ; trochu divna (OOP) syntax, abych moc nenapovedel
%  bvs(S) <-> bvs(S.Levy) and bvs(S.Pravy) and all_lt(S.Levy,S.H) and all_gt(S.Pravy,S.H), pro S/=void
%   ... all_lt(S,X) plati, kdyz vsechny prvky v S jsou mensi 
%    (podle spravne -parametricky_zadane- nerovnosti) nez X, dualne all_gt/2
%  bvs(void) <-> true
%  - a to podstatne: je to ekvivalence, tj. kdyz je splnena leva strana, tak mame spravne 
%    utvoreny BVStrom.
% - podle okolnosti (napr. pro AVL stromy) Hodnota muze byt slozena, anebo f.s. t/? muze mit dalsi 
%     argument pro reprezentaci vyvazeni  
% 2.2 zapiste podminky pro dobre utvorenou haldu (tj. haldove usporadani) 

% 2.3 napiste rotaci pro BVS
% - skoro urcite neudelate chybu v pointrech ;-)

/* zapiste BVS: (pekne, s indentaci)
       5
      / \   
     3   7
    / \
   1   4
 - co jste zapsali, muze slouzit jako testovaci data:
data(TestovaciStrom) :- TestovaciStrom = ... .
 - nebo    
data(...).
 - pouziti:
?- data(S1), insert(2,S1,S2), insert(8,S2,S0), write(S0). 
 */  
    
% 3. struktury pro reg. vyrazy, jen zakladni (z predn. Automaty a gramatiky)
% - budeme chtit RV derivovat, tj. utrhnout prvni pismeno a popsat zbyly RV

% 4. struktury pro stromy s variabilnim poctem potomku
% - ruzne varianty, typicky informace ve vrcholech
% - pouzitelne pro reprezentaci termu (pro ruzne jazyky), pro (zaklad) HTML/XML
% ! pokud mate jen konecny pocet f.s. (napr. spojek v logice), tak je muzete vyjmenovat 
%     a osetrovat samostatne, kazdou se svou specifickou aritou. Pak nemusite pouzivat 
% stromy s promenlivym poctem synu, ty jsou nutne v situacich, kdy neznate vsechny 
% funkcni symboly a/nebo jejich cetnost  (, ! casta chyba navrhu)

% 5. priste: rozebrat mozne (nerekurzivni) reprezentace pro datum:
%   - ma tri slozky: den, mesic a rok (napr. 29.2.2016)
% - nemate pro to podporu z jazyka, ale pristupove procedury set_"slozka", 
%     get_"slozka" a make (tj. konstruktor) muzete napsat a pouzivat jako interface

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% z cv. 2
% bratranecNSestrenice

% teta


% 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).

% 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 ; 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

% numeraly:
% 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.

% minus/3, minus(+X,+Y,-Z) ~ plus1(+Y,-Z,+X)  ; vlastne interfaceovy predikat
minus1(X,Y,Z):-plus1(Y,Z,X).

%minus2(X,Y,Z):-plus2(Y,Z,X). % ?
% T:-

% 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

% DC: krat2/3 akumulatorem
% hint: potrebujeme dalsi argument pro stav 
%  a interfaceovou klauli pro jeho inicializaci
%   <- uzivatel dostane klasicky interface

% 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.
*/

