IB015 Neimperativní programování
Seznamy, Aritmetika, Tail rekurze v Prologu
Jiří Barnat
Sekce
Seznamy a unifikace
IB015 Neimperativní programování - 10
Seznamy
Seznam v Prologu
• Konečná sekvence prvků.
• Různorodé (typově nestejné) prvky.
• Délkou seznamu se chápe počet prvků nejvyšší úrovně.
Zápis
• Hranaté závorky, prvky oddělené čárkou.
[marek, 2, matous, lukas(jan)]
• Prázdný seznam:
[]
• Zanořený seznam:
[ [], a, [c.Di]], [[[jo]]] ]
IB015 Neimperativní programování - 10
str. 3/38
Neprázdné seznamy
Struktura
• Neprázdný seznam se dekomponuje na hlavu seznamu (head) a tělo seznamu (tail).
• Prázdný seznam nemá interní strukturu.
Operátor I
• Pro dekompozici seznamů na hlavu a tělo.
Příklad
• ?- [H|T] = [marek,matous ,lukas, jan] . H = marek,
T = [matous, lukas, jan].
• ?- [X|Y] = [] . falše.
IB015 Neimperativní programování - 10
str. 4/38
Neprázdne seznamy - rozšířená hlava
Hlava jako prefix seznamu
• Hlavu lze zobecnit na neprázdnou konečnou sekvenci prvků.
• Prvky v hlavě seznamu jsou oddělovány čárkou.
• V jednom nezanořeném seznamuje smysluplné pouze jedno použití operátoru |.
Použití
• Správné použití
?- [X,Y|Z] = [1,2,3,4].
X = 1,
Y = 2,
Z = [3, 4] .
• Nesprávné použití
?- [X|Y|Z] = [1,2,3,4]. ERROR
IB015 Neimperativní programování - 10
str. 5/38
Anonymní proměnná
Anonymní proměnná
• Označená znakem podtržítko.
• Nelze se na ni odkázat v jiném místě programu.
• Při použití v unifikačním algoritmu neklade žádné omezení na kompatibilitu přiřazení hodnot jednotlivým proměnným.
Příklady unifikace s anonymní proměnnou
• ?- f (a,X)=f (X,b) .        ?- f (a,X)=f (_,b) . ?- f (a, _)=f (_,b). falše.                            X = b. true.
• Unifikací získejte 2. a 4. prvek seznamu Seznam:
[_,X,_,Y|_]= Seznam.
IB015 Neimperativní programování - 10
str. 6/38
Příklady unifikace těla seznamu.
• ?- [X,Y] = [1,2,3,4] . falše.
• ?- [X,Y| [Z]] = [1,2,3,4] . falše.
• ?- [_,_| [Z]] = [1,2,3] . Z = 3.
• ?- [1,2|[Z,Y]] = [1,2,3,4]. Z = 3,
Y = 4.
• ?- [1,2|[Z,Y]] = [1,2,3,4,5]. falše.
• ?- [1,2|[Z|Y]] = [1,2,3,4,5]. Z = 3,
Y = [4, 5].
IB015 Neimperativní programování - 10
Od funkcí k relacím
Pozorování
• Při vytváření programu v prologu, který má něco spočítat nebo vytvořit, postupujeme dle obecného pravidla transformace funkce f (a) = b na predikát r (a,b) .
Příklad
• Vytvořte seznam, který začíná dvěma uvedenými prvky, a to v libovolném pořadí.
• Imperativní pohled, funkce vracející požadované výsledky (samostatnou otázkou je, jak reprezentovat více výsledků)
fStartsWith(X,Y) -»* [X,Y|_] ->* [Y,X|_]
• V Prologu kódujeme jako relaci s o jedna větší aritou:
rStartsWith(X,Y,[X,Y|_]). rStartsWith(X,Y,[Y,X|_]).
IB015 Neimperativní programování - 10
str. 8/38
Příklad - rekurze na seznamech
Zadání
• Definujte predikát a2b/2, který transformuje seznam termů a na stejně dlouhý seznam termů b.
Řešení
• a2b( [],[]).
a2b([a|Ta] , [b|Tb])   :- a2b(Ta,Tb) .
Použití
• ?- a2b([a,a,a,a] ,X) . ?- a2b(X, [b,b,b,b]) . X= [b,b,b,b]. X= [a,a,a,a].
• ?- a2b(X,Y).
X = Y, Y = [] ;
X = [a] , Y = [b] ;
X = [a, a] , Y = [b, b] ;
X = [a, a, a] , Y = [b, b, b] .
IB015 Neimperativní programování - 10 str. 9/38
Sekce
Operace nad seznamy
IB015 Neimperativní programování - 10
Délka seznamu a test na bytí seznamem
length/2
• iength(L,i) je pravda pokud délka seznamu L má hodnotu i.
• Prázdný seznam má délku 0.
• ?- length([a,ab,abc],X). X = 3.
• ?- length([[l,2,3]],X). X = 1.
• ?- length(X,2).
X = [_G907, _G910] .
Test na bytí seznamem
• is_iist/i - Pravda, pokud parametr je seznam.
• ?- is_list( ['aha', [2,'b'] , [] ,2.3] ). true.
IB015 Neimperativní programování - 10
str. 11/38
Operátor ., Otevřené seznamy
Operátor .
• Předřazení prvku k seznamu (aka : z Haskellu).
• Nemá infixový zápis.
• Příklady
?- X = . (b, [1,2,3]). ?- X = .([a], [a]).
X = [b, 1, 2, 3] . X = [ [a] , a] .
Seznamy jako neúplná datová struktura
• Prolog umí pracovat i se seznamy, které nejsou kompletně definovány, tzv. otevřené seznamy.
• ?- Seznam = [llTelo], Telo = [21X] . Seznam = [1,2|X],
Telo = [2|X].
• ?- length([a,b|_],6). true.
IB015 Neimperativní programování - 10
str. 12/38
Prvky seznamu - predikát member/2
member/2
• Zjištění přítomnosti prvku v seznamu.
• member(x,D je pravda, pokud objekt X je prvkem seznamu L.
• Implementace:
member (X, [X|_]) .
member (X, [_|T] )  :- member (X,T).
Postup výpočtu:
• ?- member(lukas,[marek.matous,lukas,jan]).
?- member(lukas,[matous,lukas,j an]).
?- member(lukas,[lukas,j an]). true.
IB015 Neimperativní programování - 10
str. 13/38
Predikát member/2 - použití
Pozorování
• Volnou proměnnou lze použít jak v prvním, tak i v druhém argumentu. Pomoci predikátu je možné enumerovat prvky seznamu, ale také vynutit, že daný prvek je prvkem seznamu.
Příklady
• ?- member(X,[marek,matous,lukas,jan]). X = marek ;
X = matous ; X = lukas ; X = jan ; falše.
• ?- member( jan, [marek,matous ,lukas ,X] ) . X = jan ;
falše.
IB015 Neimperativní programování - 10
str. 14/38
Konkatenace seznamů predikátem append
append/3
• Dotaz append(Li,l2,l3) se vyhodnotí na pravda, pokud seznam l3 je zřetězením seznamů li a l2.
Definice append
• append( [] ,l ,l) .
append([Hl|Tl],l2,[Hl It3])   :- append(ti,l2,t3).
Použití
• Test na to, zda li ■ l2 = l3.
• Test na rovnost seznamů.
• Výpočet zřetězení dvou seznamů.
• Odvození prefixu, nebo sufixu v daném seznamu.
• Generování seznamů, jejichž zřetězení má daný výsledek.
IB015 Neimperativní programování - 10
Syntax se mění, myšlenka zůstává
Definice append v Prologu
• append( [] ,L ,L) .
append([Hl|Tl],L2,[H1IT3])   :- append(Tl,L2,T3).
Definice append v Haskellu
• append [] 1 = 1
append (hl:tl) 12 = hl:t3 where t3 = (append tl 12)
IB015 Neimperativní programování - 10
Predikáty nth
nthO(lndex, List, Elem)
• index prvku Elem v seznamu List, počítáno od 0, tj. první prvek má index 0.
nthl(lndex, List, Elem)
• Totéž co nthO/3, ale počítáno od 1.
nthO(N, List, Elem, Rest)
• index prvku Elem v seznamu List, počítáno od 0, tj. první prvek má index 0, Rest je seznam vzniklý ze seznamu List odebráním dotčeného prvku.
nthl(N, List, Elem, Rest)
• Totéž co nthO/4, ale počítáno od 1.
IB015 Neimperativní programování - 10
str. 17/38
Cyklické seznamy
Pozorování
• Nedokonalost unifikačního algoritmu lze "zneužít" pro definici cyklických seznamů, tj. seznamů, které jsou periodicky nekonečné.
Příklady
• ?- unify_with_occurs_check(X, [1,2,3|X]). falše.
• ?- X=[1,2,3|X], nthl(7,X,Z) . X = [1, 2, 3|X],
Z = 1.
• ?- X=[a,b|X], appendC[a.b.a.b.a],Z,X). X = [a,b|X],
Z = [b|X] .
IB015 Neimperativní programování - 10
str. 18/38
Sekce
Aritmetika
IB015 Neimperativní programování - 10
str. 19/38
SWI Prolog - Aritmetické typy
Celá čísla - integer
• Nativní typ, využíva knihovnu GMP.
• Velikost čísel omezena pouze velikostí dostupné paměti.
Desetinná čísla - float
• Nativní typ, odpovídá typu double z programovacího jazyka C.
Racionální čísla - rational
• Reprezentované s využitím složeného termu rdiv(N.M).
• Výsledek vrácený operátorem is/2 je kanonizován, tj. M je kladné a M a N nemají společného dělitele.
Konverze a unifikace
• rdiv(N,l) se konvertuje na celé číslo N.
• Automatické konverze ve směru od celých čísel k desetinným.
• Riziko vyvolání výjimky přetečení.
• Čísla různých typů se neunifikují.
IB015 Neimperativní programování - 10 str. 20/38
Aritmetické funkce a operátory
Relační operátory
</2      menší než
>/2      větší než
=</2     menší nebo rovno
>=/2    větší nebo rovno
=:=/2 rovno
=\=/2 nerovno
Vybrané aritmetické funkce
-/í unární mínus
+/i znaménko plus
+/2 součet
-li rozdíl
*/2 součin
//2 dělení
**I2 mocnina
Bitové operace
«12 bitový posun vlevo
»12 bitový posun vpravo
\//2 bitové OR
A/2 bitové AND
\/i bitová negace
xor/2 bitový XOR
1112 celočíselné dělení
rem/2 zbytek po dělení //
div/2 dělení a zaokrouhlení dolů
mod/2 zbytek po dělení div
max/2 maximum
min/2 minimum
is/2 vyhodnocení a unifikace
IB015 Neimperativní programování - 10
str. 21/38
Aritmetické operace v relacích
Pozorování
• Pro strukturovaný term, který dává do relace dva jiné termy, je možné nechat Prolog dohledat termy, pro které relace platí.
• rel(a,b).
?- rel(X,b). X = a.
Neplatí pro argumenty aritmetických operací
• V případě použití aritmetické operace takovéto chování vyžaduje inverzní aritmetickou funkci.
• Prolog při unifikaci a rezoluci nepočítá inverzní funkce,
v okamžiku požadavku na takovouto operaci ohlásí interpret chybu (nedostatečná instanciace).
• Porovnejte:
?- X is 3*3. ?- 9 is 3*X.
X = 9. ERROR
IB015 Neimperativní programování - 10
str. 22/38
Příklady nedostatečné instanciace
Vyzkoušejte
• ?- 9 is X + 1. ?- X > 3. ?- X = 2, X > 3. ERROR                         ERROR false.
Vysvětlete rozdílné chování
• Korektní definice predikátu pro výpočet délky seznamu.
length([] ,0) .
length([_IT],N)  :- length(T,X), N is X+l.
• Nevhodná definice predikátu pro výpočet délky seznamu.
lengthl([] ,0).
lengthl([_|T] ,N)  :- N is X+l, lengthl(T,X) .
• Rozdílné chování při výpočtu.
?- length([a,b],X). ?- lengthl([a,b],X).
X = 2. ERROR
IB015 Neimperativní programování - 10
Instanciace parametrů
Pozorování
• Předdefinované predikáty mohou vyžadovat, aby některé parametry byly povinně instanciované, tzn. na jejich místě nelze použít proměnnou.
Používaná notace v dokumentaci
• +Arg: musí být instanciovaný parametr.
• -Arg: očekává se proměnná.
• ?Arg: instanciovaný parametr nebo proměnná.
• OArg: parametr nebude vázán unifikací.
• :Arg: parametrem je název predikátu.
Módy použití
• Je-li binární predikát použit s dvěma instaciovanými parametry, říkáme, že predikát je použit v (+,+) módu.
IB015 Neimperativní programování - 10
str. 24/38
Příklady z dokumentace
between(+Low, +High, ?Value)
• Low and High are integers, High >=Low. If Value is an integer, Low=< Value=< High. When Value is a variable it is successively bound to all integers between Low and High. If High is inf or infinite between/3 is true iff Value>= Low, a feature that is particularly interesting for generating integers from a certain value.
plus(?lntl, ?lnt2, ?lnt3)
• True if Int3 =Intl +Int2. At least two of the three arguments must be instantiated to integers.
sort(+List, -Sorted)
• True if Sorted can be unified with a list holding the elements of List, sorted to the standard order of terms. Duplicates are removed. The implementation is in C, using natural merge sort.
The sort/2 predicate can sort a cyclic list, returning a non-cyclic version with the same elements.
IB015 Neimperativní programování - 10 str. 25/38
Sekce
Tail rekurze
IB015 Neimperativní programování - 10
Rekurze a efektivita
Pozorování
• Uvažme následující definici predikátu length.
length([] ,0) .
length( [_|T] ,N)  :- length(T,X) , N is X+l.
• Nevýhodou této definice je, že při volání dochází k výpočtu před rekurzivním voláním (při rekurzivním sestupu) i po rekurzivním volání (při vynořování z rekurze).
Tail rekurze
• Definice, jež nevynucuje výpočet po rekurzivním volání, tj. rekurzivní cíl je jeden a je uveden jako poslední podcíl.
• Výsledek je znám při dosažení dna rekurzivního sestupu.
• Menší režie výpočtu, větší efektivita.
• Platí i ve světě imperativních programovacích jazyků.
IB015 Neimperativní programování - 10
str. 27/38
Tail rekurze a akumulátory
Pozorování
• Tail-rekurzivní definice lze dosáhnout použitím akumulátoru.
• Akumulátor = pomocný shromažďovací parametr.
• Zavedení akumulátoru vyžaduje definici pomocného predikátu.
Predikát length definován tail-rekurzivně
• Realizace pomocným predikátem s akumulátorem.
length(Seznam,Délka)  :- accLen(Seznam,O.Delka).
• Definice pomocného predikátu.
accLen( [] , A, A) .
accLen( [_|T] ,A,L)  :- B is A+l, accLen(T,B,L) .
• Mód použití accLen je (?, + ,?).
IB015 Neimperativní programování - 10
str. 28/38
Iniciální hodnota akumulátorového parametru
Pozorování
• V některých případech je obtížné zvolit iniciální hodnotu akumulačního parametru.
• Uvažme následující definici pomocného predikátu accMax/3, který s využitím akumulátoru pro volání accMax(List,A,Max) počítá největší číslo v seznamu:
accMax( [] , A, A) .
accMax([H|T],A,Max)   :- H > A, accMax(T,H,Max). accMax([H|T],A.Max)   :- H =< A, accMax(T,A.Max).
Úkol
• S využitím accMax/3 definujte predikát max_member/2.
• Jakou zvolit výchozí hodnotu akumulátoru?
IB015 Neimperativní programování - 10
str. 29/38
Iniciální hodnota akumulátorového parametru
Pozorování
• V některých případech je obtížné zvolit iniciální hodnotu akumulačního parametru.
• Uvažme následující definici pomocného predikátu accMax/3, který s využitím akumulátoru pro volání accMax(List,A,Max) počítá největší číslo v seznamu:
accMax( [] , A, A) .
accMax([H|T],A,Max)   :- H > A, accMax(T,H,Max). accMax([H|T],A.Max)   :- H =< A, accMax(T,A.Max).
Úkol
• S využitím accMax/3 definujte predikát max_member/2.
• Jakou zvolit výchozí hodnotu akumulátoru?
max_member(List,Max)  :- List = [H|_], accMax(List ,H,Max) .
IB015 Neimperativní programování - 10
str. 29/38
Sekce
Řetězce, operátor syntaktické ekvivalence
IB015 Neimperativní programování - 10
str. 30/38
Řetězce v Prologu
Pozorování
• 'Ahoj' není totéž CO "Ahoj" .
• Řetězce znaků uvedených v uvozovkách jsou chápány jako seznamy čísel, které odpovídají ASCII kódům jednotlivých znaků řetězce.
• "Ahoj" == [65,104,111,106].
Automatická konverze na seznam čísel
• ?- append("Ale ","ne!",X).
X = [65,  108,  101, 32, 110, 101, 33].
Konverze na řetězce
• Vybrané předdefinované predikáty vynutí prezentaci ve formě "řetězce".
IB015 Neimperativní programování - 10
str. 31/38
Syntaktická ekvivalence (identita) - operátor ==
Syntaktická rovnost
7-
'pepa' == "Pepa".
7-
'mouka' == 'mouka'
false.
true.
7- 4 ==
3+1.
?- 3+1 == 3+1.
false.
true.
Pozor na syntaktické ekvivalenty
•     ?- 'pepa' == pepa. true.
?- [97] == "a", true.
IB015 Neimperativní programování - 10
Konverze řetězců a jejich délka
string_to_atom(?String, ?Atom)
• Logical conversion between a string and an atom. At least one of the two arguments must be instantiated. Atom can also be an integer or floating point number.
string_to_list(?String, ?List)
• Logical conversion between a string and a list of character code characters. At least one of the two arguments must be instantiated.
stringJength(+String, -Length)
• Unify Length with the number of characters in String. This predicate is functionally equivalent to atom_length/2 and also accepts atoms, integers and floats as its first argument.
IB015 Neimperativní programování - 10
str. 33/38
Zřetězení a detekce podřetězců
string_concat(?Stringl, ?String2, ?String3)
• Similar to atom_concat/3, but the unbound argument will be unified with a string object rather than an atom. Also, if both Stringl and String2 are unbound and String3 is bound to text, it breaks String3, unifying the start with Stringl and the end with String2 as append does with lists.
sub_string(+String, ?Start, ?Length, ?After, ?Sub)
• Sub is a substring of String starting at Start, with length Length, and String has After characters left after the match. See also sub_atom/5.
Příklady
• ?- sub_string('Nenene!',X,Y,Z,'ne'). X=Y, Y=2, Z=3;
X=4, Y=2, Z = 1 ; false.
• ?- sub_string('Nenene!',4,2,1,X). X = "ne".
IB015 Neimperativní programování - 10 str. 34/38
Sekce
Příklady
IB015 Neimperativní programování - 10
str. 35/38
Příklad: násobky daného čísla
Zadání
• Definujte predikát nasobky(+Cisio,+Pocet,?Seznam), který je pravdivý, pokud Seznam je prvních Počet násobků čísla Cisio.
• ?- nasobky(3,6,[3,6,9,12,15,18]). true.
Řešení
• nasobky(N,P,L)  :- aNas(N,P, [] ,L) . aNas(_,0,Acc,Acc).
aNas(N,P,A,L) :- P>0, /* prevent infinite recursion */
Pl is P-l, K is N*P, aNas(N,Pl,[K|A],L).
IB015 Neimperativní programování - 10
str. 36/38
Příklad: packList
Zadání
• V prologu naprogramujte predikát packList/2, který realizuje vynechání sousedních identických termů v seznamu, predikát předpokládá mód použití (+,?).
• ?- packList([a,a,a,l,l,c,c,c,[a],[a]],X). X = [a,l,c, [a]].
Řešení
• packList(L,P)   :- aPL(L,RP,L,[]), reverse(RP,P). aPL([] ,P,_ ,P) .
aPL([H|T],P,L,Acc)   :- H \== L, aPL(T,P,H,[H|Acc]);
H == L, aPL(T,P,L,Acc).
IB015 Neimperativní programování - 10
str. 37/38
Domácí úloha
Zadání
• V Prologu naprogramujte predikáty encodeRLE/2 a decodeRLE/2, které budou realizovat RLE kódování seznamů.
• V RLE kódování je každá n-tice stejných po sobě jdoucích prvků k v seznamu nahrazena uspořádanou dvojicí (n,k).
Příklad použití
• ?- encodeRLE([a,a,a,b,b,c,d,d,e],X). X = [(3,a),(2,b),(l,c),(2,d),(l,e)]
• ?- decodeRLE([(5,1),(1,2),(3,3)],[1,1,1,1,1,2,3,3,3]). true.
IB015 Neimperativní programování - 10
str. 38/38