Упоредно принудно логичко програмирање
Упоредно принудно логичко програмирање је верзија принудног логичког програмирања која за циљ има првенствено програмирање истовремених процеса, а не (или поред) решавање проблема ограничења задовољства. Циљеви у ограничењу логичког програмирања се истовремено процењује; истовремена процена је стога програмирана као процена циља од стране преводиоца.
Синтактички, упоредно принудно логичко програмирање је слично не-истовременим програмима, једини изузетак је да одредбе укључују чувара, који су ограничења која могу да блокирају примену клаузуле под одређеним условима. Семантички упоредно ограничење логике програмирања разликује се од својих не-истовремених верзија јер евалуација циља нема за циљ да оствари истовремено процес него налажење решења за проблем. Пре свега, та разлика утиче на то како се преводилац понаша када се више од једне клаузуле примењује: не истовремено ограничење логике програмирања рекурсивно бира све клаузуле; упоредно ограничење логике програмирања бира само једну. Ово је најочигледнији ефекат намењен на усмерење преводиоца, који никада није ревидирао избор од раније узет. Остали ефекти су семантичка могућност да се циљ не може доказати, док евалуација не падне, и на посебан начин за изједначавање циља и клаузула главу.
Ограничење руковања правила може се посматрати као облик упоредног ограничења логичког програмирања, али се користе за програмирање наметања simplifier или решења него истовремених процеса.
Опис уреди
У ограничење логичког програмирање, циљеви у текућем циљу се редом процењују, обично одвијају у ЛИФО поредку у којем новији циљеви се прво процењује. Истовремена верзија логичког програмирања омогућава вредновање циљева у паралелама: сваки циљ је оцењен у процесу, а процеси покренути истовремено. Ови процеси интеракују преко ограничења продавница: процесима можете додати ограничења за ограничења продавница, док други проверава да ли је ограничење које подразумева радње.
Додавање препрека за продавницу врши се као у редовном принудном логичком програмирању. Провера логичке импликације од ограничења врши се преко стражара у клаузулама. Стражари захтевају синтаксичко продужење: клаузуле у истовременом принудном логичком програмирању су написане као H :- G | B где је G препрека и зове стражу на клаузуле. Грубо говорећи, свежа варијанта ове тачке може да се користи да се замени буквално у циљу само ако стражар подразумевао ограничење продавнице после једначине која је буквално и клаузула главе која се додаје на њега. Прецизна дефиниција овог правила је компликованија, у наставку.
Основна разлика између не-конкурентне и упоредне принудне логике програмирања је да први има за циљ претреса, док је други циљ да спроводи истовремене процесе. Ова разлика утиче на избор да ли може да се опозове, да ли су процеси дозвољени да се не прекину, и како су изједначени циљеви и главе клаузулу.
Прва семантичка разлика између редовне и истовремене принудне логике програмирања је о стању када се више од једне клаузуле може користити за доказивање гола. Не-конкурентна логика програмирања покушава све могуће клаузуле кад преписивање циља: ако се циљ не може доказати, а његова замена са телом свеже варијантне клаузуле, друга клаузула се може доказати. То је зато што је циљ да се докаже циљ: све могуће начине да се докаже циљ је покушао. С друге стране, упоредно принудно логичко програмирањеима за циљ има програмирање паралелних процеса. У општем истовременом програмирању, ако процес прави избор, овај избор не може се опозвати. Истовремена верзија принудне логике програмирања спроводи процесе омогућавајући им да се изборе, али обавезујући се да ће их након што су предузете. Технички, ако више се од једне клаузуле може користити за преписање буквално у циљ, не-истовремена верзија покушава заузврат све клаузуле, док истовремена верзија бира једну произвољну клаузулу: супротно не-истовременој верзији, Друге клаузуле никада неће бити суђене. Ова два различита начина за руковање су вишеструки избор се често називају "не знам nondeterminism" и "не занима nondeterminism".
Када поновно писање литерала у циљу, једини клаузуле су оне чији стражар подразумева уније о ограничењу продавнице и буквалне једначине са клаузулом у глави. Стражари обезбеђују начин за причање које клаузуле не могу сматрати уопште. Ово је посебно важно имајући у виду опредељење за једну клаузулу истовремено ограничење логике програмирања: једна клаузула је изабрана, овај избор се неће никад размотрити. Без чувара, преводилац може да изабере "погрешну" клаузулу да преправим буквално, док су остали "добре" клаузуле постоје. У не-конкурентном програмирању, то је мање важно, као и преводилац увек покушава све могућности. У истовременом програмирању, преводилац обавезује једну могућност без покушаја осталих.
Други ефекат разлика између не-конкурентне и истовремене верзије је да је истовремено ограничење логика програмирања специјално дизајнирано да омогући процесе да раде без престанка. Не-престанак процеси су уобичајени у целини у истовременој преради; истовремена верзија ограничења логичког програмирања их спроводи од стране не корисног стања неуспеха: ако нема клаузула важи преписивање циља, процес евалуације овог циља престаје уместо да цела евалуација као у не-истовременом ограничењу логичког програмирања. Као резултат тога, процес евалуације за циљ има да се заустави јер нема клаузула на располагању да настави, али у исто време остали процеси стално раде.
Синхронизација међу процесима који решавању различите циљеве се постиже путем коришћења стражара. Ако циљ не може бити преписан јер све клаузуле које би се могле користити имају стражара који не подразумева ограничење продавнице, процес решавања тог циља је блокиран док ће други процеси додати ограничења која су неопходна да подразумевају стражу од најмање једне од важећих одредаба. Ова синхронизација је предмет мртве петље: ако су сви циљеви блокирани, нова ограничења ће бити додата па самим тим ни циљ никада неће бити одблокиран.
Трећи ефекат разлике између конкурентног и не истовременог логичког програмирања на путу циља је изједначавати са главом свеже варијантне клаузуле. Оперативно, то се ради тако што се провери да ли се променљиве у глави изједначавају са условима и на такав начин глава је једнака циљу. Ово правило се разликује од одговарајућег правила за ограничење логичког програмирања само омогућавајући додавање ограничења у облику променљивих = року, где је променљива једна од глава. Ово ограничење може се посматрати као облик усмерења, у томе се циљ и клаузула глава третирају се различито.
Тачније, правило говори да ли свежа варијанта H:-G|B клаузуле може да се користи да се препише циљ А као што следи. Прво, он се проверава да ли А и H имају исти предикат. Друго, он се проверава да ли постоји начин за изједначавање А са H с обзиром на тренутно ограничење продавнице; за разлику од редовног логичког програмирања, то је учињено под једностраним уједињењењем, што омогућава само променљива главе да буде једнака мандату. Треће, стражар проверава логичку импликацију ограничења продавница и једначину генерише у другом кораку; стражар може садржати варијабле које нису наведене у тачки главе: Ове варијабле се егзистенцијално тумаче. Овај метод за одлучивање применљивости свеже варијанте клаузулом за замену циља може бити компактно изражено на следећи начин: тренутно ограничење продавнице подразумева да постоји евалуацију варијабли главе и страже таква да је глава једнака циљу и стражар је подразумева. У пракси, логичка импликација се може проверити некомплетном методом.
Продужење до синтаксе и семантике за истовремено логичко програмирања је атомски рећи. Када преводилац користи клаузулу, њен стражар се додаје ограничењу продавнице. Међутим, такође додати су ограничењу тела. Због посвећености ове клаузуле, преводилац не одустаје ако је ограничење тела у супротности са продавницом. Ово стање се може избећи коришћењем атомске речи, што је варијанта у којој клаузула садржи неку врсту "другог стражара" који се проверава само за доследност. Таква клаузула је написана H :- G:D|B. Ова клаузула се користи за преписивање буквално само ако је G подразумевало ограничење продавнице и D је у складу са тим. У овом случају, и G и D се додају у ограничење продавнице.
Историја уреди
Студија упоредног принудног логичког програмирања је почела крајем 1980-их, када су неки од принципа упоредно логичког програмирања интегрисани у ограничење логичког програмирања од Мицхаел Ј. Махер. Теоретски својство упоредног принудног логичког програмирања касније се студирало од различитих аутора, као што су Вијаи А. Сарасват.
Види још уреди
Литература уреди
- Marriott, Kim; Stuckey, Peter J. (1998). Programming with constraints: An introduction. MIT Press. ISBN 978-0-262-13341-8.
- Frühwirth, Thom; Abdennadher, Slim (2003). Essentials of constraint programming. Springer. ISBN 978-3-540-67623-2.
- Jaffar, Joxan; Maher, Michael J. (1994). „Constraint logic programming: a survey”. Journal of logic programming. 19/20: 503—581. doi:10.1016/0743-1066(94)90033-7.