Kaj je logično programiranje? Definicija, jeziki (Prolog, LISP) in primeri

Razumite logično programiranje: definicija, jeziki (Prolog, LISP), primeri in osnovna logika za razvoj pravil in dejstev — vodnik za začetnike in napredne.

Logično programiranje je paradigma programiranja, kjer so programi izraženi kot zbirka stavkov v formalni logiki. Uporablja se matematična logika za opis znanja, pravil in odnosov, medtem ko mehanizmi sklepanja izvedejo izpeljave. Obstajajo specializirani programski jeziki, v katere lahko uporabnik neposredno vnaša logične stavke. Verjetno najbolj znani od teh jezikov se imenuje Prolog. Alonzo Church je uporabil obliko logičnega programiranja, ki je danes znana kot lambda račun. Logično programiranje je bilo uporabljeno tudi v jeziku LISP.

Osnovni koncepti

Programi v logičnem programiranju so sestavljeni iz dejstev (faktov) in pravil (implicativnih stavkov). Pogosto se uporablja oblika logike z Hornovimi klavzulami, kjer so pravila oblike "glava :- telo." (v Prolog notaciji). Glavni mehanizmi izvajanja so:

• Unifikacija — postopek ujemanja struktur (spremenljivk in konstanti) med poizvedbo in dejstvi/pravili.
• Rezolucija / SLD izpeljava — strateško iskanje izpeljav, pogosto z globinskim iskanjem in povratnim iskanjem (backtracking).
• Declarativno branje — program opisuje, kaj drži, ne pa korakov, kako to izvesti (čeprav izvajalci v praksi določajo proceduralni vidik).

Primeri (Prolog)

Tipičen kratek primer Prolog programa (dejstva in pravila):

 parent(alice, bob). parent(bob, carol).  ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). 

Poizvedba

 ?- ancestor(alice, carol). 

bo vrnila odgovor "true", ker se prek pravil izvede izpeljava. Prolog uporablja unifikacijo in povratno iskanje, da poišče vrednosti spremenljivk, ki zadovoljujejo poizvedbo.

LISP, lambda račun in logično programiranje

Čeprav LISP ni tipični logični jezik, je bil pogosto uporabljen za raziskave in implementacije sistemov za umetno inteligenco ter služi kot okolje za izvajanje logičnih algoritmov. Alonzo Church-ov lambda račun predstavlja teoretično podlago za funkcionalno programiranje in ima prekrivanje z logičnimi pristopi (saj so funkcije in lambda izrazi uporabni tudi pri formalnih dokazih in transformacijah).

Negacija kot neuspeh (šibka negacija)

Programi so sestavljeni iz niza pravil in dejstev. V večini primerov se pri logičnem programiranju uporablja tako imenovana negacija kot neuspeh ali šibka negacija: To pomeni, da če iz dejstev in pravil ni mogoče izpeljati nekega stavka p {\displaystyle p}, bo sistem predpostavil, da je njegova negacija resnična.

Ta pristop (ang. negation as failure) pomeni, da je negacija preizkus neuspeha dokazovanja. Pomembno je vedeti, da je takšna negacija neklasična in lahko vodi do neintuitivnih rezultatov v prisotnosti nepopolnih informacij ali cikličnih odvisnosti. Zato so za robustnejše specifične potrebe razvite razširitve, kot so negacija z refutacijo, answer set programming (ASP) ali constraint logic programming (CLP).

Naprednejše teme in razširitve

• Constraint Logic Programming (CLP) — kombinira logično programiranje z reševanjem omejitev (aritmetične, booleove, itd.).
• Answer Set Programming (ASP) — paradigma za modeliranje težjih kombinatornih problemov z različnimi semantiki negacije in močnim solverjem za izračun modelov (answer sets).
• Probabilistični logični sistemi — uvajajo verjetnostne modele (npr. ProbLog), primerne za negotovo znanje.

Uporabe

Logično programiranje se pogosto uporablja v:

• umetni inteligenci in ekspertnih sistemih,
• znanju predstavitvije in sistemih za sklepanja,
• obdelavi naravnega jezika in parserjih,
• formalnem preverjanju in dokazovanju izrekov,
• reševanju kombinatornih in omejitvenih problemov (s CLP/ASP).

Prednosti in omejitve

Prednosti: visok nivo deklarativnosti, naraven zapis znanja in pravil, močni mehanizmi izpeljav in iskanja.

Omejitve: zmogljivost pri velikih podatkovnih naborih, neintuitivna vedenja negacije kot neuspeh, ter včasih težave z determinističnim nadzorom izvajanja (če potrebujemo natančen nadzor nad strategijo iskanja).

Za začetek z logičnim programiranjem je Prolog dober vstopni jezik. Nadaljnje raziskovanje lahko vključuje CLP, ASP in probabilistične razširitve glede na specifične potrebe projekta.

Vprašanja in odgovori

V: Kaj je logično programiranje?

V: Kateri so nekateri programski jeziki, ki uporabljajo logično programiranje?

V: Kakšna je vloga pravil in dejstev pri logičnem programiranju?

V: Kaj je negacija kot neuspeh v logičnem programiranju?

V: Kaj je šibka negacija v logičnem programiranju?

V: Kdo je uporabil obliko logičnega programiranja v lambda kalkulu?

V: Kateri je najbolj znan programski jezik, ki uporabnikom omogoča neposreden vnos logičnih stavkov?

Išči po črki