IB015 Neimperativní programování
Ukázky použití Prologu a závěrečné zhodnocení
Jiří Barnat
Sekce
Einsteinova hádanka
IB015 Neimperativní programování - 12
Zadaní hádanky
Popis situace
• Je 5 domů, z nichž každý má jinou barvu.
• V každém domě žije jeden člověk, který pochází z jiného státu.
• Každý člověk pije nápoj, kouří jeden druh cigaret a chová jedno zvíře.
• Žádný z nich nepije stejný nápoj, nekouří stejný druh cigaret a nechová stejné zvíře.
Otázka
• Kdo chová rybičky?
• Za následujících předpokladů ...
IB015 Neimperativní programování - 12
str. 3/27
o
o
Brit bydlí v červeném domě. Švéd chová psa.
©Dán pije čaj.
© Zelený dům stojí hned nalevo od bílého.
O Majitel zeleného domu pije kávu.
© Ten, kdo kouří PaIIMail, chová ptáka.
© Majitel žlutého domu kouří Dunhill.
© Ten, kdo bydlí uprostřed řady domů, pije mléko.
© Nor bydlí v prvním domě.
O Ten, kdo kouří Blend, bydlí vedle toho, kdo chová kočku.
© Ten, kdo chová koně, bydlí vedle toho, kdo kouří Dunhill.
© Ten, kdo kouří BlueMaster, pije pivo.
© Němec kouří Prince.
© Nor bydlí vedle modrého domu.
© Ten, kdo kouří Blend, má souseda, který pije vodu.
IB015 Neimperativní programování - 12
str. 4/27
Řešení v Prologu
Copy-paste, aneb programátorova smrt
• einstein_0.pl
Přeuspořádání, aneb optimalizace v praxi
• einstein_l.pl
Transformace na řešení absolventa Fl
• einstein_2.pl
• einstein_3.pl
• einstein_4.pl
• einstein_5.pl
IB015 Neimperativní programování - 12
str. 5/27
Sekce
Programování s omezujícími podmínkami
IB015 Neimperativní programování - 12
Programovaní s omezujícími podmínkami
Vymezení pojmu
• Obecné neimperativní programovací paradigma.
• V množině možných řešení problému je hledané řešení popsáno pouze omezujícími podmínkami, které musí splňovat.
• Angl. ..Constraint programming". Aplikace
• Problémy vedoucí na těžké kombinatorické řešení.
• Řízení, rozvrhování, plánování.
• DNA sequencing.
IB015 Neimperativní programování - 12
str. 7/27
Obecný postup řešení a domény proměnných
Různé instance paradigmatu
• Podle typu proměnných, vystupujících v popisu problému.
• Pravdivostní hodnoty, Celočíselné hodnoty, Konečné množiny, Doména lineárních funkcí, ...
Postup řešení úloh
• Modelování problému v dané doméně.
• Specifikace proměnných a jejich rozsahů.
• Specifikace omezujících podmínek.
• Vymezení cíle.
• Zjednodušení zadání, propagace omezení.
• Systematické procházení možných valuací a hledání vyhovujícího řešení.
Myšlenka
Program Program Program
Výpočet Výpočet
IB015 Neimperativní programování - 12
str. 8/27
Constraint Programming a SWI-Prolog
Hostitelské jazyky
• Řešiče uvažovaných úloh jsou obvykle součástí jiného hostitelského programovacího jazyka nebo systému.
• Prvním výrazným hostitelem byly jazyky vycházející z logického programovacího paradigmatu.
• Constraint Logic Programming (CLP).
Knihovny ve SWI-Prologu
• clpfd: Constraint Logic Programming over Finite Domains
?- usejnodule(library(clpfd)).
• clpqr: Constraint Logic Programming over Rationals and Reals
?- usejnodule(library(clpqr)).
IB015 Neimperativní programování - 12
str. 9/27
clpfd - výrazy, omezení
Výrazy v celočíselné doméně
• Celé číslo je výrazem v celočíselné doméně.
• Proměnná je výrazem s celočíselné doméně.
• Jsou-li El a E2 výrazy v celočíselné doméně, pak
-El (unární mínus)
E1+E2 (součet), ei*E2 (součin), E1-E2 (rozdíl),
E1~E2 (umocnění), min(El,E2), max(El,E2),
E1/E2 (celočíselné dělení ořezáním), El rem E2 (zbytek po dělení /) jsou výrazy v celočíselné doméně.
Omezující podmínky
• Relační operátory předřazené znakem #.
• El #>= E2, El #=< E2, El #= E2, El #\= E2, El #> E2, El #< E2,
IB015 Neimperativní programování - 12 str. 10/27
clpfd - logické spojky
Logické spojky
• #\ Q - Negace
• P #V Q - Disjunkce
• P #/\ Q - Konjunkce
• p #<==> Q - Ekvivalence
• p #==> Q - Implikace
• p #<== Q - Implikace
Číselná reprezentace logických hodnot
• Pravda/Nepravda jsou realizovány hodnotami i a o.
• Relační operátory jsou aplikovatelné na tyto celočíselné hodnoty.
IB015 Neimperativní programování - 12
str. 11/27
Domény volných proměnných
?Var in +Domain
• Proměnná Var má hodnotu z domény Domain.
+Vars ins +Domain
• Proměnné v seznamu Vars mají hodnotu z domény Domain.
alLdifferent(Vars)
• Každá proměnná ze seznamu Vars má jinou hodnotu.
Specifikace domény
• N —jednoprvková množina obsahující celé číslo N.
• Lower. .Upper — všechna Celá Čísla I taková, Že Lower =< i =< Upper, Lower musí být celé číslo, nebo term inf označující záporné nekonečno, podobně Upper musí být celé číslo, nebo term sup označující kladné nekonečno.
• Domainl \/ Domain2 — sjednocení domén Domainl a Domain2.
IB015 Neimperativní programování - 12 str. 12/27
clpfd - jednoduché dotazy
Pozorování
• Následující dotazy jsou řešeny pouze fází propagace omezujících podmínek (neprochází se systematicky prostor všech možných přiřazení hodnot volným proměnným).
Příklady dotazů na clpfd
• ?- X #\= 20.
X in inf..19\/21..sup.
• ?- X*X #= 144. X in -12\/12.
• ?- 4*X + 2*Y #= 24, X + Y #= 9, X #>= 0, Y #>= 0. X = 3, Y = 6.
• ?- X #= Y #<==> B, X in 0..3, Y in 4..5. B = 0, X in 0..3, Y in 4..5.
IB015 Neimperativní programování - 12
str. 13/27
SEND + MORE = MONEY
Popis
• Kryptoaritmetické puzzle, každé písmeno představuje jednu cifru, žádná dvě různá písmena nepředstavují tutéž cifru. Jaké je mapování písmen na číslice?
Zadání pro clpfd
• puzzle([S,E,N,D]+ [M,0,R,E] = [M,0,N,E,Y]) :-
Vars = [S,E,N,D,M,0,R,Y],
Vars ins 0..9,
all_different(Vars),
S*1000 + E*100 + N*10 + D + M*1000 + 0*100 + R*10 + E #=
M*10000 + 0*1000 + N*100 + E*10 + Y,
M #\= 0, S #\= 0.
IB015 Neimperativní programování - 12
str. 14/27
clpfd - hledání řešení
label(+Vars)
• Zahájí hledání vyhovujících hodnot proměnných Vars.
• Totéž, CO labeling( [] ,Vars) .
labeling(+Options,+Vars)
• Zahájí hledání vyhovujících hodnot proměnných Vars.
• Parametry uvedené v seznamu Options ovlivňují způsob enumerace hledaných hodnot.
Parametry hledání
• Pořadí fixace proměnných.
• Směr prohledávání domén.
• Strategie větvení prohledávaného stromu.
IB015 Neimperativní programování - 12
str. 15/27
clpfd - parametry hledání řešení
Pořadí fixace proměnných
• íeftmost — přiřazuje hodnoty proměnným v tom pořadí, ve kterém jsou uvedeny.
• ff — preferuje proměnné s menšími doménami.
• ffc — preferuje proměnné, které participují v největším počtu omezujících podmínek.
• min — preferuje proměnná s nejmenší spodní závorou.
• max — preferuje proměnná s největší horní závorou.
Směr prohledávání domén
• up — zkouší prvky domény od nej menších k největším.
• down — zkouší prvky domény od největších k nej menším.
IB015 Neimperativní programování - 12
str. 16/27
SEND + MORE = MONEY
Odpověď cípfd bez prohledávání
• Vars = [9, E, N, D, 1, 0, R, Y], S = 9, M = 1, 0 = 0,
E in 4..7, N in 5..8, D in 2..8, R in 2..8, Y in 2..8, all.different([9, E, N, D, 1, 0, R, Y]), 1000*9+91*E+ -90*N+D+ -9000*1+ -900*0+10*R+ -1*Y#=0.
Požadavek na prohledávání
• Uvedením podcíle labeK [s,e,n,d]) .
Odpověd cípfd s vyhledáním valuací proměnných S,E,N a D
• Vars = [9, 5, 6, 7, 1, 0, 8, 2], S = 9, E = 5, N = 6, D = 7, M=1,0=0,R=8,Y=2; falše.
IB015 Neimperativní programování - 12
str. 17/27
clpfd - vybrané predikáty omezujících podmínek
sum (+Vars ,+Rel, ?Expr)
• Součet hodnot proměnných v seznamu Vars je v relaci Rei s hodnotou výrazu Expr.
sca lar_product (+C s, + Vs, +Re 1, ?Expr)
• Skalární součin seznamu čísel Cs s čísly, nebo proměnnými v seznamu Vs, je v relaci Rei s hodnotou výrazu Expr.
serialized(+Starts ,+Durations)
• Pro hodnoty Starts=[Sl.....SN] a Durations=[Dl.....DN] ,
platí, že úlohy začínající v čase si a trvající dobu Dl se nepřekrývají, tj. si+di =< s j nebo sj+dj =< si.
IB015 Neimperativní programování - 12
clpfd a celočíselná aritmetika
Jiné použití clpfd v Prologu
• Aritmetické vyhodnocování v celých číslech bez nutnosti instanciace argumentů aritmetických operací (propagace hodnot všemi směry).
Příklad
• n_factorial(0,l). n_factorial(N,F) :-
N #> 0, NI #= N - 1, F #= N * Fl, n_factorial(Nl,Fl).
• ?- n_factorial(N,l) . N = 0 ;
N = 1 ; falše.
IB015 Neimperativní programování - 12
Sekce
Deklarativní versus imperativní
IB015 Neimperativní programování - 12
str. 20/27
Deklarativní programovací paradigma
Princip
• Programem je především formulace cíle a vztahu požadovaného výsledku výpočtu k daným vstupům.
• Popis postupu výpočtu není požadován, neboje druhotným vstupem zadávaným kvůli zvýšení efektivity výpočtu.
Výhody a nevýhody
+ Kratší a srozumitelnější kód. + Méně skrytých chyb.
- Náročnější tvorba kódu, požaduje schopnost abstrakce.
- Riziko neefektivního řešení.
Obtížná přímá kontrola výpočetního HW.
IB015 Neimperativní programování - 12
str. 21/27
Imperativní programovací paradigma
Princip
• Programem je popis transformace zadaných vstupů na požadovaný výsledek.
• Popis vztahů výsledku vzhledem ke vstupům není požadován, neboje do programu vkládán za účelem kontroly korektnosti popisované transformace.
Výhody a nevýhody
+ Detailní kontrola nad postupem výpočtu.
+ Efektivní využití dostupného HW .
+ Snazší tvorba kódu.
- Více prostoru pro zanesení chyb.
- Skryté a dlouho neodhalené chyby.
- Nečitelnost významu programu.
IB015 Neimperativní programování - 12
str. 22/27
Průnik deklarativních a imperativního světa
Jazykové konstrukce
• Nepojmenované funkce (lambda funkce).
• Parametrický polymorfismus / generické programování.
• Silná typová kontrola.
• Sémantika jazyka oddělená od výpočetního HW.
Programátorský styl
• Přenos kontroly typů z doby za běhu programu do doby kompilace.
• Deklarace vzájemných vztahů vnitřních dat v imperativním programu.
• Programování bez pomocných přepisovatelných proměnných.
IB015 Neimperativní programování - 12
str. 23/27
Příklad použití deklarativního stylu
Původně imperativním stylem
• int vysledek=l; for (int i=l; i<=N; {
vysledek=vysledek*i;
}
print výsledek;
Nově deklarativním stylem
• int fact(int n) {
if (n==0) return 1; else return n*fact(n-l);
}
print fact(N);
IB015 Neimperativní programování - 12
Příklad použití deklarativního stylu
Původně imperativním stylem
• int vysledek=l; • Co to vlastně počítá?
for (int i=l; i<=N; {
vysledek=vysledek*i;
}
print výsledek;
Nově deklarativním stylem
• int fact(int n) {
if (n==0) return 1; else return n*fact(n-l);
}
print fact(N);
IB015 Neimperativní programování - 12
Příklad použití deklarativního stylu
Původně imperativním stylem
• int vysledek=l;
for (int i=l;  i<=N; i++) {
vysledek=vysledek*i;
}
print výsledek;
• Co to vlastně počítá?
• Přepisovatelná proměnná navíc, těžší optimalizace.
Nově deklarativním stylem
• int fact(int n) {
if (n==0) return 1; else return n*fact(n-l);
}
print fact(N);
IB015 Neimperativní programování - 12
Příklad použití deklarativního stylu
Původně imperativním stylem
• int vysledek=l; for (int i=l; i<=N; {
vysledek=vysledek*i;
}
print výsledek;
Nově deklarativním stylem
• int fact(int n) {
if (n==0) return 1; else return n*fact(n-l);
}
print fact(N);
IB015 Neimperativní programování - 12
• Co to vlastně počítá?
• Přepisovatelná proměnná navíc, těžší optimalizace.
• Větší prostor pro zanesení chyb (i=i, í<=n).
Příklad použití deklarativního stylu
Původně imperativním stylem
• int vysledek=l;
for (int i=l;  i<=N; i++) {
vysledek=vysledek*i;
}
print výsledek;
Nově deklarativním stylem
• int fact(int n) {
if (n==0) return 1; else return n*fact(n-l);
}
print fact(N);
IB015 Neimperativní programování - 12
• Co to vlastně počítá?
• Přepisovatelná proměnná navíc, těžší optimalizace.
• Větší prostor pro zanesení chyb (i=i, í<=n).
• „Skryté" chování pro n=o.
Příklad použití deklarativního stylu
Původně imperativním stylem
• int vysledek=l;
for (int i=l;  i<=N; i++) {
vysledek=vysledek*i;
}
print výsledek;
Nově deklarativním stylem
• int fact(int n) {
if (n==0) return 1; else return n*fact(n-l);
}
print fact(N);
• Co to vlastně počítá?
• Přepisovatelná proměnná navíc, těžší optimalizace.
• Větší prostor pro zanesení chyb (i=i, í<=n).
• „Skryté" chování pro n=o.
• Jasné chování pro n=o.
IB015 Neimperativní programování - 12
str. 24/27
Příklad použití deklarativního stylu
Původně imperativním stylem
• int vysledek=l;
for (int i=l;  i<=N; i++) {
vysledek=vysledek*i;
}
print výsledek;
Nově deklarativním stylem
• int fact(int n) {
if (n==0) return 1; else return n*fact(n-l);
}
print fact(N);
• Co to vlastně počítá?
• Přepisovatelná proměnná navíc, těžší optimalizace.
• Větší prostor pro zanesení chyb (i=i, í<=n).
• „Skryté" chování pro n=o.
• Jasné chování pro n=o.
• Pojmenovaná funkce, syntaktická indicie pro sémantický význam.
IB015 Neimperativní programování - 12
str. 24/27
Sekce
A to je konec
IB015 Neimperativní programování - 12
Závěrem
Co si odneseme do života ...
• Funkcionální výpočetní paradigma.
• Solidní základy programovacího jazyka Haskell.
• Solidní základy programování v Prologu.
Čím ještě nám byl kurz prospěšný ...
• Deklarativní návyky při návrhu programů a algoritmů mnohokrát využijeme v naší (převážně imperativní) informatické praxi.
• Mentální posilovna.
IB015 Neimperativní programování - 12
str. 26/27
Závěrem
Co si odneseme do života ...
• Funkcionální výpočetní paradigma.
• Solidní základy programovacího jazyka Haskell.
• Solidní základy programování v Prologu.
Čím ještě nám byl kurz prospěšný ...
• Deklarativní návyky při návrhu programů a algoritmů mnohokrát využijeme v naší (převážně imperativní) informatické praxi.
• Mentální posilovna.
IB015 Neimperativní programování - 12
str. 26/27
Poděkování
Přednášejícího studentům
• Za vzornou docházku a přípravu jak na přednášky, tak i na cvičení, vnitrosemestrální a zkouškové písemky, a za celkově poctivý přístup ke studiu.
Studentů přednášejícímu
• Formou zpětné vazby například vyplněním studentské ankety a upozorněním na zásadní, ale i okrajové nedostatky jak přednášejícího, tak i jím připravených studijních materiálů.
IB015 Neimperativní programování - 12
str. 27/27