Принудно логичко програмирање

С Википедије, слободне енциклопедије
Парадигме програмирања

Принудно логичко програмирање је облик принуде програма, у којем логика програмирања је проширена на концепте за ограничење задовољства. Принудни логички програм је логика програма који садржи ограничења у телу клаузула. Пример клаузуле укључујући ограничења је 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 само зато што је први израз изграђен коришћењем + а други користе - .

Реалс и функција симболи могу да се комбинују, што је довело до термина који се изржавају преко реалних бројева и функција симбола који се примењују у другим терминима. Формално, варијабле и константе су прави изрази, као и сваки аритметичка оператор над другим изразима. Варијабле, константе (зеро арити функцијом симболи) и изрази су термини, као и било који симбол функција примењује се на крају. Другим речима, термини се граде преко израза, док се изрази граде преко бројева и варијабли. У овом случају, променљиве се крећу преко реалних бројева и услова. Другим речима, променљива може да прави број као вредност, док друга има термин.

Једнакост два мандата може бити поједностављена применом правила за стабла, ако ниједан од ова два термина није прави израз. На пример, ако два термина имају исту функцију симбол и број subterms, њихова равноправност ограничења може бити замењена једнакостима subterms.

Фините домени[уреди | уреди извор]

Трећа класа ограничења користи се за ограничење логичког програмирање које даје коначан домен. Вредности променљивих су у овом случају узете из коначног домена, често од целих бројева. За сваку променљиву, другачији домен може се одредити X::[1..5], на пример значи да је вредност X између 1 и 5. домену променљиве може се дати набрајајући све вредности променљиве се могу узети; Стога, декларација изнад домена може се такође написати X:: [1,2,3,4,5]. Овај други начин наводећи домен омогућава домене који нису састављени од целих бројева, као што су X:: [Георге, Мари, Јохн]. Ако домен променљиве није одређен, претпоставља се да се скуп целих бројева представља на језику. Групи варијабла може се дати исти домен користећи декларацију као [X,Y,Z]::[1..5].

Домен променљиве може да се смањи током извршавања. Заиста, као преводилац додаје ограничења на ограничење продавнице, обавља наметања пропагирања да спроводи неку врсту локалне доследности, и ове операције може смањити домен варијабли. Ако се домен променљиве испразни, ограничење продавница је недоследно, и алгоритам се повлачи. Ако домен променљиве постаје сингл, променљивој може бити додељена јединствена вредност у свом домену. Облици доследности обично спроводе се лук доследности, хипер-лук доследности, и везану доследност. Садашњи домен променљиве може се разгледати применом специфичних литерала; На пример, dom(X,D) сазна тренутни домен D једне променљиве X.

Што се тиче домена реалних бројева, функтори могу користити домене целих бројева. У овом случају, термин може бити израз преко целих бројева, константа, или примена функтора над другим терминима. Променљиве могу да узму произвољан термин као вредност, ако њен домен није наведен да је скуп целих бројева или константи.

Ограничење продавница[уреди | уреди извор]

Ограничење продавница садржи задовољива ограничења која су тренутно преузета. Може се сматрати да је оно тренутна замена је за редовно логичко програмирање. Када су дозвољени само дрво услови, ограничење продавница садржи ограничења у виду t1=t2; ова ограничења се поједностави уједињења, што је резултирало ограничења облик променљива = рок; таква ограничења су еквивалент измени.

Међутим, ограничење продавница може да садржи и ограничења у виду t1!=t2, ако су разлике != између термини дозвољене. Када су дозвољени ограничења преко реалних бројева или коначних домена, ограничење продавница такође може да садржи домен-специфична ограничења као што су X+2=Y/2, итд

Ограничење продавница проширује концепт тренутне замене на два начина. Прво, она не садржи само ограничења која проистичу из изједначавања буквално са главом свеже варијантне клаузуле, већ и ограничења тела клаузула. Друго, не садржи само ограничења на облик променљива = вредност, али и ограничења посматраног ограничењу језика. Иако је резултат успешне евалуације редовна логика програма је коначна супституција, резултат за ограничење логике програма је коначно ограничење продавница, које могу да садрже ограничења на облик променљиве = вредност, али у целини може да садржи произвољна ограничења.

Домаин специфична ограничења могу доћи до ограничења продавница до тела клаузула и до изједначавања буквално са клаузулном главом: на пример, ако преводилац преписује дословно A(X+2) са клаузулом чије свеже варијанта глава A(Y/2), ограничење X+2=Y/2 додаје се у ограничење продавнице. Ако се променљива појављује у стварној или ограниченом домену изражавања, може само узети вредност у реалним бројевима или коначном домену. Таква променљива не може да узме термин направљен од функтора примењен на другим терминима као вредност. Ограничење продавница је unsatisfiable ако је променљива у обавези да предузме обе вредности специфичне области и функтора примењен на услове.

Након ограничења се додаје ограничење продавнице, неке операције се изводе на ограничење продавнице. Који послови се обављају зависи перформанси домена и ограничења. На пример, уједињење се користи за коначно дрвеће једнакости, променљиво елиминисање једначина полинома преко реалних бројева, ограничење ширења како би се спровео неки облик локалне доследности за коначан домен. Ове операције су усмерене на доношење ограничења продавница једноставније да се провери за задовољивост и решење.

Као резултат тих операција, додавање нових ограничења могу променити старе. Битно је да преводилац може да поништи ове промене када је повлачи. Најједноставнији начин је случај за преводиоца да спасе комплетно стање у продавници сваки пут када прави избор (да бира клаузулу да преправим за циљ). Ефикаснијих метода за дозвољавајуће ограничење продавница да се врати у претходно стање постоји. Конкретно, само да сачувате промене на ограничење продавници постигнут између две тачке избора, укључујући и промене на старим ограничења. Ово се може урадити једноставном уштедом старе вредности на ограничења која су модификована; овај метод се назива заостаје. Напреднији метод је да сачувате промене које су урађено на модификованим ограничења. На пример, линеарни ограничење се мења променом своју коефицијент: штеди разлику између старог и новог коефицијента омогућава враћање промену. Овај други метод се зове семантички повлачење изјаве, јер су семантика промене је прилично сачуван од старе верзије само ограничења.

Означавање[уреди | уреди извор]

Означавање литерала се користи на варијабли преко коначних доменима да проверите задовољивост или делимичну задовољивост о ограничењу продавница и да нађе задовољавајући задатак. Обележавање буквално има облик означавања ([варијабли]), где је аргумент листа варијабли преко коначних домена. Кад год се преводилац процењује такав буквалан, обавља претрагу над доменом варијабли на листи ће наћи задатак да задовољава сва релевантна ограничења. Типично, то се ради форми повлачење изјаве: променљиве се вреднују како, покушавајући све могуће вредности за сваки од њих, и одустајање када се открије недоследност.

Прва употреба обележавања либерала је да стварне провере задовољивости или делимично задовољивости на ограничење продавнице. Када преводилац додаје ограничење за ограничење продавнице, он само спроводи један облик локалне доследности у томе. Ова операција не може детектовати недоследност чак и ако је ограничење продавница unsatisfiable. Обележавање буквално преко скупа варијабли спроводи проверу задовољивости од ограничења преко ових варијабли. Као резултат тога, користећи све променљиве наведене у резултатима ограничење продавницу у проверу задовољивости у продавници.

Друга употреба обележавања либерала је заправо да одреди процену варијабли које задовољава ограничење продавнице. Без етикетирања либерала, променљивим се додељују вредности само када је ограничење продавница садржи ограничења облика X=вредности и када се локална доследност смањује домен променљиве на једној вредности. Обележавање буквално преко неких варијабли присиљава ове променљиве да се процене. Другим речима, после етикете либерал разматра, све варијабле којима се додељују вредности.

Типично, ограничења логичких програма су написани на такав начин да се обележавања литерали оцењује тек након што се више ограничења могу акумулирати у ограничење продавнице. То је зато што обележавања литерала спроводе претрагу, а претрага је ефикаснија ако постоје више ограничења да буду задовољни. Проблем задовољство ограничење је типично решење ограничења логике програма који има следећу структуру: 

решење(X):-ограничења(X), етикетирање(X)
ограничење(X):- (сва ограничења CSP-а)

Када преводилац оцењује циљ решавања (args), ставља тело свеже варијанте прве клаузуле у тренутни циљ. Пошто први циљ је ограничења (X'), друга клаузула се оцењује, а ова операција креће све ограничења у тренутном циљу и на крају у ограничење продавнице. Буквално означавање (X') се онда процењују, због чега је потрага за решење о ограничењу продавнице. Пошто ограничење продавница садржи управо ограничења оригиналног проблема задовољства препрека, ова операција тражи решење првобитног проблема.

Програм reformulations[уреди | уреди извор]

Дато ограничење логике програма се може преформулисати да побољша своју ефикасност. Прво правило је да обележавања литерали ће бити постављено након што се више ограничења на обележеним литералима акумулира у ограничење продавнице. Док у теорији A(X):- означавање (X),X>0 је еквивалентно A(X):-X>0, означавање (X), потрага која се обавља када се преводилац сусреће са етикетирањем либерала на ограничење радња која не садржи ограничења X>0. Као резултат тога, она може генерисати решења, као што су X=-1, која су касније сазнали да се не задовољавају овим ограничењима. С друге стране, у другој формулацији се претрес врши само када је ограничење већ у ограничењу продавнице. Као резултат тога, тражи се враћа само решења која су у складу са тим, искористивши чињеницу да додатна ограничења смањују простор за претрагу.

Други реформулација која може повећати ефикасност је да поставите ограничења пред речи у телу клаузула. Опет, A(X):-B(X),X>0 и A(X):-X>0,B(X) у принципу противвредности. Међутим, први може захтевати више рачунања. На пример, ако је ограничење продавница садржи ограничења X<-2, преводилац рекурсивно процењује B(X) у првом случају; ако успе, онда сазна да је ограничење продавница у супротности са приликом додавања X>0. У другом случају, када се процењује да је клаузула, преводилац први додаје X>0 за ограничење продавнице, а онда евентуално оцењује B(X). Од ограничења продавнице после додавања X>0 испостави се да нису у складу, рекуезивна евалуација B(X) се не обавља уопште.

Трећа реформулација која може повећати ефикасност је додатак вишка ограничења. Ако програмер зна (било којим средствима) да решење неког проблема задовољава специфичнаа ограничења, могу укључити ту препреку да изазове недоследност о ограничењу продавнице у најкраћем могућем року. На пример, ако се унапред зна да ће процена B(X) резултирати позитивној вредности X, програмер може додати X>0 пре било какве појаве B(X).  Као пример, A(X,Y):-B(X),C(X) неће успети на крају A(-2,Z), али ово је сазнао током евалуације subgoal B(X). С друге стране, ако је изнад клаузула замењена A(X,Y):-X>0,A(X),B(X), преводилац повлачи чим ограничење X>0 се додаје у ограничења продавница, која се дешава пред евалуацијом B(X) и почиње.

Ограничена правила за руковање[уреди | уреди извор]

Ограничена правила за руковање су првобитно дефинисана као самостални формализам за одређивање ограничења решења, а касније су уграђене у логичком програмирању. Постоје две врсте принуде правила руковања. Правила прве врсте наводе да, под одређеним условима, скуп ограничења је еквивалентан другом. Правила друге врсте наводе да, под одређеним условима, скуп ограничења подразумева још једну. У језику ограничење логика програмирања подржава ограничење руковања правила, програмер може да користи ова правила да прецизира могући rewritings на ограничење продавнице и могуће допуне ограничења према њему. У наставку су пример правила: 

A(X) <=> B(X) | C(X)
A(X) ==> B(X) | C(X)

Прво правило каже да, ако B(X) које подразумева продавница, ограничење A(X) може се преписати као C(X). Као пример, N*X>0 можемо записати као X>0, ако продавница имплицира да N>0. Симбол <=> подсећа на једнакост у логици, и каже да је прво ограничење еквивалентно овом другом. У пракси, то значи да ће прво ограничење бити замењено са другом.

Друго правило наводи да је друго ограничење последица првог, ако је ограничење у средини подразумева ограничење продавнице. Као резултат тога, ако је A(X) у ограничењу продавнице и B(X) подразумева ограничење продавнице, а затим се C(X) може додати продавници. За разлику од случаја еквиваленције, ово је додатак, а не замена: ново ограничење се додаје, али оно старо остаје.

Еквиваленција омогућава поједностављење наметања продавнице заменом неких ограничења са неким једноставнијим; посебно ако је треће ограничење у правилу еквиваленције истина, а друго ограничење је подразумијевано, прво ограничење је уклоњено из ограничења продавнице. Закључак омогућава додавање нових ограничења, што може довести до доказивања недоследности о ограничењу продавнице, а може генерално смањити количину потраге потребне да успостави своју задовољивости.

Логика програмирања одредби у вези са ограниченим правилима за руковање може да се користи за спецификацију метода за утврђивање задовољивости на ограничење продавнице. Различите клаузуле се користе за спровођење различитих избора метода; ограничено руковање правила се користе за кориговање ограничења продавнице током извршења. Као пример, може имплементирати одустајање са јединицом простирања на овај начин. Нека (L) представља пропозиционалну клаузулу, у којој су литерали на листи у истом редоследу као што се оцењују. Алгоритам може бити имплементиран користећи клаузуле за избор додељивања литерала за тачно или нетачно, и ограниченим руковањем правила да одреди ширење. Ова правила прописују да ([ l | L ]) се може уклонити ако је l = истина следи из продавнице, и може се написати као има (L) ако је l лажно следи из продавнице. Слично томе, ([l]) може бити замењен са l = истина. У овом примеру, избор вредности за променљиву је реализован коришћењем клаузуле логичко програмирање; међутим, може се кодирани у ограниченим правилима руковања користећи продужно назови дисјунктивно ограничење руковања правила или CHR∨.

Одоздо према горе евалуација[уреди | уреди извор]

Стандардна стратегија евалуације логичких програма је одозго надоле и дубине првог: од гола, један број одредаба су идентификоване као могуће за доказивање циља, а рекурзија над литералима њихових тела се врши. Алтернатива стратегија је да почну од чињеница и користе клаузуле за извођење нових чињеница; Ова стратегија се зове одоздо према горе. Сматра се боље од оне од врха надоле када је циљ да произведе све последице датог програма, уместо доказивања гола. Посебно, проналажење последице програма у стандардној одозго надоле и дубине првог начина не може се прекинути док одоздо нагоре стратегија за вредновање не престане.

Стратегија евалуације одоздо нагоре одржава скуп чињеница које смо показали до сада током евалуације. Овај сет је иницијално празан. Са сваким кораком, нове чињенице су изведене применом програма клаузула у постојећим чињеницама, и додају у скуп. На пример, процена одоздо према горе од следећег програма захтева два корака: 

A(q).
B(X):-A(X).

Скуп последица је иницијално празан. На првом кораку A(q) је једина клаузула чије се тело може доказати (јер је празна), и A(q) се стога додаје у тренутни скуп последица. На другом кораку, пошто је A(q) доказано, друга клаузула може користити и B(q) које је додато у последицама. Пошто ниједна друга последица се не може доказати из {A(q),B(q)}, извршење престаје.

Предност евалуације одоздо према горе преко одозго надоле је да циклус извођења не производе бесконачну петљу. То је зато што додавање последица тренутан скуп последица који већ садржи нема ефекта. Као пример, додавање треће клаузуле да горе програм генерише циклус извођења у евалуацији одозго надоле: 

A(q).
B(X):-A(X).
A(X):-B(X).

На пример, док оцењивање свих одговора до циља A(X), одозго надоле стратегија ће производити сљедећа извођења: 

A(q)
A(q):-B(q), B(q):-A(q), A(q)
A(q):-B(q), B(q):-A(q), A(q):-B(q), B(q):-A(q), A(q)

Другим речима, једина последица A(q) је произведена прва, али онда алгоритам циклуса током извођења не производи било који други одговор. 

Стратегија одоздо према горе нема исти недостатак, као и последице које су већ изведене и немају ефекта. На горе програм, стратегија одоздо према горе почиње додајући A(q) на скупу последица; у другом кораку, B(X):-A(X) се користи за извођење B(q); у трећем кораку, једине чињенице које се могу извести из текућих последица су A(q) и B(q), који су међутим, већ у скупу последица. Као резултат тога, алгоритам се зауставља.

У горњем примеру, користе се само чињенице из подземних литерала. Генерално, свака клаузула која садржи само ограничења у телу сматра се чињеницом. На пример, клаузула A(X):-X>0,X<10 сматра чињеницу као добром. За ове продужене дефиниције чињеница, неке чињенице могу бити еквивалент док не синтаксически једнаке. На пример, A(q) је еквивалентно A(X):-X=q и оба су еквивалентна A(X):-X=Y, Y=q. Да би се решио овај проблем, чињенице су преведене на нормалну форму у којој глава садржи тупле свих-различитих варијабли; две чињенице су онда еквивалентне ако су њихова тела еквивалентна на варијабли главе, то јест, њихови сетови решења су исти када су ограничени на ове варијабле.

Као што је описано, одозго према горе приступ има предност не узимајући у обзир последице које су већ изведене. Међутим, још увек можемо извући последице које су подразумевале оне које су већ изведене док не буде једнак било који од њих. Као пример, процена одоздо према горе од следећих програма је бесконачан: 

A(0).
A(X):-X>0.
A(X):-X=Y+1, A(Y).

Одоздо према горе евалуациони алгоритам прво произлази да је A(X) истинит за =0 и X>0. У другом кораку, прва чињеница са трећом клаузулом омогућава извођење А(1). У трећем кораку А(2) је изведена, итд Међутим, ове чињенице су се већ подразумевале чињеницом да је A(X) истинит за било ненегативан X. Овај недостатак може да се превазиђе тако што ће се entailment чињенице додати у тренутан скуп последица. Ако је нова последица већ подразумевала скуп, није додат на њега. Од чињенице се чувају као клаузуле, евентуално са "локалним променљивима", entailment је ограничен због варијабли њихових глава.

Упоредно принудно логичко програмирање[уреди | уреди извор]

Истовремене верзије принудног логичког програмирања немају за циљ програмирање истовремених процеса, него решавања проблема ограничења задовољства. Циљеви у принудном логичком програмирању се истовремено процењују; истовремена процена је стога програмирана као процена циља од стране преводиоца.

Синтактички, истовремено принудно логичко програмирање је слично не-истовременим програмима, једини изузетак је да одредбе укључују чувара, који су ограничења која могу да блокирају примену клаузуле под одређеним условима. Семантички истовремено ограничење логике програмирања разликује се од својих не-истовремених верзија јер евалуација циља нема за циљ да оствари истовремено процес него налажење решења за проблем. Пре свега, та разлика утиче на то како се преводилац понаша када се више од једне клаузуле примењује: не истовремено ограничење логике програмирања рекурсивно бира све клаузуле; истовремено ограничење логике програмирања бира само једну. Ово је најочигледнији ефекат намењен на усмерење преводиоца, који никада није ревидирао избор од раније узет. Остали ефекти су семантичка могућност да се циљ не може доказати, док евалуација не падне, и на посебан начин за изједначавање циља и клаузула главу.

Апликације[уреди | уреди извор]

Ограничење логике програмирања је примењено на многим пољима, попут грађевинарства, машинства, дигиталне верификације кола, аутоматизовање распореда, контрола ваздушног саобраћаја, финансија, и других.

Историја[уреди | уреди извор]

Ограничење логике програмирања увели су Јаффар и Лассез у 1987. Они су генерализовали запажање да је термин једначине и disequations  Prolog II. специфичан облик ограничења, и генерализовање ове идеје произвољном ограниченом језику. Прве имплементације овог концепта су  Prolog III, CLP(R), и CHIP.

Види још[уреди | уреди извор]

Литература[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Принудно_логичко_програмирање&oldid=26982557”