|
Логическото програмиране е парадигма в програмирането, която е разработена през 70-те години, за решаването на задачи, свързани с изкуствения интелект. Вместо да се гледа на компютърната програма като описание стъпка по стъпка на един алгоритъм, програмата е замислена като логична теория, а на извикващата процедура се гледа като на теоремата, на която трябва да се установи истината. По този начин, изпълнението на програмата означава търсене на доказателство. В традиционните (императивни) езици за програмиране, програмата е процедурна спецификация как проблем трябва да бъде решен, а при езиците за логическо програмиране, програмата дава на компютъра описание на проблема, като използва редица факти и правила, а след това го кара да намери всички възможни решения.
Логическото програмиране има своите корени в [https://en.wikipedia.org/wiki/Lambda_calculus ламбда смятането], разработено от [[Алонсо Чърч]] през 1930 г. Въпреки това, първото предложение за използване на логика за представяне на компютърни програми е направено от Кордел Грийн (1969 г.) в [[Станфордски университет|Станфордския Университет]].<ref>Cordell Green. '''Application of Theorem Proving to Problem Solving''' IJCAI 1969.</ref> По същото време Фостър и Елкок представят [[:en:Absys|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>
Една от най-известните системи, основана на процедурно представяне и използване на знания, е езикът [[:en:Planner_(programming_language)|Planner]], разработен в [[Масачузетски технологичен институт|MIT]] от [[:en:Carl_Hewitt|Карл Хюит]] (1969 г.)<ref>Carl Hewitt. '''Planner: A Language for Proving Theorems in Robots''' IJCAI 1969.</ref>. Той е предназначен за представяне и контрол на информация и дава възможност да се разглеждат не всички възможни, а само най-вероятните връзки. Друго популярно приложение е системата [[:en:SHRDLU|SHRDLU]] на [[:en:Terry_Winograd|Тери Виноград]] [[Станфордски университет|(Станфордския Университет]] SRI International).
Създаден като алтернатива на процедурното представяне е езикът [[Пролог (език за програмиране)|PROLOG]] от [[:en:Alain_Colmerauer|Алан Колмерю]] и [[Филип Ръсел]] в [[:en:Aix-Marseille_University|университета в Екс-Марсилия]], Франция, през 1973 година. PROLOG е доразвит от логика [[Робърт Ковалски]], който е член на групата AI в [[Единбургски университет|университета в Единбург]]<ref>Kowalski, R. A. (1988). [http://www.doc.ic.ac.uk/~rak/papers/the%20early%20years.pdf "The early years of logic programming"]</ref><ref>''Communications of the ACM'' '''31''': 38. [[Digital object identifier|doi]]:[http://dl.acm.org/citation.cfm?doid=35043.35046 10.1145/35043.35046]</ref>.
Изследователи от [[:en:Tokyo_Institute_of_Technology|Института за New Generation Computer Technology]] в Токио са използвали [[Пролог (език за програмиране)|PROLOG]] като основа за сложни логически програмни езици, известни като [[:en:Fifth_generation_computer|езици пето поколение]].
Друга скорошна работа включва разработването на езици, разглеждащи времево зависими данни, като например „сметката е платена вчера“. Тези езици са базирани на [[:en:Temporal_logic|темпоралната логика]], която позволява твърденията да бъдат разположени в потока на времето.<ref>[http://www.britannica.com/technology/artificial-intelligence-programming-language Artificial intelligence programming language]
Written by: [http://www.britannica.com/contributor/BJ-Copeland/4511 B.J. Copeland]
</ref>
[[:en:Association_for_Logic_Programming|Aсоциацията за логическо програмиране]] е основана за насърчаване на логическото програмиране през 1986 г.
== Концепции ==
=== Логика и контрол ===
:''Основна статия: [[:en:Declarative_programming|Declarative programming]]''
Логическото програмиране може да бъде разглеждано като контролиран извод. Важна концепция в логическото програмиране е разделянето на програмите на техните логически и контролни компоненти. С езици за чисто логическо програмиране, логическият компонент сам установява решенията. Контролният компонент може да се променя, за да осигури алтернативни начини за изпълнение на логическа програма. Тази идея е пресъздадена от мотото
=== Решаване на проблем ===
В опростения случай, в който логическа програма и най-важната основна цел не съдържат променливи, основният довод изгражда [[:en:And–or_tree|и-или дърво]], което представлява обхвата на търсене за разрешаване на целта. Най-важната цел е коренът на дървото. Като се вземе предвид всяко разклонение и всяка точка, чието начало съответства на разклонението, съществуват серия от подразклонения, кореспондиращи с подцелите. Тези подразклонения са групирани заедно с „и“. Алтернативните серии от подразклонения, кореспондиращи с алтернативни варианти за решаване на разклонението, са групирани заедно от „или“.
Всяка стратегия за търсене може да бъде използвана за търсене на обхвата. Пролог използва последователна, „последен-влязъл-последен-излязъл“, проследяваща назад стратегия, в която се разглеждат само една алтернатива и една подцел. Други стратегии за търсене, като например паралелното търсене, смисленото проследяване назад или най-доброто първо търсене за намиране на оптимално решение, също са възможни.
В най-общият случай, когато подцелите имат общи променливи, могат да бъдат използвани други стратегии, като например избиране на подцел, която е най-обща или е достатъчно спешна, така че е необходима само една процедура. Такива стратегии се използват, например в [[:en:Concurrent_logic_programming|конкурентното логическо програмиране]].
=== Отрицание като провал ===
:''Основна статия: [[:en:Negation_as_failure|Отрицание като провал]]''
За повечето практически приложения, както и за приложения, които изискват не-еднообразни разсъждения в изкуствения интелект, логическите програми, които използват Хорнови клаузи, трябва да бъдат разширени до нормални логически програми с отрицателни условия. Една ''клауза'' в нормална логическа програма има формата:
и се чете декларативно като логическа импликация:
:<samp> H if A<sub>1</sub> and … and A<sub>n</sub> and not B<sub>1</sub> and … and not B<sub>n</sub>.</samp>
където <samp>H</samp> и всички <samp>A<sub>i</sub></samp> и <samp>B<sub>i</sub></samp> са атомни формули. Отрицанието в негативните литерали <samp>not B<sub>i</sub></samp> обикновено се отнася като " [[:en:Negation_as_failure|отрицание като провал]] ", защото в повечето приложения, в които се имплементира, отрицателното условие <samp>not B<sub>i</sub></samp> демонстрира, че положителното условие <samp>B<sub>i</sub></samp> не успява да се задържи. Например:
<source lang="prolog">
canfly(X) :- bird(X), not abnormal(X).
Има две възможни решения, които решават първата подцел <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“, която, когато се прилага към израз, връща стойността истина ако (и само ако) оценката на израза не успее. Подобен оператор обикновено е вграден и в съвременните [[:en:Prolog|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] показа, че при определени естествени условия, то е вярно (а понякога и пълно) изпълнение на класическото отрицание по отношение на целостта на програмата. Целостта се отнася приблизително до настройване на всички програмни клаузи с едни и същи предикати от лявата страна:
=== Представяне на знания ===
Фактът, че клаузите на Хорн могат да дадат процедурна интерпретация и обратното, процедурите за редуциране на целите могат да бъдат разбрани като клаузите на Хорн + обратния довод, означава че логическите програми комбинират декларативни и процедурни изобразявания на [[:en:Knowledge_representation_and_reasoning|познание ]]. Обхващането на [[ :en:Negation_as_failure|отрицанието като провал]], означава че логическото програмиране е вид [[ :en:Non-monotonic_logic|немонотонна логика]].<p>Въпреки нейната опростеност в сравнение с класическата логика, тази комбинация от клаузи на Хорн и отрицание като провал, се е доказала като учудващо изразителна. Комбинацията е натурален език за изразяване на здравомислещи закони за причина и резултат, както в [[ :en:Situation_calculus|ситуационното смятане]] и [[ :en:Event_calculus|събитийно смятане]].</p><p>В най-общият случай, когато подцели имат общи променливи, могат да бъдат използвани други стратегии, като например избиране на подцел, която е най-обща или е достатъчно спешна, така че е необходима само една процедура. Такива стратегии се използват, например в [[ :en:Concurrent_logic_programming|конкурентното логическо програмиране]].</p>
== Езици за логическо програмиране ==
=== Пролог ===
Програмният език [[Пролог (език за програмиране)|Пролог]] е създаден от [[:en:Alain_Colmerauer|Ален Колмерое]] през 1972 година. Той е резултат на съвместната работа между Колмерое и [[Робърт Ковалски]] в [[Единбург]]. Колмерое е работил върху [https://en.wikipedia.org/wiki/Natural_language_understanding естественият език на разбиране], използвайки логика за да представи семантиката и използвайки резолюция за съответните въпроси и отговори. През лятото на 1971 година, Колмерое и Ковалски открили, че клаузалната форма на логика може да се използва за представяне на официални граматики, а теоремата за резолюция доказала, че биха могли да бъдат използвани и за граматичен разбор. Те установили как някои теореми се доказали, като хипер-резолюцията и естественият език на разбиране [https://en.wikipedia.org/wiki/SLD_resolution SL-резолюцията] през 1971 година. Процедурното тълкуване на Ковалски и LUSH, са описани в бележка от 1973 година и са публикувани година по-късно.
През лятото и есента на 1972 година двамата отново работили заедно и разработили процесуално тълкуване на последиците. Чрез декларативно-процесуалната интерпретация, по-късно образували нотацията на програмният език Пролог,
=== Металогично програмиране ===
Тъй като математическа логика има традиция за разграничаване на [[:en:Object_language|обектен език]] и метаезик, логическото програмиране също позволява [[Metalevel programming|програмиране на мета ниво]]. Най-простата металогическа програма е така наречената „[[:en:Vanilla_(computing)|vanilla]]“„vanilla“ мета-интерпретатор:
<source lang="prolog">
solve(true).
=== Ограничително логическо програмиране ===
''Основна статия: [[:en:Constraint_logic_programming|Ограничително логическо програмиране]]''
[[:en:Constraint_logic_programming|Ограничително логическо програмиране]] съчетава Horn логика на програмиране с [[:en:Constraint_solving|решенията за ограничение]]. Тя разширява Horn клаузите, като позволява на някои предикати, декларирани като ограничаващи предикати, да се появят като литерали в тялото на клаузи. Програмата с ограничителна логика е набор от клаузи във формат:
:<samp>H :- C<sub>1</sub>, …, C<sub>n</sub> B<sub>1</sub>, …, B<sub>n</sub>.</samp>
където <samp>H</samp> и всички <samp>B<sub>i</sub></samp> са атомни формули, а <samp>C<sub>i</sub></samp> са ограниченията. Декларативно, такива клаузи се четат като обикновени логически импликации:
Решението е: <samp>2010 ≤ T, T ≤ 2012</samp>.
Ограничително логическо програмиране е използвано за решаване на проблеми в сфери като [[:en:Civil_engineering|гражданско строителство]], [[:en:Mechanical_engineering|машиностроене]], проверка [[:en:Digital_circuit|на цифрова схеми]], [[:en:Automated_timetabling|автоматизирано изготвяне на разписание]], [[:en:Air_traffic_control|контрол на въздушното движение]] и финанси. Тя е тясно свързана с [[:en:Abductive_logic_programming|абдуктивното логическо програмиране]].
=== Конкурентно логическо програмиране ===
''Основна статия: [//en.wikipedia.org/wiki/Concurrent_programming Конкуриращото логическо програмиране]''
Конкурентното логическо програмиране интегрира концепции от логическото програмиране в [//en.wikipedia.org/wiki/Concurrent_programming конкурентно програмиране]. Неговото развитие е дало голям тласък през 1980 г. от избора на езика за програмиране на [[:en:Fifth_generation_computer|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>.Програмата с конкурираща логика е набор от пазените [[:en:Horn_clauses|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> се нарича [[:en:Guard_(computing)|гард]] на клаузата, а <samp>|</samp> е операторът. Декларативно, пазената Horn клауза се чете като обикновена логическа импликация:
:<samp>H if G<sub>1</sub> and … and G<sub>n</sub> and B<sub>1</sub> and … and B<sub>n</sub>.</samp>
Въпреки това, процедурно, когато има няколко клаузи, чиито начала <code>H</code> съвпадат с дадена цел, тогава всички клаузи се изпълняват паралелно, проверявайки дали тяхната охрана <samp>G<sub>1</sub>, …, G<sub>n</sub></samp> задържа. Ако охраната на повече от една клауза задържи, се извършва избор се от една от клаузите, и изпълнение продължава с подцели <samp>B<sub>1</sub>, …, B<sub>n</sub></samp> на избраната клауза. Тези подцели могат да се извършат и паралелно. По този начин конкурентното логическо програмиране прилага форма на „не ми пука недетерминизъм“, а не „Не знам недетерминизъм“
Програмата ще генерира недетерминистично единично решение – например <samp>Merge = [ace, queen, 1, king, 4, 2]</samp>.
Може да се каже, че конкурентното логическо програмиране се основава на предаването на съобщения и следователно е предмет на същата неопределеност като други конкурентни системи за предаване на съобщения, също като [[:en:Actor_model|Actors]] (виж [[:en:Indeterminacy_in_concurrent_computation|Indeterminacy in concurrent computation]]). Carl Hewitt твърди, че конкуриращо логическо програмиране не се основава на логиката затова, че изчислителни стъпки не могат да бъдат логически изведени.
Въпреки това, в конкурентното логическо програмиране всеки резултат на изчисление е завършващо логично следствие на програмата, както и всеки частичен резултат на частично изчисление е логично следствие на програмата и остатъчната цел (процес на мрежата). Следователно, неопределеността на изчисления означава, че не всички логически последици на програмата могат да бъдат изведени.
=== Конкурентно условно логическо програмиране ===
''Основна статия: [//en.wikipedia.org/wiki/Concurrent_constraint_logic_programming [Конкурентно условно логическо програмиране]]''<br />
[//en.wikipedia.org/wiki/Concurrent_constraint_logic_programming Конкурентното[Конкурентно условно логическо програмиране]] съчетава едновременно конкурентно логическо програмиране и условно логическо програмиране, използвайки условия за контролиране на конкурентността. Една клауза може да съдържа условен израз, който представлява множество от условия, които могат да блокират изпълнението на клаузата. Когато условните изрази на няколко клаузи са изпълнени, конкурентното условно логическо програмиране решава коя от клаузите да изпълни.
=== Индуктивно логическо програмиране ===
''Основна статия: [//en.wikipedia.org/wiki/Inductive_logic_programming [Индуктивно логическо програмиране]]''<br />
Индуктивното логическо програмиране е подполе на машинното самообучение, което използва логическото програмиране за представяне на примери, знания и хипотези. Скорошни дейности в тази област довеждат до формирането на нови области: [//en.wikipedia.org/wiki/Statistical_relational_learning [статистическо релационно самообучение]] и [[вероятностно индуктивно логическо програмиране]].
=== Логическо програмиране от по-висок ред ===
Няколко изследователи разширяват логическото програмиране с функции за [//en.wikipedia.org/wiki/Higher-order_programming [програмиране от по-висок ред]], взаимствани от [//en.wikipedia.org/wiki/Higher-order_logic [логиката от по-висок ред]], като например предикатните променливи. Такива езици са например разширенията на Пролог: [//en.wikipedia.org/wiki/HiLog [HiLog]] и [//en.wikipedia.org/wiki/%CE%9BProlog [λProlog]].
=== Линейно логическо програмиране ===
Логическото програмиране с [[:en:Linear_logic|линейна логика]] е довело до подобрение в дизайна на логическите езици за програмиране, които са значително по-изразителни в сравнение с тези базирани на класическата логика. Рог клаузните програми могат само да изобразят промяна в състоянието, чрез промяна в аргументите на предикатите. В линейното логическо програмиране, може да се прави промяна на състоянието със заобикаляща линейна логика. Някои предишни дизайни на логическите езици за програмиране са базирани на линейната логика.
=== Обектно-ориентирано логическо програмиране ===
[[:en:F-logic|F-logic]] добавя към логическото програмиране обекти и рамков синтаксис. Редица системи са базирани на F-logic, включително [[:en:Flora-2|Flora-2]], [http://dbis.informatik.uni-freiburg.de/index.php?project=Florid [FLORID]],и високо мащабна търговска система [http://www.semafora-systems.com/en/products/ontobroker/ [Ontobroker]].
[[:en:Logtalk|Logtalk]] добавя към програмният език Пролог поддръжка на обекти, протоколи и други концепции на ООП. Той е лесно преносим и поддържа повечето стандартни съвместими Пролог системи.
=== Трансакционно логическо програмиране ===
== Вижте също: ==
*[[:en:Boolean_satisfiability_problem|Boolean satisfiability problem]]
*[[:en:Constraint_logic_programming|Constraint logic programming]]
*[[:en:Datalog|Datalog]]<li>[[:en:Functional_programming|Functional programming]]</li>*[[:en:Inductive_logic_programming|Inductive logic programming]]<li>[[:en:Fuzzy_logic|Fuzzy logic]]</li><li>[[:en:Logic_in_computer_science|Logic in computer science]] (includes [[:en:Formal_methods|Formal methods]])</li><li>[[:en:Category:Logic_programming_languages|Logic programming languages]]</li><li>[[:en:Programming_paradigm|Programming paradigm]]</li><li>[[:en:R++|R++]]
</li><li>[[:en:Reasoning_system|Reasoning system]]</li><li>[[:en:Logic_programming|Relational programming]]</li><li>[[:en:Satisfiability|Satisfiability]]</li>
== Източници: ==
<li>[http://www.logicprogramming.org/ Association for Logic Programming (ALP)]</li>
<li>[http://www.mpprogramming.com/Cpp/ Logic programming in C++ with Castor]</li>
<li>Logic programming in [[:en:Oz_(programming_language)|Oz]]</li>
<li>[http://www.pdc.com/index-dk.html Prolog Development Center] <li>[http://docs.racket-lang.org/racklog/ Racklog: Logic Programming in Racket]</li>
| 