Parallel sheklewli logikalıq programmalastırıw

Parallel sheklewli logikalıq programmalastırıw — bul sheklewli logikalıq programmalastırıwdıń bir versiyası bolıp, ol tiykarınan sheklewlerdi qanaatlandırıw máselelerin sheshiwden góre (yamasa oǵan qosımsha retinde) parallel processlerdi programmalastırıwǵa arnalǵan. Sheklewli logikalıq programmalastırıwdaǵı maqsetler parallel bahalanadı; sonlıqtan parallel process interpretator tárepinen maqsetti bahalaw retinde programmalastırıladı.

Sintaksislik jaqtan, parallel sheklewli logikalıq programmalar parallel emes programmalarǵa uqsaydı, tek bir ayırmashılıǵı — qaǵıydalardıń ishinde baqlawshılar (guards) bar, olar ayırım shártlerde qaǵıydanıń qollanılıwın bloklay alatuǵın sheklewler bolıp tabıladı. Semantikalıq jaqtan, parallel sheklewli logikalıq programmalastırıw óziniń parallel emes versiyalarınan ayırmashılıq etedi, sebebi maqsetti bahalaw máseleniń sheshimin tabıwdan góre parallel processti ámelge asırıwǵa arnalǵan. Eń áhmiyetlisi, bul ayırmashılıq interpretatordıń bir neshe qaǵıyda qollanıwǵa bolatuǵın jaǵdayda ózin qalay tutıwına tásir etedi: parallel emes sheklewli logikalıq programmalastırıw rekursiv túrde barlıq qaǵıydalardı sınap kóredi; parallel sheklewli logikalıq programmalastırıw tek birin tańlaydı. Bul interpretatordıń aldın qabıl etken tańlawın hesh qashan qayta kórip shıqpaytuǵın itibarǵa alınǵan baǵdarlanǵanlıǵınıń eń anıq tásiri bolıp tabıladı. Bunıń basqa tásirleri — pútkil bahalaw sátsiz bolmasa da dálillenbeytuǵın maqsettiń bolıwınıń semantikalıq múmkinshiligi hám maqset penen qaǵıyda basın teńlestiriwdiń arnawlı usılı.

Sheklewlerdi qayta islew qaǵıydaları parallel sheklewli logikalıq programmalastırıwdıń bir forması retinde qaralıwı múmkin,Frühwirth, Thom. "Theory and practice of constraint handling rules." The Journal of Logic Programming 37.1-3 (1998): 95-138. biraq olar parallel processlerdi programmalastırıwdan góre sheklewlerdi ápiwayılastırıwshı yamasa sheshiwshini programmalastırıw ushın qollanıladı.

 Túsindirme 
Sheklewli logikalıq programmalastırıwda, aǵımdaǵı maqsettegi maqsetler izbe-iz bahalanadı, ádette jańa maqsetler birinshi bahalanatuǵın LIFO tártibinde ámelge asırıladı. Logikalıq programmalastırıwdıń parallel versiyası maqsetlerdi parallel bahalawǵa múmkinshilik beredi: hárbir maqset bir process tárepinen bahalanadı hám processler parallel isleydi. Bul processler sheklewler qoyması arqalı óz-ara tásir etedi: bir process sheklewler qoymasına sheklew qosıwı múmkin, al ekinshisi bir sheklewdiń qoymadan kelip shıǵıwın tekseredi.

Qoymaǵa sheklew qosıw ádettegi sheklewli logikalıq programmalastırıwdaǵı sıyaqlı ámelge asırıladı. Sheklewdiń kelip shıǵıwın tekseriw qaǵıydalarǵa qoyılǵan baqlawshılar arqalı boladı. Baqlawshılar sintaksislik keńeytiwdi talap etedi: parallel sheklewli logikalıq programmalastırıwdıń qaǵıydası H :- G | B túrinde jazıladı, bul jerde G — qaǵıydanıń baqlawshısı dep atalatuǵın sheklew. Qısqasha aytqanda, bul qaǵıydanıń jańa variantı maqsettegi literaldı almastırıw ushın tek ǵana eger oǵan literal menen qaǵıyda basınıń teńlemesi qosılǵannan keyin baqlawshı sheklewler qoymasınan kelip shıqsa ǵana qollanılıwı múmkin. Bul qaǵıydanıń anıq anıqlaması quramalıraq hám tómende keltirilgen.

Parallel emes hám parallel sheklewli logikalıq programmalastırıw arasındaǵı tiykarǵı ayırmashılıq — birinshisi izlewge, al ekinshisi parallel processlerdi ámelge asırıwǵa baǵdarlanǵan. Bul ayırmashılıq tańlawlardı biykarlaw múmkinshiligine, processlerdiń juwmaqlanbawına ruqsat etiliw-etilmewine hám maqsetler menen qaǵıyda baslarınıń qalay teńlestiriliwine tásir etedi.

Ádettegi hám parallel sheklewli logikalıq programmalastırıw arasındaǵı birinshi semantikalıq ayırmashılıq maqsetti dálillew ushın birden kóp qaǵıyda qollanılıwı múmkin bolǵan shártke baylanıslı. Parallel emes logikalıq programmalastırıw maqsetti qayta jazǵanda barlıq múmkin bolǵan qaǵıydalardı sınap kóredi: eger maqset qaǵıydanıń jańa variantınıń denesi menen almastırılǵanda dálillenbese, basqa qaǵıyda sınap kóriledi (eger bar bolsa). Sebebi maqset — maqsetti dálillew: maqsetti dálillewdiń barlıq múmkin jolları sınap kóriledi. Ekinshi tárepten, parallel sheklewli logikalıq programmalastırıw parallel processlerdi programmalastırıwǵa baǵdarlanǵan. Ulıwma parallel programmalastırıwda, eger process bir tańlaw islese, bul tańlawdı biykar etiwge bolmaydı. Sheklewli logikalıq programmalastırıwdıń parallel versiyası processlerge tańlawǵa ruqsat beriw arqalı olardı ámelge asıradı, biraq olar qabıl etilgennen keyin sol tańlawǵa baylanıslı boladı. Texnikalıq jaqtan, eger maqsettegi literaldı qayta jazıw ushın birden kóp qaǵıyda qollanılıwı múmkin bolsa, parallel emes versiya barlıq qaǵıydalardı gezegi menen sınaydı, al parallel versiya tek bir qálegen qaǵıydanı tańlaydı: parallel emes versiyadan ózgesheligi, basqa qaǵıydalar hesh qashan sınap kórilmeydi. Kóp tańlawlardı qayta islewdiń bul eki hár túrli usılı kóbinese ««bilmeymen» deterministlik emesligi» hám ««qızıqpayman» deterministlik emesligi» dep ataladı.

Maqsettegi literaldı qayta jazǵanda, tek ǵana baqlawshısı sheklewler qoyması menen literaldıń qaǵıyda basına teńlemesiniń birikpesinen kelip shıǵatuǵın qaǵıydalar ǵana esapqa alınadı. Baqlawshılar qaysı qaǵıydalardıń ulıwma esapqa alınbawı kerekligin kórsetiw usılın támiyinleydi. Bul ásirese parallel sheklewli logikalıq programmalastırıwdıń bir qaǵıydaǵa baylanıslılıǵın esapqa alǵanda áhmiyetli: bir qaǵıyda tańlanǵannan keyin, bul tańlaw hesh qashan qayta kórip shıǵılmaydı. Baqlawshılarsız, interpretator literaldı qayta jazıw ushın «qáte» qaǵıydanı tańlawı múmkin edi, al basqa «jaqsı» qaǵıydalar bar bolsa da. Parallel emes programmalastırıwda bul onsha áhmiyetli emes, sebebi interpretator bárqulla barlıq múmkinshiliklerdi sınap kóredi. Parallel programmalastırıwda interpretator basqaların sınap kórmesten tek bir múmkinshilikke baylanıslı boladı.

Parallel emes hám parallel versiya arasındaǵı ayırmashılıqtıń ekinshi tásiri — parallel sheklewli logikalıq programmalastırıw processlerdiń juwmaqlanbastan islewine ruqsat beriw ushın arnawlı proektlestirilgen. Juwmaqlanbaytuǵın processler ulıwma parallel qayta islewde kóp ushırasadı; sheklewli logikalıq programmalastırıwdıń parallel versiyası olardı sátsizlik shártin paydalanbaw arqalı ámelge asıradı: eger maqsetti qayta jazıw ushın hesh qanday qaǵıyda qoljetimli bolmasa, bul maqsetti bahalap atırǵan process parallel emes sheklewli logikalıq programmalastırıwdaǵı sıyaqlı pútkil bahalawdı sátsiz etiwdiń ornına toqtaydı. Nátiyjede, maqsetti bahalap atırǵan process dawam etiw ushın hesh qanday qaǵıyda bolmaǵanlıqtan toqtap qalıwı múmkin, biraq sol waqıtta basqa processler islewdi dawam etedi.

Hár túrli maqsetlerdi sheshiwshi processler arasındaǵı sinxronizaciya baqlawshılardı paydalanıw arqalı ámelge asırıladı. Eger maqsetti qayta jazıw múmkin bolmasa, sebebi qollanılıwı múmkin bolǵan barlıq qaǵıydalardıń baqlawshısı sheklewler qoymasınan kelip shıqpaydı, bul maqsetti sheship atırǵan process basqa processler qollanılatuǵın qaǵıydalardıń keminde biriniń baqlawshısınıń kelip shıǵıwı ushın kerekli sheklewlerdi qosqanǵa shekem bloklanadı. Bul sinxronizaciya tıǵılıslarǵa alıp keliwi múmkin: eger barlıq maqsetler bloklansa, jańa sheklewler qosılmaydı hám sonlıqtan hesh bir maqset hesh qashan bloktan shıǵarılmaydı.

Parallel hám parallel emes logikalıq programmalastırıw arasındaǵı ayırmashılıqtıń úshinshi tásiri — maqsettiń qaǵıydanıń jańa variantınıń bası menen qalay teńlestiriliwi. Operaciyalıq jaqtan, bul bastaǵı ózgeriwshilerdiń bas maqsetke teń bolatuǵınday etip termlerge teńlestiriliwi múmkinligin tekseriw arqalı ámelge asırıladı. Bul qaǵıyda sheklewli logikalıq programmalastırıwdıń tiyisli qaǵıydasınan ózgeshelenedi, sebebi ol tek ǵana ózgeriwshi=term formasındaǵı sheklewlerdi qosıwǵa ruqsat beredi, bul jerde ózgeriwshi — bastıń ózgeriwshilerinen biri. Bul sheklewdi baǵdarlılıqtıń bir forması retinde qarawǵa boladı, bunda maqset penen qaǵıyda bası hár qıylı qaraladı.

Anıǵıraq aytqanda, qaǵıydanıń H:-G|B jańa variantınıń A maqsetin qayta jazıw ushın qollanılıwı múmkinligin anıqlaytuǵın qaǵıyda tómendegishe. Birinshiden, A hám H birdey predikatqa iye me, sonı tekseriledi. Ekinshiden, házirgi sheklewler qoymasın esapqa alǵanda A-nı H-qa teńlestiriwdiń bir usılı bar ma, sonı tekseriledi; ádettegi logikalıq programmalastırıwdan ózgesheligi, bul tek ǵana bastıń ózgeriwshisin termge teńlestiriwge ruqsat beretuǵın bir tárepleme unifikaciya arqalı ámelge asırıladı. Úshinshiden, baqlawshı sheklewler qoymasınan hám ekinshi basqıshta payda bolǵan teńlemelerden kelip shıǵıwı tekseriledi; baqlawshı qaǵıyda basında kórsetilmegen ózgeriwshilerdi óz ishine alıwı múmkin: bul ózgeriwshiler ekzistenciallıq mániste interpretaciyalanadı. Qaǵıydanıń jańa variantınıń maqsetti almastırıw ushın qollanılıwın anıqlawdıń bul usılın qısqasha tómendegishe ańlatıwǵa boladı: házirgi sheklewler qoymasınan, qaǵıyda basınıń hám baqlawshınıń ózgeriwshileriniń sonday bir bahalanıwı bar ekenligi kelip shıǵadı, onda qaǵıyda bası maqsetke teń boladı hám baqlawshı (qoymadan) kelip shıǵadı. Ámeliyatta, kelip shıǵıw tolıq emes usıl menen tekseriliwi múmkin.

Parallel logikalıq programmalastırıwdıń sintaksisi hám semantikasına keńeytpe — bul atomlıq xabarlaw. Interpretator bir qaǵıydanı qollanǵanda, onıń baqlawshısı sheklewler qoymasına qosıladı. Biraq, denedegi sheklewler de qosıladı. Usı qaǵıydaǵa baylanıslı bolǵanlıqtan, eger denedegi sheklewler qoymaǵa sáykes kelmese, interpretator artqa qaytpaydı. Bul jaǵdaydan atomar aytıwdı paydalanıw arqalı qashıwǵa boladı, bul qaǵıydanıń tek ǵana sáykeslikke tekseriletuǵın «ekinshi baqlawshınıń» bir túrin óz ishine alatuǵın variantı. Bunday qaǵıyda H :- G:D|B dep jazıladı. Bul qaǵıyda literaldı qayta jazıw ushın tek ǵana eger G sheklewler qoymasınan kelip shıqsa hám D oǵan sáykes kelse ǵana qollanıladı. Bul jaǵdayda, G da, D da sheklewler qoymasına qosıladı.

 Tariyxı 
Parallel sheklewli logikalıq programmalastırıwdı izertlew 1980-jıllardıń aqırında, Maykl Dj. Maxer tárepinen parallel logikalıq programmalastırıwdıń ayırım principleri sheklewli logikalıq programmalastırıwǵa integraciyalanǵanda baslandı. Parallel sheklewli logikalıq programmalastırıwdıń teoriyalıq qásiyetleri keyinirek hár túrli avtorlar, sonıń ishinde Martin Rinard hám Vidjay A. Sarasvat tárepinen izertlendi.

 Derekler 

Kategoriya:Programmalastırıw paradigmaları
__BÖLİDİMÖNDEMEW__