Войти
Логическое программирование - это парадигма программирования, которая в основном на основе формальной логики. Любая программа, написанная на логическом языке программирования, представляет собой набор предложений в логической форме, выражающий факты и правила о некоторой проблемной области. Основные семейства языков логического программирования включают Prolog, программирование наборов ответов (ASP) и Datalog. На всех этих языках правила записываются в виде предложений:
и декларативно читаются как логические следствия:
Hназывается главой правила, а B1,..., Bnназывается телом. Факты - это правила, не имеющие тела и записанные в упрощенной форме:
В простейшем случае, когда все H, B1,..., Bnявляются атомарными формулами, эти предложения являются называются определенными предложениями или предложениями Хорна. Однако есть много расширений этого простого случая, наиболее важным из которых является случай, когда условия в теле предложения также могут быть отрицаниями атомарных формул. Языки логического программирования, которые включают это расширение, имеют возможности представления знаний немонотонной логики.
В ASP и Datalog логические программы имеют только декларативное чтение, и их выполнение выполняется средствами процедуры проверки или генератора моделей, поведение которых не предназначено для управления программистом. Однако в семействе языков Prolog логические программы также имеют процедурную интерпретацию как процедуры редукции цели:
. Рассмотрим следующий пункт в качестве примера:
на основе примера, который использовал Терри Виноград для иллюстрации языка программирования Планировщик. В качестве предложения в логической программе его можно использовать как в качестве процедуры для проверки того, Xподвержен ошибкам, проверяя, является ли Xчеловеком, и в качестве процедуры поиска X, который подвержен ошибкам, путем нахождения X, который является человеком. Даже факты имеют процедурную интерпретацию. Например, предложение:
может использоваться как как процедура, чтобы показать, что сократявляется человеком, так и как процедура для поиска X, то есть человекпутем "присвоения" socratesX.
Декларативное чтение логических программ может использоваться программистом для проверки их правильности. Кроме того, основанные на логике методы преобразования программ также могут использоваться для преобразования логических программ в логически эквивалентные программы, которые более эффективны. В семействе языков логического программирования Prolog программист может также использовать известное поведение механизма выполнения при решении задач для повышения эффективности программ.
Использование математической логики для представления и выполнения компьютерных программ также является особенностью лямбда-исчисления, разработанный Алонсо Черч в 1930-х годах. Однако первое предложение использовать клаузальную форму логики для представления компьютерных программ было сделано Корделлом Грином. При этом использовалась аксиоматизация подмножества LISP вместе с представлением отношения ввода-вывода, чтобы вычислить отношение путем моделирования выполнения программы в LISP. Absys Фостера и Элкока, с другой стороны, использовали комбинацию уравнений и лямбда-исчисления на языке программирования утверждений, который не налагает ограничений на порядок выполнения операций.
Логическое программирование в его нынешней форме можно проследить до дебатов в конце 1960-х - начале 1970-х годов о декларативном и процедурном представлении знаний в искусственном интеллекте. Сторонники декларативного представления особенно работали в Стэнфорде, связанном с Джоном Маккарти, Бертрамом Рафаэлем и Корделлом Грином, а также в Эдинбурге с Джон Алан Робинсон (академик из Сиракузского университета ), Пэт Хейс и Роберт Ковальски. Защитники процедурных представлений были в основном сосредоточены в MIT под руководством Марвина Мински и Сеймура Паперта.
. Хотя это было основано на логических методах доказательства, Planner, разработанный в Массачусетском технологическом институте, был первым языком, появившимся в рамках этой процедурной парадигмы. В планировщике реализован управляемый образцом вызов процедурных планов из целей (т. Е. Уменьшение цели или обратная цепочка ) и из утверждений (т. Е. прямая цепочка ). Наиболее влиятельной реализацией Planner была подмножество Planner, называемое Micro-Planner, реализованное Джерри Сассман, Юджином Чарняком и Терри Виноградом. Он использовался для реализации программы Винограда для понимания естественного языка SHRDLU, которая была знаковой для того времени. Чтобы справиться с очень ограниченными системами памяти в то время, Planner использовал структуру управления с возвратом, так что за один раз нужно было хранить только один возможный путь вычисления. Planner дал начало языкам программирования QA-4, Popler, Conniver, QLISP и параллельному языку Ether.
Хейс и Ковальски в Эдинбурге попытались согласовать основанный на логике декларативный подход к представлению знаний с процедурным подходом Planner.. Хейс (1973) разработал эквациональный язык Golux, в котором различные процедуры могут быть получены путем изменения поведения средства доказательства теорем. Ковальский, с другой стороны, разработал разрешение SLD, вариант SL-разрешения, и показал, как оно трактует последствия как процедуры снижения цели. Ковальский сотрудничал с Колмерауэром из Марселя, который развил эти идеи при разработке и реализации языка программирования Пролог.
Ассоциация логического программирования была основана для продвижения логического программирования. в 1986 году.
Пролог дал начало языкам программирования ALF, Fril, Gödel, Mercury, Oz, Ciao, Visual Prolog, XSB и λProlog, а также различные языки программирования параллельной логики, логика ограничений программирование языков и журнала данных.
Логическое программирование можно рассматривать как управляемую дедукцию. Важным понятием в логическом программировании является разделение программ на их логический компонент и компонент управления. В языках программирования чистой логики только логический компонент определяет производимые решения. Компонент управления может быть изменен для обеспечения альтернативных способов выполнения логической программы. Это понятие выражено слоганом
, где «Логика» представляет логическую программу, а «Управление» представляет различные стратегии доказательства теорем.
В упрощенном пропозициональном случае, когда логическая программа и атомарная цель верхнего уровня не содержат переменных, обратное рассуждение определяет и / или дерево, которое составляет пространство поиска для решения цели. Цель верхнего уровня - корень дерева. Для любого узла в дереве и любого предложения, чья голова соответствует этому узлу, существует набор дочерних узлов, соответствующих подцелям в теле предложения. Эти дочерние узлы сгруппированы знаком «и». Альтернативные наборы потомков, соответствующие альтернативным способам решения узла, сгруппированы вместе знаком «или».
Для поиска в этом пространстве можно использовать любую стратегию поиска. Prolog использует последовательную стратегию обратного отслеживания по принципу «последний пришел - первый ушел», в которой одновременно рассматривается только одна альтернатива и одна подцель. Также возможны другие стратегии поиска, такие как параллельный поиск, интеллектуальный поиск с возвратом или поиск по первому лучшему для поиска оптимального решения.
В более общем случае, когда подцели разделяют переменные, могут использоваться другие стратегии, такие как выбор подцели, которая является наиболее точным экземпляром или достаточно конкретизирована, так что применяется только одна процедура. Такие стратегии используются, например, в параллельном логическом программировании.
Для большинства практических приложений, а также для приложений, требующих немонотонных рассуждений в искусственном интеллекте, логика предложения Хорна программы необходимо расширить до программ с нормальной логикой с отрицательными условиями. Предложение в программе с нормальной логикой имеет вид:
и декларативно читается как логическое следствие:
, где Hи все Aiи Biявляются атомарными формулами. Отрицание в отрицательных литералах not B iобычно упоминается как «отрицание как отказ », потому что в большинстве реализаций отрицательное условие not B iпоказано как удерживать, показывая, что положительное условие Biне выполняется. Например:
canfly (X): - птица (X), а не аномалия (X). ненормальный (X): - раненый (X). птица (джон). птица (мэри). раненый (джон).
Учитывая цель найти что-то, что может летать:
: - canfly (X).
есть два возможных решения, которые решают первую подзадачу bird (X), а именно X = johnи X = mary. Вторая подцель не аномальный (john)первого возможного решения терпит неудачу, потому что раненый (john)преуспевает и, следовательно, ненормально (john)успешно. Однако вторая подцель не аномальный (mary)второго варианта решения завершается успешно, потому что wounded (mary)терпит неудачу и, следовательно, ненормально (mary)не выполняется. Следовательно, X = mary- единственное решение цели.
У Micro-Planner была конструкция под названием «thnot», которая при применении к выражению возвращает значение «истина», если (и только если) оценка выражения не выполняется. Эквивалентный оператор обычно встроен в современные реализации Prolog. Обычно это записывается как не (Цель)или \ + Цель, где Цель- это некая цель (предложение), которую должна доказать программа. Этот оператор отличается от отрицания в логике первого порядка: отрицание, такое как \ + X == 1, не выполняется, когда переменная Xбыла привязана к атому 1, но успешно во всех остальных случаях, в том числе когда Xне привязан. Это делает рассуждение Пролога немонотонным : X = 1, \ + X == 1всегда терпит неудачу, а \ + X == 1, X = 1может быть успешным, привязав Xк 1, в зависимости от того, был ли изначально привязан X(обратите внимание, что стандартный Prolog выполняет цели в порядке слева направо).
Логический статус отрицания как отказа не был решен до тех пор, пока Кейт Кларк [1978] не показал, что при определенных естественных условиях это правильная (а иногда и полная) реализация классического отрицания в отношении завершения программы.. Завершение составляет примерно рассмотрение набора всех программных предложений с одним и тем же предикатом в левой части, скажем
как определение предиката
, где «iff» означает «если и только если». Запись завершения также требует явного использования предиката равенства и включения набора соответствующих аксиом для равенство. Однако для реализации отрицания посредством отказа требуются только if-половины определений без аксиом равенства.
Например, завершение приведенной выше программы:
Понятие завершения тесно связано с семантикой ограничения Маккарти для рассуждений по умолчанию и с предположением о закрытом мире.
As альтернатива семантике завершения, отрицание как отказ может также интерпретироваться эпистемически, как в семантике стабильной модели из программирование набора ответов. В этой интерпретации не (B i) буквально означает, что B i неизвестно или не верится. Эпистемическая интерпретация имеет то преимущество, что ее можно очень просто комбинировать с классическим отрицанием, как в «расширенном логическом программировании», чтобы формализовать такие фразы, как «обратное не может быть показано», где «противоположное» является классическим отрицанием и «не может быть показано »- это эпистемическая интерпретация отрицания как неудачи.
Тот факт, что предложениям Хорна можно дать процедурную интерпретацию, и, наоборот, что процедуры снижения цели можно понимать как предложения Хорна + обратное рассуждение, означает, что логические программы объединяют декларативные и процедурные представления знаний. Включение отрицания в качестве отказа означает, что логическое программирование является разновидностью немонотонной логики.
Несмотря на свою простоту по сравнению с классической логикой, эта комбинация предложений Хорна и отрицания в качестве отказа доказала свою эффективность. быть удивительно выразительным. Например, он обеспечивает естественное представление разумных законов причины и следствия, формализованных как исчислением ситуаций, так и исчислением событий. Также было показано, что это вполне естественно соответствует полуформальному языку законодательства. В частности, Праккен и Сартор приписывают представление Закона о британском гражданстве как логической программы, оказавшей «огромное влияние на развитие вычислительных представлений законодательства, демонстрируя, как логическое программирование позволяет интуитивно привлекательные представления, которые могут быть непосредственно использованы для создания автоматических выводов»..
Язык программирования Prolog был разработан в 1972 году Аленом Колмерауэром. Он возник в результате сотрудничества Колмерауэра в Марселе и Роберта Ковальски в Эдинбурге. Колмерауэр работал над пониманием естественного языка, используя логику для представления семантики и используя разрешение для ответов на вопросы. Летом 1971 года Колмерауэр и Ковальски обнаружили, что клаузальная форма логики может использоваться для представления формальных грамматик, а средства доказательства теорем разрешения могут использоваться для синтаксического анализа. Они заметили, что некоторые средства доказательства теорем, такие как гиперразрешение, ведут себя как анализаторы снизу вверх, а другие, такие как SL-resolution (1971), ведут себя как синтаксические анализаторы сверху вниз.
Следующим летом 1972 года Ковальский, снова работая с Колмерауэром, разработал процедурную интерпретацию последствий. Эта двойная декларативная / процедурная интерпретация позже была формализована в нотации Пролога
, которую можно читать (и использовать) как декларативно, так и процедурно. Также стало ясно, что такие предложения могут быть ограничены определенными предложениями или предложениями Хорна, где H, B1,..., Bn- все формулы атомарной логики предикатов, и что SL-разрешение может быть ограничено (и обобщенные) до LUSH или SLD-разрешения. Процедурная интерпретация Ковальски и LUSH были описаны в меморандуме 1973 года, опубликованном в 1974 году.
Колмерауэр и Филипп Руссель использовали эту двойную интерпретацию предложений как основу Пролога, который был реализован летом и осенью 1972 года. Первая программа на языке Prolog, также написанная в 1972 году и реализованная в Марселе, была французской системой ответов на вопросы. Использование Prolog в качестве практического языка программирования дало большой импульс разработкой компилятора Дэвидом Уорреном в Эдинбурге в 1977 году. Эксперименты показали, что Edinburgh Prolog может конкурировать по скорости обработки с другими языками символического программирования, такими как как Лисп. Эдинбургский Пролог стал стандартом де-факто и сильно повлиял на определение стандарта ISO Пролог.
Абдуктивное логическое программирование - это расширение нормального логического программирования, которое позволяет некоторым предикатам, объявленным как сокращаемые предикаты, быть «открытыми» или неопределенными. Предложение в программе абдуктивной логики имеет вид:
, где H- атомарная формула, которая не сводится, все Bi- литералы, предикаты которых не сводятся, а Ai- атомарные формулы, предикаты которых сводимы. Приводимые предикаты могут быть ограничены ограничениями целостности, которые могут иметь вид:
где Li- произвольные литералы (определенные или сокращаемые, и атомарная или отрицательная). Например:
canfly (X): - птица (X), нормальный (X). ложь: - нормальный (X), раненый (X). птица (джон). птица (мэри). раненый (джон).
, где предикат нормальныйявляется сокращаемым.
Решение проблем достигается путем вывода гипотез, выраженных в терминах сводимых предикатов, как решений проблем, которые необходимо решить. Эти проблемы могут быть либо наблюдениями, которые необходимо объяснить (как в классическом абдуктивном мышлении ), либо целями, которые необходимо решить (как в нормальном логическом программировании). Например, гипотеза normal (mary)объясняет наблюдение canfly (mary). Более того, та же самая гипотеза влечет за собой единственное решение X = maryцели найти что-то, что может летать:
: - canfly (X).
Абдуктивное логическое программирование использовалось для диагностики неисправностей, планирования, обработки естественного языка и машинного обучения. Он также использовался для интерпретации отрицания как неудачи как формы абдуктивного рассуждения.
Поскольку математическая логика имеет давнюю традицию различать объектный язык и метаязык, логическое программирование также позволяет. Простейшей мета-программой является так называемый метаинтерпретатор "vanilla ":
solution (true). решить ((A, B)): - решить (A), решить (B). решить (A): - пункт (A, B), решить (B).
где истина представляет собой пустую конъюнкцию, а предложение (A, B) означает, что существует предложение уровня объекта в форме A: - B.
Металогическое программирование позволяет представлениям уровня объекта и метауровня для сочетаться, как в естественном языке. Его также можно использовать для реализации любой логики, указанной как правила вывода. Металогика используется в логическом программировании для реализации метапрограмм, которые манипулируют другими программами, базами данных, базами знаний или аксиоматическими теориями как данными.
Программирование логики ограничений объединяет логическое программирование предложения Horn с решением ограничений. Он расширяет предложения Horn, позволяя некоторым предикатам, объявленным как предикаты ограничений, встречаться как литералы в теле предложений. Программа логики ограничений - это набор предложений вида:
, где Hи все Bi- атомарные формулы, а Ci- ограничения. Декларативно такие предложения читаются как обычные логические следствия:
Однако, в то время как предикаты в заголовках предложений определяются программой логики ограничений, предикаты в ограничениях предопределены некоторой теоретико-модельной структурой или теорией, зависящей от предметной области.
Процедурно подцели, предикаты которых определены программой, решаются путем редукции целей, как в обычном логическом программировании, но ограничения проверяются на выполнение с помощью решателя ограничений, зависящего от предметной области, который реализует семантику предикаты ограничений. Исходная проблема решается путем сведения ее к выполнимой совокупности ограничений.
Следующая программа с логикой ограничений представляет игрушечную временную базу данных историиДжона как учителя:
преподает (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.
Здесь ≤и <- предикаты ограничений с их обычной предполагаемой семантикой. Следующее целевое предложение запрашивает базу данных, чтобы узнать, когда джонодновременно преподавал логикуи был профессором:
Решение 2010 ≤ T, T ≤ 2012.
Программирование с ограничениями логики использовалось для решения задач в таких областях, как гражданское строительство, машиностроение, проверка цифровых схем, автоматическое планирование, управление воздушным движением и финансы. Это тесно связано с абдуктивным логическим программированием.
Параллельное логическое программирование объединяет концепции логического программирования с параллельным программированием. Его развитие получило большой импульс в 1980-х годах, когда он выбрал язык системного программирования для японского проекта пятого поколения (FGCS).
Программа параллельной логики представляет собой набор защищенных предложений Хорна формы:
Конъюнкция G1,..., G nназывается охранником предложения, а |- оператор фиксации. Декларативно защищенные предложения Хорна читаются как обычные логические следствия:
Однако процедурно, когда есть несколько предложений, заголовки которых Hсоответствуют заданной цели, тогда все предложения выполняются параллельно, проверяя, соответствуют ли их охранники G1,..., G nдержи. Если защитные меры более чем одного предложения остаются верными, то одно из предложений совершается, и выполнение продолжается с подцелями B1,..., B nвыбранного пункта. Эти подцели также могут выполняться параллельно. Таким образом, параллельное логическое программирование реализует форму «недетерминизма безразлично», а не «недетерминизма не знаю».
Например, следующая программа параллельной логики определяет предикат shuffle (Left, Right, Merge), который можно использовать для перемешивания двух списков Leftи Вправо, объединяя их в один список Объединить, сохраняющий порядок двух списков Влевои Вправо:
в случайном порядке (,). перемешать (влево, вправо, объединить): - Влево = [Первая | Отдых] | Слияние = [Первая | ShortMerge], перемешайте (Rest, Right, ShortMerge). перемешать (влево, вправо, объединить): - Вправо = [Первая | Отдых] | Слияние = [Первая | ShortMerge], перемешайте (Left, Rest, ShortMerge).
Здесь представляет пустой список, а [Head | Tail]представляет собой список с первым элементом Head, за которым следует список Tail, как в Прологе. (Обратите внимание, что первое вхождение |во втором и третьем предложениях - это конструктор списка, тогда как второе вхождение |- это оператор фиксации.) Программа может использоваться для Например, чтобы перетасовать списки [туз, дама, король]и [1, 4, 2]с помощью предложения цели:
перемешать ([туз, дама, король ], [1, 4, 2], слияние).
Программа недетерминированно сгенерирует одно решение, например Merge = [ace, queen, 1, king, 4, 2].
Возможно, параллельное логическое программирование основано на передаче сообщений, поэтому подвержен той же неопределенности, что и другие системы параллельной передачи сообщений, такие как Действующие лица (см. Неопределенность в параллельных вычислениях ). Карл Хьюитт утверждал, что параллельное логическое программирование не основано на логике в его понимании того, что вычислительные шаги не могут быть логически выведены. Однако в параллельном логическом программировании любой результат завершения вычисления является логическим следствием программы, а любой частичный результат частичного вычисления является логическим следствием программы и остаточной цели (технологической сети). Таким образом, неопределенность вычислений означает, что не все логические последствия программы могут быть выведены.
Параллельное программирование логики ограничений сочетает в себе параллельное логическое программирование и логическое программирование ограничений, используя ограничения для управления параллелизмом. Предложение может содержать защиту, которая представляет собой набор ограничений, которые могут блокировать применимость предложения. Когда соблюдены меры защиты нескольких предложений, параллельное программирование логики ограничений делает твердый выбор в пользу использования только одного.
Индуктивное логическое программирование связано с обобщением положительных и отрицательных примеров в контексте базовых знаний: машинное обучение логических программ. Недавняя работа в этой области, сочетающая логическое программирование, обучение и вероятность, дала начало новой области статистического реляционного обучения и вероятностного индуктивного логического программирования.
Некоторые исследователи расширили логическое программирование с помощью функций программирования высшего порядка, производных от логики высшего порядка, таких как переменные предиката. К таким языкам относятся расширения Prolog HiLog и λProlog.
Базовое логическое программирование в рамках линейной логики привело к разработке логического программирования языки, которые значительно более выразительны, чем основанные на классической логике. Программы с предложениями Horn могут представлять изменение состояния только путем изменения аргументов предикатов. В линейном логическом программировании можно использовать внешнюю линейную логику для поддержки изменения состояния. Некоторые ранние разработки языков логического программирования, основанные на линейной логике, включают LO [Andreoli Pareschi, 1991], Lolli, ACL и Forum [Miller, 1996]. Форум дает целенаправленную интерпретацию всей линейной логики.
F-логика расширяет логическое программирование с помощью объектов и синтаксиса фрейма.
Logtalk расширяет язык программирования Prolog с поддержкой объектов, протоколов и других концепций ООП. Он поддерживает большинство совместимых со стандартами систем Prolog в качестве внутренних компиляторов.
Логика транзакции - это расширение логического программирования с логической теорией обновлений с изменением состояния. Он имеет как теоретико-модельную семантику, так и процедурную. Реализация подмножества логики транзакций доступна в системе Флора-2. Также доступны другие прототипы .
 | На Викискладе есть материалы, связанные с Логическое программирование. |
