Kontentke ótiw

Logikalıq programmalastırıw

Wikipedia — erkin enciklopediya

Logikalıq programmalastırıw — bul formal logikaǵa tiykarlanǵan programmalastırıw, maǵlıwmatlar bazası hám bilimlerdi kórsetiw paradigması. Logikalıq programma — bul qanday da bir másele tarawı haqqındaǵı bilimlerdi bildiretuǵın logikalıq formadaǵı sózler dizimi toplamı. Esaplaw sol tarawdaǵı máselelerdi sheshiw ushın sol bilimlerge logikalıq pikirlewdi qollanıw arqalı orınlanadı. Tiykarǵı logikalıq programmalastırıw tili shańaraqlarına Prolog, Juwaplar Toplamın Programmalastırıw (ASP) hám Datalog kiredi.

Tariyxı

Kompyuter programmaların kórsetiw hám orınlaw ushın matematikalıq logikanı paydalanıw sonday-aq 1930-jıllarda Alonzo Cherch tárepinen islep shıǵılǵan lyambda esaplawınıń da bir ózgesheligi bolıp tabıladı. Degen menen, kompyuter programmaların kórsetiw ushın logikanıń klauzal formasın qollanıw boyınsha birinshi usınıs Kordell Grin tárepinen islengen. Bul LISPtiń bir bóliminiń aksiomatizaciyasın kirgiziw-shıǵarıw qatnasınıń kórinisi menen birge paydalanıp, LISPtegi programmanıń orınlanıwın simulyaciyalaw arqalı qatnastı esaplaǵan. Foster hám Elkoktıń Absys programması bolsa, kerisinshe, operaciyalardıń orınlanıw tártibine hesh qanday sheklew qoymaytuǵın tastıyıqlawshı programmalastırıw tilinde teńlemeler menen lyambda esaplawınıń birikpesin paydalanǵan.

Logikalıq programmalastırıw, óziniń házirgi faktler hám qaǵıydalar sintaksisi menen, 1960-jıllardıń aqırında hám 1970-jıllardıń basında jasalma intellekttegi bilimlerdiń deklarativ hám proceduralıq kórsetiliwleri haqqındaǵı talqılawlarǵa barıp taqaladı. Deklarativ kórsetiliwlerdiń tárepdarları tiykarınan Stenfordta, Djon Makkarti, Bertram Rafael hám Kordell Grin menen baylanıslı hám Edinburgta, Djon Alan Robinson (Sirakuza universitetinen akademiyalıq miyman), Pet Xeys hám Robert Kovalski menen islegen. Proceduralıq kórinislerdiń tárepdarları tiykarınan MIT-te, Marvin Minskiy hám Seymur Papert basshılıǵında toplanǵan[1].

Logikanıń dálillew usıllarına tiykarlanǵanına qaramastan, MIT-te Karl Xyuitt tárepinen islep shıǵılǵan Planner usı proceduralıq paradigma ishinde payda bolǵan birinshi til boldı. Planner maqsetlerden (yaǵnıy, maqsetti qısqartıw yamasa keri baylanıslı shınjır) hám tastıyıqlawlardan (yaǵnıy, alǵa baylanıslı shınjır) proceduralıq jobalardıń úlgi boyınsha shaqırılıwın óz ishine alǵan. Plannerdiń eń tásirli implementaciyası — bul Plannerdiń kishi toplamı, Gerri Sassman, Yevgeniy Charnyak hám Terri Vinograd tárepinen ámelge asırılǵan Micro-Planner. Vinograd Micro-Plannerdi ataqlı, tábiyiy tildi túsinip alıw programması SHRDLU-dı ámelge asırıw ushın paydalandı. Nátiyjelilik maqsetinde, Planner keri izlew basqarıw strukturasın paydalandı, solay etip bir waqıtta tek bir múmkin bolǵan esaplaw jolın ǵana saqlaw kerek boldı. Planner QA4, Popler, Conniver, QLISP programmalastırıw tilleriniń hám Ether parallel tiliniń payda bolıwına sebep boldı.

Edinburgtaǵı Xeys hám Kovalski bilimlerdiń logikaǵa tiykarlanǵan deklarativ usılın Plannerdiń proceduralıq usılı menen kelistiriwge háreket etti. Xeys (1973) teńlemeli til, Golux-tı islep shıqtı, onda teorema dálillewshiniń háreketin ózgertiw arqalı hár túrli proceduralar alıwǵa bolatuǵın edi.

Sol waqıtta, Marseldegi Alen Kolmerauer semantikanı kórsetiw ushın logikanı hám soraw-juwap ushın rezolyuciyanı paydalanıp, tábiyiy tildi túsinip alıw ústinde islep atırǵan edi. 1971-jıldıń jazında Kolmerauer Kovalskidi Marselge shaqırdı hám olar birgelikte logikanıń klauzal formasınıń formal grammatikalardı kórsetiw ushın paydalanılıwı múmkin ekenin hám rezolyuciya teorema dálillewshileriniń sintaksislik analizlew ushın paydalanılıwı múmkin ekenin anıqladı. Olar giper-rezolyuciya[2] sıyaqlı ayırım teorema dálillewshileriniń tómennen-joqarıǵa analizlewshiler retinde, al SL rezolyuciyası (1971)[3] sıyaqlı basqalarınıń joqarıdan-tómenge analizlewshiler retinde isleytuǵının baqladı.

Keyingi 1972-jıldıń jazında, Kovalski, jáne de Kolmerauer menen birge islep, klauzal formadaǵı implikaciyalardıń proceduralıq interpretaciyasın islep shıqtı. Sonday-aq, bunday klauzalardıń anıq klauzalarǵa yamasa Xorn klauzalarına sheklenip qoyılıwı múmkin ekenligi hám SL-rezolyuciyasınıń SLD rezolyuciyasına sheklenip (hám ulıwmalastırılıp) qoyılıwı múmkin ekenligi de anıq boldı. Kovalskidiń proceduralıq interpretaciyası hám SLD 1973-jılǵı esabatında táriyiplengen hám 1974-jılı baspadan shıǵarılǵan[4].

Kolmerauer, Filip Russel menen birge, proceduralıq interpretaciyanı 1972-jıldıń jazında hám gúzinde ámelge asırılǵan Prologtıń tiykarı retinde qollandı. 1972-jılı jazılǵan hám Marselde ámelge asırılǵan birinshi Prolog programması — bul francuz tilindegi soraw-juwap sisteması edi. Prologtı ámeliy programmalastırıw tili retinde paydalanıw 1977-jılı Edinburgta Devid X. D. Uorren tárepinen kompilyator islep shıǵarılıwı menen úlken pát aldı. Eksperimentler Edinburg Prologınıń Lisp sıyaqlı basqa simvollıq programmalastırıw tilleriniń qayta islew tezligi menen básekilese alatuǵının kórsetti[5]. Edinburg Prologı de-fakto standartqa aylandı hám ISO standartı Prologtıń anıqlamasına kúshli tásir etti.

Logikalıq programmalastırıw 1980-jılları xalıqaralıq dıqqattı tarttı, ol Yaponiya Xalıqaralıq Sawda hám Sanaat Ministrligi tárepinen Besinshi Áwlad Kompyuter Sistemaları (FGCS) proekti ushın programmalıq támiynattı islep shıǵıw ushın tańlanǵanda. FGCS proekti úlken parallel kompyuterlerde aldınǵı qatar Jasalma Intellekt qosımshaların islep shıǵıw ushın logikalıq programmalastırıwdı qollanıwdı maqset etti. Proekt dáslep Prologtı paydalanıwdı izertlegen bolsa da, keyinirek FGCS kompyuter arxitekturasına jaqınıraq bolǵanlıqtan, parallel logikalıq programmalastırıwdı paydalanıwdı qabıl etti.

Degen menen, parallel logikalıq programmalastırıwdıń minnetlemeli tańlaw ózgesheligi tildiń logikalıq semantikası menen hám onıń bilimlerdi kórsetiw hám máselelerdi sheshiw qosımshaları ushın jaramlılıǵına kesent etti. Sonıń menen birge, proektte islep shıǵılǵan parallel kompyuter sistemaları anaǵurlım dástúrli, ulıwma maqsetli kompyuterlerdiń rawajlanıwında bolıp atırǵan alǵa ilgerilewler menen básekilese almadı. Usı eki másele birlesip FGCS proektiniń óz maqsetlerine erise almawına alıp keldi. Logikalıq programmalastırıwǵa da, jasalma intellektke de qızıǵıwshılıq dúnya júzi boyınsha tómenledi.

Sol waqıtta, Prologtı qollanıwǵa tiykarlanǵanlar qosılǵan, anaǵurlım deklarativ logikalıq programmalastırıw usılları FGCS proektinen ǵárezsiz túrde alǵa ilgerilewdi dawam etti. Atap aytqanda, Prolog deklarativ hám proceduralıq bilimlerdi kórsetiwdi birlestiriw ushın islep shıǵılǵanına qaramastan, logikalıq programmalardıń taza deklarativ interpretaciyası deduktiv maǵlıwmatlar bazaları tarawındaǵı qosımshalar ushın itibar orayına aylandı. Bul tarawdaǵı jumıslar shama menen 1977-jılı, Erve Galler hám Djek Minker Tuluzada logika hám maǵlıwmatlar bazaları boyınsha seminar shólkemlestirgende kózge túse basladı[6]. Bul taraw aqırında Datalog dep qayta ataldı.

Logikalıq programmalardıń logikalıq, deklarativ oqılıwına bul itibar 1980-jılları sheklewli logikalıq programmalastırıwdıń hám 1990-jılları Juwaplar Toplamın Programmalastırıwdıń rawajlanıwı menen jáne de kúsheytildi. Ol sonday-aq Prologtıń sońǵı qosımshalarında da jańadan ayrıqsha itibarǵa iye bolmaqta[7].

Logikalıq Programmalastırıw Associaciyası (ALP) 1986-jılı Logikalıq Programmalastırıwdı xoshametlew ushın dúzildi. Onıń 2000-jılǵa shekemgi rásmiy jurnalı — Logikalıq Programmalastırıw Jurnalı boldı. Onıń tiykar salıwshı bas redaktorı Dj. Alan Robinson edi[8]. 2001-jılı jurnal Logika hám Algebralıq Programmalastırıw Jurnalı dep qayta ataldı hám ALP-nıń rásmiy jurnalı Kembridj Universiteti Baspası tárepinen baspadan shıǵarılǵan Logikalıq Programmalastırıwdıń Teoriyası hám Ámeliyatı boldı.

Koncepciyalar

Logikalıq programmalar semantika hám máselelerdi sheshiw usıllarınıń bay túrine, sonday-aq programmalastırıw, maǵlıwmatlar bazaları, bilimlerdi kórsetiw hám máselelerdi sheshiwde keń qollanıw tarawlarına iye.

Algoritm = Logika + Basqarıw

Maqsetlerdi kishi maqsetlerge qısqartıw ushın keri oylawdı qollanatuǵın logikalıq programmalardıń proceduralıq interpretaciyası — bul algoritmniń háreketin alıw ushın bilimlerdiń deklarativ, logikalıq kórinisin paydalanıwdı basqarıw ushın máselelerdi sheshiw strategiyasın paydalanıwdıń arnawlı bir jaǵdayı. Ulıwmalıq alǵanda, hár túrli algoritmler alıw ushın birdey logikalıq kóriniske hár túrli máselelerdi sheshiw strategiyaları qollanılıwı múmkin. Alternativ túrde, berilgen máselelerdi sheshiw strategiyası menen hár túrli logikalıq kórinislerdi paydalanıp hár túrli algoritmler alıwǵa boladı[9].

Eki tiykarǵı máselelerdi sheshiw strategiyası — bul keri oylaw (maqsetti qısqartıw) hám alǵa pikirlew, sáykes túrde joqarıdan-tómenge hám tómennen-joqarıǵa oylaw dep te ataladı.

Propoziciyalıq Xorn klauzal programması hám joqarı dárejeli atomlıq maqset sıyaqlı ápiwayı jaǵdayda, keri oylaw maqsetti sheshiw ushın izlew keńisligin quraytuǵın hám-yamasa teregin anıqlaydı. Joqarı dárejeli maqset terektiń tamırı bolıp tabıladı. Terektegi hár qanday túyin hám bası túyin menen sáykes keletuǵın hár qanday klauza berilgen bolsa, klauzanıń denesindegi kishi maqsetlerge sáykes keletuǵın balalar túyinleri toplamı bar. Bul balalar túyinleri «hám» menen birge gruppalanǵan. Túyindi sheshiwdiń alternativ usıllarına sáykes keletuǵın alternativ balalar toplamları «yamasa» menen birge gruppalanǵan.

Bul keńislikti izlew ushın qálegen izlew strategiyasın paydalanıwǵa boladı. Prolog izbe-iz, sońǵı-kirgen-birinshi-shıqqan, keri izlew strategiyasın paydalanadı, bunda bir waqıtta tek bir alternativa hám bir kishi maqset qaraladı. Mısalı, kishi maqsetler parallel sheshiliwi múmkin, al klauzalar da parallel sınaqtan ótkeriliwi múmkin. Birinshi strategiya hám-parallel, al ekinshi strategiya yamasa-parallel dep ataladı. Aqıllı keri izlew[10] yamasa optimal sheshim tabıw ushın eń jaqsı-birinshi izlew sıyaqlı basqa izlew strategiyaları da múmkin.

Kishi maqsetler ózgeriwshilerdi bólise alatuǵın anaǵurlım ulıwma, propoziciyalıq emes jaǵdayda, eń kóp instanciyalanǵan yamasa tek bir procedura qollanılatuǵınday jetkilikli instanciyalanǵan kishi maqsetti tańlaw sıyaqlı basqa strategiyalardı da paydalanıwǵa boladı. Bunday strategiyalar, mısalı, parallel logikalıq programmalastırıwda qollanıladı[11].

Derekler

  1. ↑ Kowalski, R. A. (1988). "The early years of logic programming". Communications of the ACM 31: 38–43. doi:10.1145/35043.35046. http://www.doc.ic.ac.uk/~rak/papers/the%20early%20years.pdf. 
  2. ↑ Robinson. 
  3. ↑ Kowalski. 
  4. ↑ Kowalski. «Predicate Logic as a Programming Language». Department of Artificial Intelligence, Edinburgh University (1973). Also in Proceedings IFIP Congress, Stockholm, North Holland Publishing Co., 1974, pp. 569–574.
  5. ↑ Warren. 
  6. ↑ Gallaire, Hervé; Minker, John 'Jack', red. (1978), „Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977“, Advances in Data Base Theory, New York, ISBN 978-0-306-40060-5 {{citation}}: Unknown parameter |publisher= ignored (járdem).
  7. ↑ Warren, D.S.. Prolog: The Next 50 Years — 3–19 bet. DOI:10.1007/978-3-031-35254-6_1. 
  8. ↑ Robinson. 
  9. ↑ R.A.Kowalski (July 1979). "Algorithm=Logic + Control". Communications of the ACM 22 (7): 424–436. doi:10.1145/359131.359136. 
  10. ↑ Bruynooghe, M.. Implementations of Prolog — 194–215 bet. 
  11. ↑ Genesereth, M.R. (1985). Logic programming. 
«https://kaa.wikipedia.org/w/index.php?title=Logikalıq_programmalastırıw&oldid=168789» saytınan alınǵan