Логическото програмиране е парадигма за програмиране, която се основава на принципите на формалната логика, анализ на предикатите и предикатното смятане.
Други свързани парадигми за програмиране са например императивното програмиране, структурно програмиране и функционалното програмиране.
Програмите, написани на език за логическо програмиране, представляват поредица от логически правила и факти. Основни езици за логическо програмиране са Prolog и Visial Prolog, ASP и Datalog.
Правилата са написани във формата на клаузи: H :- B1, ..., Bn. Правилото има логически смисъл на импликация, която се чете „H е вярно, ако е вярно B1, ..., Bn“: H if B1 and ... and Bn. Правилата имат глава (следствие) H и тяло (опашка, предпоставки) B1, ..., Bn. Правилата дават информация за условията, които са достатъчни за изпълняването на дадена връзка или свойство. Главата на правилото се състои от единствен атом и означава свойството или връзката, която ще е в сила, ако са изпълнени всички предпоставки на правилото. Тялото на правилото се състои от поредица от атоми. Знакът, разделящ тялото и главата, се чете „е вярно, ако“.
Фактите могат да се третират като правила без тяло, т.е. безусловни правила. Те имат следната форма: H. В най-простия случай, когато H, B1, ..., Bn са атомарни формули, тези клаузи се наричат клаузи на Хорн. Съществуват редица вариации на този случай, например когато тялото е съставено от отрицанията на атомарни формули (отрицателни Хорнови клаузи).
В ASP и Datalog, програмите се характеризират само с декларативно четене и тяхното изпълнение се извършва с помощта на процедури за „доказателство“, чието поведение не е под контрола на програмиста. За разлика от това, в Пролог-базираните езици, програмите се характеризират с т.нар. процедурна интерпретация: за да се реши H, трябва да се реши B1 и ... и Bn. Например нека имаме следната клауза: fallible(X) :- human(X). базирана на пример, използван от Terry Winograd, за да илюстрира програмния език Planner. Като клауза в една логическа програма може да се използва, както като процедура, която проверява дали X е склонен да греши, като се провери дали X е човек, така и като процедура за намирането на човек X, който е склонен на греши, чрез намирането на X, който да е човек. Дори фактите имат процедурна интерпретация. Например клаузата: human(socrates). може да се използва едновременно като процедура, която показва, че socrates е човек, и като процедура, която намира X, който е човек, чрез определянето на socrates за човек.
Декларативното четене при програмите, написани на логически език за програмиране, може да се използва за проверка на коректността на програмата. Също така може да се използват техники за програмно трансформиране на една логически-базирана програма към друга такава, еквивалентна на нея, но по-ефективна. В Пролог-базираните логически езици може да се използва механизмът на изпълнение на програмата за подобряване на ефективността.
История Логическото програмиране е парадигма в програмирането, която е разработена през 70-те години, за решаването на задачи, свързани с изкуствения интелект. Вместо да се гледа на компютърната програма като описание стъпка по стъпка на един алгоритъм, програмата е замислена като логична теория, а на извикващата процедура се гледа като на теоремата, на която трябва да се установи истината. По този начин, изпълнението на програмата означава търсене на доказателство. В традиционните (императивни) езици за програмиране, програмата е процедурна спецификация как проблем трябва да бъде решен, а при езиците за логическо програмиране, програмата дава на компютъра описание на проблема, като използва редица факти и правила, а след това го кара да намери всички възможни решения.
Логическото програмиране има своите корени в ламбда смятането, разработено от Алонсо Чърч през 1930 г. Въпреки това, първото предложение за използване на логика за представяне на компютърни програми е направено от Кордел Грийн (1969 г.) в Станфордския Университет.Cordell Green. Application of Theorem Proving to Problem Solving IJCAI 1969. По същото време Фостър и Елкок представят Absys, първия език за логическо програмиране.J.M. Foster and E.W. Elcock. ABSYS 1: An Incremental Compiler for Assertions: an Introduction, Machine Intelligence 4, Edinburgh U Press, 1969, pp. 423 – 429
Една от най-известните системи, основана на процедурно представяне и използване на знания, е езикът Planner, разработен в MIT от Карл Хюит (1969 г.).Carl Hewitt. Planner: A Language for Proving Theorems in Robots IJCAI 1969. Той е предназначен за представяне и контрол на информация и дава възможност да се разглеждат не всички възможни, а само най-вероятните връзки. Друго популярно приложение е системата SHRDLU на Тери Виноград (Станфордския Университет SRI International).
Създаден като алтернатива на процедурното представяне е езикът PROLOG от Алан Колмерю и Филип Ръсел в университета в Екс-Марсилия, Франция, през 1973 година. PROLOG е доразвит от логика Робърт Ковалски, който е член на групата AI в университета в Единбург.Kowalski, R. A. (1988). "The early years of logic programming"Communications of the ACM 31: 38. doi:10.1145/35043.35046
Изследователи от Института за New Generation Computer Technology в Токио са използвали PROLOG като основа за сложни логически програмни езици, известни като езици пето поколение.
Друга работа включва разработването на езици, разглеждащи времевозависими данни, като например „сметката е платена вчера“. Тези езици са базирани на темпоралната логика, която позволява твърденията да бъдат разположени в потока на времето.Artificial intelligence programming language, Written by: B.J. Copeland
Aсоциацията за логическо програмиране е основана за насърчаване на логическото програмиране през 1986 г.
Концепции Логика и контрол
Логическото програмиране може да бъде разглеждано като контролиран извод. Важна концепция в логическото програмиране е разделянето на програмите на техните логически и контролни компоненти. С езици за чисто логическо програмиране, логическият компонент сам установява решенията. Контролният компонент може да се променя, за да осигури алтернативни начини за изпълнение на логическа програма. Тази идея е пресъздадена от мотото Алгоритъм = Логика + Контрол където „Логика“ означава логическа програма, а „Контрол“ символизира различни стратегии за доказване на теореми.
Решаване на проблем В опростения случай, в който логическа програма и най-важната основна цел не съдържат променливи, основният довод изгражда и-или дърво, което представлява обхвата на търсене за разрешаване на целта. Най-важната цел е коренът на дървото. Като се вземе предвид всяко разклонение и всяка точка, чието начало съответства на разклонението, съществуват серия от подразклонения, кореспондиращи с подцелите. Тези подразклонения са групирани заедно с „и“. Алтернативните серии от подразклонения, кореспондиращи с алтернативни варианти за решаване на разклонението, са групирани заедно от „или“.
Всяка стратегия за търсене може да бъде използвана за търсене на обхвата. Пролог използва последователна, „последен-влязъл-последен-излязъл“, проследяваща назад стратегия, в която се разглеждат само една алтернатива и една подцел. Други стратегии за търсене, като например паралелното търсене, смисленото проследяване назад или най-доброто първо търсене за намиране на оптимално решение, също са възможни.
В най-общия случай, когато подцелите имат общи променливи, могат да бъдат използвани други стратегии, като например избиране на подцел, която е най-обща или е достатъчно спешна, така че е необходима само една процедура. Такива стратегии се използват, например в конкурентното логическо програмиране.
Отрицание като провал
За повечето практически приложения, както и за приложения, които изискват не-еднообразни разсъждения в изкуствения интелект, логическите програми, които използват Хорнови клаузи, трябва да бъдат разширени до нормални логически програми с отрицателни условия. Една клауза в нормална логическа програма има формата: H :- A1, …, An, not B1, …, not Bn. и се чете декларативно като логическа импликация: H if A1 and … and An and not B1 and … and not Bn. където H и всички Ai и Bi са атомни формули. Отрицанието в негативните литерали not Bi обикновено се отнася като „отрицание като провал“, защото в повечето приложения, в които се имплементира, отрицателното условие not Bi демонстрира, че положителното условие Bi не успява да се задържи. Например: canfly(X) :- bird(X), not abnormal(X). abnormal(X) :- wounded(X). bird(john). bird(mary). wounded(john). Изобразяване на целта (твърдението) за намиране на нещо, което може да лети: :- canfly(X). Има две възможни решения, които решават първата подцел bird(X), а именно X = john и X = mary. Втората подцел not abnormal(john) от първото възможно решение се проваля, тъй като wounded(john) успява и поради това abnormal(john) успява. Въпреки това втората подцел not abnormal(mary) на второто възможно решение успява, тъй като wounded(mary) се проваля, и затова abnormal(mary) се проваля. Ето защо, X = mary е единственото решение на първоначално поставената цел.
Micro-Planner е имал конструкция наречена „thnot“, която, когато се прилага към израз, връща стойността истина ако (и само ако) оценката на израза не успее. Подобен оператор обикновено е вграден и в съвременните Prolog реализации. Обикновено се изписва като not(Goal) или \+ Goal , къдетоGoal е някаква цел (твърдение), което да бъде доказано от програмата. Този оператор се различава от отрицанието в първия ред логика: отрицание като \+ X == 1 се проваля, когато променливата X е свързана към атома 1 , но тя успява във всички останали случаи, включително когато X е неконсолидиран. Това прави разсъждението Prolog нееднозначно: X = 1, \+ X == 1 винаги се проваля, докато \+ X == 1, X = 1 може да успее, свързвайки X към 1 , в зависимост от това дали X първоначално е обвързан (имайте предвид, че стандартния Prolog изпълнява твърдения от ляво надясно).
Логическият статус на отрицанието като провал е неразрешено, докато Кийт Кларк показа, че при определени естествени условия, то е вярно (а понякога и пълно) изпълнение на класическото отрицание по отношение на целостта на програмата. Целостта се отнася приблизително до настройване на всички програмни клаузи с едни и същи предикати от лявата страна: Н: – Body 1. ... Н: – Body к. като определение на предиката H iff (Body1 or … or Bodyk) където „iff“ означава „ако и само ако“. Изписването на цялото изисква изричното използване на равнопоставени предикати и включване на набор от подходящи аксиоми за равенство. Въпреки това, прилагането на отрицанието чрез провал се нуждае само от половинките IF-на определенията без аксиоми на равенство.
Например завършването на програмата горе е: canfly(X) iff bird(X), not abnormal(X). abnormal(X) iff wounded(X). bird(X) iff X = john or X = mary. X = X. not john = mary. not mary = john. Представата за завършеност е тясно свързана с определението на Маккарти за разсъждение по подразбиране и че по презумпция едно твърдение е вярно, ако за него е известно, че е вярно – допускането на затворен свят.
Като алтернатива на семантиката на завършване, отрицанието като провал може да се тълкува и познавателно, както в семантиките на стабилен модел на програмирането с редица отговори. В тази интерпретация not(Bi) означава буквално, че Bi не е известно. Познавателното тълкуване има предимството, че може да се комбинира с класическото отрицание, както в „разширеното логическо програмиране“, да се формализират фрази като „противоположното не може да се докаже“, където „противоположното“ е класическо отрицание, и „не може да се докаже“ е познавателна интерпретация на отрицанието като провал.
Представяне на знания