Логическо програмиране

Логическото програмиране е парадигма за програмиране, която се основава на принципите на формалната логика, анализ на предикатите и предикатното смятане.

Други свързани парадигми за програмиране са например императивното програмиране, структурно програмиране и функционалното програмиране.

Програмите, написани на език за логическо програмиране, представляват поредица от логически правила и факти. Основни езици за логическо програмиране са Prolog и Visial Prolog, ASP и Datalog.

Правилата са написани във формата на клаузи:

H :- B₁, ..., B_n.

Правилото има логически смисъл на импликация, която се чете „H е вярно, ако е вярно B₁, ..., B_n“:

H if B₁ and ... and B_n.

Правилата имат глава (следствие) H и тяло (опашка, предпоставки) B₁, ..., B_n. Правилата дават информация за условията, които са достатъчни за изпълняването на дадена връзка или свойство. Главата на правилото се състои от единствен атом и означава свойството или връзката, която ще е в сила, ако са изпълнени всички предпоставки на правилото. Тялото на правилото се състои от поредица от атоми. Знакът, разделящ тялото и главата, се чете „е вярно, ако“.

Фактите могат да се третират като правила без тяло, т.е. безусловни правила. Те имат следната форма:

H.

В най-простия случай, когато H, B₁, ..., B_n са атомарни формули, тези клаузи се наричат клаузи на Хорн. Съществуват редица вариации на този случай, например когато тялото е съставено от отрицанията на атомарни формули (отрицателни Хорнови клаузи).

В ASP и Datalog, програмите се характеризират само с декларативно четене и тяхното изпълнение се извършва с помощта на процедури за „доказателство“, чието поведение не е под контрола на програмиста. За разлика от това, в Пролог-базираните езици, програмите се характеризират с т.нар. процедурна интерпретация:

за да се реши H, трябва да се реши B₁ и ... и B_n.

Например нека имаме следната клауза:

fallible(X) :- human(X).

базирана на пример, използван от Terry Winograd, за да илюстрира програмния език Planner. Като клауза в една логическа програма може да се използва, както като процедура, която проверява дали X е склонен да греши, като се провери дали X е човек, така и като процедура за намирането на човек X, който е склонен на греши, чрез намирането на X, който да е човек. Дори фактите имат процедурна интерпретация. Например клаузата:

human(socrates).

може да се използва едновременно като процедура, която показва, че socrates е човек, и като процедура, която намира X, който е човек, чрез определянето на socrates за човек.

Декларативното четене при програмите, написани на логически език за програмиране, може да се използва за проверка на коректността на програмата. Също така може да се използват техники за програмно трансформиране на една логически-базирана програма към друга такава, еквивалентна на нея, но по-ефективна. В Пролог-базираните логически езици може да се използва механизмът на изпълнение на програмата за подобряване на ефективността.

История

Логическото програмиране е парадигма в програмирането, която е разработена през 70-те години, за решаването на задачи, свързани с изкуствения интелект. Вместо да се гледа на компютърната програма като описание стъпка по стъпка на един алгоритъм, програмата е замислена като логична теория, а на извикващата процедура се гледа като на теоремата, на която трябва да се установи истината. По този начин, изпълнението на програмата означава търсене на доказателство. В традиционните (императивни) езици за програмиране, програмата е процедурна спецификация как проблем трябва да бъде решен, а при езиците за логическо програмиране, програмата дава на компютъра описание на проблема, като използва редица факти и правила, а след това го кара да намери всички възможни решения.

Логическото програмиране има своите корени в ламбда смятането, разработено от Алонсо Чърч през 1930 г. Въпреки това, първото предложение за използване на логика за представяне на компютърни програми е направено от Кордел Грийн (1969 г.) в Станфордския Университет. По същото време Фостър и Елкок представят Absys, първия език за логическо програмиране.

Една от най-известните системи, основана на процедурно представяне и използване на знания, е езикът Planner, разработен в MIT от Карл Хюит (1969 г.). Той е предназначен за представяне и контрол на информация и дава възможност да се разглеждат не всички възможни, а само най-вероятните връзки. Друго популярно приложение е системата SHRDLU на Тери Виноград (Станфордския Университет SRI International).

Създаден като алтернатива на процедурното представяне е езикът PROLOG от Алан Колмерю и Филип Ръсел в университета в Екс-Марсилия, Франция, през 1973 година. PROLOG е доразвит от логика Робърт Ковалски, който е член на групата AI в университета в Единбург.

Изследователи от Института за New Generation Computer Technology в Токио са използвали PROLOG като основа за сложни логически програмни езици, известни като езици пето поколение.

Друга работа включва разработването на езици, разглеждащи времевозависими данни, като например „сметката е платена вчера“. Тези езици са базирани на темпоралната логика, която позволява твърденията да бъдат разположени в потока на времето.

Aсоциацията за логическо програмиране е основана за насърчаване на логическото програмиране през 1986 г.

Концепции

Логика и контрол

Логическото програмиране може да бъде разглеждано като контролиран извод. Важна концепция в логическото програмиране е разделянето на програмите на техните логически и контролни компоненти. С езици за чисто логическо програмиране, логическият компонент сам установява решенията. Контролният компонент може да се променя, за да осигури алтернативни начини за изпълнение на логическа програма. Тази идея е пресъздадена от мотото

Алгоритъм = Логика + Контрол

където „Логика“ означава логическа програма, а „Контрол“ символизира различни стратегии за доказване на теореми.

Решаване на проблем

В опростения случай, в който логическа програма и най-важната основна цел не съдържат променливи, основният довод изгражда и-или дърво, което представлява обхвата на търсене за разрешаване на целта. Най-важната цел е коренът на дървото. Като се вземе предвид всяко разклонение и всяка точка, чието начало съответства на разклонението, съществуват серия от подразклонения, кореспондиращи с подцелите. Тези подразклонения са групирани заедно с „и“. Алтернативните серии от подразклонения, кореспондиращи с алтернативни варианти за решаване на разклонението, са групирани заедно от „или“.

Всяка стратегия за търсене може да бъде използвана за търсене на обхвата. Пролог използва последователна, „последен-влязъл-последен-излязъл“, проследяваща назад стратегия, в която се разглеждат само една алтернатива и една подцел. Други стратегии за търсене, като например паралелното търсене, смисленото проследяване назад или най-доброто първо търсене за намиране на оптимално решение, също са възможни.

В най-общия случай, когато подцелите имат общи променливи, могат да бъдат използвани други стратегии, като например избиране на подцел, която е най-обща или е достатъчно спешна, така че е необходима само една процедура. Такива стратегии се използват, например в конкурентното логическо програмиране.

Отрицание като провал

За повечето практически приложения, както и за приложения, които изискват не-еднообразни разсъждения в изкуствения интелект, логическите програми, които използват Хорнови клаузи, трябва да бъдат разширени до нормални логически програми с отрицателни условия. Една клауза в нормална логическа програма има формата:

H :- A₁, …, A_n, not B₁, …, not B_n.

и се чете декларативно като логическа импликация:

H if A₁ and … and A_n and not B₁ and … and not B_n.

където H и всички A_i и B_i са атомни формули. Отрицанието в негативните литерали not B_i обикновено се отнася като „отрицание като провал“, защото в повечето приложения, в които се имплементира, отрицателното условие not B_i демонстрира, че положителното условие B_i не успява да се задържи. Например:

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 изпълнява твърдения от ляво надясно).

Логическият статус на отрицанието като провал е неразрешено, докато Кийт Кларк [1978] показа, че при определени естествени условия, то е вярно (а понякога и пълно) изпълнение на класическото отрицание по отношение на целостта на програмата. Целостта се отнася приблизително до настройване на всички програмни клаузи с едни и същи предикати от лявата страна:

Н: – Body 1.

...

Н: – Body к.

като определение на предиката

H iff (Body₁ or … or Body_k)

където „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(B_i) означава буквално, че B_i не е известно. Познавателното тълкуване има предимството, че може да се комбинира с класическото отрицание, както в „разширеното логическо програмиране“, да се формализират фрази като „противоположното не може да се докаже“, където „противоположното“ е класическо отрицание, и „не може да се докаже“ е познавателна интерпретация на отрицанието като провал.

Представяне на знания

Фактът, че клаузите на Хорн могат да дадат процедурна интерпретация и обратното, процедурите за редуциране на целите могат да бъдат разбрани като клаузите на Хорн + обратния довод, означава че логическите програми комбинират декларативни и процедурни изобразявания на познание. Обхващането на отрицанието като провал, означава че логическото програмиране е вид немонотонна логика.

Въпреки нейната опростеност в сравнение с класическата логика, тази комбинация от клаузи на Хорн и отрицание като провал, се е доказала като учудващо изразителна. Комбинацията е натурален език за изразяване на здравомислещи закони за причина и резултат, както в ситуационното смятане и събитийно смятане.

В най-общия случай, когато подцели имат общи променливи, могат да бъдат използвани други стратегии, като например избиране на подцел, която е най-обща или е достатъчно спешна, така че е необходима само една процедура. Такива стратегии се използват, например в конкурентното логическо програмиране.

Езици за логическо програмиране

Пролог

Програмният език Пролог е създаден от Ален Колмерое през 1972 година. Той е резултат на съвместната работа между Колмерое и Робърт Ковалски в Единбург. Колмерое е работил върху естественият език на разбиране, използвайки логика за да представи семантиката и използвайки резолюция за съответните въпроси и отговори. През лятото на 1971 година, Колмерое и Ковалски открили, че клаузалната форма на логика може да се използва за представяне на официални граматики, а теоремата за резолюция доказала, че биха могли да бъдат използвани и за граматичен разбор. Те установили как някои теореми се доказали, като хипер-резолюцията и естественият език на разбиране SL-резолюцията през 1971 година. Процедурното тълкуване на Ковалски и LUSH, са описани в бележка от 1973 година и са публикувани година по-късно.

През лятото и есента на 1972 година двамата отново работили заедно и разработили процесуално тълкуване на последиците. Чрез декларативно-процесуалната интерпретация, по-късно образували нотацията на програмния език Пролог,

H :- B₁, ..., B_n.

която може да бъде четена и използвана, както декларативно така и процесуално.

Колмерое заедно с Филипе Роузел, използват двойното тълкуване, като основа на Пролог и така осъществяват неговото реализиране през късното лято на 1972 година. Първата Пролог програма написана през 1972 година и пусната в Марсилия, е била система за въпроси и отговори на френски език. Разработването на компилатора от Дейвид Уорън в Единбург през 1977 година дава голям тласък за развитието на Пролог като практически език за програмиране. Експериментите показали, че единбургският Пролог може да се конкурира по отношение скоростта на обработка с други символни езици за програмиране, като Lisp. С това той оказал силно въздействие върху дефиницията за ISOна Пролога.

Абдуктивно логическо програмиране

Абдуктивното логическо програмиране е разширение на обикновеното логическо програмиране, което позволява някои предикати, декларирани като абдуктивни, да бъдат „отворени“ или неопределени. Клаузата в абдуктивната логическа програма има следната формула:

H :- B₁, …, B_n, A₁, …, A_n.

където H е атомна формула, която не е абдуктивна, всички B_i са литерали, чиито предикати също не са абдуктивни, а A_i са предикати, чиито литерали са абдуктивни. Абдуктивните предикати могат да бъдат ограничени от ограничения за интегритет, които могат да имат следният вид:

false :- B₁, …, B_n.

където Bi са произволни литерали (дефинирани или индуцирани и атомни или отрицателни). Например:

canfly(X) :- bird(X), normal(X).
false :- normal(X), wounded(X).
bird(john).
bird(mary).
wounded(john).

където предиката принципно е абдуктивен.

Решаването на проблеми се постига чрез извличане на хипотези, изразени по отношение на абдуктивните предикати. Тези проблеми могат да бъдат или наблюдения, които трябва да бъдат обяснени (както в класическата абдукция) или задачи, които да бъдат решени (както е в обикновената логика на програмиране). Например хипотезата normal(mary) обяснява наблюдението canfly(mary). Освен това, същата хипотеза предполага, че единственото решение X = mary намира нещо, което може да лети:

:- canfly(X).

Абдуктивното логическо програмиране е било използвано за диагностики, за откриване на грешки, планиране, обработка на език и машинно обучение. Също така е използвано, за да интерпретира как отрицанието като провал е част от абдукцията.

Металогично програмиране

Тъй като математическа логика има традиция за разграничаване на обектен език и метаезик, логическото програмиране също позволява програмиране на мета ниво. Най-простата металогическа програма е така наречената „vanilla“ мета-интерпретатор:

solve(true).
solve((A,B)):- solve(A),solve(B).
solve(A):- clause(A,B),solve(B).

където вярно представлява празена връзка. (A,B) означава, че има клауза за обектно-ниво на форма A:-B. Металогичното програмиране позволява на представители от обектното и от мета нивото да бъдат комбинирани, като на естествен език. Той може да бъде използван за осъществяване на всяка логика, която следва заключителните правила.

Ограничително логическо програмиране

Ограничително логическо програмиране съчетава Horn логика на програмиране с решенията за ограничение. Тя разширява Horn клаузите, като позволява на някои предикати, декларирани като ограничаващи предикати, да се появят като литерали в тялото на клаузи. Програмата с ограничителна логика е набор от клаузи във формат:

H :- C₁, …, C_n B₁, …, B_n.

където H и всички B_i са атомни формули, а C_i са ограниченията. Декларативно, такива клаузи се четат като обикновени логически импликации:

H if C₁ and … and C_n and B₁ and … and B_n.

Въпреки това, като се има предвид, предикатите в главите на клаузи са определени от програмата с ограничителна логика, предикатите в ограниченията са предварително определени от някои домейн-специфицирана моделно-теоретична структура или теория. Процедурно подцелите, чиито предикати са определени от програмата, са решени чрез цел намаляване, както в обикновеното логическо програмиране, но ограниченията са проверени за удовлетворяване на специфично ограничение от домейна, с което се прилага семантиката на предикатите. Първоначалният проблем е решен като го сведе до задоволителна връзка между ограниченията.

Следната програмата с ограничителна логика представлява измислена времева база данни от историята на Джон като учител :

teaches(john, hardware, T) :- 1990 ≤ T, T < 1999.

teaches(john, software, T) :- 1999 ≤ T, T < 2005.

teaches(john, logic, T) :- 2005 ≤ T, T ≤ 2012.

rank(john, instructor, T) :- 1990 ≤ T, T < 2010.

rank(john, professor, T) :- 2010 ≤ T, T < 2014.

Тук ≤ и < са ограничителни предикати с тяхнота обичайна семантика. Следната заявки в базата данни има за цел да разберете, кога Джон едновременно учи логика и е професор:

:- teaches(john, logic, T), rank(john, professor, T).

Решението е: 2010 ≤ T, T ≤ 2012.

Ограничително логическо програмиране е използвано за решаване на проблеми в сфери като гражданско строителство, машиностроене, проверка на цифрова схеми, автоматизирано изготвяне на разписание, контрол на въздушното движение и финанси. Тя е тясно свързана с абдуктивното логическо програмиране.

Конкурентно логическо програмиране

Конкурентното логическо програмиране интегрира концепции от логическото програмиране в конкурентно програмиране. Неговото развитие е дало голям тласък през 1980 г. от избора на езика за програмиране на Japanese Fifth Generation Project (FGCS). Програмата с конкурираща логика е набор от пазените Horn clauses на формата :

H :- G₁, …, G_n | B₁, …, B_n.

Съединението G₁, …, G_n се нарича гард на клаузата, а | е операторът. Декларативно, пазената Horn клауза се чете като обикновена логическа импликация:

H if G₁ and … and G_n and B₁ and … and B_n.

Въпреки това, процедурно, когато има няколко клаузи, чиито начала H съвпадат с дадена цел, тогава всички клаузи се изпълняват паралелно, проверявайки дали тяхната охрана G₁, …, G_n задържа. Ако охраната на повече от една клауза задържи, се извършва избор се от една от клаузите, и изпълнение продължава с подцели B₁, …, B_n на избраната клауза. Тези подцели могат да се извършат и паралелно. По този начин конкурентното логическо програмиране прилага форма на „не ми пука недетерминизъм“, а не „Не знам недетерминизъм“

Например следната програма с конкурентна логика определя предикат shuffle(Left, Right, Merge), който може да се използва, за да разбъркате два списъка Left и Right, комбинирайки ги в един списък Merge, който запазва подредбата на двата списъка Left and Right:

 shuffle([], [], []).
 shuffle(Left, Right, Merge) :-
      Left = [First | Rest] | 
      Merge = [First | ShortMerge],
      shuffle(Rest, Right, ShortMerge).
 shuffle(Left, Right, Merge) :-
      Right = [First | Rest] |
      Merge = [First | ShortMerge],
      shuffle(Left, Rest, ShortMerge).

Тук, [] представлява празен списък, а [Head | Tail] представлява списък с първия елемент Head последван от списък Tail. Програмата може да се използва, например за да разбъркате списъците [ace, queen, king] и [1, 4, 2], като се позовава на клаузата за цел:

 shuffle([ace, queen, king], [1, 4, 2], Merge).

Програмата ще генерира недетерминистично единично решение – например Merge = [ace, queen, 1, king, 4, 2].

Може да се каже, че конкурентното логическо програмиране се основава на предаването на съобщения и следователно е предмет на същата неопределеност като други конкурентни системи за предаване на съобщения, също като Actors (виж Indeterminacy in concurrent computation). Carl Hewitt твърди, че конкуриращо логическо програмиране не се основава на логиката затова, че изчислителни стъпки не могат да бъдат логически изведени.

Въпреки това, в конкурентното логическо програмиране всеки резултат на изчисление е завършващо логично следствие на програмата, както и всеки частичен резултат на частично изчисление е логично следствие на програмата и остатъчната цел (процес на мрежата). Следователно, неопределеността на изчисления означава, че не всички логически последици на програмата могат да бъдат изведени.

Конкурентно условно логическо програмиране

Конкурентно условно логическо програмиране съчетава едновременно конкурентно логическо програмиране и условно логическо програмиране, използвайки условия за контролиране на конкурентността. Една клауза може да съдържа условен израз, който представлява множество от условия, които могат да блокират изпълнението на клаузата. Когато условните изрази на няколко клаузи са изпълнени, конкурентното условно логическо програмиране решава коя от клаузите да изпълни.

Индуктивно логическо програмиране

Индуктивното логическо програмиране е подполе на машинното самообучение, което използва логическото програмиране за представяне на примери, знания и хипотези. Скорошни дейности в тази област довеждат до формирането на нови области: статистическо релационно самообучение и вероятностно индуктивно логическо програмиране.

Логическо програмиране от по-висок ред

Няколко изследователи разширяват логическото програмиране с функции за програмиране от по-висок ред, заимствани от логиката от по-висок ред, като например предикатните променливи. Такива езици са например разширенията на Пролог: HiLog и λProlog.

Линейно логическо програмиране

Логическото програмиране с линейна логика е довело до подобрение в дизайна на логическите езици за програмиране, които са значително по-изразителни в сравнение с тези базирани на класическата логика. Рог клаузните програми могат само да изобразят промяна в състоянието, чрез промяна в аргументите на предикатите. В линейното логическо програмиране, може да се прави промяна на състоянието със заобикаляща линейна логика. Някои предишни дизайни на логическите езици за програмиране са базирани на линейната логика.

Обектно-ориентирано логическо програмиране

F-logic добавя към логическото програмиране обекти и рамков синтаксис. Редица системи са базирани на F-logic, включително Flora-2, FLORID, и високо мащабна търговска система Ontobroker.

Logtalk добавя към програмния език Пролог поддръжка на обекти, протоколи и други концепции на ООП. Той е лесно преносим и поддържа повечето стандартни съвместими Пролог системи.

Трансакционно логическо програмиране

Трансакционната логика е разширение на логическото програмиране с теория на официално-модифицирани актуализации. Тя има както модело-теоретична семантика така и процесуална такава. Нейната имплементацията на подмножеството и е налична в системата на Flora-2. Други прототипи също са на разположение.

Източници

Тази страница частично или изцяло представлява превод на страницата Logic_programming в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​

Външни препратки

• Библиографии на английски език за логическо програмиране Архив на оригинала от 2008-12-04 в Wayback Machine.
• Prolog Development Center Архив на оригинала от 2016-04-08 в Wayback Machine.
• Association for Logic Programming (ALP)