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

Логическое программирование — это парадигма программирования , представления баз данных и знаний, основанная на формальной логике . Логическая программа — это набор предложений в логической форме, представляющий знания о некоторой проблемной области. Вычисления выполняются путем применения логических рассуждений к этим знаниям для решения проблем в предметной области. Основные семейства языков логического программирования включают Prolog , Answer Set Programming (ASP) и Datalog . Во всех этих языках правила записаны в виде предложений :

A :- B1, ..., Bn.

и читаются как повествовательные предложения в логической форме:

A if B1 and ... and Bn.

A называется главой правила, B1, ..., Bn называется телом , а Bi называются литералами или условиями. При n = 0 правило называется фактом и записывается в упрощенном виде:

A.

Запросы (или цели) имеют тот же синтаксис, что и тела правил, и обычно записываются в форме:

?- B1, ..., Bn.

В простейшем случае предложений Хорна (или «определенных» предложений) все A, B ₁ , ..., B _n представляют собой атомарные формулы вида p(t ₁ ,..., t _m ​​), где p — это символ-предикат, обозначающий отношение, например «материнство», а t _i — это термины, обозначающие объекты (или индивидуумы). Термины включают как постоянные символы, такие как «Чарльз», так и переменные, такие как X, которые начинаются с заглавной буквы.

Рассмотрим, например, следующую программу предложений Хорна:

mother_child(elizabeth, charles).
father_child(charles, william).
father_child(charles, harry).
parent_child(X, Y) :- 
     mother_child(X, Y).
parent_child(X, Y) :- 
     father_child(X, Y).
grandparent_child(X, Y) :- 
     parent_child(X, Z), 
     parent_child(Z, Y).

По запросу программа выдает ответы. Например, для запроса ?- parent_child(X, william), единственный ответ

X = charles

Можно задавать разные вопросы. Например программу можно запросить как для создания бабушек и дедушек, так и для генерации внуков. Его даже можно использовать для генерации всех пар внуков, бабушек и дедушек или просто для проверки, является ли данная пара такой парой:

grandparent_child(X, william).
X = elizabeth

?- grandparent_child(elizabeth, Y).
Y = william;
Y = harry.

?- grandparent_child(X, Y).
X = elizabeth
Y = william;
X = elizabeth
Y = harry.

?- grandparent_child(william, harry).
no
?- grandparent_child(elizabeth, harry).
yes

Хотя логические программы предложений Хорна являются полными по Тьюрингу , для большинства практических приложений программы предложений Хорна необходимо расширить до «нормальных» логических программ с отрицательными условиями. Например, определение родственного брата использует отрицательное условие, где предикат = определяется предложением X = X:

sibling(X, Y) :- 
     parent_child(Z, X), 
     parent_child(Z, Y), 
     not(X = Y).

Языки логического программирования, включающие отрицательные условия, обладают возможностями представления знаний немонотонной логики .

В ASP и Datalog логические программы имеют только декларативное чтение, а их выполнение осуществляется с помощью процедуры доказательства или генератора моделей, поведение которых не предназначено для контроля со стороны программиста. Однако в семействе языков Пролог логические программы также имеют процедурную интерпретацию как процедуры редукции цели. С этой точки зрения под пунктом A :- B ₁ ,...,B _n понимается как:

решить A, решать B1, и... и решить Bn.

Отрицательные условия в теле предложений также имеют процедурную интерпретацию, известную как отрицание как отказ : отрицательный литерал not B считается выполненным тогда и только тогда, когда положительный литерал B не удерживается.

Большая часть исследований в области логического программирования была посвящена попыткам разработать логическую семантику отрицания как неудачи, а также разработке другой семантики и других реализаций отрицания. Эти разработки, в свою очередь, сыграли важную роль в поддержке разработки формальных методов логической проверки и преобразования программ .

История

Использование математической логики для представления и выполнения компьютерных программ также является особенностью лямбда-исчисления , разработанного Алонзо Чёрчем в 1930-х годах. Однако первое предложение использовать клаузальную форму логики для представления компьютерных программ было сделано Корделлом Грином . При этом использовалась аксиоматизация подмножества LISP вместе с представлением отношения ввода-вывода для вычисления отношения путем моделирования выполнения программы в LISP. Фостера и Элкока С другой стороны, Absys использовала комбинацию уравнений и лямбда-исчисления в языке ассертивного программирования, который не накладывает никаких ограничений на порядок выполнения операций.

Логическое программирование с его нынешним синтаксисом фактов и правил можно проследить до дебатов конца 1960-х и начала 1970-х годов о декларативном и процедурном представлениях знаний в искусственном интеллекте . Сторонники декларативных представлений особенно работали в Стэнфорде , связанном с Джоном Маккарти , Бертрамом Рафаэлем и Корделлом Грином, а также в Эдинбурге с Джоном Аланом Робинсоном (академическим гостем из Сиракузского университета ), Пэтом Хейсом и Робертом Ковальски . Сторонники процессуального представительства в основном сосредоточились в Массачусетском технологическом институте под руководством Марвина Мински и Сеймура Пейперта .

был основан на логических методах доказательства, Несмотря на то, что Planner он был разработан Карлом Хьюиттом из Массачусетского технологического института и стал первым языком, появившимся в рамках этой процедурной парадигмы. В Planner реализован управляемый шаблонами вызов процедурных планов из целей (т. е. уменьшения цели или обратной цепочки ) и из утверждений (т. е. прямой цепочки ). Самой влиятельной реализацией Planner стало подмножество Planner, названное Micro-Planner, реализованное Джерри Сассманом , Юджином Чарняком и Терри Виноградом . Виноград использовал Micro-Planner для реализации знаковой программы понимания естественного языка SHRDLU . В целях повышения эффективности Planner использовал структуру управления с обратным отслеживанием, так что одновременно можно было хранить только один возможный путь вычислений. Planner дал начало языкам программирования QA4 , Тополя, Коварный, КЛИСП, и параллельный язык Ether.

Хейс и Ковальски в Эдинбурге попытались примирить основанный на логике декларативный подход к представлению знаний с процедурным подходом Планнера. Хейс (1973) разработал эквациональный язык Golux, в котором различные процедуры можно было получить, изменяя поведение средства доказательства теорем.

Тем временем Ален Кольмерауэр в Марселе работал над пониманием естественного языка , используя логику для представления семантики и используя разрешение для ответов на вопросы. Летом 1971 года Кольмерауэр пригласил Ковальского в Марсель, и вместе они обнаружили, что клаузальная форма логики может использоваться для представления формальных грамматик , а средства доказательства теорем разрешения можно использовать для синтаксического анализа. Они заметили, что некоторые средства доказательства теорем, такие как гиперразрешение, вести себя как парсеры снизу вверх и другие, такие как разрешение SL (1971) вести себя как парсеры сверху вниз.

Следующим летом 1972 года Ковальский, снова работая с Кольмерауэром, разработал процедурную интерпретацию импликаций в клаузальной форме. Также стало ясно, что такие предложения могут быть ограничены определенными предложениями или предложениями Хорна , и что разрешение SL может быть ограничено (и обобщено) резолюцией SLD . Процедурная интерпретация Ковальского и SLD были описаны в записке 1973 года, опубликованной в 1974 году.

Кольмерауэр вместе с Филиппом Русселем использовали процедурную интерпретацию как основу Пролога, который был реализован летом и осенью 1972 года. Первая программа Пролога, также написанная в 1972 году и реализованная в Марселе, представляла собой французскую вопросно-ответную систему. Использование Пролога в качестве практического языка программирования получило большой импульс благодаря разработке компилятора Дэвидом Уорреном в Эдинбурге в 1977 году. Эксперименты показали, что Эдинбургский Пролог может конкурировать по скорости обработки с другими языками символьного программирования, такими как Лисп . Эдинбургский Пролог стал стандартом де-факто и сильно повлиял на определение стандарта Пролога ISO .

Японии выбрало его Логическое программирование привлекло международное внимание в 1980-х годах, когда Министерство международной торговли и промышленности для разработки программного обеспечения для проекта компьютерных систем пятого поколения (FGCS). Целью проекта FGCS было использование логического программирования для разработки передовых приложений искусственного интеллекта на компьютерах с массовым параллелизмом . Хотя изначально в проекте изучалось использование Пролога, позже было принято использование параллельного логического программирования , поскольку оно было ближе к компьютерной архитектуре FGCS.

Однако функция обязательного выбора параллельного логического программирования вмешивалась в логическую семантику языка. и с его пригодностью для представления знаний и приложений для решения проблем. Более того, параллельные компьютерные системы, разработанные в рамках проекта, не смогли конкурировать с достижениями, имеющими место в разработке более традиционных компьютеров общего назначения. Вместе эти две проблемы привели к тому, что проект FGCS не смог достичь своих целей. Интерес как к логическому программированию, так и к искусственному интеллекту упал во всем мире.

Тем временем более декларативные подходы к логическому программированию, в том числе основанные на использовании Пролога, продолжали развиваться независимо от проекта FGCS. В частности, хотя Пролог был разработан для объединения декларативного и процедурного представления знаний, чисто декларативная интерпретация логических программ стала в центре внимания приложений в области дедуктивных баз данных . Работа в этой области стала заметной примерно в 1977 году, когда Эрве Галлер и Джек Минкер организовали в Тулузе семинар по логике и базам данных. В конечном итоге это поле было переименовано в Datalog .

Этот акцент на логическом, декларативном чтении логических программ получил дополнительный импульс благодаря развитию логического программирования с ограничениями в 1980-х годах и программирования наборов ответов в 1990-х годах. Ему также уделяется повышенное внимание в недавних приложениях Пролога.

Ассоциация логического программирования (ALP) была основана в 1986 году для продвижения логического программирования. Его официальным журналом до 2000 года был «Журнал логического программирования» . Его главным редактором-основателем был Дж. Алан Робинсон . В 2001 году журнал был переименован в The Journal of Logic and Algebraic Programming , а официальным журналом ALP стала Theory and Practice of Logic Programming , издаваемая издательством Cambridge University Press .

Концепции

Логические программы обладают богатым разнообразием семантики и методов решения проблем, а также широким спектром приложений в программировании, базах данных, представлении знаний и решении проблем.

Алгоритм = Логика + Управление

Процедурная интерпретация логических программ, использующая обратные рассуждения для сведения целей к подцелям, представляет собой частный случай использования стратегии решения задач для управления использованием декларативного, логического представления знаний для получения поведения алгоритма . В более общем смысле, к одному и тому же логическому представлению можно применять разные стратегии решения проблем для получения разных алгоритмов. Альтернативно, разные алгоритмы могут быть получены с заданной стратегией решения проблем, используя разные логические представления.

Двумя основными стратегиями решения проблем являются обратное рассуждение (снижение цели) и прямое рассуждение , также известное как рассуждение сверху вниз и снизу вверх соответственно.

В простом случае пропозициональной программы предложения Хорна и атомарной цели верхнего уровня обратные рассуждения определяют дерево «и-или» , которое образует пространство поиска для решения цели. Цель верхнего уровня — это корень дерева. Для любого узла в дереве и любого предложения, заголовок которого соответствует этому узлу, существует набор дочерних узлов, соответствующих подцелям в теле предложения. Эти дочерние узлы сгруппированы вместе с помощью «и». Альтернативные наборы дочерних элементов, соответствующие альтернативным способам решения узла, группируются вместе с помощью «или».

Для поиска в этом пространстве можно использовать любую стратегию поиска. Пролог использует последовательную стратегию поиска с возвратом «последним пришел — первым вышел», в которой одновременно рассматриваются только одна альтернатива и одна подцель. Например, подцели можно решать параллельно, а также параллельно отрабатывать пункты. Первая стратегия называется и-параллельно , а вторая стратегия называется или-параллельно . Другие стратегии поиска, такие как интеллектуальный возврат, или поиск по принципу «сначала лучшее», чтобы найти оптимальное решение, также возможны.

В более общем, непропозициональном случае, когда подцели могут иметь общие переменные, можно использовать другие стратегии, например, выбор подцели, которая наиболее конкретизирована или достаточно конкретизирована, чтобы применима только одна процедура. Такие стратегии используются, например, в параллельном логическом программировании .

В большинстве случаев обратное рассуждение на основе запроса или цели более эффективно, чем прямое рассуждение. Но иногда при программировании журнала данных и набора ответов может не быть запроса, отдельного от набора предложений в целом, и тогда создание всех фактов, которые могут быть получены из предложений, является разумной стратегией решения проблем. Вот еще один пример, где прямое рассуждение превосходит обратное рассуждение в более традиционной вычислительной задаче, где цель ?- fibonacci(n, Result) это найти n ^й число Фибоначчи:

fibonacci(0, 0).
fibonacci(1, 1).

fibonacci(N, Result) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1, F1),
    fibonacci(N2, F2),
    Result is F1 + F2.

Здесь отношение fibonacci(N, M) обозначает функцию fibonacci(N) = Mи предикат N is Expression — это нотация Пролога для предиката, который создает экземпляр переменной. N к значению Expression.

Учитывая цель вычисления числа Фибоначчи n, обратные рассуждения сводят цель к двум подцелям: вычислению чисел Фибоначчи n-1 и n-2. Это сводит подцель вычисления числа Фибоначчи для n-1 к двум подцелям вычисления чисел Фибоначчи для n-2 и n-3, избыточно вычисляя числа Фибоначчи для n-2. Этот процесс сведения одной подцели Фибоначчи к двум подцелям Фибоначчи продолжается до тех пор, пока не достигнет чисел 0 и 1. Его сложность имеет порядок 2. ^н . Напротив, прямое рассуждение генерирует последовательность чисел Фибоначчи, начиная с 0 и 1, без каких-либо повторных вычислений, и его сложность линейна по отношению к n.

Пролог не может выполнять прямые рассуждения напрямую. Но можно добиться эффекта прямого рассуждения в контексте обратного рассуждения посредством табличного представления : подцели сохраняются в таблице вместе с их решениями. Если подцель встречается повторно, она решается напрямую с использованием решений, уже имеющихся в таблице, вместо повторного решения подцелей.

с

См. Также: Функциональное программирование § Сравнение с логическим программированием.

Логическое программирование можно рассматривать как обобщение функционального программирования, в котором функции являются частным случаем отношений. Например, функция мать(X) = Y (каждый X имеет только одну мать Y) может быть представлена ​​отношением мать(X, Y). В этом отношении логические программы похожи на реляционные базы данных , которые также представляют функции как отношения.

По сравнению с реляционным синтаксисом функциональный синтаксис более компактен для вложенных функций. Например, в функциональном синтаксисе определение бабушки по материнской линии можно записать во вложенной форме:

maternal_grandmother(X) = mother(mother(X)).

То же определение в реляционной нотации необходимо записать в невложенной, сплющенной форме:

maternal_grandmother(X, Y) :- mother(X, Z), mother(Z, Y).

Однако вложенный синтаксис можно рассматривать как синтаксический сахар для невложенного синтаксиса. Ciao Prolog, например, преобразует функциональный синтаксис в реляционную форму и выполняет полученную логическую программу, используя стандартную стратегию выполнения Пролога. Более того, то же преобразование можно использовать для выполнения вложенных отношений, которые не являются функциональными. Например:

grandparent(X) := parent(parent(X)).
parent(X) := mother(X).
parent(X) := father(X).

mother(charles) := elizabeth.
father(charles) := phillip.
mother(harry) := diana.
father(harry) := charles.

?- grandparent(X,Y).
X = harry,
Y = elizabeth.
X = harry,
Y = phillip.

с

Термин «реляционное программирование» использовался для обозначения множества языков программирования, в которых функции рассматриваются как частный случай отношений. Некоторые из этих языков, например miniKanren и реляционное линейное программирование — это языки логического программирования в смысле этой статьи.

Однако реляционный язык RML является императивным языком программирования. основная конструкция которого представляет собой реляционное выражение, которое похоже на выражение в логике предикатов первого порядка.

Другие языки реляционного программирования основаны на реляционном исчислении. или реляционная алгебра.

Семантика

Основная статья: Синтаксис и семантика логического программирования

С чисто логической точки зрения существует два подхода к декларативной семантике логических программ предложений Хорна: один подход — это исходная следствий логических , которая понимает решение цели как демонстрацию того, что цель — это теорема, которая верна во всех моделях семантика программа.

В этом подходе вычисления доказывают теоремы в логике первого порядка ; и как обратные рассуждения , как при разрешении SLD, так и прямые рассуждения , как при гиперразрешении, являются правильными и полными методами доказательства теорем. Иногда такие методы доказательства теорем также рассматриваются как обеспечивающие отдельную теоретико-доказательную (или операционную) семантику для логических программ. Но с логической точки зрения это скорее методы доказательства, чем семантика.

Другой подход к декларативной семантике программ предложений Хорна — это выполнимости семантика , которая понимает решение цели как демонстрацию того, что цель истинна (или удовлетворена) в некоторой предполагаемой (или стандартной) модели программы. Для программ предложений Хорна всегда существует такая стандартная модель: это уникальная минимальная модель программы.

Неформально говоря, минимальная модель — это модель, которая, если рассматривать ее как набор всех фактов (без переменных), которые верны в модели, содержит не меньший набор фактов, который также является моделью программы.

Например, следующие факты представляют собой минимальную модель семейных отношений, приведенную во введении к этой статье. Все остальные факты без переменных в модели ложны:

mother_child(elizabeth, charles).
father_child(charles, william).
father_child(charles, harry).
parent_child(elizabeth, charles).
parent_child(charles, william).
parent_child(charles, harry).
grandparent_child(elizabeth, william).
grandparent_child(elizabeth, harry).

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

Примечательно, что одни и те же методы решения задач прямого и обратного рассуждения, которые изначально были разработаны для семантики логических следствий, в равной степени применимы и к семантике выполнимости: прямое рассуждение генерирует минимальную модель программы предложений Хорна, извлекая новые факты из существующих. фактов до тех пор, пока не будут созданы новые дополнительные факты. Обратное рассуждение, которое успешно сводит цель к подцелям до тех пор, пока все подцели не будут решены с помощью фактов, гарантирует, что цель верна в минимальной модели, без явного создания модели.

Разницу между двумя декларативными семантиками можно увидеть с помощью определений сложения и умножения в последующей арифметике , которая представляет натуральные числа. 0, 1, 2, ... как последовательность слагаемых вида 0, s(0), s(s(0)), .... В целом, термин s(X) представляет собой преемника X, а именно X + 1. Вот стандартные определения сложения и умножения в функциональной записи:

     X + 0 = X.
     X + s(Y)    = s(X + Y). 
i.e. X + (Y + 1) = (X + Y) + 1

     X × 0 = 0.
     X × s(Y)    = X + (X × Y). 
i.e. X × (Y + 1) = X + (X × Y).

Вот те же определения, что и для логической программы, используя add(X, Y, Z) представлять X + Y = Z, и multiply(X, Y, Z) представлять X × Y = Z:

add(X, 0, X).
add(X, s(Y), s(Z)) :- add(X, Y, Z).

multiply(X, 0, 0).
multiply(X, s(Y), W) :- multiply(X, Y, Z), add(X, Z, W).

Обе декларативные семантики дают одни и те же ответы для одних и тех же экзистенциально квантифицированных соединений целей сложения и умножения. Например 2 × 2 = X есть решение X = 4; и X × X = X + X имеет два решения X = 0 и X = 2:

?- multiply(s(s(0)), s(s(0)), X).
X = s(s(s(s(0)))).

?- multiply(X, X, Y), add(X, X, Y).
X = 0, Y = 0.
X = s(s(0)), Y = s(s(s(s(0)))).

Однако при семантике логического следствия существуют нестандартные модели программы, в которых, например, add(s(s(0)), s(s(0)), s(s(s(s(s(0)))))), то есть 2 + 2 = 5 это правда. Но с семантикой выполнимости существует только одна модель, а именно стандартная модель арифметики, в которой 2 + 2 = 5 является ложным.

В обеих семантиках цель ?- add(s(s(0)), s(s(0)), s(s(s(s(s(0)))))) терпит неудачу. В семантике достижимости неудача цели означает, что истинное значение цели ложно. Но в семантике логических последствий неудача означает, что истинное значение цели неизвестно.

Отрицание как неудача

Основная статья: Отрицание как неудача

Отрицание как неудача (NAF), как способ сделать вывод о том, что отрицательное состояние not p справедливо, показав, что положительное условие p не выдерживает критики, уже была особенностью ранних систем Пролога. Результирующее расширение разрешения SLD называется SLDNF . Подобная конструкция, получившая название «thnot», также существовала в Micro-Planner .

Логическая семантика NAF оставалась неразгаданной до тех пор, пока Кит Кларк показал, что при определенных естественных условиях NAF является эффективным, правильным (а иногда и полным) способом рассуждения с семантикой логических следствий с использованием завершения логической программы в логике первого порядка.

Завершение примерно равнозначно набору всех предложений программы с одним и тем же предикатом в заголовке, скажем:

A :- Body1.

...

A :- Bodyk.

как определение сказуемого:

A iff (Body1 or ... or Bodyk)

где iff означает «тогда и только тогда, когда». В пополнение также входят аксиомы равенства, соответствующие унификации . Кларк показал, что доказательства, генерируемые SLDNF, структурно аналогичны доказательствам, генерируемым методом естественной дедукции после завершения программы.

Рассмотрим, например, следующую программу:

should_receive_sanction(X, punishment) :- 
    is_a_thief(X),
    not should_receive_sanction(X, rehabilitation).
    
should_receive_sanction(X, rehabilitation) :-
    is_a_thief(X),
    is_a_minor(X),
    not is_violent(X).
    
is_a_thief(tom).

Учитывая цель определения того, должен ли Том получить санкцию, первое правило успешно показывает, что Том должен быть наказан:

?- should_receive_sanction(tom, Sanction).
Sanction = punishment.

Это потому, что Том — вор, и нельзя доказать, что Тома следует реабилитировать. Невозможно доказать, что Тома следует реабилитировать, потому что нельзя доказать, что Том несовершеннолетний.

Однако если мы получим новую информацию о том, что Том действительно несовершеннолетний, предыдущий вывод о том, что Том должен быть наказан, заменяется новым выводом о том, что Тома следует реабилитировать:

minor(tom).

?- should_receive_sanction(tom, Sanction).
Sanction = rehabilitation.

Это свойство отзыва вывода при добавлении новой информации называется немонотонностью и делает логическое программирование немонотонной логикой .

Но если нам теперь скажут, что Том жесток, вывод о том, что Том должен быть наказан, будет восстановлен:

violent(tom).

?- should_receive_sanction(tom, Sanction).
Sanction = punishment.

Завершение этой программы:

should_receive_sanction(X, Sanction) iff 
    Sanction = punishment, is_a_thief(X), 
    not should_receive_sanction(X, rehabilitation)
 or Sanction = rehabilitation, is_a_thief(X), is_a_minor(X),
    not is_violent(X).
    
is_a_thief(X) iff X = tom.
is_a_minor(X) iff X = tom.
is_violent(X) iff X = tom.

Понятие завершения тесно связано с Джона Маккарти семантикой ограничения для рассуждений по умолчанию: и к Рэя Рейтера предположению о закрытом мире .

Семантика завершения для отрицания представляет собой семантику логического следствия, для которой SLDNF обеспечивает теоретико-доказательную реализацию. Однако в 1980-е годы семантика выполнимости стала более популярной для логических программ с отрицанием. В семантике выполнимости отрицание интерпретируется в соответствии с классическим определением истины в предполагаемой или стандартной модели логической программы.

В случае логических программ с отрицательными условиями существует два основных варианта семантики выполнимости: В обоснованной семантике предполагаемая модель логической программы представляет собой уникальную трехзначную минимальную модель, которая существует всегда. Обоснованная семантика обобщает понятие индуктивного определения в математической логике. XSB Пролог реализует обоснованную семантику с использованием разрешения SLG.

В альтернативной семантике стабильной модели может не быть намеченных моделей или несколько предполагаемых моделей, все из которых минимальны и двузначны. Семантика стабильной модели лежит в основе программирования набора ответов (ASP).

Как обоснованная, так и устойчивая семантика модели применима к произвольным логическим программам с отрицанием. Однако для стратифицированной программ логики обе семантики совпадают. Например, программа наказания воров (локально) стратифицирована, и все три семантики программы определяют одну и ту же предполагаемую модель:

should_receive_sanction(tom, punishment).
is_a_thief(tom).
is_a_minor(tom).
is_violent(tom).

Попытки понять отрицание в логическом программировании также способствовали развитию абстрактных структур аргументации . В аргументационной интерпретации отрицания первоначальный аргумент о том, что Тома следует наказать, потому что он вор, подвергается критике со стороны аргумента о том, что его следует реабилитировать, потому что он несовершеннолетний. Но тот факт, что Том жесток, подрывает аргумент о том, что Тома следует реабилитировать, и восстанавливает аргумент о том, что Тома следует наказать.

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

Метапрограммирование , при котором программы рассматриваются как данные, уже было особенностью ранних реализаций Пролога. Например, реализация Пролога в Эдинбурге DEC10 включала «интерпретатор и компилятор, оба написанные на самом Прологе». Простейшая метапрограмма — это так называемый « ванильный » метаинтерпретатор:

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

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

Метапрограммирование — это применение более общего использования металогики или метаязыка для описания и рассуждений о другом языке, называемом объектным языком .

Металогическое программирование позволяет комбинировать представления на уровне объекта и на метауровне, как в естественном языке. Например, в следующей программе атомарная формула attends(Person, Meeting) встречается как в виде формулы уровня объекта, так и в качестве аргумента метапредикатов prohibited и approved.

prohibited(attends(Person, Meeting)) :- 
    not(approved(attends(Person, Meeting))).

should_receive_sanction(Person, scolding) :- attends(Person, Meeting), 
    lofty(Person), prohibited(attends(Person, Meeting)).
should_receive_sanction(Person, banishment) :- attends(Person, Meeting), 
    lowly(Person), prohibited(attends(Person, Meeting)).

approved(attends(alice, tea_party)).
attends(mad_hatter, tea_party).
attends(dormouse, tea_party).

lofty(mad_hatter).
lowly(dormouse).

?- should_receive_sanction(X,Y).
Person = mad_hatter,
Sanction = scolding.
Person = dormouse,
Sanction = banishment.

с пониманием разума

В своем популярном «Введении в когнитивную науку» Пол Тагард рассматривает логику и правила как альтернативные подходы к моделированию человеческого мышления. Он утверждает, что правила, имеющие форму ЕСЛИ условие, ТО действие , «очень похожи» на логические условные выражения, но они проще и имеют большую психологическую правдоподобность (стр. 51). Среди других различий между логикой и правилами он утверждает, что логика использует дедукцию, а правила используют поиск (стр. 45) и могут использоваться для рассуждений как в прямом, так и в обратном направлении (стр. 47). Предложения в логике «должны интерпретироваться как универсально истинные », но правила могут быть значениями по умолчанию , допускающими исключения (стр. 44).

Он утверждает, что «в отличие от логики, системы, основанные на правилах, могут также легко представлять стратегическую информацию». о том, что делать» (стр. 45). Например: «ЕСЛИ вы хотите поехать домой на выходные и у вас есть билет на автобус, ТО вы можете сесть на автобус». Он не замечает, что та же самая стратегия сведения цели к подцелям может быть интерпретирована, в манере логического программирования, как применение обратных рассуждений к логическому условию:

can_go(you, home) :- have(you, bus_fare), catch(you, bus).

Все эти характеристики систем, основанных на правилах — поиск, прямое и обратное рассуждение, рассуждение по умолчанию и сокращение целей — также являются определяющими характеристиками логического программирования. Это предполагает, что вывод Тагарда (стр. 56) о том, что:

Большая часть человеческих знаний естественным образом описывается в терминах правил, и многие виды мышления, такие как планирование, могут быть смоделированы с помощью систем, основанных на правилах.

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

Другие аргументы, показывающие, как логическое программирование можно использовать для моделирования аспектов человеческого мышления, представлены Китом Стеннингом и Михиэлем ван Ламбалгеном в их книге: Человеческое мышление и когнитивная наука. Они показывают, как немонотонный характер логических программ можно использовать для объяснения действий человека при решении различных психологических задач. Они также показывают (стр. 237), что «рассуждения в закрытом мире под видом логического программирования имеют привлекательную нейронную реализацию, в отличие от классической логики».

В «Правильной трактовке событий» Михиль ван Ламбалген и Фриц Хамм исследуют использование программирования логики ограничений для кодирования «временных понятий на естественном языке, глядя на то, как люди конструируют время».

Представление знаний

Использование логики для представления процедурных знаний и стратегической информации было одной из основных целей, способствующих раннему развитию логического программирования. Более того, он продолжает оставаться важной особенностью семейства языков логического программирования Пролог и сегодня. Однако многие приложения логического программирования, включая приложения Пролога, все чаще фокусируются на использовании логики для представления чисто декларативных знаний. Эти приложения включают в себя как представление общих знаний , так и представление знаний в конкретной области .

Здравый смысл включает в себя знания о причине и следствии, формализованные, например, в исчислении ситуаций , исчислении событий и языках действий . Приведем упрощенный пример, иллюстрирующий основные особенности таких формализмов. Первое предложение гласит, что факт имеет место сразу после того, как событие инициирует (или вызывает) этот факт. Второе предложение — это аксиома фрейма , которая гласит, что факт, который имеет место в определенный момент времени, продолжает сохраняться и в следующий раз, если только он не будет прерван событием, которое произойдет в данный момент. Эта формулировка позволяет одновременно произойти более чем одному событию:

holds(Fact, Time2) :- 
    happens(Event, Time1),
    Time2 is Time1 + 1,
    initiates(Event, Fact).
     
holds(Fact, Time2) :- 
	happens(Event, Time1),
    Time2 is Time1 + 1,
    holds(Fact, Time1),
    not(terminated(Fact, Time1)).

terminated(Fact, Time) :-
   happens(Event, Time),
   terminates(Event, Fact).

Здесь holds является метапредикатом, подобным solve выше. Однако, тогда как solve имеет только один аргумент, который применяется к общим предложениям, первый аргумент holds — это факт, а второй аргумент — это время (или состояние). Атомная формула holds(Fact, Time) выражает то, что Fact держится на Time. Такие изменяющиеся во времени факты еще называют флюэнтами . Атомная формула happens(Event, Time) выражает, что Событие происходит в Time.

Следующий пример иллюстрирует, как эти предложения можно использовать для рассуждения о причинно-следственной связи в мире игрушечных кубиков . Здесь в исходном состоянии в момент времени 0 зеленый блок находится на столе, а красный блок уложен на зеленый блок (как светофор). В момент времени 0 красный блок перемещается на стол. В момент 1 зеленый блок перемещается на красный блок. Перемещение объекта на место прекращает факт нахождения объекта на каком-либо месте и инициирует факт нахождения объекта на том месте, куда его перемещают:

holds(on(green_block, table), 0).
holds(on(red_block, green_block), 0).

happens(move(red_block, table), 0).
happens(move(green_block, red_block), 1).

initiates(move(Object, Place), on(Object, Place)).
terminates(move(Object, Place2), on(Object, Place1)).

?- holds(Fact, Time).

Fact = on(green_block,table),
Time = 0.
Fact = on(red_block,green_block),
Time = 0.
Fact = on(green_block,table),
Time = 1.
Fact = on(red_block,table),
Time = 1.
Fact = on(green_block,red_block),
Time = 2.
Fact = on(red_block,table),
Time = 2.

Прямые и обратные рассуждения дают одинаковые ответы на цель. holds(Fact, Time). Но прямое рассуждение генерирует беглые потоки постепенно во временном порядке, а обратное рассуждение генерирует беглые слова регрессивно в конкретной области , как в случае использования регрессии в исчислении ситуаций .

Логическое программирование также оказалось полезным для представления экспертных систем в экспертных системах . Но человеческий опыт, как и здравый смысл общего назначения, по большей части неявный и неявный , и зачастую такое неявное знание сложно представить в явных правилах. Однако эта трудность не возникает, когда логические программы используются для представления существующих явных правил деловой организации или юридического органа.

Например, вот упрощенная версия первого предложения Закона о британском гражданстве, в котором говорится, что человек, родившийся в Великобритании, становится британским гражданином в момент рождения, если родитель этого человека является британцем. гражданин на момент рождения:

initiates(birth(Person), citizen(Person, uk)):-
    time_of(birth(Person), Time),
    place_of(birth(Person), uk),
    parent_child(Another_Person, Person),
    holds(citizen(Another_Person, uk), Time).

Исторически сложилось так, что в 1980-х годах представление значительной части Закона о британском гражданстве как логической программы оказал «огромное влияние на развитие компьютерных представлений законодательства, показав, как логическое программирование позволяет создавать интуитивно привлекательные представления, которые можно напрямую использовать для генерации автоматических выводов».

Совсем недавно появилась система ПРОЛЕГ, Основанная в 2009 году и состоящая примерно из 2500 правил и исключений из гражданского кодекса и правил Верховного суда Японии, она стала, возможно, крупнейшей базой правовых норм в мире.

Варианты и расширения

Пролог

Основная статья: Пролог

Правило вывода SLD-резолюции нейтрально в отношении порядка, в котором подцели в телах предложений могут быть выбраны для решения. Ради эффективности Пролог ограничивает этот порядок порядком записи подцелей. SLD также нейтрально относится к стратегии поиска в пространстве доказательств SLD. Пролог просматривает это пространство сверху вниз, в глубину, пробуя разные предложения для решения одной и той же (под)цели в том порядке, в котором они написаны.

Преимущество этой стратегии поиска состоит в том, что текущая ветвь дерева может быть эффективно представлена ​​стеком . Когда предложение цели на вершине стека сокращается до нового предложения цели, новое предложение цели помещается на вершину стека. Когда выбранная подцель в предложении цели наверху стека не может быть решена, стратегия поиска возвращается назад , удаляя предложение цели из вершины стека и повторяя попытку решения выбранной подцели в предыдущем предложении цели, используя следующее предложение, соответствующее выбранной подцели.

Обратный поиск можно ограничить с помощью подцели, называемой Cut и записываемой как !, которая всегда завершается успешно, но не может быть возвращена. Сокращение может быть использовано для повышения эффективности, но также может повлиять на логический смысл предложений. Во многих случаях использование отсечения может быть заменено отрицанием как неудачей. Фактически, отрицание как неудача может быть определено в Прологе, используя Cut вместе с любым литералом, скажем, Fail , который объединяется с заголовком предложения no:

not(P) :- P, !, fail.
not(P).

Пролог помимо вырезания предоставляет и другие возможности, не имеющие логической интерпретации. К ним относятся встроенные предикаты Assert и Retract для деструктивного обновления состояния программы во время ее выполнения.

Например, приведенный выше пример мира игрушечных блоков можно реализовать без аксиом фрейма, используя деструктивное изменение состояния:

on(green_block, table).
on(red_block, green_block).

move(Object, Place2) :- 
	retract(on(Object, Place1)), 
	assert(on(Object, Place2).

Последовательность событий перемещения и результирующее расположение блоков можно вычислить, выполнив запрос:

?- move(red_block, table), move(green_block, red_block), on(Object, Place).

Object = red_block,
Place = table.
Object = green_block,
Place = red_block.

Различные расширения логического программирования были разработаны, чтобы обеспечить логическую основу для такого деструктивного изменения состояния.

Широкий спектр приложений Пролога, как изолированно, так и в сочетании с другими языками, освещается в Году книги Пролога. празднование 50-летия Пролога в 2022 году.

Пролог также внес свой вклад в разработку других языков программирования, включая ALF , Fril , Gödel , Mercury , Oz , Ciao , Visual Prolog , XSB и λProlog .

Программирование логики ограничений

Основная статья: Программирование логики ограничений

Логическое программирование с ограничениями (CLP) сочетает в себе логическое программирование предложений Хорна с решением ограничений . Он расширяет предложения Хорна, позволяя некоторым предикатам, объявленным как предикаты ограничений, появляться в теле предложения как литералы. Предикаты ограничений не определяются фактами и правилами в программе, но предопределены некоторой специфичной для предметной области теоретико-модельной структурой или теорией.

Процедурно, подцели, предикаты которых определены программой, решаются путем уменьшения цели, как в обычном логическом программировании, но ограничения упрощаются и проверяются на выполнимость с помощью специфичного для предметной области решателя ограничений, который реализует семантику предикатов ограничений. Исходная задача решается путем сведения ее к выполнимой комбинации ограничений.

Интересно, что первая версия Пролога уже включала предикат ограничения dif(term1, term2) из ​​докторской диссертации Филиппа Русселя 1972 года, который завершается успешно, если оба его аргумента являются разными терминами, но задерживается, если любой из терминов содержит переменную.

Следующая программа логики ограничений представляет собой игрушечную временную базу данных john's история как учитель:

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.

Здесь ≤ и < являются предикатами ограничений со своей обычной предполагаемой семантикой. Следующее предложение цели запрашивает базу данных, чтобы узнать, когда john оба преподавали logic и был professor:

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

Решение 2010 ≤ T, T ≤ 2012 результат упрощения ограничений 2005 ≤ T, T ≤ 2012, 2010 ≤ T, T < 2014.

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

Журнал данных

Основная статья: Журнал данных

Datalog — это язык определения базы данных, который сочетает в себе реляционное представление данных, как в реляционных базах данных , с логическим представлением, как в логическом программировании.

Реляционные базы данных используют реляционное исчисление или реляционную алгебру с реляционными операциями , такими как объединение , пересечение , разность множеств и декартово произведение , для определения запросов, которые обращаются к базе данных. Datalog использует логические связки, такие как или , а также не в телах правил для определения отношений как части самой базы данных.

На ранних этапах разработки реляционных баз данных было признано, что рекурсивные запросы не могут быть выражены ни в реляционной алгебре, ни в реляционном исчислении, и что этот недостаток можно устранить, введя оператор наименьшей фиксированной точки. Напротив, рекурсивные отношения могут определяться естественным образом с помощью правил логических программ без необходимости использования каких-либо новых логических связок или операторов.

Журнал данных отличается от более общего логического программирования тем, что в качестве терминов используются только константы и переменные. Более того, все факты не содержат переменных, а правила ограничены, так что если они выполняются снизу вверх, то производные факты также не содержат переменных.

Например, рассмотрим семейную базу данных:

mother_child(elizabeth, charles).
father_child(charles, william).
father_child(charles, harry).
parent_child(X, Y) :- 
     mother_child(X, Y).
parent_child(X, Y) :- 
     father_child(X, Y).
ancestor_descendant(X, Y) :- 
     parent_child(X, X).
ancestor_descendant(X, Y) :- 
     ancestor_descendant(X, Z), 
     ancestor_descendant(Z, Y).

Выполнение «снизу вверх» получает следующий набор дополнительных фактов и завершается:

parent_child(elizabeth, charles).
parent_child(charles, william).
parent_child(charles, harry).

ancestor_descendant(elizabeth, charles).
ancestor_descendant(charles, william).
ancestor_descendant(charles, harry).

ancestor_descendant(elizabeth, william).
ancestor_descendant(elizabeth, harry).

Выполнение сверху вниз дает те же ответы на запрос:

?- ancestor_descendant(X, Y).

Но затем это переходит в бесконечный цикл. Однако выполнение сверху вниз с табличным представлением дает те же ответы и завершается без цикла.

Программирование набора ответов

Основная статья: Программирование набора ответов

Как и журнал данных, программирование набора ответов (ASP) не является полным по Тьюрингу. Более того, вместо того, чтобы отделять цели (или запросы) от программы, которая будет использоваться для решения целей, ASP рассматривает всю программу как цель и решает цель, создавая стабильную модель, которая делает цель истинной. Для этой цели используется семантика стабильной модели , согласно которой логическая программа может иметь ноль, одну или несколько предполагаемых моделей. Например, следующая программа представляет собой вырожденный вариант задачи раскраски карты, заключающейся в окраске двух стран в красный или зеленый цвет:

country(oz).
country(iz).
adjacent(oz, iz).
colour(C, red) :- country(C), not(colour(C, green)).
colour(C, green) :- country(C), not(colour(C, red)).

Задача имеет четыре решения, представленные четырьмя устойчивыми моделями:

country(oz). country(iz). adjacent(oz, iz). colour(oz, red).   colour(iz, red).

country(oz). country(iz). adjacent(oz, iz). colour(oz, green). colour(iz, green).

country(oz). country(iz). adjacent(oz, iz). colour(oz, red).   colour(iz, green).

country(oz). country(iz). adjacent(oz, iz). colour(oz, green). colour(iz, red).

Чтобы представить стандартную версию задачи раскраски карты, нам нужно добавить ограничение, согласно которому две соседние страны не могут быть окрашены в один и тот же цвет. В ASP это ограничение можно записать в виде предложения вида:

:- country(C1), country(C2), adjacent(C1, C2), colour(C1, X), colour(C2, X).

С добавлением этого ограничения проблема теперь имеет только два решения:

country(oz). country(iz). adjacent(oz, iz). colour(oz, red).   colour(iz, green).

country(oz). country(iz). adjacent(oz, iz). colour(oz, green). colour(iz, red).

Добавление ограничений вида :- Body. исключает модели, в которых Body это правда.

Как ни странно, ограничения в ASP отличаются от ограничений в CLP . Ограничения в CLP — это предикаты, которые определяют ответы на запросы (и решения целей). Ограничения в ASP — это положения, исключающие модели, которые в противном случае удовлетворяли бы целям. Ограничения в ASP аналогичны ограничениям целостности в базах данных.

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

Большинство реализаций ASP выполняются в два этапа: сначала они реализуют программу всеми возможными способами, сводя ее к программе пропозициональной логики (известной как заземление ). Затем они применяют решатель задач пропозициональной логики, такой как алгоритм DPLL или булев решатель SAT . Однако некоторые реализации, такие как s(CASP) использовать целенаправленную, нисходящую процедуру, подобную SLD, без заземление.

логическое

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

Абдуктивное логическое программирование (ALP), как и CLP, расширяет обычное логическое программирование, позволяя телам предложений содержать литералы, предикаты которых не определены в предложениях. В ALP эти предикаты объявляются как абдуктивные (или предполагаемые ) и используются, как и в абдуктивных рассуждениях, для объяснения наблюдений или, в более общем плане, для добавления в программу новых фактов (в качестве предположений) для решения целей.

Например, предположим, что нам дано начальное состояние, в котором красный блок находится на зеленом блоке стола в момент 0:

holds(on(green_block, table), 0).
holds(on(red_block, green_block), 0).

Предположим, нам также задана цель:

?- holds(on(green_block,red_block), 3), holds(on(red_block,table), 3).

Цель может представлять собой наблюдение, и в этом случае решением является объяснение наблюдения. Или цель может представлять собой желаемое будущее положение дел, и в этом случае решением является план достижения цели.

Мы можем использовать правила причины и следствия, представленные ранее, для решения цели, рассматривая happens предикат как сводимый:

holds(Fact, Time2) :- 
    happens(Event, Time1),
    Time2 is Time1 + 1,
    initiates(Event, Fact).
     
holds(Fact, Time2) :- 
	happens(Event, Time1),
    Time2 is Time1 + 1,
    holds(Fact, Time1),
    not(terminated(Fact, Time1)).
    
terminated(Fact, Time) :-
   happens(Event, Time),
   terminates(Event, Fact).

initiates(move(Object, Place), on(Object, Place)).
terminates(move(Object, Place2), on(Object, Place1)).

ALP решает цель, рассуждая в обратном порядке и добавляя в программу предположения для решения сводимых подцелей. В этом случае существует множество альтернативных решений, в том числе:

happens(move(red_block, table), 0).
happens(tick, 1).
happens(move(green_block, red_block), 2).

happens(tick,0).
happens(move(red_block, table), 1).
happens(move(green_block, red_block), 2).

happens(move(red_block, table), 0).
happens(move(green_block, red_block), 1).
happens(tick, 2).

Здесь tick это событие, которое отмечает ход времени, не вызывая и не прекращая никаких беглых потоков.

Существуют также решения, в которых оба move события происходят одновременно. Например:

happens(move(red_block, table), 0).
happens(move(green_block, red_block), 0).
happens(tick, 1).
happens(tick, 2).

Такие решения, если они нежелательны, можно удалить, добавив ограничение целостности, похожее на условие ограничения в ASP:

:- happens(move(Block1, Place), Time), happens(move(Block2, Block1), Time).

Абдуктивное логическое программирование использовалось для диагностики неисправностей, планирования, обработки естественного языка и машинного обучения. Его также использовали для интерпретации отрицания как неудачи как формы абдуктивного рассуждения.

логическое

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

Индуктивное логическое программирование (ILP) — это подход к машинному обучению , который создает логические программы как гипотетические обобщения положительных и отрицательных примеров. Учитывая логическую программу, представляющую базовые знания и положительные примеры вместе с ограничениями, представляющими отрицательные примеры, система ПДОДИ создает логическую программу, которая обобщает положительные примеры, исключая при этом отрицательные примеры.

ILP похожа на ALP в том, что их можно рассматривать как создание гипотез для объяснения наблюдений и как использование ограничений для исключения нежелательных гипотез. Но в ALP гипотезы — это факты без переменных, а в ILP гипотезы — это общие правила.

Например, имея только базовые знания об отношениях мать_ребенок и отец_ребенок, а также подходящие примеры отношения дедушка_ребенок, современные системы ILP могут генерировать определение дедушки и дедушки_ребенка, изобретая вспомогательный предикат, который можно интерпретировать как отношение родитель_ребенок:

grandparent_child(X, Y):- auxiliary(X, Z), auxiliary(Z, Y).
auxiliary(X, Y):- mother_child(X, Y).
auxiliary(X, Y):- father_child(X, Y).

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

Недавняя работа в области ILP, сочетающая логическое программирование, обучение и вероятность, привела к появлению областей статистического реляционного обучения и вероятностного индуктивного логического программирования .

логическое

Основная статья: Параллельное логическое программирование

Параллельное логическое программирование объединяет концепции логического программирования с параллельным программированием . Его развитию был дан большой импульс в 1980-х годах, когда он был выбран в качестве языка системного программирования японского проекта пятого поколения (FGCS) .

Программа параллельной логики представляет собой набор защищенных предложений Хорна вида:

H :- G1, ..., Gn | B1, ..., Bn.

Союз G1, ... , Gn называется защитой пункта, а | является оператором обязательства. Декларативно защищенные предложения Хорна читаются как обычные логические выводы:

H if G1 and ... and Gn and B1 and ... and Bn.

Однако в процессуальном отношении при наличии нескольких статей, главы которых H соответствуют заданной цели, то все предложения выполняются параллельно, проверяя, являются ли их охранники G1, ... , Gn держать. Если соблюдаются меры защиты более чем одного предложения, то делается фиксированный выбор одного из предложений, и выполнение продолжается с подцелями B1, ..., Bn выбранного пункта. Эти подцели также могут выполняться параллельно. Таким образом, параллельное логическое программирование реализует форму «не обращать внимания на недетерминизм», а не «не знать недетерминизм».

Например, следующая программа параллельной логики определяет предикат shuffle(Left, Right, Merge), который можно использовать для перетасовки двух списков Left и Right, объединив их в один список Merge который сохраняет порядок двух списков Left и 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].

Карл Хьюитт утверждал что из-за неопределенности параллельных вычислений параллельное логическое программирование не может реализовать общий параллелизм. Однако согласно логической семантике любой результат вычисления параллельной логической программы является логическим следствием программы, даже если не все логические последствия могут быть получены.

Параллельное программирование логики ограничений

Основная статья: Параллельное программирование логики ограничений

Параллельное программирование логики ограничений сочетает в себе параллельное логическое программирование и логическое программирование с ограничениями , используя ограничения для управления параллелизмом. Предложение может содержать защиту, представляющую собой набор ограничений, которые могут блокировать применимость этого пункта. Когда меры защиты нескольких предложений удовлетворены, параллельное программирование логики ограничений делает выбор в пользу использования только одного.

Логическое программирование высшего порядка

Некоторые исследователи расширили логическое программирование с помощью функций программирования более высокого порядка , полученных из логики высшего порядка , таких как переменные-предикаты. К таким языкам относятся расширения Пролога HiLog. и λПролог .

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

Основание логического программирования на линейной логике привело к созданию языков логического программирования, которые значительно более выразительны, чем языки, основанные на классической логике. Программы предложений Хорна могут представлять изменение состояния только путем изменения аргументов предикатов. В программировании линейной логики можно использовать окружающую линейную логику для поддержки изменения состояния. Некоторые ранние разработки языков логического программирования, основанные на линейной логике, включают LO, глупый, ACL, и Форум. Форум обеспечивает целенаправленную интерпретацию всей линейной логики.

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

F-логика расширяет логическое программирование объектами и синтаксисом фреймов.

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

Программирование логики транзакций

Логика транзакции представляет собой расширение логического программирования с помощью логической теории обновлений, изменяющих состояние. Он имеет как теоретико-модельную семантику, так и процедурную. Реализация подмножества логики транзакций доступна в Flora-2. система. и другие прототипы Доступны .

См. также

• Автоматизированное доказательство теорем
• Проблема логической выполнимости
• Программирование логики ограничений
• Теория управления
• Ученый-компьютерщик
• Оборка
• Функциональное программирование
• Нечеткая логика
• Индуктивное логическое программирование
• Линейная логика
• Логика в информатике (включая формальные методы )
• Логические языки программирования
• Программируемый логический контроллер
• Р++
• Система рассуждений
• Машинное обучение на основе правил
• Удовлетворенность
• Синтаксис и семантика логического программирования

Источники

Общие сведения

• Барал, К.; Гельфонд, М. (1994). «Логическое программирование и представление знаний» (PDF) . Журнал логического программирования . 19–20: 73–148. дои : 10.1016/0743-1066(94)90025-6 .
• Ковальский, Р.А. (1988). «Ранние годы логического программирования» (PDF) . Коммуникации АКМ . 31 : 38–43. дои : 10.1145/35043.35046 . S2CID   12259230 . [1]
• Ллойд, JW (1987). Основы логического программирования (2-е изд.). Спрингер-Верлаг.

Другие источники

• Джон Маккарти. «Программы со здравым смыслом» . Симпозиум по механизации мыслительных процессов . Национальная физическая лаборатория. Теддингтон, Англия. 1958.
• Миллер, Дейл; Надатур, Гопалан; Пфеннинг, Фрэнк; Щедров, Андре (1991). «Единые доказательства как основа логического программирования» . Анналы чистой и прикладной логики . 51 (1–2): 125–157. дои : 10.1016/0168-0072(91)90068-W .
• Эхуд Шапиро (редактор). Параллельный Пролог . МТИ Пресс. 1987.
• Джеймс Слэгл. «Эксперименты с дедуктивной программой вопросов и ответов» . САСМ. Декабрь 1965 года.
• Габбай, Дов М .; Хоггер, Кристофер Джон; Робинсон, Дж. А., ред. (1993-1998). Справочник по логике в искусственном интеллекте и логическом программировании . 1–5, Издательство Оксфордского университета.

Дальнейшее чтение

• Карл Хьюитт. « Процедурное внедрение знаний в Planner ». IJCAI 1971.
• Карл Хьюитт. « Повторяющийся упадок логического программирования и почему оно будет перевоплощено ». Весенний симпозиум AAAI: Что пошло не так и почему: уроки исследований и приложений ИИ , 2006 г.: 2–9.
• Евгений Данцин, Томас Эйтер, Георг Готтлоб, Андрей Воронков: Сложность и выразительная сила логического программирования . АКМ Компьютер. Выж. 33 (3): 374–425 (2001).
• Ульф Нильссон и Ян Малушинский, Логика, программирование и Пролог

Внешние ссылки

• логического программирования Запись в виртуальной библиотеке
• Библиографии по логическому программированию, заархивированные 4 декабря 2008 г. в Wayback Machine.
• Ассоциация логического программирования (ALP)
• Теория и практика логического программирования (журнал)
• Логическое программирование на C++ с помощью Castor
• Логическое программирование. Архивировано 3 сентября 2011 г. в Wayback Machine в Озе.
• Центр разработки Пролога
• Racklog: логическое программирование в Racket