Принудно логичко програмирање је облик принуде програма, у којем логика програмирања је проширена на концепте за ограничење задовољства. Принудни логички програм је логика програма који садржи ограничења у телу клаузула. Пример клаузуле укључујући ограничења је A(X,Y) :- X+Y>0, B(X), C(Y). У овој клаузули, X+Y>0 је ограничење; A(X,Y), B(X), и C(Y) су литерали као у редовном логичком програмирању. Ова клаузула каже један услов под којим је изјава A(X,Y) држи: X+Y је већи од нуле и оба B(X) и C(Y) су истинита.
Као и редовно логичко програмирање, програми се упита о вероватноћи циља, који може да садржи ограничења поред литерала. Доказ за циљ се састоји од клаузула чија су задовољива ограничења и литерали који могу да користе и друге клаузуле тела. Извршење се врши преко тумача, који полази од циља и рекурсивно скенира клаузуле покушавајући да докаже циљ. Ограничења са којима се сусрећу током овог прегледа се налазе у одређеним ограниченим продавницама. Ако овај скуп налази unsatisfiable, преводилац се повлачи, покушавајући да искористе друге одредбе за доказивање циља. У пракси, задовољивости на ограничење продавници може се проверити помоћу непотпуних алгоритама, који не открије увек недоследност.
Преглед Формално, принудни логички програми су као редовне програмске логике, али тела клаузула могу да садрже ограничења, поред редовних програмских логичких литерала. Као пример, X>0 је ограничење, а укључена је у последњој клаузули следећег принудног логичког програма. B(X,1):- X<0. B(X,Y):- X=1, Y>0. A(X,Y):- X>0, B(X,Y). Као у редовном логичком програмирању, вредновање циља као што је A(X,1) захтева оцену тела последње клаузуле са Y=1. Као у редовној логици програмирања, заузврат захтева доказивање самог циља B(X,1). За разлику од редовне логике програмирања, такође захтева да ограничење треба да задовољ: X>0, ограничење у телу последње клаузуле (у редовном логичком програмирању, X>0 се не може доказати, осим ако је X везан за потпуно приземљени рок и извршење програма неће успети ако то није случај).
Да ли ће ограничење бити задовољно не може увек да се одреди када ограничење наиђе. У овом случају, на пример, вредност X није одређена приликом вредновања задње клаузуле. Као резултат тога, ограничење X>0 није задовољно ни повређено у овом тренутку. Уместо поступања у процени B(X,1), а затим проверавања да ли је резултирало вредности X као позитивне касније, преводилац продавнице ограничења X>0, а затим наставља у процени B(X,1); На овај начин, преводилац може да детектује кршење ограничења X>0 током процене B(X,1), и одмах одустане ако је то случај, уместо да чекају процену B(X,1) да закључи.
У принципу, процена ограничења логике програма одвија се као у редовном логичком програму, али ограничења са којима се сусрећу током процене се налазе у одређеној ограниченој продавници. Као пример, вредновње гола A(X,1) приходи са оцењивања тела првог дела реченице са Y=1; Ова процена додаје X>0 за ограничење продавнице и тражи гол B(X,1) да се докаже. Док покушава да докаже тај циљ, прва клаузула је примењива, али његова вредност додаје X<0 за ограничење продавнице. Овај додатак чини ограничење продавница unsatisfiable, а преводилац повлачи, уклањање последњег додатка од ограничење продавнице. Евалуација друге клаузуле додаје X=1 и Y>0 за ограничење продавнице. Пошто је ограничење продавница задовољиво и ниједна друга буквално није је остала да се докаже, преводилац престаје са решењем X=1, Y=1.
Семантика Семантика ограничених логичких програма може да се дефинише у смислу виртуелне преводиоце који одржава пар G, S током извршења. Први елемент овог пара се зове тренутни циљ; Други елемент се зове ограничење продавнице. Садашњи циљ садржи литерал преводиоца покушава да докаже и може да садржи и нека ограничења да покушава да задовољи; ограничена продавница садржи све задовољиве препреке преводиоца које је до сада преузела.
У почетку, тренутни циљ је циљ и ограничена продавница је празна. Преводилац наставља уклањањем првог елемента из тренутног циља и њеном анализом. Детаљи ове анализе су испод објашњени, али на крају ове анализе може произвести успешан завршетак или неуспех. Ова анализа може да подразумева рекурзивне позиве и додавање нових литерале до тренутног циља и новог ограничења за ограничење продавнице. Преводилац се повлачи ако је неуспех генерисан. Успешан престанак се генерише када је струја циљ празна и ограничење продавница задовољиво.
Детаљи анализе буквално су скинути са циљем који следи. Након уклањања овога буквално испред решења, он се проверава да ли је ограничење или буквално. Ако је ограничење, она се додаје ограниченој продавници. Ако је буквална, клаузула чија је глава има исти предикат буквално који је изабран; клаузула је преписана заменом своје променљиве са новим варијаблама (варијабле се не јавља у циљу): резултат се зове свежа варијанта клаузулом; тело свеже варијанте клаузуле се затим ставља испред циља; једнакост сваког аргумента буквално са одговарајућим једним од свежег варијанте главе налази се у испред решења као добра.
Неки провере се врше током тих операција. Посебно, ограничење продавница проверава доследност сваки пут када се ново ограничење додаје на њега. У принципу, кад год је ограничење продавница unsatisfiable алгоритам може да одустане. Међутим, провера unsatisfiable на сваком кораку ће бити неефикасна. Из тог разлога, непотпуна задовољивост жетона се може користити. У пракси, задовољивости се проверавају помоћу методе које поједностављују наметања радњи, то јест, преписати га у еквивалентне али једноставније облику за решавање. Ове методе понекад, али не увек докажу unsatisfiable једног unsatisfiable ограничења продавница.
Преводилац је доказао циљ када је струја циља празна, а ограничење продавница није откривено unsatisfiable. Резултат извршења је тренутни сет (симплифиед) ограничења. Овај скуп може да обухвати ограничења као што је X=2 да сила променљивих на специфичну вредност, али може обухватити ограничења као што X>2 да само везују променљиве а да нема посебну вредност.
Формално, семантика принудне логике програмирања је дефинисана у смислу извођења. Транзиција је пар парова Гол/продавница, истиче G, S --> G', S'. Такав пар наводи могућност одласка из стања G, S у стање G', S'. Таква транзиција је могуће у три могућа случаја: * елемент G је ограничење C, G' = G\ {C} и S' = S' = S u {C}; Другим речима, ограничење може да се помера са циљем ка ограниченој продавници
* елемент G буквално L(t1,...,tn), постоји клаузула преписана користећи нове променљиве, је L(t'1,...,t'n): - B, G' је G са L(t1,...,t'n) замењена t1 = t'1,...,tn = t'n, B, и S' = S; Другим речима, буквално може бити замењено тело свеже варијанте клаузулом који има исти предикат у глави, додајући тело свеже варијанте и горе једнакости појмова до циља
* S и S' еквивалентни у складу са специфичном ограниченом семантиком Низ прелаза је порекло. А циљ G може доказати да ли постоји извођење из G,0 у 0, S за неко задовољиво ограничење продавница S. Семантика формализује могуће еволуције тумача да произвољно бира литерале у циљу процеса и клаузула да замени литерале. Другим речима, циљ доказан овом семантиком ако постоји низ избора литерала и клаузула, међу многим евентуално оних, који доводе до празног циља и задовољиве продавнице.
Актуални преводиоци обрађују елементе циља у ЛИФО ред : елементи се додају у предњи и обрађују од напред. Они такође бирају клаузулу другог правила према редоследу којим су писане, и препише ограничење продавници када је модификована.
Трећи могући вид транзиције је замена ограничење продавнице са еквивалентним један. Ово замена је ограничена на оне које се обављају специфичним методама, као што је ограничење размножавања. Семантика ограничења логике програмирања је параметарско не само на врсту ограничења користи, али и методи за преправљање ограничења продавнице. Специфичне методе које се користе у пракси замене ограничења продавнице са једним који је једноставније да реши. Ако је ограничење продавница unsatisfiability, ово поједностављивање може открити овај unsatisfiability понекад, али не увек.
Резултат процене за циљ против ограничене логике програма је дефинисан ако је циљ доказан. У овом случају, постоји извођење од почетног пара на пару, где је циљ је празан. Ограничење продавница овог другог пара сматра се резултатом процене. То је зато што ограничење продавница садржи све препреке претпоставља задовољиве да докажу циљ. Другим речима, циљ је показао за све променљиве вредности које задовољавају ова ограничења.
Паровима једнакост у погледу два литерале често се компактно означавају L(t1,...,tn) = (t'1,...,t'n): ово је скраћеница за ограничења t1 = t'1,...,tn = t'n. Заједничка варијанта семантике за ограничење логичког програмирања додаје L(t1,...,tn) = L(t'1,...,t'n) директно на ограничење продавнице радије него до циља.
Услови и ограничења Различите дефиниције термина се користе, стварајући различите врсте принуда логичког програмирања: преко дрвећа, реалних бројева или коначних домена. Нека врста ограничења која је увек присутна је једнакост услова. Таква ограничења су неопходна, јер је преводилац додаје t1 = t2 до циља кад год литерала P(...t1...) је замењен са телом клаузуле свеже варијанте чији је начелник P(...t2...) .
Стабло услови Ограничење логике програмирање са три термина опонаша редовну логику програмирања складиштења супституције као ограничења у ограниченој продавници. Правила су променљиве, константе, и функција симбола које се примењују на другим терминима. Једина ограничења сматрају се једнакости и неједнакости између термина. Једнакост је посебно важна, јер ограничења попут t1 = t2 често генерише преводиоца. Равноправности ограничења о условима може бити поједностављена, која је решена, путем уједињења:
Ограничење t1 = t2 може бити поједностављено ако су оба термина симболи функција које се примењују на другим терминима. Ако су два симбола функција исти и број subterms је такође исти, ово ограничење може бити замењена са поравнавањем једнакости subterms. Ако се услови састоје од симбола различитих функција или истог функтора али на различитим бројем мандата, ограничење је unsatisfiable.
Ако је један од два термина променљива, једину дозвољену вредност променљиве може узети други термин. Као резултат тога, други термин може да замени променљиву у тренутном циљу и ограничење продавнице, тако практично уклања променљиву из разматрања. У конкретном случају једнакости променљиве са собом, ограничење може бити уклоњено као и увек задовољно.
У овом облику ограничење задовољства, променљиве вредности су термини.
Реалс Ограничење логике програмирање са реалних бројева користи праве изразе и термине. Када не користе никакву функцију симболи, термини су изрази преко реалних бројева, вероватно укључујући и варијабле. У том случају, свака променљива може имати само реалан број као вредност.
Да будемо прецизни, термини су изрази преко променљивих и реалних константи. Једнакост између термина је врста ограничења која је увек присутна, као преводилац генерише једнакост услова током извршења. Као пример, ако је први литерал тренутног циљ A(X+1) и преводилац је изабрао клаузулу да је A(Y-1):-Y=1 после преправљања је променљива, ограничења која се додају резултату су X+1=Y-1 и Y=1. Правила поједностављења која се користи за функције симбола се очигледно не користе: X+1=Y-1 није unsatisfiable само зато што је први израз изграђен коришћењем + а други користе - .