Uporedno prinudno logičko programiranje

Uporedno prinudno logičko programiranje je verzija prinudnog logičkog programiranja koja za cilj ima prvenstveno programiranje istovremenih procesa, a ne (ili pored) rešavanje problema ograničenja zadovoljstva. Ciljevi u ograničenju logičkog programiranja se istovremeno procenjuje; istovremena procena je stoga programirana kao procena cilja od strane prevodioca.

Sintaktički, uporedno prinudno logičko programiranje je slično ne-istovremenim programima, jedini izuzetak je da odredbe uključuju čuvara, koji su ograničenja koja mogu da blokiraju primenu klauzule pod određenim uslovima. Semantički uporedno ograničenje logike programiranja razlikuje se od svojih ne-istovremenih verzija jer evaluacija cilja nema za cilj da ostvari istovremeno proces nego nalaženje rešenja za problem. Pre svega, ta razlika utiče na to kako se prevodilac ponaša kada se više od jedne klauzule primenjuje: ne istovremeno ograničenje logike programiranja rekursivno bira sve klauzule; uporedno ograničenje logike programiranja bira samo jednu. Ovo je najočigledniji efekat namenjen na usmerenje prevodioca, koji nikada nije revidirao izbor od ranije uzet. Ostali efekti su semantička mogućnost da se cilj ne može dokazati, dok evaluacija ne padne, i na poseban način za izjednačavanje cilja i klauzula glavu.

Ograničenje rukovanja pravila može se posmatrati kao oblik uporednog ograničenja logičkog programiranja, ali se koriste za programiranje nametanja simplifier ili rešenja nego istovremenih procesa.

Opis

U ograničenje logičkog programiranje, ciljevi u tekućem cilju se redom procenjuju, obično odvijaju u LIFO poredku u kojem noviji ciljevi se prvo procenjuje. Istovremena verzija logičkog programiranja omogućava vrednovanje ciljeva u paralelama: svaki cilj je ocenjen u procesu, a procesi pokrenuti istovremeno. Ovi procesi interakuju preko ograničenja prodavnica: procesima možete dodati ograničenja za ograničenja prodavnica, dok drugi proverava da li je ograničenje koje podrazumeva radnje.

Dodavanje prepreka za prodavnicu vrši se kao u redovnom prinudnom logičkom programiranju. Provera logičke implikacije od ograničenja vrši se preko stražara u klauzulama. Stražari zahtevaju sintaksičko produženje: klauzule u istovremenom prinudnom logičkom programiranju su napisane kao H :- G | B gde je G prepreka i zove stražu na klauzule. Grubo govoreći, sveža varijanta ove tačke može da se koristi da se zameni bukvalno u cilju samo ako stražar podrazumevao ograničenje prodavnice posle jednačine koja je bukvalno i klauzula glave koja se dodaje na njega. Precizna definicija ovog pravila je komplikovanija, u nastavku.

Osnovna razlika između ne-konkurentne i uporedne prinudne logike programiranja je da prvi ima za cilj pretresa, dok je drugi cilj da sprovodi istovremene procese. Ova razlika utiče na izbor da li može da se opozove, da li su procesi dozvoljeni da se ne prekinu, i kako su izjednačeni ciljevi i glave klauzulu.

Prva semantička razlika između redovne i istovremene prinudne logike programiranja je o stanju kada se više od jedne klauzule može koristiti za dokazivanje gola. Ne-konkurentna logika programiranja pokušava sve moguće klauzule kad prepisivanje cilja: ako se cilj ne može dokazati, a njegova zamena sa telom sveže varijantne klauzule, druga klauzula se može dokazati. To je zato što je cilj da se dokaže cilj: sve moguće načine da se dokaže cilj je pokušao. S druge strane, uporedno prinudno logičko programiranjeima za cilj ima programiranje paralelnih procesa. U opštem istovremenom programiranju, ako proces pravi izbor, ovaj izbor ne može se opozvati. Istovremena verzija prinudne logike programiranja sprovodi procese omogućavajući im da se izbore, ali obavezujući se da će ih nakon što su preduzete. Tehnički, ako više se od jedne klauzule može koristiti za prepisanje bukvalno u cilj, ne-istovremena verzija pokušava zauzvrat sve klauzule, dok istovremena verzija bira jednu proizvoljnu klauzulu: suprotno ne-istovremenoj verziji, Druge klauzule nikada neće biti suđene. Ova dva različita načina za rukovanje su višestruki izbor se često nazivaju "ne znam nondeterminism" i "ne zanima nondeterminism".

Kada ponovno pisanje literala u cilju, jedini klauzule su one čiji stražar podrazumeva unije o ograničenju prodavnice i bukvalne jednačine sa klauzulom u glavi. Stražari obezbeđuju način za pričanje koje klauzule ne mogu smatrati uopšte. Ovo je posebno važno imajući u vidu opredeljenje za jednu klauzulu istovremeno ograničenje logike programiranja: jedna klauzula je izabrana, ovaj izbor se neće nikad razmotriti. Bez čuvara, prevodilac može da izabere "pogrešnu" klauzulu da prepravim bukvalno, dok su ostali "dobre" klauzule postoje. U ne-konkurentnom programiranju, to je manje važno, kao i prevodilac uvek pokušava sve mogućnosti. U istovremenom programiranju, prevodilac obavezuje jednu mogućnost bez pokušaja ostalih.

Drugi efekat razlika između ne-konkurentne i istovremene verzije je da je istovremeno ograničenje logika programiranja specijalno dizajnirano da omogući procese da rade bez prestanka. Ne-prestanak procesi su uobičajeni u celini u istovremenoj preradi; istovremena verzija ograničenja logičkog programiranja ih sprovodi od strane ne korisnog stanja neuspeha: ako nema klauzula važi prepisivanje cilja, proces evaluacije ovog cilja prestaje umesto da cela evaluacija kao u ne-istovremenom ograničenju logičkog programiranja. Kao rezultat toga, proces evaluacije za cilj ima da se zaustavi jer nema klauzula na raspolaganju da nastavi, ali u isto vreme ostali procesi stalno rade.

Sinhronizacija među procesima koji rešavanju različite ciljeve se postiže putem korišćenja stražara. Ako cilj ne može biti prepisan jer sve klauzule koje bi se mogle koristiti imaju stražara koji ne podrazumeva ograničenje prodavnice, proces rešavanja tog cilja je blokiran dok će drugi procesi dodati ograničenja koja su neophodna da podrazumevaju stražu od najmanje jedne od važećih odredaba. Ova sinhronizacija je predmet mrtve petlje: ako su svi ciljevi blokirani, nova ograničenja će biti dodata pa samim tim ni cilj nikada neće biti odblokiran.

Treći efekat razlike između konkurentnog i ne istovremenog logičkog programiranja na putu cilja je izjednačavati sa glavom sveže varijantne klauzule. Operativno, to se radi tako što se proveri da li se promenljive u glavi izjednačavaju sa uslovima i na takav način glava je jednaka cilju. Ovo pravilo se razlikuje od odgovarajućeg pravila za ograničenje logičkog programiranja samo omogućavajući dodavanje ograničenja u obliku promenljivih = roku, gde je promenljiva jedna od glava. Ovo ograničenje može se posmatrati kao oblik usmerenja, u tome se cilj i klauzula glava tretiraju se različito.

Tačnije, pravilo govori da li sveža varijanta H:-G|B klauzule može da se koristi da se prepiše cilj A kao što sledi. Prvo, on se proverava da li A i H imaju isti predikat. Drugo, on se proverava da li postoji način za izjednačavanje A sa H s obzirom na trenutno ograničenje prodavnice; za razliku od redovnog logičkog programiranja, to je učinjeno pod jednostranim ujedinjenjenjem, što omogućava samo promenljiva glave da bude jednaka mandatu. Treće, stražar proverava logičku implikaciju ograničenja prodavnica i jednačinu generiše u drugom koraku; stražar može sadržati varijable koje nisu navedene u tački glave: Ove varijable se egzistencijalno tumače. Ovaj metod za odlučivanje primenljivosti sveže varijante klauzulom za zamenu cilja može biti kompaktno izraženo na sledeći način: trenutno ograničenje prodavnice podrazumeva da postoji evaluaciju varijabli glave i straže takva da je glava jednaka cilju i stražar je podrazumeva. U praksi, logička implikacija se može proveriti nekompletnom metodom.

Produženje do sintakse i semantike za istovremeno logičko programiranja je atomski reći. Kada prevodilac koristi klauzulu, njen stražar se dodaje ograničenju prodavnice. Međutim, takođe dodati su ograničenju tela. Zbog posvećenosti ove klauzule, prevodilac ne odustaje ako je ograničenje tela u suprotnosti sa prodavnicom. Ovo stanje se može izbeći korišćenjem atomske reči, što je varijanta u kojoj klauzula sadrži neku vrstu "drugog stražara" koji se proverava samo za doslednost. Takva klauzula je napisana H :- G:D|B. Ova klauzula se koristi za prepisivanje bukvalno samo ako je G podrazumevalo ograničenje prodavnice i D je u skladu sa tim. U ovom slučaju, i G i D se dodaju u ograničenje prodavnice.

Istorija

Studija uporednog prinudnog logičkog programiranja je počela krajem 1980-ih, kada su neki od principa uporedno logičkog programiranja integrisani u ograničenje logičkog programiranja od Michael J. Maher. Teoretski svojstvo uporednog prinudnog logičkog programiranja kasnije se studiralo od različitih autora, kao što su Vijai A. Sarasvat.

Vidi još

• Curry, logički funkcionalni programski jezik, koji omogućava programiranje istovremenih sistema.
• ToonTalk
• Janus
• Alice

Literatura

• 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.