Seznamy (pokračování) Optimalizace posledního volání -• Last Call Optimization (LCO) -• Implementační technika snižující nároky na paměť -• Mnoho vnořených rekurzivních volání je náročné na paměť -• Použití LCO umožňuje vnořenou rekurzi s konstantními pamětovými nároky -• Typický příklad, kdy je možné použití LCO: M procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule 3 cíle předcházející tomuto rekurzivnímu volání musí být deterministické M p( ...):- ... % žádné rekurzivní voláni v těle klauzule p( ...):- ... % žádné rekurzivní voláni v těle klauzule p(...) :- ..., !, p( ... ). % řez zajišťuje determinismus «• Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 17. března 2009 2 Seznamy LCO a akumulátor -• Reformulace rekurzivní procedury, aby umožnila LCO -• Výpočet délky seznamu length( Seznam, Délka ) lengthC [], 0 ). lengthC [ H | T ], Délka ) :- lengthC T, DelkaO ), Délka is 1 + DelkaO. Hana Rudová, Logické programování I, 1 7. března 2009 3 Seznamy LCO a akumulátor -• Reformulace rekurzivní procedury, aby umožnila LCO -• Výpočet délky seznamu length( Seznam, Délka ) lengthC [], 0 ). lengthC [ H | T ], Délka ) :- lengthC T, DelkaO ), Délka is 1 + DelkaO. -• Upravená procedura, tak aby umožnila LCO: % lengthC Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam'' Hana Rudová, Logické programování I, 1 7. března 2009 3 Seznamy LCO a akumulátor -• Reformulace rekurzivní procedury, aby umožnila LCO -• Výpočet délky seznamu length( Seznam, Délka ) lengthC [], 0 ). lengthC [ H | T ], Délka ) :- lengthC T, DelkaO ), Délka is 1 + DelkaO. -• Upravená procedura, tak aby umožnila LCO: % lengthC Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam'' lengthC Seznam, Délka ) :- lengthC Seznam, 0, Délka ). % pomocný predikát lengthC [] , Délka, Délka ). % celková délka = započítaná délka lengthC [ H | T ] , A, Délka ) :- A0 is A + 1, lengthC T, A0, Délka ). M Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 1 7. března 2009 3 Seznamy max_list s akumulátorem Výpočet největšího prvku v seznamu max_l ist (Seznam, Max) max_list([X], X). max_list([X|T], Max) :-max_li st(T,MaxT), ( MaxT >= X, !, Max = MaxT Max = X ). Hana Rudová, Logické programování I, 1 7. března 2009 4 Seznamy max_list s akumulátorem Výpočet největšího prvku v seznamu max_l ist (Seznam, Max) max_list([X], X). max_list([X|T], Max) :-max_li st(T,MaxT), ( MaxT >= X, !, Max = MaxT Max = X ). max_list([H|T],Max) :- max_list(T,H,Max). max_list([], Max, Max). max_list([H|T], CastecnyMax, Max) :-( H > CastecnyMax, !, max_list(T, H, Max ) max_list(T, CastecnyMax, Max) ). Hana Rudová, Logické programování I, 17. března 2009 4 Seznamy Akumulátor jako seznam -• Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam ) M reverseC [] , [] ). reverseC [ H | T ], Opacny ) :- Hana Rudová, Logické programování I, 1 7. března 2009 5 Seznamy Akumulátor jako seznam -• Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam ) M reverseC [] , [] ). reverseC [ H | T ], Opacny ) :-reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). M naivní reverse s kvadratickou složitosti Hana Rudová, Logické programování I, 1 7. března 2009 5 Akumulátor jako seznam -• Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam ) M reverseC [] , [] ). reverseC [ H | T ], Opacny ) :-reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). M naivní reverse s kvadratickou složitosti -• reverse pomocí akumulátoru s lineární složitostí M % reverseC Seznam, Akumulátor, Opacny ): % Opacny obdržíme přidáním prvků ze Seznam do Akumulátor v opačném poradi Hana Rudová, Logické programování I, 1 7. března 2009 5 Seznamy Akumulátor jako seznam Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam ) M reverseC [] , [] ). reverseC [ H | T ], Opacny ) :-reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). M naivní reverse s kvadratickou složitosti reverse pomocí akumulátoru s lineární složitostí M % reverseC Seznam, Akumulátor, Opacny ): % Opacny obdržíme přidáním prvků ze Seznam do Akumulátor v opačném poradi reverse( Seznam, OpacnySeznam ) :- reverse( Seznam, [], OpacnySeznam). reverse( [], S, S ). reverse( [ H | T ], A, Opacny ) :- reverse( T, [ H | A ], Opacny ). % přidání H do akumulátoru Hana Rudová, Logické programování I, 1 7. března 2009 5 Seznamy Akumulátor jako seznam «• Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam ) M reverseC [] , [] ). reverseC [ H | T ], Opacny ) :-reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). M naivní reverse s kvadratickou složitosti -• reverse pomocí akumulátoru s lineární složitostí M % reverseC Seznam, Akumulátor, Opacny ): % Opacny obdržíme přidáním prvků ze Seznam do Akumulátor v opačném poradi reverse( Seznam, OpacnySeznam ) :- reverse( Seznam, [], OpacnySeznam). reverse( [], S, S ). reverse( [ H | T ], A, Opacny ) :- reverse( T, [ H | A ], Opacny ). % přidání H do akumulátoru -• zpětná konstrukce seznamu (srovnej s předchozí doprednou konstrukcí, např. append) Hana Rudová, Logické programování I, 17. března 2009 5 Seznamy Neefektivita při spojování seznamů M Sjednocení dvou seznamů -• append( [], S, S ). appendC [X|S1], S2, [X|S3] ) :- append( SI, S2, S3 ). Hana Rudová, Logické programování I, 1 7. března 2009 6 Seznamy Neefektivita při spojování seznamů M Sjednocení dvou seznamů -• append( [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3 ). -• ?- appendC [2,3], [1], S ). Hana Rudová, Logické programování I, 1 7. března 2009 6 Seznamy Neefektivita při spojování seznamů M Sjednocení dvou seznamů -• append( [], S, S ). appendC [X|S1], S2, [X|S3] ) :- append( SI, S2, S3 ). -• ?- append( [2,3], [1], S ). postupné volání cílů: append( [2,3], [1], S ) - append( [3], [1], S') - append( [], [1], S" ) Hana Rudová, Logické programování I, 1 7. března 2009 6 Seznamy Neefektivita při spojování seznamů M Sjednocení dvou seznamů -• append( [], S, S ). appendC [X|S1], S2, [X|S3] ) :- append( SI, S2, S3 ). -• ?- append( [2,3], [1], S ). postupné volání cílů: append( [2,3], [1], S ) - append( [3], [1], S') - append( [], [1], S" ) -• Vždy je nutné projít celý první seznam Hana Rudová, Logické programování I, 1 7. března 2009 6 Seznamy Rozdílové seznamy -• Zapamatování konce a připojení na konec: rozdílové seznamy Hana Rudová, Logické programování I, 17. března 2009 7 Seznamy Rozdílové seznamy -• Zapamatování konce a připojení na konec: rozdílové seznamy -• [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] M Reprezentace prázdného seznamu: L-L Hana Rudová, Logické programování I, 17. března 2009 7 Seznamy Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L A1 \i Z1 A2 MM L1 Z2 M L2 appendC Al-Zl, Z1-Z2, A1-Z2 ) LI L2 L3 L3 Hana Rudová, Logické programování I, 1 7. března 2009 7 Seznamy Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L A1 \i Z1 A2 MM L1 Z2 M L2 appendC Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 [2,3] [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 L3 Hana Rudová, Logické programování I, 1 7. března 2009 7 Seznamy Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L A1 \i Z1 A2 MM L1 Z2 M L2 L3 appendC Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 [2,3] [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 [2,3|Z1]-Z2 Hana Rudová, Logické programování I, 1 7. března 2009 7 Seznamy Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L A1 \i Z1 A2 MM L1 Z2 M L2 L3 appendC Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 [2,3] [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 [2,3|Z1]-Z2 [2,3,1|Z2]-Z2 Hana Rudová, Logické programování I, 1 7. března 2009 7 Seznamy Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L A1 \i Z1 A2 MM L1 Z2 M L2 L3 appendC Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 [2,3] [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 [2,3|Z1]-Z2 [2,3,1|Z2]-Z2 -• ?- appendC [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S = Al - Z2 = [2,31 ZI] - Z2 = [2,31 [1|Z2] ] - Z2 ZI = [1|Z2] S = [2,3,1|Z2]-Z2 -• Jednotková složitost, oblíbená technika ale není tak flexibilní Hana Rudová, Logické programování I, 1 7. března 2009 7 Seznamy Akumulátor vs. rozdílové seznamy: reverse reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). kvadratická složitost reverseC Seznam, Opacny ) :- reverseOC Seznam, [], Opacny ). reverseOC [] , S, S ). reverseOC [ H | T ], A, Opacny ) :- reverseOC T, [ H I A ], Opacny ). akumulátor Clineárni) Hana Rudová, Logické programování I, 1 7. března 2009 8 Seznamy Akumulátor vs. rozdílové seznamy: reverse reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). kvadratická složitost reverseC Seznam, Opacny ) :- reverseOC Seznam, [], Opacny ). reverseOC [] , S, S ). reverseOC [ H | T ], A, Opacny ) :- reverseOC T, [ H I A ], Opacny ). akumulátor Clineárni) reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[]). reverseOC [], S-S ). reverseOC [ H | T ], Opacny-OpacnyKonec ) :- rozdílové seznamy reverseOC T, Opacny-[ H | OpacnyKonec] ). Clineárni) Hana Rudová, Logické programování I, 1 7. března 2009 8 Seznamy Akumulátor vs. rozdílové seznamy: reverse reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). kvadratická složitost reverseC Seznam, Opacny ) :- reverseOC Seznam, [], Opacny ). reverseOC [] , S, S ). reverseOC [ H | T ], A, Opacny ) :- reverseOC T, [ H I A ], Opacny ). akumulátor Oineárni) reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[]). reverseOC [], S-S ). reverseOC [ H | T ], Opacny-OpacnyKonec ) :- rozdílové seznamy reverseOC T, Opacny-[ H | OpacnyKonec] ). Oineárni) Příklad: operace pro manipulaci s frontou M test na prázdnost, přidání na konec, odebrání ze začátku Hana Rudová, Logické programování I, 1 7. března 2009 8 Seznamy Vestavěné predikáty Vestavěné predikáty -• Predikáty pro řízení běhu programu 3 fail , true, ... «• Různé typy rovností M unifikace, aritmetická rovnost, ... -• Databázové operace M změna programu (programové databáze) za jeho běhu -• Vstup a výstup -• Všechna řešení programu -• Testování typu termu -• proměnná?, konstanta?, struktura?, ... M Konstrukce a dekompozice termu M argumenty?, funktor?, ... Hana Rudová, Logické programování I, 17. března 2009 10 Vestavěné predikáty Databázové operace Databáze: specifikace množiny relací Prologovský program: programová databáze, kde jsou relace specifikovány explicitně (fakty) i implicitně (pravidly) Vestavěné predikáty pro změnu databáze během provádění programu: assert( Klauzule ) přidání Klauzule do programu asserta( Klauzule ) přidání na začátek assertz( Klauzule ) přidání na konec retract( Klauzule ) smazání klauzule unifikovatelné s Klauzule Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování I, 17. března 2009 1 1 Vestavěné predikáty Příklad: databázové operace -• Caching: odpovědi na dotazy jsou přidány do programové databáze Hana Rudová, Logické programování I, 17. března 2009 12 Vestavěné predikáty Příklad: databázové operace -• Caching: odpovědi na dotazy jsou přidány do programové databáze M ?- solve( problem, Solution), assertaC solve( problem, Solution) ). -• :- dynamic solve/2. % nezbytné při použití v SICStus Prologu Hana Rudová, Logické programování I, 1 7. března 2009 1 2 Vestavěné predikáty Příklad: databázové operace Caching: odpovědi na dotazy jsou přidány do programové databáze M ?- solve( problem, Solution), assertaC solve( problem, Solution) ). -• :- dynamic solve/2. % nezbytné při použití v SICStus Prologu Příklad: uloz_trojice( Seznámí, Seznam2 ) :-member( XI, Seznámí ), member( X2, Seznam2 ), spocitej_treti( XI, X2, X3 ), assertz( trojice( XI, X2, X3 ) ), f ai 1 . Hana Rudová, Logické programování I, 17. března 2009 12 Vestavěné predikáty Příklad: databázové operace -• Caching: odpovědi na dotazy jsou přidány do programové databáze M ?- solve( problem, Solution), assertaC solve( problem, Solution) ). -• :- dynamic solve/2. % nezbytné při použití v SICStus Prologu M Příklad: uloz_trojice( Seznámí, Seznam2 ) :- member( XI, Seznámí ), member( X2, Seznam2 ), spocitej_treti( XI, X2, X3 ), assertz( trojice( XI, X2, X3 ) ), f ai 1 . uloz_trojice( _, _ ) :- !. Hana Rudová, Logické programování I, 17. března 2009 12 Vestavěné predikáty Vstup a výstup user chápán jako jeden ze vstupních proudů datový výstup na terminál chápán jako jeden z výstupních proudů soubor 1 soubor 2 program může číst data ze vstupního proudu (input stream) program může zapisovat data do výstupního proudu (output stream) dva aktivní proudy -• aktivní vstupní proud M aktivní výstupní proud uživatelský terminál - user 3 datový vstup z terminálu uživatelsky terminal program user soubor 3 soubor 4 vstupni proudy vystupni proudy Hana Rudová, Logické programování I, 1 7. března 2009 13 Vestavěné predikáty Vstupní a výstupní proudy: vestavěné predikáty -• změna (otevření) aktivního vstupního/výstupního proudu: see(S)/tell (S) ctem" ( Soubor ) :- see( Soubor ), cteni_ze_souboru( Informace ), see( user ). -• uzavření aktivního vstupního/výstupního proudu: seen/told Hana Rudová, Logické programování I, 1 7. března 2009 1 4 Vestavěné predikáty Vstupní a výstupní proudy: vestavěné predikáty -• změna (otevření) aktivního vstupního/výstupního proudu: see(S)/tell (S) ctem" ( Soubor ) :- see( Soubor ), cteni_ze_souboru( Informace ), see( user ). -• uzavření aktivního vstupního/výstupního proudu: seen/told M zjištění aktivního vstupního/výstupního proudu: seeing(S)/telling(S) ctem" ( Soubor ) :- seeing( StarySoubor ), see( Soubor ) , cteni_ze_souboru( Informace ), seen, see( StarySoubor ). Hana Rudová, Logické programování I, 1 7. března 2009 1 4 Vestavěné predikáty Sekvenční přístup -• čtení dalšího termu: read(Term) * při čtení jsou termy odděleny tečkou | ?- read(A), read( ahoj(B) ), Hana Rudová, Logické programování I, 1 7. března 2009 k textovým souborům readC [C,D] ). 15 Vestavěné predikáty Sekvenční přístup k textovým souborům -• čtení dalšího termu: read(Term) * při čtení jsou termy odděleny tečkou | ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahojC petre ). [ ahoj( 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme Hana Rudová, Logické programování I, 1 7. března 2009 1 5 Vestavěné predikáty Sekvenční přístup k textovým souborům -• čtení dalšího termu: read(Term) * při čtení jsou termy odděleny tečkou | ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahojC petre ). [ ahoj( 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme M po dosažení konce souboru je vrácen atom end_of_f i 1 e 3 zápis dalšího termu: write(Term) ?- write( ahoj ). ?- write( 'Ahoj Petre!' ). nový řádek na výstup: ni N mezer na výstup: tab(N) Hana Rudová, Logické programování I, 1 7. března 2009 1 5 Vestavěné predikáty Sekvenční přístup k textovým souborům -• čtení dalšího termu: read(Term) 3 při čtení jsou termy odděleny tečkou | ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahojC petre ). [ ahoj( 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme M po dosažení konce souboru je vrácen atom end_of_f i 1 e 3 zápis dalšího termu: write(Term) ?- write( ahoj ). ?- write( 'Ahoj Petre!' ). nový řádek na výstup: ni N mezer na výstup: tab(N) -• čtení/zápis dalšího znaku: getO(Znak) , get(NeprazdnyZnak)/put(Znak) 3 po dosažení konce souboru je vrácena -1 Hana Rudová, Logické programování I, 1 7. března 2009 1 5 Vestavěné predikáty Příklad čtení process_file( Soubor ) :- seeingC StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, i ■ j seen, see( StarySoubor ). repeat. repeat :- repeat. Hana Rudová, Logické programování I, 1 7. března 2009 1 6 ze souboru % zjištěni aktivního proudu % otevřeni souboru Soubor % čteni termu Term % manipulace s termem % je konec souboru? % uzavřeni souboru % aktivace původniho proudu % opakováni Vestavěné predikáty Ctení programu ze souboru -• Interpretování kódu programu -• ?- consul t(program). M ?- consultCprogram.pl') . -• ?- consultC [programl, 'program2.pl'] ). -• ?- [program] . 3 ?- [user] . zadávání kódu ze vstupu ukončené CTRL+D Hana Rudová, Logické programování I, 1 7. března 2009 1 7 Vestavěné predikáty Ctení programu ze souboru -• Interpretování kódu programu -• ?- consul t(program). M ?- consultCprogram.pl') . -• ?- consultC [programl, 'program2.pl'] ). -• ?- [program] . 3 ?- [user] . zadávání kódu ze vstupu ukončené CTRL+D -• Kompilace kódu programu 3 ?- compile( [programl, 'program2.pl'] ). -• další varianty podobně jako u interpretování -• typické zrychlení: 5 až 10 krát Hana Rudová, Logické programování I, 1 7. března 2009 1 7 Vestavěné predikáty