Nikdo jistě nepochybuje o užitečnosti logického programování. Znalost většiny vývojářů ovšem končí u Prologu (pokud vůbec), což je sice velmi elegantní a propracovaný jazyk, ale má i pár nevýhod. Moderní implementace nabízejí tabling, čímž zaručují vyvarování se nekonečné smyčky, pokud program splňuje „bounded term-depth property“, ale až na nečetné výjimky nepodporují disjunkci (protože trvají na Hornových klauzulích). Řešení poskytuje až ASP (dříve nazývané „stable models programming“).
Na první pohled vypadá program v ASP jako program v Prologu. Jedním z hlavních rozdílů je, že umožňuje disjunkci v hlavě pravidla. Výsledkem programu jsou pak všechny stabilní modely, jež odpovídají daným faktům a pravidlům. Typické použití je pro řešení kombinatorických problémů, například barvení grafu.
Z programu v ASP se nejdříve odstraní proměnné, tj. logicky se pravidla převedou na výrokovou logiku. Následně se použije SAT solver, jenž zkonstruuje model (nebo modely), pokud je množina formulí splnitelná. U nedisjunktních programů je tedy výsledek stejný, jako v Prologu (který používá SLD rezoluci).
Jednoduchý příklad:
borders(czechia,slovakia).
borders(czechia,poland).
borders(X,Y) :- borders(Y,X).
Prolog korektně vydá čtyři výsledky, stejně jako ASP, nicméně Prolog k nim dojde směrem od dotazu, kdežto v případě ASP se vybuduje celý model „odspodu“.
Z uvedeného vyplývá, že bez disjunkce je efektivnější použít Prolog. Pokud však charakter problému vyžaduje disjunkci, je ASP lepší volbou.
@1 Grounding v predikátové logice se dost podstatně liší od groundingu v ASP. Spousta optimalizací formulaci problému ve výrokové logice redukuje při zachování sémantiky. Vždy lze vymyslet nějaký teoretický worst case, nicméně u praktických problémů k explozi většinou nedochází. Stěžejní je, jako u všeho, vytipovat takovou množinu problémů, které ASP řeší rychle. Většinou jde o exponenciální problémy, jako třeba plánování, NP-úplné algoritmy v grafech apod.
@1 Teoreticky je to ještě horší než u prologu, protože ASP umožňuje kvantifikované formule nebo optimalizační pravidla a ty se často rozkládají do velkého počtu formulí výrokové logiky. Je tak potřeba si dávat velký pozor na volbu správné reprezentace programu.
Co se mi na ASP líbí je velice dobrá čitelnost výsledných programů (lépe se čtou než píšou) a snadná rozšiřitelnost o další podmínky nebo heuristiky. Oproti prologu vidím největší výhodu právě v rozšířené syntaxi a v deklarativnosti programu.
Např. x :- 3 { něco } 5. - znamená, že aspoň 3 a max. 5 musí být splněno (můžu napsat pro každé x platí ..., a tím se dostávám do pí a sigma tříd složitosti). V prologu se to rozepíše do více pravidel, takže se nezvýší časová složitost (program ale řeší to samé, není to o tom že by něco šlo řešit v ASP a v prologu ne). Tady ano, protože program se dá napsat do málo bitů, ale generuje hodně pravidel.
Prolog ale moc neznám, tak možná už podobné rozšíření existuje taky.
Autor se zabývá vývojem kompilátorů a knihoven pro objektově-orientované programovací jazyky.
Přečteno 36 043×
Přečteno 25 230×
Přečteno 23 683×
Přečteno 20 070×
Přečteno 17 767×