Loginis programavimas Spausdinti
( 5 Votes )
Parašė Aurimas Šimkus   

Loginis programavimas yra viena iš keturių programavimo paradigmų (imperatyvus, objektinis, funkcinis, loginis programavimas). Abi, loginio ir funkcinio programavimo, paradigmos priskiriamos platesnei deklaratyviojo programavimo paradigmai. Paprastai deklaratyviosios programavimo kalbos priešinamos su imepatyviosiomis. Dauguma programuotojų yra įpratę programuoti aprašydami detalius algoritmus, pažingsniui apibūdinančius, ką ir kaip programa turės atlikti. Tai yra imperatyvusis programavimas (C++, FPS, ...) Deklaratyviosiose programavimo kalbose paprastai nenurodoma, kaip detaliai programa turės veikti (kokius konkrečius tarpinius žingsnius turės atlikti), tačiau nurodoma tik aiškiai apibrėžta užduotis užduotis (ką reikės padaryti).

 

Imperatyviosios ir deklaratyviosios kalbos pavyzdys

Tarkime, reikia parašyti programą, kuri iš prekių sąrašo išrinktu prekes, kurios yra brangesnės nei 100 Lt. Pateikiame psiaudo kodo algoritmus, realizuotus imperatyvia ir deklaratyvia programavimo kalbomis:

Imperatyvus programavimas                                           
Deklaratyvus programavimas

kol indeksas=1 nelygu dydis(Sarasas):
      indeksas = indeksas + 1,
      Preke = Sarasas[indeksas]
      jeigu Preke.Prekes_kaina > 100,
          tada  Preke -> Atrinktos

Atrinktos = is Sarasas isrink Preke,
     kur K = Preke.Prekes_kaina ir
     K > 100

Pateiktame pavyzdyje reikėtų atkreipti dėmesį į tai, kad interaktyviosios kalbos pavyzdyje yra detalizuojamas kiekveinas reikalingos informacijos išgavimo žingsnis (apsirašomas indeksas, kurio pagalba atrinksim vis naują prekę, taip pat rašoma sąlyga (jei bus taip ,darysim taip)). Tuo tarpu deklaratyviosios kalbos pavyzdyje matome tiesiog užklausą, kuria pasakoma, iš kur, ką ir pagal ką gauti ir kam priskirti. Tokios užklausos yra daug panašesnės į žmogaus kalbą. Juk paprastai nenurodynėjame paslaugos tiekėjui, kaip konkrečiai atlikti užduotį, tiesiog pasakome tai, kokio rezultato norime.

 

Loginio programavimo istorija

Viskas prasidėjo laikotarpyje tarp 1960-1970 m.m. diskusijomis apie tai, kaip reikėtų programuoti dirbtinį intelektą (DI, angl. AI). Viena pusė (Stenfordo ir Edinburgo universitetai) palaikė deklaratyviojo programavimo idėją, tuo tarpu kita pusė (MIT universitetas) - procedūrinio (imperatyviojo) programavimo idėją. Deklaratyviojo programavimo šalininkai teigė, kad procedūriškai neįmanoma (arba labai sudėtinga) aprašyti visas situacijas, į kurias gali patekti dirbtinis intelektas. Jie teigė, kad dirbtinį intelektą reikia programuoti pagal matematinę logiką.

Prolog turbūt yra vienas iš geriausių loginio programavimo kalbų pavyzdžių, plačiausiai naudojamų ir šiandien. Ją 1972 m. sukurtė Alain Colmerauer ir Philippe Roussel. Ji yra grįsta formaliaja ir pirmos eilės logika. Pavadinimas kilo iš posakio "PROgramming in LOGic". Be Prolog, taip pat buvo sukruta ir daug kitų loginio programavimo kalbų: Datalog, Logtalk, Oz, XSB, Lambda Prolog, ... Nemažai iš jų (Datalog, Lambda Prolog, ...) yra sukurtos būtent iš Prolog. Taip buvo daroma norint išplėsti Prolog kalbos galimybes: geriau adapduoti duomenų bazėms, pridėti objektinio programavimo galimybių, pridėti grafinį programavimą arba net pakeisti logikos laipsnį į aukštesnį (Lambda Prolog)).

 

Loginių programų vykdymo principas

Programuojant logine programavimo kalba yra aprašoma žinių bazė. Tai yra įvairių faktų (aksiomų) ir taisyklių (ryšių tarp faktų) rinkinys. Programa yra vykdoma vykdant užklausą. Ši užklausa dar suvokiama kaip teiginys (pvz., '2+2 yra 4'). Interpretatorius bando atsakyti į šią užklausą remdamasis žinių bazės turiniu, t.y. jis bando rasti įrodymų, patvirtinančių arba paneigiančių šią užklausą (teiginį). Jei teiginys abstraktus, interpreatatorius grąžina visus galimus atsakymus.

Teiginio tvirtinimas gali vykti kelaiis būdais:

  • surandant pirmąjį teiginį patvirtinantį faktą (tradicinsi atvejis),
  • surandant geriausiai teiginį patvirtinantį faktą.

Patvirtinančio fakto paieška taip pat gali būti skirtinga;

  • ieškant nuo žinių bazės pradžios einant žemyn (tradicinis atvejis),
  • vykdant paralelinę paieška ir ieškant keliose vietose vienu metu.

Pateikiame psiaudo loginės programos vykdymo pavyzdį tradiciniu atveju, kai yra aprašyti 3 faktai, 2 taisyklės ir kviečiamos dvi užklausos (teiginiai):

Prolog interpretavimo pavyzdys

Taigi žinių bazėje yra aprašyti 3 faktai: "2+2 yra 2" (koks faktas bebūtų aprašytas, jis programoje jis laikomas teisingu - aksioma), "Vilnius - Lietuvos sostinė", "šalta"; 2 taisyklės: "jei miestas yra šalies sostinė, tai jis negali priklausyti kitai šaliai" ir "jei yra šalta, tai šiuo metu yra žiema". Šiunčiame dvi užklausas: "šalta" ir "žiema". Panagrinėkime programos vykdyma abiem atvejais.

Teiginys - "šalta". Teiginys siunčiamas į interpretatorių ir interpretatorius pradeda jo įrodymą. Žingsniai:

  1. Interpretatorius tikrina, ar faktas "2+2 yra 2" patvirtina (yra toks pat, kaip ir teiginys) teiginį "šaltą" - ne.
  2. Toliau tikrina, ar antrasis faktas patvirtiną teiginį - ne.
  3. Tikrina trečiąjį faktą: faktas "šalta" patvirtiną teiginį "šalta". Programai grąžinamas patvirtinimas.

Teiginys "žiema". Interpretatorius gauna šį teiginį ir ieško jo patvirtinimo žinių bazėje. Pirmi žingsniai tokie patys, kaip ir pirmuoju atveju. Faktai baigiasi. Prasideda taisyklės (sąryšiai). Tikrinama pirmoji taisyklė: kadangi teisinys "žiema" neturi nieko bendra su šalimis ar sostinėmis, tai ši taisyklė teiginio nepatvirtina. Tikrinama kita taisykle - "jei yra šalta, tai šiuo metu yra žiema". Taisyklėje randami raktiniai žodžiai: "šalta" ir "žiema". Norint patvirtinimo, kad yra "šalta", reikia patvirtinimo, kad yra "žiema". Interpretatorius iš naujo peržiūri žinių bazę (žr. aukščiau į užklausos "šalta" patvirtinimą) ir patvirtina teiginį - "šalta". Vadinasi, patvirtinamas ir teiginys "žiema".

Jeigu nepavyktų rasti teiginį (užklausą) patvirtinančių faktų ar taisyklių, interpretatorius grąžintų atsakymą, kad patvirtinimas nepavyko.