Seznamy (pokračování) 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 I T ], A, Délka ) :- A0 is A + 1, lengthC T, A0, Délka ). Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 17. března 2009 3 Seznamy 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: ■ procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule ■ cíle předcházející tomuto rekurzivnímu volání musí být deterministické ■ pC ...):- ... % žádné rekurzivní voláni v těle klauzule pC ...):- ... % žádné rekurzivní voláni v těle klauzule pC-..) :- !, pC ■■■ )■ % ř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 max_list s akumulátorem Výpočet největšího prvku v seznamu max_"list(Seznam, Max) max_listC[X], X). max_listC[X|T], Max) :-max_li st CT,MaxT), C MaxT >= X, !, Max = MaxT Max = X ). max_listC[H|T],Max) :- max_listCT,H,Max). max_listC[], Max, Max). max_li st C[H|T], CastecnyMax, Max) :-C H > CastecnyMax, !, max_listCT, H, Max ) max_listCT, 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 ) ■ reverseC [] , [] ) . reverseC [ H | T ], Opacny ) :-reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). ■ naivní reverse s kvadratickou složitosti reverse pomocí akumulátoru s lineární složitostí ■% reverseC Seznam, Akumulátor, Opacny ): % Opacny obdržíme přidáním prvků ze Seznam do Akumulátor v opačném poradi reversef Seznam, OpacnySeznam ) :- reversef Seznam, [], OpacnySeznam). reversef [], S, S ). reversef [ H | T ], A, Opacny ) :- reversef T, [ H | A ], Opacny ). % přidání H do akumulátoru ■ zpětná konstrukce seznamu (srovnej s předchozí dopřednou konstrukcí, např. append) Hana Rudová, Logické programování I, 17. března 2009 5 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 Z1 A2 Z2 L1 1 L2 \ append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 [2,3] [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 L3 [2,3|Z1]-Z2 [2,3,1|Z2]-Z2 ?- append( [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S = AI - Z2 = [2,3|Zl] - Z2 = [2,3| [1|Z2] ] - Z2 Zl = [1|Z2] S = [2,3,1|Z2]-Z2 Jednotková složitost, oblíbená technika ale není tak flexibilní Hana Rudová, Logické programování I, 17. března 2009 7 Neefektivita při spojování seznamů Sjednocení dvou seznamů append( [], S, S ). append( [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ždyje nutné projít celý první seznam Hana Rudová, Logické programování I, 17. března 2009 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 | A ], Opacny ). akumulátor Oineárni) reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[]). reverseOC □ , S-S ). reverseOC [ H | T ], Opacny-OpacnyKonec ) :- reverseOC T, Opacny-[ H | OpacnyKonec] ). rozdílové seznamy Cl i neárni) Příklad: operace pro manipulaci s frontou ■ test na prázdnost, přidání na konec, odebrání ze začátku Hana Rudová, Logické programování I, 17. března 2009 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 ) asserta( Klauzule ) assertz( Klauzule ) retract( Klauzule ) přidání Klauzule do programu přidání na začátek přidání na konec 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 Vestavěné predikáty Vestavěné predikáty Predikáty pro řízení běhu programu ■ fai 1 , true, ... Různé typy rovností ■ unifikace, aritmetická rovnost, ... Databázové operace ■ změna programu (programové databáze) zajeho běhu Vstup a výstup Všechna řešení programu Testování typu termu ■ proměnná?, konstanta?, struktura?, ... Konstrukce a dekompozice termu ■ argumenty?, funktor?, ... Hana Rudová, Logické programování I, 17. března 2009 Vestavěné predikáty Příklad: databázové operace Caching: odpovědi na dotazy jsou přidány do programové databáze ■ ?- solve( problem, Solution), asserta( 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 ) ), fai 1. uloz_trojice( _, _ ) :- !. Hana Rudová, Logické programování I, 17. března 2009 Vestavěné predikáty Vstup a výstup uživatelsky terminal vstupni proudy 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 ■ aktivní výstupní proud uživatelský terminál - user ■ datový vstup z terminálu 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 user program —k soubor 4 vystupni proudy Hana Rudová, Logické programování I, 17. března 2009 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. ahoj C petre ). [ ahojC 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme ■ po dosažení konce souboru je vrácen atom end_of_file zápis dalšího termu: write(Term) ?- writeC ahoj ). ?- write( 'Ahoj Petre!' ). nový řádek na výstup: nl N mezer na výstup: tab(N) čtení/zápis dalšího znaku: getO(Znak) , get(NeprazdnyZnak)/put(Znak) ■ po dosažení konce souboru je vrácena -1 Hana Rudová, Logické programování I, 17. března 2009 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)/te"l"l (S) ctěni( Soubor ) :- see( Soubor ), cteni_ze_souboru( Informace ), see( user ). ■ uzavření aktivního vstupního/výstupního proudu: seen/told ■ zjištění aktivního vstupního/výstupního proudu: seeing(S)/te"l"ling(S) ctěni( Soubor ) :- seeing( StarySoubor ), see( Soubor ), cteni_ze_souboru( Informace ), seen, see( StarySoubor ). Hana Rudová, Logické programování I, 17. března 2009 Vestavěné predikáty Příklad čtení ze souboru process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ) , Term == end_of_file, % zjištěni aktivniho proudu % otevřeni souboru Soubor % čteni termu Term % manipulace s termem % je konec souboru? seen, see( StarySoubor ). % uzavřeni souboru % aktivace původniho proudu repeat. repeat repeat. % opakováni Hana Rudová, Logické programování I, 17. března 2009 Vestavěné predikáty Čtení programu ze souboru ■ Interpretování kódu programu ■ ?- consult(program). ■ ?- consult('program.pl'). ■ ?- consult( [programl, 'program2.pl'] ). ■ ?- [program]. ■ ?- [user]. zadávání kódu ze vstupu ukončené CTRL+D ■ Kompilace kódu programu ■ ?- compile( [programl, 'program2.pl']). ■ další varianty podobně jako u interpretování ■ typické zrychlení: 5 až 10 krát Hana Rudová, Logické programování I, 17. března 2009 17 Vestavěné predikáty