Loginis programavimas: apibrėžimas, Prolog, taisyklės ir neigimas

Loginis programavimas - tai matematinės logikos idėjų ir formalizmų taikymas kompiuterių programoms rašyti. Tokiuose sprendimuose programos dažniausiai aprašomos ne kaip procedūrų sekos, o kaip faktų ir taisyklių rinkinys, iš kurio vykdymo sistema automatiškai išveda atsakymus į užklausas. Yra specializuotų programavimo kalbų, kuriose naudotojas gali tiesiogiai įvesti loginius teiginius — bene žinomiausia iš jų yra Prolog. Istoriškai į kompiuterių mokslo teoriją prisidėjo ir kita paradigmos dalis: Alonzo Churchas sukūrė lambda skaičiavimo teoriją, žinomą kaip lambda skaičiuote, kuri padėjo formuoti bendresnius programavimo kalbų modelius; taip pat idėjos apie simbolinį apdorojimą ir taisyklių manipuliaciją buvo svarbios kalbai LISP.

Taisyklės, faktai ir užklausos

Loginę programą sudaro:

Faktai — atskiri teiginiai, kuriuos laikome tiesa (pvz., parent(jonas,petras)).
Taisyklės — loginių sąlygų reikšmė, kuri apibrėžia, kaip vieni teiginiai išvedami iš kitų (pvz., ancestor(X,Y) :- parent(X,Y) reiškia, kad jeigu X yra Y tėvas, X yra ir protėvis).
Užklausos — klausimai sistemai, ar tam tikras teiginys yra išvedamas iš esamų faktų ir taisyklių (pvz., ?- ancestor(jonas,klaudija)).

Programos taisyklės dažnai išreiškiamos kaip Horn'o klauzulės (vienas išraiškos galas — galva, ir sąlygos — kūnas). Loginių uždavinių sprendimą realizuoja automatinis mechanizmas, pagrįstas unifikacija, atgaline (backtracking) paieška ir resolucija (dažnai SLD-resolucija Prologe).

Prolog: pagrindai ir pavyzdys

Prolog yra deklaratyvi kalba, kurioje vartotojas nurodo, kas yra tiesa, o vykdymo sistema nusprendžia, kaip iš to gauti atsakymus. Pagrindiniai mechanizmai — unifikacija, atgalinis paieškos mechanizmas ir failo sistemos priemonės, tokios kaip cut (restrikcija paieškai).

Pavyzdys mažos Prolog programos:

parent(jonas, petras). parent(petras, klaudija).  ancestor(X,Y) :- parent(X,Y). ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

Užklausa ?- ancestor(jonas, klaudija). sugrąžins teigiamą atsakymą, nes sistema randa kelių žingsnių išvedimą per tarpinį petras. Prologe taip pat galima gauti visus sprendinius (visi X ir Y), naudoti kintamuosius, sąrašus, ir integruoti sudėtingesnes bibliotekas (pvz., DCG natūralaus kalbos apdorojimui, CLP – ribų sprendimams).

Neigimas ir „neigimas kaip nesėkmė“

Dažnai loginiame programavime naudojamas neigimas kaip nesėkmė (angl. negation as failure arba silpnasis neigimas). Tai reiškia, kad jei iš faktų ir taisyklių neįmanoma išvesti tam tikros sąlygos p {\displaystyle p}, $p$ sistema darys prielaidą, kad jos paneigimas yra teisingas. Tokia prielaida glaudžiai susijusi su uždaro pasaulio prielaida (closed-world assumption): kas neišreikšta kaip teisinga — laikoma klaidinga.

Reikia atskirti tai nuo klasikinės (stiprios) logikos neigimo: neigimas kaip nesėkmė yra netiesioginis ir neturi klasikinių logikos garantijų (tai yra ne monotoniška sprendimo strategija). Dėl to buvo sukurti formalesni semantikos modeliai, kad apibrėžtų neigimą įvairiuose kontekstuose, pavyzdžiui:

Well-founded semantics — sprendžia tam tikrus prieštaravimus, suteikiant trijų reikšmių logiką (tiesa / melas / neišspręsta).
Stable model semantics (answer set programming) — leidžia išreikšti ne monotoniškas žinias ir kompleksinius nenumatomus scenarijus.

Semantika, privalumai ir ribotumai

Loginis programavimas turi keletą svarbių savybių:

Deklaratyvumas: programuotojas aprašo ką norima gauti, o ne kaip tai pasiekti.
Aiški formali semantika: paprastos taisyklės gali būti vertinamos pagal logikos modelius.
Galinga paieška ir atgalinio spėjimo mechanizmai: patogu kurti ekspertines sistemas, žinių bazes, natūralios kalbos apdorojimą ir kt.

Nepaisant stipriųjų pusių, yra ir trūkumų:

Ne visos užduotys (ypač tokioms, kur reikia intensyvaus „valstybės“ valdymo ar našaus skaičiavimo) tinka loginiam požiūriui.
Neigimas kaip nesėkmė gali sukelti netikėtų rezultatų esant neišsamioms žinioms.
Efektyvumas ir mastelio klausimai: kai kuriems problemų tipams reikia papildomų optimizacijų arba hibridinių sprendimų (pvz., CLP, procedūriniai plėtiniai).

Pritaikymas ir alternatyvos

Loginis programavimas plačiai naudojamas dirbtiniuose intelektuose, ekspertinėse sistemose, schemų sudaryme, natūralios kalbos analizėje ir žinių atstovavime. Kiti artimi metodai — Answer Set Programming (ASP), Constraint Logic Programming (CLP) ir hibridinės paradigmos, kurios derina logiką su imperatyviais ar funkciniais elementais, kai reikia geresnio našumo arba kitokio semantikos modelio.

Šiame tekste pateikti pagrindiniai loginio programavimo principai ir Prolog pavyzdys leidžia suprasti, kaip formalios logikos priemonės gali tapti praktine programavimo priemone ir kokias specifines problemas sprendžia ši paradigma.

Klausimai ir atsakymai

K: Kas yra loginis programavimas?

A: Loginis programavimas - tai programavimo metodas, kai kompiuterių programoms rašyti naudojama matematinė logika.

K: Kokios yra kelios programavimo kalbos, kuriose naudojamas loginis programavimas?

A: Kai kurios programavimo kalbos, kuriose naudojamas loginis programavimas, yra Prolog ir LISP.

K: Koks taisyklių ir faktų vaidmuo loginiame programavime?

A: Loginio programavimo programas sudaro taisyklių ir faktų rinkinys.

K: Kas yra neigimas kaip nesėkmė loginiame programavime?

A: Neigimas kaip nesėkmė - tai loginio programavimo sąvoka, kai, jei iš faktų ir taisyklių neįmanoma išvesti tam tikros sąlygos, sistema daro prielaidą, kad jos neigimas yra teisingas.

K: Kas yra silpnasis neigimas loginiame programavime?

A: Silpnasis neigimas - tai kitas terminas, reiškiantis neigimą kaip nesėkmę, kuris yra loginio programavimo sąvoka.

K: Kas naudojo loginio programavimo formą lambda skaičiuotę?

A: Alonzo Churchas naudojo loginio programavimo formą, kuri šiandien žinoma kaip lambda skaičiuoklė.

K: Kuri iš žinomiausių programavimo kalbų leidžia naudotojams tiesiogiai įvesti loginius teiginius?

A: Prologas yra bene geriausiai žinoma programavimo kalba, leidžianti naudotojams tiesiogiai įvesti loginius teiginius.