Уикипедия

Логическо програмиране: Разлика между версии

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
м без двоеточие в заглавие на раздел
Редакция без резюме
Ред 1:
{{обработка|премахване на вътр препратки към англ У}}
'''Логическото програмиране''' е [[парадигма за програмиране]], която се основава на принципите на [[формална логика|формалната логика]] и [[предикатно смятане|предикатното смятане]].
 
Други парадигми за програмиране са например [[Императивно програмиране|императивното програмиране]] и [[Функционално програмиране|функционалното програмиране]].
 
Програмите, написани на език за логическо програмиране, представляват поредица от правила и факти. Основни езици за логическо програмиране са [[Пролог (език за програмиране)|Prolog]], [https://en.wikipedia.org/wiki/Answer_set_programming [ASP]] и [https://en.wikipedia.org/wiki/Datalog [Datalog]].
 
Правилата са написани във формата на клаузи:
Line 15 ⟶ 14:
Фактите могат да се третират като правила без тяло, т.е. безусловни правила. Те имат следната форма:
:<samp>H.</samp>
В най-простия случай, когато <samp>H, B<sub>1</sub>, ..., B<sub>n</sub></samp> са атомарни формули, тези клаузи се наричат [https://en.wikipedia.org/wiki/Horn_clause [клаузи на Хорн]]. Съществуват редица вариации на този случай, например, когато тялото е съставено от отрицанията на атомарни формули (отрицателни Хорнови клаузи).
<br>
В ASP и Datalog, програмите се характеризират само с [https://en.wikipedia.org/wiki/Declarative_programming [декларативно]] четене и тяхното изпълнение се извършва с помощта на процедури за „доказателство“, чието поведение не е под контрола на програмиста. За разлика от това, в Пролог-базираните езици, програмите се характеризират с т.н. процедурна интерпретация:
:<samp>за да се реши H, трябва да се реши B<sub>1</sub> и ... и B<sub>n</sub>.</samp>
Например, нека имаме следната клауза:
:<samp>fallible(X) :- human(X).</samp>
базирана на пример, използван от [https://en.wikipedia.org/wiki/Terry_Winograd [Terry Winograd]]<ref>{{cite journal|author= T. Winograd (1972).|title= Understanding natural language |journal= Cognitive Psychology |volume=3| issue = 1 – 191|doi=10.1016/0010 – 0285(72)90002 – 3}}</ref>, за да илюстрира програмния език [https://en.wikipedia.org/wiki/Planner_(programming_language) [Planner]]. Като клауза в една логическа програма, може да се използва, както като процедура, която проверява дали X е склонен да греши, като се провери дали X е човек, така и като процедура за намирането на човек X, който е склонен на греши, чрез намирането на X, който да е човек. Дори фактите имат процедурна интерпретация. Например, клаузата:
:<samp>human(socrates).</samp>
може да се изпозва едновременно като процедура, която показва, че socrates е човек, и като процедура, която намира X, който е човек, чрез определянето на socrates за човек.
 
Декларативното четене при програмите, написани на логически език за програмиране, може да се използва за проверка на коректността на програмата. Също така, може да се използват техники за [https://en.wikipedia.org/wiki/Program_transformation [програмно трансформиране]] на една логически-базирана програма към друга такава, еквивалентна на нея, но по-ефективна. В Пролог-базираните логически езици може да се иползва механизмът на изпълнение на програмата за подобряване на ефективността.
 
== История ==
Логическото програмиране е парадигма в програмирането, която е разработена през 70-те години, за решаването на задачи, свързани с изкуствения интелект. Вместо да се гледа на компютърната програма като описание стъпка по стъпка на един алгоритъм, програмата е замислена като логична теория, а на извикващата процедура се гледа като на теоремата, на която трябва да се установи истината. По този начин, изпълнението на програмата означава търсене на доказателство. В традиционните (императивни) езици за програмиране, програмата е процедурна спецификация как проблем трябва да бъде решен, а при езиците за логическо програмиране, програмата дава на компютъра описание на проблема, като използва редица факти и правила, а след това го кара да намери всички възможни решения.
 
Логическото програмиране има своите корени в [https://en.wikipedia.org/wiki/Lambda_calculus [ламбда смятането]], разработено от [[Алонсо Чърч]] през 1930 г. Въпреки това, първото предложение за използване на логика за представяне на компютърни програми е направено от Кордел Грийн (1969 г.) в [[Станфордски университет|Станфордския Университет]].<ref>Cordell Green. '''Application of Theorem Proving to Problem Solving''' IJCAI 1969.</ref> По същото време Фостър и Елкок представят [[Absys]], първия език за логическо програмиране.<ref>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</ref>
 
Една от най-известните системи, основана на процедурно представяне и използване на знания, е езикът [[Planner]], разработен в [[Масачузетски технологичен институт|MIT]] от [[Карл Хюит]] (1969 г.)<ref>Carl Hewitt. '''Planner: A Language for Proving Theorems in Robots''' IJCAI 1969.</ref>. Той е предназначен за представяне и контрол на информация и дава възможност да се разглеждат не всички възможни, а само най-вероятните връзки. Друго популярно приложение е системата [[SHRDLU]] на [[Тери Виноград]] [[Станфордски университет|(Станфордския Университет]] SRI International).
Line 81 ⟶ 80:
Има две възможни решения, които решават първата подцел <samp>bird(X)</samp>, а именно <samp>X = john</samp> и <samp>X = mary</samp>. Втората подцел <samp>not abnormal(john)</samp> от първото възможно решение се проваля, тъй като <samp>wounded(john)</samp> успява и поради това <samp>abnormal(john)</samp> успява. Въпреки това втората подцел <samp>not abnormal(mary)</samp> на второто възможно решение успява, тъй като <samp>wounded(mary)</samp> се проваля, и затова <samp>abnormal(mary)</samp> се проваля. Ето защо, <samp>X = mary</samp> е единственото решение на първоначално поставената цел.
 
Micro-Planner е имал конструкция наречена „thnot“, която, когато се прилага към израз, връща стойността истина ако (и само ако) оценката на израза не успее. Подобен оператор обикновено е вграден и в съвременните [[Prolog]] реализации. Обикновено се изписва като <code>not( ''Goal'' )</code> или <code>\+ ''Goal''</code> , където<code>''Goal''</code> е някаква цел (твърдение), което да бъде доказано от програмата. Този оператор се различава от отрицанието в първия ред логика: отрицание като <code>\+ X == 1</code> се проваля, когато променливата <code>X</code> е свързана към атома <code>1</code> , но тя успява във всички останали случаи, включително когато <code>X</code> е неконсолидиран. Това прави разсъждението Prolog е [https://en.wikipedia.org/wiki/Non-monotonic_logic не-еднозначно[нееднозначно]] : <code>X = 1, \+ X == 1</code> винаги се проваля, докато <code>\+ X == 1, X = 1</code> може да успее, свързвайки <code>X</code> към <code>1</code> , в зависимост от това дали <code>X</code> първоначално е обвързан (имайте предвид, че стандартния Prolog изпълнява твърдения от ляво на дясно).
 
Логическият статус на отрицанието като провал е неразрешено, докато Кийт Кларк [1978] показа, че при определени естествени условия, то е вярно (а понякога и пълно) изпълнение на класическото отрицание по отношение на целостта на програмата. Целостта се отнася приблизително до настройване на всички програмни клаузи с едни и същи предикати от лявата страна:
Line 98 ⟶ 97:
:<samp> not john = mary.</samp>
:<samp> not mary = john.</samp>
Представата за завършеност е тясно свързана с [https://en.wikipedia.org/wiki/Circumscription_(logic) [определението на МакКартиМаккарти]] за разсъждение по подразбиране и, че по презумпция едно твърдение е вярно, ако за него е известно, че е вярно – [https://en.wikipedia.org/wiki/Closed-world_assumption [допускането на затворен свят]].
 
Като алтернатива на семантиката на завършване, отрицанието като провал може да се тълкува и познавателно, както в [https://en.wikipedia.org/wiki/Stable_model_semantics [семантиките на стабилен модел]] на [https://en.wikipedia.org/wiki/Answer_set_programming [програмирането с редица отговори]]. В тази интерпретация <samp>not(B<sub>i</sub>)</samp> означава буквално, че <samp>B<sub>i</sub></samp> не е известно. Познавателното тълкуване има предимството, че може да се комбинира с класическото отрицание, както в "разширеното логическо програмиране", да се формализират фрази като „противоположното не може да се докаже“, където „противоположното“ е класическо отрицание, и „не може да се докаже“ е познавателна интерпретация на отрицанието като провал.
 
=== Представяне на знания ===
Line 107 ⟶ 106:
== Езици за логическо програмиране ==
=== Пролог ===
Програмният език [[Пролог (език за програмиране)|Пролог]] е създаден от [[Ален Колмерое]] през 1972 година. Той е резултат на съвместната работа между Колмерое и [[Робърт Ковалски]] в [[Единбург]]. Колмерое е работил върху [https://en.wikipedia.org/wiki/Natural_language_understanding [естественият език на разбиране]], използвайки логика за да представи семантиката и използвайки резолюция за съответните въпроси и отговори. През лятото на 1971 година, Колмерое и Ковалски открили, че клаузалната форма на логика може да се използва за представяне на официални граматики, а теоремата за резолюция доказала, че биха могли да бъдат използвани и за граматичен разбор. Те установили как някои теореми се доказали, като хипер-резолюцията и естественият език на разбиране [https://en.wikipedia.org/wiki/SLD_resolution [SL-резолюцията]] през 1971 година. Процедурното тълкуване на Ковалски и LUSH, са описани в бележка от 1973 година и са публикувани година по-късно.
 
През лятото и есента на 1972 година двамата отново работили заедно и разработили процесуално тълкуване на последиците. Чрез декларативно-процесуалната интерпретация, по-късно образували нотацията на програмният език Пролог,
 
:<samp>H :- B<sub>1</sub>, …..., B<sub>n</sub>.</samp>
 
която може да бъде четена и използвана, както декларативно така и процесуално.
 
Колмерое заедно с Филипе Роузел, използват двойното тълкуване, като основа на Пролог и така осъществяват неговото реализиране през късното лято на 1972 година. Първата Пролог програма написана през 1972 година и пусната в Марсилия, е била система за въпроси и отговори на френски език. Разработването на компилатора от Дейвид Уорън в Единбург през 1977 година дава голям тласък за развитието на Пролог като практически език за програмиране. Експериментите показали, че единбургският Пролог може да се конкурира по отношение скоростта на обработка с други символни езици за програмиране, като [https://en.wikipedia.org/wiki/Lisp_(programming_language) [Lisp]]. С това той оказал силно въздействие върху дефиницията за [https://en.wikipedia.org/wiki/International_Organization_for_Standardization [ISO]]на Пролога.
 
=== Абдуктивно логическо програмиране ===
[https://en.wikipedia.org/wiki/Abductive_logic_programming [Абдуктивното логическо програмиране]] е разширение на обикновеното логическо програмиране, което позволява някои предикати, декларирани като абдуктивни, да бъдат „отворени“ или неопределени. Клаузата в абдуктивната логическа програма има следната формула:
 
:<samp>H :- B<sub>1</sub>, …, B<sub>n</sub>, A<sub>1</sub>, …, A<sub>n</sub>.</samp>
Line 136 ⟶ 135:
където предиката принципно е абдуктивен.
 
Решаването на проблеми се постига чрез извличане на хипотези, изразени по отношение на абдуктивните предикати. Тези проблеми могат да бъдат или наблюдения, които трябва да бъдат обяснени (както в [https://en.wikipedia.org/wiki/Abductive_reasoning [класическата абдукция]]) или задачи, които да бъдат решени (както е в обикновената логика на програмиране). Например хипотезата <samp>normal(mary)</samp> обяснява наблюдението <samp>canfly(mary)</samp>. Освен това, същата хипотеза предполага, че единственото решение <samp>X = mary</samp> намира нещо, което може да лети:
<source lang="prolog">
:- canfly(X).
Line 173 ⟶ 172:
 
=== Конкурентно логическо програмиране ===
''Основна статия: [//en.wikipedia.org/wiki/Concurrent_programming [Конкуриращото логическо програмиране]]''
 
Конкурентното логическо програмиране интегрира концепции от логическото програмиране в [//en.wikipedia.org/wiki/Concurrent_programming [конкурентно програмиране]]. Неговото развитие е дало голям тласък през 1980 г. от избора на езика за програмиране на [[Japanese Fifth Generation Project (FGCS)]].<ref>{{cite journal|author= T. Winograd (1972).|title= Understanding natural language |journal= Cognitive Psychology |volume=3| issue = 1 – 191|doi=10.1016/0010 – 0285(72)90002 – 3}}</ref>.Програмата с конкурираща логика е набор от пазените [[Horn clauses]] на формата :
:<samp>H :- G<sub>1</sub>, …, G<sub>n</sub> | B<sub>1</sub>, …, B<sub>n</sub>.</samp>
Съединението <samp>G<sub>1</sub>, …, G<sub>n</sub></samp> се нарича [[гард]] на клаузата, а <samp>|</samp> е операторът. Декларативно, пазената Horn клауза се чете като обикновена логическа импликация:
Взето от „https://bg.wikipedia.org/wiki/Логическо_програмиране“.