Логическое программирование — это парадигма программирования , представления баз данных и знаний , основанная на формальной логике . Логическая программа — это набор предложений в логической форме, представляющий знания о некоторой проблемной области. Вычисления выполняются путем применения логических рассуждений к этим знаниям для решения проблем в предметной области. Основные семейства языков логического программирования включают Prolog , Answer Set Programming (ASP) и Datalog . Во всех этих языках правила записаны в виде предложений :
A :- B1, ..., Bn.
и читаются как повествовательные предложения в логической форме:
A if B1 and ... and Bn.
A
называется главой правила , , ..., называется телом , а литералы или условия. При n = 0 правило называется фактом и записывается в упрощенном виде:B1
Bn
Bi
A.
Запросы (или цели) имеют тот же синтаксис, что и тела правил, и обычно записываются в форме:
?- B1, ..., Bn.
В простейшем случае предложений Хорна (или «определенных» предложений) все A, B 1 , ..., B n представляют собой атомарные формулы вида p(t 1 ,..., t m ), где p — это символ-предикат, обозначающий отношение, например «материнство», а t i — это термины, обозначающие объекты (или индивидуумы). Термины включают как постоянные символы, такие как «Чарльз», так и переменные, такие как X, которые начинаются с заглавной буквы.
Рассмотрим, например, следующую программу предложений Хорна:
мать_ребёнка ( Элизабет , Чарльз ). отец_ребёнок ( Чарльз , Уильям ). отец_ребёнок ( Чарльз , Гарри ). родитель_ребенок ( X , Y ) : — мать_ребенок ( X , Y ). родитель_ребенок ( X , Y ) : — отец_ребенок ( X , Y ). дедушка_ребенок ( X , Y ) : - родительский_ребенок ( X , Z ), родительский_ребенок ( Z , Y ).
По запросу программа выдает ответы. Например ?- parent_child(X, william)
, для запроса единственным ответом является
Х = Чарльз
Можно задавать разные вопросы. Например, к программе можно запросить как создание бабушек и дедушек, так и создание внуков. Его даже можно использовать для генерации всех пар внуков, бабушек и дедушек или просто для проверки, является ли данная пара такой парой:
grandparent_child ( X , Уильям ). Х = Элизабет?- дедушка_ребенок ( Элизабет , Y ). Y = Уильям ; Y = Гарри .?- дедушка_ребенок ( X , Y ). X = Элизабет Y = Уильям ; X = Элизабет Y = Гарри .?- дедушка_ребенок ( Уильям , Гарри ). нет ?- grandparent_child ( Элизабет , Гарри ). да
Хотя логические программы предложений Хорна полны по Тьюрингу , [1] [2] для большинства практических приложений программы предложений Хорна необходимо расширять до «нормальных» логических программ с отрицательными условиями. Например, определение родственного брата использует отрицательное условие, где предикат = определяется предложением X = X:
родной брат ( X , Y ) : - родительский_ребенок ( Z , X ), родительский_ребенок ( Z , Y ), а не ( X = Y ).
Языки логического программирования, включающие отрицательные условия, обладают возможностями представления знаний немонотонной логики .
В ASP и Datalog логические программы имеют только декларативное чтение, а их выполнение осуществляется с помощью процедуры доказательства или генератора моделей, поведение которых не предназначено для контроля со стороны программиста. Однако в семействе языков Пролог логические программы также имеют процедурную интерпретацию как процедуры редукции цели. С этой точки зрения под пунктом A :- B 1 ,...,B n понимается как:
A
, решать и... и решать .B1
Bn
Отрицательные условия в телах предложений также имеют процедурную интерпретацию, известную как отрицание как отказ : отрицательный литерал not B
считается действительным тогда и только тогда, когда положительный литерал B
не выполняется.
Большая часть исследований в области логического программирования была посвящена попыткам разработать логическую семантику отрицания как неудачи, а также разработке другой семантики и других реализаций отрицания. Эти разработки, в свою очередь, сыграли важную роль в поддержке разработки формальных методов логической проверки и преобразования программ .
Использование математической логики для представления и выполнения компьютерных программ также является особенностью лямбда-исчисления , разработанного Алонзо Чёрчем в 1930-х годах. Однако первое предложение использовать клаузальную форму логики для представления компьютерных программ было сделано Корделлом Грином . [3] При этом использовалась аксиоматизация подмножества LISP вместе с представлением отношения ввода-вывода для вычисления отношения путем моделирования выполнения программы в LISP. С другой стороны, Absys Фостера и Элкока использовал комбинацию уравнений и лямбда-исчисления в языке ассертивного программирования, который не накладывает никаких ограничений на порядок выполнения операций. [4]
Логическое программирование с его нынешним синтаксисом фактов и правил можно проследить до дебатов конца 1960-х и начала 1970-х годов о декларативном и процедурном представлениях знаний в искусственном интеллекте . Сторонники декларативных представлений особенно работали в Стэнфорде , связанном с Джоном Маккарти , Бертрамом Рафаэлем и Корделлом Грином, а также в Эдинбурге с Джоном Аланом Робинсоном (академическим гостем из Сиракузского университета ), Пэтом Хейсом и Робертом Ковальски . Сторонники процессуального представительства в основном сосредоточились в Массачусетском технологическом институте под руководством Марвина Мински и Сеймура Пейперта . [5]
Несмотря на то, что Planner был основан на методах доказательства логики, он был разработан Карлом Хьюиттом из Массачусетского технологического института и стал первым языком, появившимся в рамках этой процедурной парадигмы. [6] В Planner реализован управляемый шаблонами вызов процедурных планов из целей (т. е. уменьшения цели или обратной цепочки ) и из утверждений (т. е. прямой цепочки ). Самой влиятельной реализацией Planner стало подмножество Planner, названное Micro-Planner, реализованное Джерри Сассманом , Юджином Чарняком и Терри Виноградом . Виноград использовал Micro-Planner для реализации знаковой программы понимания естественного языка SHRDLU . [7] В целях повышения эффективности Planner использовал структуру управления с возвратом, так что одновременно можно было хранить только один возможный путь вычислений. Planner дал начало языкам программирования QA4 , [8] Popler, [9] Conniver, [10] QLISP, [11] и параллельному языку Ether. [12]
Хейс и Ковальски в Эдинбурге попытались примирить основанный на логике декларативный подход к представлению знаний с процедурным подходом Планнера. Хейс (1973) разработал эквациональный язык Golux, в котором различные процедуры можно было получить, изменяя поведение средства доказательства теорем. [13]
Тем временем Ален Кольмерауэр в Марселе работал над пониманием естественного языка , используя логику для представления семантики и используя разрешение для ответов на вопросы. Летом 1971 года Кольмерауэр пригласил Ковальского в Марсель, и вместе они обнаружили, что клаузальная форма логики может использоваться для представления формальных грамматик и что средства доказательства теорем разрешения могут использоваться для синтаксического анализа. Они заметили, что некоторые средства доказательства теорем, такие как гиперразрешение [14] , ведут себя как синтаксические анализаторы снизу вверх, а другие, такие как разрешение SL (1971) [15], ведут себя как анализаторы сверху вниз.
Следующим летом 1972 года Ковальский, снова работая с Кольмерауэром, разработал процедурную интерпретацию импликаций в клаузальной форме. Также стало ясно, что такие предложения могут быть ограничены определенными предложениями или предложениями Хорна , и что разрешение SL может быть ограничено (и обобщено) резолюцией SLD . Процедурная интерпретация Ковальского и SLD были описаны в записке 1973 года, опубликованной в 1974 году. [16]
Кольмерауэр вместе с Филиппом Русселем использовали процедурную интерпретацию в качестве основы Пролога, который был реализован летом и осенью 1972 года. Первая программа Пролога, также написанная в 1972 году и реализованная в Марселе, представляла собой французскую вопросно-ответную систему. Использование Пролога в качестве практического языка программирования получило большой импульс благодаря разработке Дэвидом Уорреном в Эдинбурге в 1977 году компилятора. Эксперименты показали, что Эдинбургский Пролог может конкурировать по скорости обработки с другими языками символьного программирования , такими как Лисп . [17] Эдинбургский Пролог стал стандартом де-факто и сильно повлиял на определение стандарта ISO Пролог.
Логическое программирование привлекло международное внимание в 1980-х годах, когда Министерство международной торговли и промышленности Японии выбрало его для разработки программного обеспечения для проекта компьютерных систем пятого поколения (FGCS). Целью проекта FGCS было использование логического программирования для разработки передовых приложений искусственного интеллекта на компьютерах с массовым параллелизмом . Хотя изначально в проекте изучалось использование Пролога, позже было принято использование параллельного логического программирования , поскольку оно было ближе к компьютерной архитектуре FGCS.
Однако функция обязательного выбора в параллельном логическом программировании мешала логической семантике языка [18] и его пригодности для представления знаний и приложений для решения проблем. Более того, параллельные компьютерные системы, разработанные в рамках проекта, не смогли конкурировать с достижениями, имеющими место в разработке более традиционных компьютеров общего назначения. Вместе эти две проблемы привели к тому, что проект FGCS не смог достичь своих целей. Интерес как к логическому программированию, так и к искусственному интеллекту упал во всем мире. [19]
Тем временем более декларативные подходы к логическому программированию, в том числе основанные на использовании Пролога, продолжали развиваться независимо от проекта FGCS. В частности, хотя Пролог был разработан для объединения декларативных и процедурных представлений знаний, чисто декларативная интерпретация логических программ стала в центре внимания приложений в области дедуктивных баз данных . Работа в этой области стала заметной примерно в 1977 году, когда Эрве Галлер и Джек Минкер организовали в Тулузе семинар по логике и базам данных. [20] В конечном итоге это поле было переименовано в Datalog .
Этот акцент на логическом, декларативном чтении логических программ получил дополнительный импульс благодаря развитию логического программирования с ограничениями в 1980-х годах и программирования наборов ответов в 1990-х годах. Ему также уделяется новое внимание в недавних приложениях Пролога [21].
Ассоциация логического программирования (ALP) была основана в 1986 году для продвижения логического программирования. Его официальным журналом до 2000 года был «Журнал логического программирования» . Его главным редактором-основателем был Дж. Алан Робинсон . [22] В 2001 году журнал был переименован в The Journal of Logic and Algebraic Programming , а официальным журналом ALP стала Theory and Practice of Logic Programming , издаваемая издательством Cambridge University Press .
Логические программы обладают богатым разнообразием семантики и методов решения проблем, а также широким спектром приложений в программировании, базах данных, представлении знаний и решении проблем.
Процедурная интерпретация логических программ, использующая обратные рассуждения для сведения целей к подцелям, представляет собой частный случай использования стратегии решения задач для управления использованием декларативного, логического представления знаний для получения поведения алгоритма . В более общем смысле, к одному и тому же логическому представлению можно применять разные стратегии решения проблем для получения разных алгоритмов. Альтернативно, разные алгоритмы могут быть получены с заданной стратегией решения проблем, используя разные логические представления. [23]
Двумя основными стратегиями решения проблем являются обратное рассуждение (снижение цели) и прямое рассуждение , также известное как рассуждение сверху вниз и снизу вверх соответственно.
В простом случае пропозициональной программы предложения Хорна и атомарной цели верхнего уровня обратные рассуждения определяют дерево «и-или» , которое образует пространство поиска для решения цели. Цель верхнего уровня — это корень дерева. Для любого узла в дереве и любого предложения, заголовок которого соответствует этому узлу, существует набор дочерних узлов, соответствующих подцелям в теле предложения. Эти дочерние узлы сгруппированы вместе с помощью «и». Альтернативные наборы дочерних элементов, соответствующие альтернативным способам решения узла, группируются вместе с помощью «или».
Для поиска в этом пространстве можно использовать любую стратегию поиска. Пролог использует последовательную стратегию поиска с возвратом «последним пришел — первым вышел», в которой одновременно рассматриваются только одна альтернатива и одна подцель. Например, подцели можно решать параллельно, а также параллельно отрабатывать пункты. Первая стратегия называетсяи-параллельно , а вторая стратегия называетсяили-параллельно . Возможны и другие стратегии поиска, такие как интеллектуальный поиск с возвратом[24]или поиск по принципу «сначала лучшее» для нахождения оптимального решения[25]
В более общем, непропозициональном случае, когда подцели могут иметь общие переменные, можно использовать другие стратегии, например, выбор подцели, которая наиболее конкретизирована или достаточно конкретизирована, чтобы применима только одна процедура. [26] Такие стратегии используются, например, в параллельном логическом программировании .
В большинстве случаев обратное рассуждение на основе запроса или цели более эффективно, чем прямое рассуждение. Но иногда при программировании журнала данных и набора ответов может не быть запроса, отдельного от набора предложений в целом, и тогда создание всех фактов, которые могут быть получены из предложений, является разумной стратегией решения проблем. Вот еще один пример, где прямое рассуждение превосходит обратное рассуждение в более традиционной вычислительной задаче, цель которой ?- fibonacci(n, Result)
— найти n- е число Фибоначчи:
Фибоначчи ( 0 , 0 ). Фибоначчи ( 1 , 1 ).фибоначчи ( N , Результат ) : - N > 1 , N1 равно N - 1 , N2 равно N - 2 , фибоначчи ( N1 , F1 ), фибоначчи ( N2 , F2 ), Результат равен 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 n . Напротив, прямое рассуждение генерирует последовательность чисел Фибоначчи, начиная с 0 и 1, без каких-либо повторных вычислений, и его сложность линейна по отношению к n.
Пролог не может выполнять прямые рассуждения напрямую. Но можно добиться эффекта прямого рассуждения в контексте обратного рассуждения посредством табличного представления : подцели сохраняются в таблице вместе с их решениями. Если подцель встречается повторно, она решается напрямую с использованием решений, уже имеющихся в таблице, вместо повторного решения подцелей. [27]
Логическое программирование можно рассматривать как обобщение функционального программирования, в котором функции являются частным случаем отношений. [28] Например, функция мать(X) = Y (каждый X имеет только одну мать Y) может быть представлена отношением мать(X, Y). В этом отношении логические программы похожи на реляционные базы данных , которые также представляют функции как отношения.
По сравнению с реляционным синтаксисом функциональный синтаксис более компактен для вложенных функций. Например, в функциональном синтаксисе определение бабушки по материнской линии можно записать во вложенной форме:
maternal_grandmother ( X ) = мать ( мать ( X )).
То же определение в реляционной нотации необходимо записать в невложенной, сплющенной форме:
maternal_grandmother ( X , Y ) :- мать ( X , Z ), мать ( Z , Y ).
Однако вложенный синтаксис можно рассматривать как синтаксический сахар для невложенного синтаксиса. Ciao Prolog, например, преобразует функциональный синтаксис в реляционную форму и выполняет полученную логическую программу, используя стандартную стратегию выполнения Пролога. [29] Более того, то же преобразование можно использовать для выполнения вложенных отношений, которые не являются функциональными. Например:
дедушка ( X ) := родитель ( родитель ( X )). родитель ( X ) := мать ( X ). родитель ( X ) := отец ( X ).мать ( Чарльз ) := Элизабет . отец ( Чарльз ) := Филипп . мать ( Гарри ) := Диана . отец ( Гарри ) := Чарльз .?- дедушка ( X , Y ). X = Гарри , Y = Элизабет . X = Гарри , Y = Филипп .
Термин «реляционное программирование» использовался для обозначения множества языков программирования, в которых функции рассматриваются как частный случай отношений. Некоторые из этих языков, такие как miniKanren [28] и реляционное линейное программирование [30], являются языками логического программирования в смысле этой статьи.
Однако реляционный язык RML является императивным языком программирования [31] , основной конструкцией которого является реляционное выражение, подобное выражению в логике предикатов первого порядка.
Другие языки реляционного программирования основаны на реляционном исчислении [32] или реляционной алгебре. [33]
С чисто логической точки зрения существует два подхода к декларативной семантике логических программ предложений Хорна . программа.
В этом подходе вычисления доказывают теоремы в логике первого порядка ; и как обратные рассуждения , как при разрешении SLD, так и прямые рассуждения , как при гиперразрешении, являются правильными и полными методами доказательства теорем. Иногда такие методы доказательства теорем также рассматриваются как обеспечивающие отдельную теоретико-доказательную (или операционную) семантику для логических программ. Но с логической точки зрения это скорее методы доказательства, чем семантика.
Другой подход к декларативной семантике программ предложений Хорна — это семантика выполнимости , которая понимает решение цели как демонстрацию того, что цель истинна (или удовлетворена) в некоторой предполагаемой (или стандартной) модели программы. Для программ предложений Хорна всегда существует такая стандартная модель: это уникальная минимальная модель программы.
Неформально говоря, минимальная модель — это модель, которая, если ее рассматривать как набор всех (без переменных) фактов, которые верны в модели, содержит не меньший набор фактов, который также является моделью программы.
Например, следующие факты представляют собой минимальную модель семейных отношений, приведенную во введении к этой статье. Все остальные факты без переменных в модели ложны:
мать_ребёнка ( Элизабет , Чарльз ). отец_ребёнок ( Чарльз , Уильям ). отец_ребёнок ( Чарльз , Гарри ). родитель_ребенок ( Элизабет , Чарльз ). родитель_ребенок ( Чарльз , Уильям ). родитель_ребенок ( Чарльз , Гарри ). grandparent_child ( Элизабет , Уильям ). grandparent_child ( Элизабет , Гарри ).
Семантика выполнимости также имеет альтернативную, более математическую характеристику как наименее фиксированную точку функции, которая использует правила программы для получения новых фактов из существующих фактов за один шаг вывода.
Примечательно, что одни и те же методы решения проблем, такие как прямое и обратное рассуждение, которые изначально были разработаны для семантики логических следствий, в равной степени применимы и к семантике выполнимости: прямое рассуждение генерирует минимальную модель программы предложений Хорна, извлекая новые факты из существующих. фактов до тех пор, пока не будут созданы новые дополнительные факты. Обратное рассуждение, которое успешно сводит цель к подцелям до тех пор, пока все подцели не будут решены с помощью фактов, гарантирует, что цель верна в минимальной модели, без явного создания модели. [34]
Разницу между двумя декларативными семантиками можно увидеть с помощью определений сложения и умножения в последующей арифметике , которая представляет натуральные числа 0, 1, 2, ...
как последовательность членов формы 0, s(0), s(s(0)), ...
. В общем, этот термин s(X)
представляет собой преемника X,
именно X + 1.
Вот стандартные определения сложения и умножения в функциональной записи:
Х + 0 = Х. Х + s(Y) = s(X + Y).т.е. X + (Y + 1) = (X + Y) + 1 Х × 0 = 0. X × s(Y) = X + (X × Y).т.е. X × (Y + 1) = X + (X × Y).
Вот те же определения, что и в логической программе, которые используются add(X, Y, Z)
для представления X + Y = Z,
и multiply(X, Y, Z)
для представления X × Y = Z
:
добавить ( Икс , 0 , Икс ). добавить ( X , s ( Y ), s ( Z )) :- добавить ( X , Y , Z ).умножить ( X , 0 , 0 ). умножить ( X , s ( Y ), W ) :- умножить ( X , Y , Z ), сложить ( X , Z , W ).
Обе декларативные семантики дают одни и те же ответы для одних и тех же экзистенциально квантифицированных соединений целей сложения и умножения. Например, 2 × 2 = X
есть решение X = 4
; и X × X = X + X
имеет два решения X = 0
и X = 2
:
?- умножить ( s ( s ( 0 )), s ( s ( 0 )), X ). Икс = s ( s ( s ( s ( 0 )))).?- умножить ( X , X , Y ), сложить ( 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)))))),
ie 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 оставалась нерешенной до тех пор , пока Кейт Кларк [35] не показал, что при определенных естественных условиях NAF является эффективным, правильным (а иногда и полным) способом рассуждения с семантикой логических последствий, использующим завершение логической программы в первую очередь. логика заказа.
Завершение примерно равнозначно набору всех предложений программы с одним и тем же предикатом в заголовке, скажем:
A :- Body1.
...
A :- Bodyk.
как определение сказуемого:
A iff (Body1 or ... or Bodyk)
где iff
означает «тогда и только если». В пополнение также входят аксиомы равенства, соответствующие унификации . Кларк показал, что доказательства, генерируемые SLDNF, структурно аналогичны доказательствам, генерируемым методом естественной дедукции после завершения программы.
Рассмотрим, например, следующую программу:
must_receive_sanction ( X , наказание ) :- is_a_thief ( X ), а не must_receive_sanction ( X , реабилитация ). must_receive_sanction ( X , реабилитация ) :- is_a_thief ( X ), is_a_minor ( X ), а не is_violent ( X ). is_a_thief ( том ).
Учитывая цель определения того, должен ли Том получить санкцию, первое правило успешно показывает, что Том должен быть наказан:
?- must_receive_sanction ( том , Санкция ). Санкция = наказание .
Это потому, что Том — вор, и нельзя доказать, что Тома следует реабилитировать. Невозможно доказать, что Тома следует реабилитировать, потому что нельзя доказать, что Том несовершеннолетний.
Однако если мы получим новую информацию о том, что Том действительно несовершеннолетний, предыдущий вывод о том, что Том должен быть наказан, заменяется новым выводом о том, что Тома следует реабилитировать:
минор ( том ).?- must_receive_sanction ( том , Санкция ). Санкция = реабилитация .
Это свойство отзыва вывода при добавлении новой информации называется немонотонностью и делает логическое программирование немонотонной логикой .
Но если нам теперь скажут, что Том жесток, вывод о том, что Том должен быть наказан, будет восстановлен:
жестокий ( Том ).?- must_receive_sanction ( том , Санкция ). Санкция = наказание .
Завершение этой программы:
must_receive_sanction ( X , Sanction ) тогда и только тогда, когда Sanction = наказание , is_a_thief ( X ), not must_receive_sanction ( X , реабилитация ) или Sanction = реабилитация , is_a_thief ( X ), is_a_minor ( X ), а не is_violent ( X ). is_a_thief ( X ) тогда и только тогда, когда X = tom . is_a_minor ( X ) тогда и только тогда, когда X = tom . is_violent ( X ) тогда и только тогда, когда X = tom .
Понятие завершения тесно связано с семантикой ограничения Джона Маккарти для рассуждений по умолчанию [36] и с предположением Рэя Рейтера о закрытом мире . [37]
Семантика завершения для отрицания представляет собой семантику логического следствия, для которой SLDNF обеспечивает теоретико-доказательную реализацию. Однако в 1980-е годы семантика выполнимости стала более популярной для логических программ с отрицанием. В семантике выполнимости отрицание интерпретируется в соответствии с классическим определением истины в предполагаемой или стандартной модели логической программы.
В случае логических программ с отрицательными условиями существует два основных варианта семантики выполнимости: В обоснованной семантике предполагаемая модель логической программы представляет собой уникальную трехзначную минимальную модель, которая существует всегда. Обоснованная семантика обобщает понятие индуктивного определения в математической логике. [38] XSB Prolog [39] реализует обоснованную семантику, используя разрешение SLG. [40]
В альтернативной семантике стабильной модели может не быть намеченных моделей или несколько предполагаемых моделей, все из которых минимальны и двузначны. Семантика стабильной модели лежит в основе программирования набора ответов (ASP).
Как обоснованная, так и устойчивая семантика модели применима к произвольным логическим программам с отрицанием. Однако для программ стратифицированной логики обе семантики совпадают. Например, программа наказания воров (локально) стратифицирована, и все три семантики программы определяют одну и ту же предполагаемую модель:
must_receive_sanction ( том , наказание ). is_a_thief ( том ). is_a_minor ( том ). is_violent ( Том ).
Попытки понять отрицание в логическом программировании также способствовали развитию абстрактных структур аргументации . [41] В аргументационной интерпретации отрицания первоначальный аргумент о том, что Том должен быть наказан, потому что он вор, подвергается нападению со стороны аргумента о том, что его следует реабилитировать, потому что он несовершеннолетний. Но тот факт, что Том склонен к насилию, подрывает аргумент о том, что Тома следует реабилитировать, и восстанавливает аргумент о том, что Тома следует наказать.
Метапрограммирование , при котором программы рассматриваются как данные, уже было особенностью ранних реализаций Пролога. [42] [43] Например, реализация Пролога в Эдинбурге DEC10 включала «интерпретатор и компилятор, оба написанные на самом Прологе». [43] Простейшей метапрограммой является так называемый « ванильный » метаинтерпретатор:
решить ( верно ). решить (( Б , С )):- решить ( Б ), решить ( С ). решить ( A ):- пункт ( A , B ), решить ( B ).
где true представляет собой пустой союз, а (B,C) — составной термин, представляющий союз B и C. Предикатное предложение (A,B) означает, что существует предложение формы A :- B.
Метапрограммирование — это применение более общего использования металогики или метаязыка для описания и рассуждений о другом языке, называемом объектным языком .
Металогическое программирование позволяет комбинировать представления на уровне объекта и на метауровне, как в естественном языке. Например, в следующей программе атомарная формула attends(Person, Meeting)
встречается и как формула уровня объекта, и как аргумент метапредикатов prohibited
иapproved.
запрещено ( посещает ( Человек , Собрание )) :- не ( разрешено ( посещает ( Человек , Собрание )))).must_receive_sanction ( Человек , ругание ) :- посещает ( Человек , Встреча ), высокое ( Человек ), запрещено ( посещает ( Человек , Встреча )). must_receive_sanction ( Человек , изгнание ) :- посещает ( Человек , Встреча ), смиренно ( Человек ), запрещено ( посещает ( Человек , Встреча )).одобрено ( присутствует ( алиса , tea_party )). посещает ( mad_hatter , tea_party ). посещает ( соня , чаепитие ).высокий ( mad_hatter ). скромный ( соня ).?- must_receive_sanction ( X , Y ). Человек = mad_hatter , Санкция = ругань . Человек = соня , Санкция = изгнание .
В своем популярном «Введении в когнитивную науку» [44] Пол Тагард рассматривает логику и правила как альтернативные подходы к моделированию человеческого мышления. Он утверждает, что правила, имеющие форму ЕСЛИ условие, ТО действие , «очень похожи» на логические условные предложения, но они проще и имеют большую психологическую правдоподобность (стр. 51). Среди других различий между логикой и правилами он утверждает, что логика использует дедукцию, а правила используют поиск (стр. 45) и могут использоваться для рассуждений как в прямом, так и в обратном направлении (стр. 47). Предложения в логике «должны интерпретироваться как универсально истинные », но правила могут быть значениями по умолчанию , допускающими исключения (стр. 44).
Он утверждает, что «в отличие от логики, системы, основанные на правилах, также могут легко представлять стратегическую информацию о том, что делать» (стр. 45). Например: «ЕСЛИ ты хочешь поехать домой на выходные и у тебя есть билет на автобус, ТОГДА ты можешь сесть на автобус». Он не замечает, что та же самая стратегия сведения цели к подцелям может быть интерпретирована в духе логического программирования как применение обратного рассуждения к логическому условию:
can_go ( ты , домой ) :- есть ( ты , bus_fare ), поймать ( ты , автобус ).
Все эти характеристики систем, основанных на правилах — поиск, прямое и обратное рассуждение, рассуждение по умолчанию и сокращение целей — также являются определяющими характеристиками логического программирования. Это предполагает, что вывод Тагарда (стр. 56) о том, что:
Большая часть человеческих знаний естественным образом описывается в терминах правил, и многие виды мышления, такие как планирование, могут быть смоделированы с помощью систем, основанных на правилах.
также применимо к логическому программированию.
Другие аргументы, показывающие, как логическое программирование можно использовать для моделирования аспектов человеческого мышления, представлены Кейтом Стеннингом и Михиэлем ван Ламбалгеном в их книге «Человеческое мышление и когнитивная наука». [45] Они показывают, как немонотонный характер логических программ можно использовать для объяснения действий человека при решении различных психологических задач. Они также показывают (стр. 237), что «рассуждения в закрытом мире под видом логического программирования имеют привлекательную нейронную реализацию, в отличие от классической логики».
В книге «Правильная обработка событий» [46] Михель ван Ламбалген и Фриц Хамм исследуют использование логического программирования с ограничениями для кодирования «временных понятий на естественном языке, глядя на то, как люди конструируют время».
Использование логики для представления процедурных знаний и стратегической информации было одной из основных целей, способствующих раннему развитию логического программирования. Более того, он продолжает оставаться важной особенностью семейства языков логического программирования Пролог и сегодня. Однако многие приложения логического программирования, включая приложения Пролога, все больше сосредотачиваются на использовании логики для представления чисто декларативных знаний. Эти приложения включают в себя как представление общих знаний , так и представление знаний в конкретной области .
Здравый смысл включает в себя знания о причине и следствии, формализованные, например, в исчислении ситуаций , исчислении событий и языках действий . Приведем упрощенный пример, иллюстрирующий основные особенности таких формализмов. Первое предложение гласит, что факт имеет место сразу после того, как событие инициирует (или вызывает) этот факт. Второе предложение представляет собой аксиому фрейма , которая гласит, что факт, который имеет место в определенный момент времени, продолжает сохраняться и в следующий раз, если он не будет прерван событием, которое произойдет в данный момент. Эта формулировка позволяет одновременно произойти более чем одному событию:
удерживается ( Факт , Время2 ) :- происходит ( Событие , Время1 ), Время2 равно Времени1 + 1 , инициируется ( Событие , Факт ). удерживается ( Факт , Время2 ) :- происходит ( Событие , Время1 ), Время2 равно Времени1 + 1 , удерживается ( Факт , Время1 ), не ( прекращается ( Факт , Время1 )).прекращено ( Факт , Время ) :- происходит ( Событие , Время ), завершается ( Событие , Факт ).
Вот holds
метапредикат, аналогичный solve
приведенному выше. Однако, хотя solve
у него только один аргумент, который применяется к общим предложениям, первый аргумент holds
— это факт, а второй аргумент — время (или состояние). Атомная формула holds(Fact, Time)
выражает, что Fact
справедливо при Time
. Такие изменяющиеся во времени факты еще называют флюэнтами . Атомная формула happens(Event, Time)
выражает, что Событие происходит в Time
.
Следующий пример иллюстрирует, как эти предложения можно использовать для рассуждения о причинно-следственной связи в мире игрушечных кубиков . Здесь в исходном состоянии в момент времени 0 зеленый блок находится на столе, а красный блок уложен на зеленый блок (как светофор). В момент времени 0 красный блок перемещается на стол. В момент 1 зеленый блок перемещается на красный блок. Перемещение объекта на место прекращает факт нахождения объекта на каком-либо месте и инициирует факт нахождения объекта на том месте, куда его перемещают:
содержит ( on ( green_block , table ), 0 ). содержит ( on ( red_block , green_block ), 0 ).происходит ( move ( red_block , table ), 0 ). происходит ( move ( green_block , red_block ), 1 ).инициирует ( move ( Object , Place ), on ( Object , Place )). завершается ( move ( Object , Place2 ), on ( Object , Place1 )).?- выполняется ( Факт , Время ).Факт = включен ( green_block , таблица ), Время = 0. Факт = включен ( red_block , green_block ), Время = 0. Факт = включен ( green_block , таблица ), Время = 1. Факт = включен ( red_block , таблица ), Время = 1. Факт = включено ( green_block , red_block ), Время = 2. Факт = включено ( red_block , таблица ), Время = 2.
Прямые и обратные рассуждения дают одинаковые ответы на цель holds(Fact, Time)
. Но прямое рассуждение генерирует беглые слова постепенно во временном порядке, а обратное рассуждение генерирует беглые слова регрессивно , как в случае использования регрессии для конкретной предметной области в ситуационном исчислении . [47]
Логическое программирование также оказалось полезным для представления экспертных систем в экспертных системах . [48] Но человеческий опыт, как и здравый смысл общего назначения, по большей части является неявным и неявным , и часто трудно представить такое неявное знание в явных правилах. Однако эта трудность не возникает, когда логические программы используются для представления существующих явных правил деловой организации или юридического органа.
Например, вот упрощенная версия первого предложения Закона о британском гражданстве, в котором говорится, что человек, родившийся в Великобритании, становится британским гражданином в момент рождения, если родитель этого человека является британцем. гражданин на момент рождения:
инициирует ( рождение ( Person ), гражданин ( Person , uk )):- time_of ( рождение ( Person ), Time ), место_of ( рождение ( Person ), uk ), родительский_ребенок ( Another_Person , Person ), удерживает ( гражданин ( Another_Person , uk ) ), Время ).
Исторически сложилось так, что представление значительной части Закона о британском гражданстве в виде логической программы в 1980-х годах [49] «оказало огромное влияние на развитие компьютерных представлений законодательства, показав, как логическое программирование обеспечивает интуитивно привлекательные представления, которые могут быть непосредственно использованы в генерировать автоматические выводы». [50]
Совсем недавно система PROLEG, [51] созданная в 2009 году и состоящая примерно из 2500 правил и исключений из гражданского кодекса и правил Верховного суда Японии, стала, возможно, крупнейшей базой правовых норм в мире. [52]
Правило вывода SLD нейтрально в отношении порядка, в котором подцели в телах предложений могут быть выбраны для решения. Ради эффективности Пролог ограничивает этот порядок порядком записи подцелей. SLD также нейтрально относится к стратегии поиска в пространстве доказательств SLD. Пролог просматривает это пространство сверху вниз, в глубину, пробуя разные предложения для решения одной и той же (под)цели в том порядке, в котором они написаны.
Преимущество этой стратегии поиска состоит в том, что текущая ветвь дерева может быть эффективно представлена стеком . Когда предложение цели на вершине стека сокращается до нового предложения цели, новое предложение цели помещается на вершину стека. Когда выбранная подцель в предложении цели наверху стека не может быть решена, стратегия поиска возвращается назад , удаляя предложение цели из вершины стека и повторяя попытку решения выбранной подцели в предыдущем предложении цели, используя следующее предложение, соответствующее выбранной подцели.
Обратный поиск можно ограничить с помощью подцели, называемой Cut и записываемой как !, которая всегда завершается успешно, но не может быть возвращена. Сокращения можно использовать для повышения эффективности, но они также могут влиять на логический смысл предложений. Во многих случаях использование отсечения может быть заменено отрицанием как неудачей. Фактически, отрицание как неудача может быть определено в Прологе, используя Cut вместе с любым литералом, скажем, Fail , который объединяется с заголовком предложения no:
не ( P ) :- P , !, провалиться . нет ( П ).
Пролог помимо вырезания предоставляет и другие возможности, не имеющие логической интерпретации. К ним относятся встроенные предикаты Assert и Retract для деструктивного обновления состояния программы во время ее выполнения.
Например, приведенный выше пример мира игрушечных блоков можно реализовать без аксиом фрейма, используя деструктивное изменение состояния:
включен ( green_block , таблица ). включен ( красный_блок , зеленый_блок ).перемещение ( Объект , Место2 ) : - отвести ( Вкл ( Объект , Место1 )), утвердить ( Вкл ( Объект , Место2 ).
Последовательность событий перемещения и результирующее расположение блоков можно вычислить, выполнив запрос:
?- переместить ( red_block , table ), переместить ( green_block , red_block ), on ( Object , Place ).Объект = red_block , Место = таблица . Объект = green_block , Место = red_block .
Различные расширения логического программирования были разработаны, чтобы обеспечить логическую основу для такого деструктивного изменения состояния. [53] [54] [55]
Широкий спектр приложений Пролога, как изолированно, так и в сочетании с другими языками, освещен в Книге Года Пролога [21] , посвященной 50-летнему юбилею Пролога в 2022 году.
Пролог также внес свой вклад в разработку других языков программирования, включая ALF , Fril , Gödel , Mercury , Oz , Ciao , Visual Prolog , XSB и λProlog .
Логическое программирование с ограничениями (CLP) сочетает в себе логическое программирование предложений Хорна с решением ограничений . Он расширяет предложения Хорна, позволяя некоторым предикатам, объявленным как предикаты ограничений, появляться в теле предложения как литералы. Предикаты ограничений не определяются фактами и правилами в программе, но предопределены некоторой специфичной для предметной области теоретико-модельной структурой или теорией.
Процедурно, подцели, предикаты которых определены программой, решаются путем редукции цели, как в обычном логическом программировании, но ограничения упрощаются и проверяются на выполнимость с помощью специфичного для предметной области решателя ограничений, который реализует семантику предикатов ограничений. Исходная задача решается путем сведения ее к выполнимой комбинации ограничений.
Интересно, что первая версия Пролога уже включала предикат ограничения dif(term1, term2) из докторской диссертации Филиппа Русселя 1972 года, который завершается успешно, если оба его аргумента являются разными терминами, но задерживается, если любой из терминов содержит переменную. [52]
Следующая программа логики ограничений представляет собой игрушечную темпоральную базу данных john's
истории учителя:
учит ( Джон , аппаратное обеспечение , T ) : - 1990 ≤ T , T < 1999. учит ( Джон , программное обеспечение , T ) : - 1999 ≤ T , T < 2005. учит ( Джон , логика , T ) : - 2005 ≤ T , Т ≤ 2012. ранг ( джон , преподаватель , Т ) : - 1990 ≤ Т , Т < 2010. ранг ( джон , профессор , Т ) : - 2010 ≤ Т , Т < 2014.
Здесь ≤
и <
— предикаты ограничений с их обычной семантикой. Следующее предложение цели запрашивает базу данных, чтобы узнать, когда john
оба были обучены logic
и были professor
:
?- учит ( джон , логика , Т ), звание ( джон , профессор , Т ).
Решение 2010 ≤ T, T ≤ 2012
является результатом упрощения ограничений2005 ≤ T, T ≤ 2012, 2010 ≤ T, T < 2014.
Программирование логики ограничений использовалось для решения проблем в таких областях, как гражданское строительство , машиностроение , проверка цифровых схем , автоматическое составление расписаний , управление воздушным движением и финансы. Оно тесно связано с абдуктивным логическим программированием .
Datalog — это язык определения базы данных, который сочетает в себе реляционное представление данных, как в реляционных базах данных , с логическим представлением, как в логическом программировании.
Реляционные базы данных используют реляционное исчисление или реляционную алгебру с реляционными операциями , такими как объединение , пересечение , разность множеств и декартово произведение , для определения запросов, которые обращаются к базе данных. Datalog использует логические связки , такие как или , а не в телах правил для определения отношений как части самой базы данных.
На ранних этапах разработки реляционных баз данных было признано, что рекурсивные запросы не могут быть выражены ни в реляционной алгебре, ни в реляционном исчислении, и что этот недостаток можно устранить, введя оператор наименьшей фиксированной точки. [56] [57] Напротив, рекурсивные отношения могут быть определены естественным образом с помощью правил в логических программах без необходимости использования каких-либо новых логических связок или операторов.
Журнал данных отличается от более общего логического программирования тем, что в качестве терминов используются только константы и переменные. Более того, все факты не содержат переменных, а правила ограничены, так что если они выполняются снизу вверх, то производные факты также не содержат переменных.
Например, рассмотрим семейную базу данных:
мать_ребенка ( Элизабет , Чарльз ). отец_ребенок ( Чарльз , Уильям ). отец_ребёнок ( Чарльз , Гарри ). родитель_ребенок ( X , Y ) : — мать_ребенок ( X , Y ). родитель_ребенок ( X , Y ) : — отец_ребенок ( X , Y ). предок_потомок ( X , Y ) : - родительский_ребенок ( X , X ). ancestor_descendant ( X , Y ) :- ancestor_descendant ( X , Z ), ancestor_descendant ( Z , Y ).
Выполнение «снизу вверх» получает следующий набор дополнительных фактов и завершается:
родитель_ребенок ( Элизабет , Чарльз ). родитель_ребенок ( Чарльз , Уильям ). родитель_ребенок ( Чарльз , Гарри ).ancestor_descendant ( Элизабет , Чарльз ). ancestor_descendant ( Чарльз , Уильям ). ancestor_descendant ( Чарльз , Гарри ).ancestor_descendant ( Элизабет , Уильям ). ancestor_descendant ( Элизабет , Гарри ).
Выполнение сверху вниз дает те же ответы на запрос:
?- предок_потомок ( X , Y ).
Но затем это переходит в бесконечный цикл. Однако выполнение сверху вниз с табличным представлением дает те же ответы и завершается без цикла.
Как и журнал данных, программирование набора ответов (ASP) не является полным по Тьюрингу. Более того, вместо того, чтобы отделять цели (или запросы) от программы, которая будет использоваться для решения целей, ASP рассматривает всю программу как цель и решает цель, создавая стабильную модель, которая делает цель истинной. Для этой цели используется семантика стабильной модели , согласно которой логическая программа может иметь ноль, одну или несколько предполагаемых моделей. Например, следующая программа представляет собой вырожденный вариант задачи раскраски карты, заключающейся в окраске двух стран в красный или зеленый цвет:
страна ( унция ). страна ( из ). соседний ( унция , из ). цвет ( C , красный ) :- страна ( C ), не ( цвет ( C , зеленый )). цвет ( C , зеленый ) :- страна ( C ), не ( цвет ( C , красный )).
Задача имеет четыре решения, представленные четырьмя устойчивыми моделями:
страна ( унция ). страна ( из ). соседний ( унция , из ). цвет ( унция , красный ). цвет ( из , красный ).страна ( унция ). страна ( из ). соседний ( унция , из ). цвет ( унция , зеленый ). цвет ( из , зеленый ).страна ( унция ). страна ( из ). соседний ( унция , из ). цвет ( унция , красный ). цвет ( из , зеленый ).страна ( унция ). страна ( из ). соседний ( унция , из ). цвет ( унция , зеленый ). цвет ( из , красный ).
Чтобы представить стандартную версию задачи раскраски карты, нам нужно добавить ограничение, согласно которому две соседние страны не могут быть окрашены в один и тот же цвет. В ASP это ограничение можно записать в виде предложения вида:
:- страна ( C1 ), страна ( C2 ), соседняя ( C1 , C2 ), цвет ( C1 , X ), цвет ( C2 , X ).
С добавлением этого ограничения проблема теперь имеет только два решения:
страна ( унция ). страна ( из ). соседний ( унция , из ). цвет ( унция , красный ). цвет ( из , зеленый ).страна ( унция ). страна ( из ). соседний ( унция , из ). цвет ( унция , зеленый ). цвет ( из , красный ).
Добавление ограничений формы :- Body.
исключает модели, в которых Body
верно.
Как ни странно, ограничения в ASP отличаются от ограничений в CLP . Ограничения в CLP — это предикаты, которые определяют ответы на запросы (и решения целей). Ограничения в ASP — это положения, исключающие модели, которые в противном случае удовлетворяли бы целям. Ограничения в ASP аналогичны ограничениям целостности в базах данных.
Эта комбинация обычных предложений логического программирования и предложений ограничений иллюстрирует методологию создания и тестирования решения проблем в ASP: обычные предложения определяют пространство поиска возможных решений, а ограничения отфильтровывают нежелательные решения. [58]
Большинство реализаций ASP выполняются в два этапа: сначала они реализуют программу всеми возможными способами, сводя ее к программе пропозициональной логики (известной как заземление ). Затем они применяют решатель задач пропозициональной логики, такой как алгоритм DPLL или булев решатель SAT . Однако в некоторых реализациях, таких как s(CASP) [59], используется целенаправленная нисходящая процедура, подобная разрешению SLD, без заземления.
Абдуктивное логическое программирование [60] (ALP), как и CLP, расширяет обычное логическое программирование, позволяя телам предложений содержать литералы, предикаты которых не определены предложениями. В ALP эти предикаты объявляются как абдуктивные (или предполагаемые ) и используются, как и в абдуктивных рассуждениях , для объяснения наблюдений или, в более общем плане, для добавления в программу новых фактов (в качестве предположений) для решения целей.
Например, предположим, что нам дано начальное состояние, в котором красный блок находится на зеленом блоке стола в момент 0:
содержит ( on ( green_block , table ), 0 ). содержит ( on ( red_block , green_block ), 0 ).
Предположим, нам также задана цель:
?- держит ( on ( green_block , red_block ), 3 ), держит ( on ( red_block , table ), 3 ).
Цель может представлять собой наблюдение, и в этом случае решением является объяснение наблюдения. Или цель может представлять собой желаемое будущее положение дел, и в этом случае решением является план достижения цели. [61]
Мы можем использовать правила причины и следствия, представленные ранее, для решения цели, рассматривая предикат happens
как сводимый:
удерживается ( Факт , Время2 ) :- происходит ( Событие , Время1 ), Время2 равно Времени1 + 1 , инициируется ( Событие , Факт ). удерживается ( Факт , Время2 ) :- происходит ( Событие , Время1 ), Время2 равно Времени1 + 1 , удерживается ( Факт , Время1 ), не ( прекращается ( Факт , Время1 )). прекращено ( Факт , Время ) :- происходит ( Событие , Время ), завершается ( Событие , Факт ).инициирует ( move ( Object , Place ), on ( Object , Place )). завершается ( move ( Object , Place2 ), on ( Object , Place1 )).
ALP решает цель, рассуждая в обратном порядке и добавляя в программу предположения для решения сводимых подцелей. В этом случае существует множество альтернативных решений, в том числе:
происходит ( move ( red_block , table ), 0 ). происходит ( галочка , 1 ). происходит ( move ( green_block , red_block ), 2 ).
происходит ( галочка , 0 ). происходит ( move ( red_block , table ), 1 ). происходит ( move ( green_block , red_block ), 2 ).
происходит ( move ( red_block , table ), 0 ). происходит ( move ( green_block , red_block ), 1 ). происходит ( галочка , 2 ).
Вот tick
событие, которое отмечает ход времени, не инициируя и не прекращая никаких беглых потоков.
Существуют также решения, в которых два move
события происходят одновременно. Например:
происходит ( move ( red_block , table ), 0 ). происходит ( move ( green_block , red_block ), 0 ). происходит ( галочка , 1 ). происходит ( галочка , 2 ).
Такие решения, если они нежелательны, можно удалить, добавив ограничение целостности, которое похоже на условие ограничения в ASP:
:- происходит ( перемещение ( Блок1 , Место ), Время ), происходит ( перемещение ( Блок2 , Блок1 ), Время ).
Абдуктивное логическое программирование использовалось для диагностики неисправностей, планирования, обработки естественного языка и машинного обучения. Его также использовали для интерпретации отрицания как неудачи как формы абдуктивного рассуждения. [62]
Индуктивное логическое программирование (ILP) — это подход к машинному обучению , который создает логические программы как гипотетические обобщения положительных и отрицательных примеров. Учитывая логическую программу, представляющую базовые знания и положительные примеры вместе с ограничениями, представляющими отрицательные примеры, система ПДОДИ создает логическую программу, которая обобщает положительные примеры, исключая при этом отрицательные примеры.
ILP похожа на ALP в том, что их можно рассматривать как создание гипотез для объяснения наблюдений и как использование ограничений для исключения нежелательных гипотез. Но в ALP гипотезы — это факты без переменных, а в ILP гипотезы — это общие правила. [63] [64]
Например, имея только базовые знания об отношениях мать_ребенок и отец_ребенок, а также подходящие примеры отношения дедушка_ребенок, современные системы ILP могут генерировать определение дедушки и дедушки_ребенка, изобретая вспомогательный предикат, который можно интерпретировать как отношение родитель_ребенок: [65 ]
grandparent_child ( X , Y ):- вспомогательный ( X , Z ), вспомогательный ( Z , Y ). вспомогательный ( X , Y ):- мать_ребенок ( X , Y ). вспомогательный ( X , Y ):- отец_ребенок ( X , Y ).
Стюарт Рассел [66] назвал такое изобретение новых концепций наиболее важным шагом, необходимым для достижения ИИ человеческого уровня.
Недавняя работа в области ILP, сочетающая логическое программирование, обучение и вероятность, привела к появлению областей статистического реляционного обучения и вероятностного индуктивного логического программирования .
Параллельное логическое программирование объединяет концепции логического программирования с параллельным программированием . Его развитию был дан большой импульс в 1980-х годах, когда он был выбран в качестве языка системного программирования японского проекта пятого поколения (FGCS) . [67]
Программа параллельной логики представляет собой набор защищенных предложений Хорна вида:
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
:
перетасовать ([], [], []). перемешать ( влево , вправо , объединить ) : - Влево = [ Первый | Отдых ] | Объединить = [ Первый | ShortMerge ], перемешать ( Rest , Right , ShortMerge ). перемешать ( влево , вправо , объединить ) : - Вправо = [ Первый | Отдых ] | Объединить = [ Первый | ShortMerge ], перемешать ( Left , Rest , ShortMerge ).
Здесь []
представляет пустой список и [Head | Tail]
представляет список, в котором за первым элементом Head
следует список Tail
, как в Прологе. (Обратите внимание, что первое появление | во втором и третьем предложениях — это конструктор списка, тогда как второе появление | — это оператор фиксации.) Программу можно использовать, например, для перетасовки списков [ace, queen, king]
и [1, 4, 2]
вызова предложения цели. :
перетасовать ([ туз , дама , король ], [ 1 , 4 , 2 ], объединить ).
Программа недетерминированно сгенерирует единственное решение, например Merge = [ace, queen, 1, king, 4, 2]
.
Карл Хьюитт утверждал [68] , что из-за неопределенности параллельных вычислений параллельное логическое программирование не может реализовать общий параллелизм. Однако согласно логической семантике любой результат вычисления параллельной логической программы является логическим следствием программы, даже если не все логические последствия могут быть получены.
Параллельное логическое программирование с ограничениями [69] сочетает в себе параллельное логическое программирование и логическое программирование с ограничениями , используя ограничения для управления параллелизмом. Предложение может содержать защиту, представляющую собой набор ограничений, которые могут блокировать применимость этого пункта. Когда меры защиты нескольких предложений удовлетворены, параллельное программирование логики ограничений делает выбор в пользу использования только одного.
Некоторые исследователи расширили логическое программирование с помощью функций программирования более высокого порядка, полученных из логики высшего порядка , таких как переменные-предикаты. К таким языкам относятся расширения Пролога HiLog [70] и λProlog . [71]
Основание логического программирования на основе линейной логики привело к созданию языков логического программирования, которые значительно более выразительны, чем языки, основанные на классической логике. Программы предложений Хорна могут представлять изменение состояния только путем изменения аргументов предикатов. В программировании линейной логики можно использовать окружающую линейную логику для поддержки изменения состояния. Некоторые ранние разработки языков логического программирования, основанные на линейной логике, включают LO, [72] Lolli, [73] ACL, [74] и Forum. [75] Форум обеспечивает целенаправленную интерпретацию всей линейной логики.
F-логика [76] расширяет логическое программирование объектами и синтаксисом фреймов.
Logtalk [77] расширяет язык программирования Пролог поддержкой объектов, протоколов и других концепций ООП. Он поддерживает большинство совместимых со стандартами систем Пролога в качестве внутренних компиляторов.
Транзакционная логика [53] представляет собой расширение логического программирования с помощью логической теории обновлений, изменяющих состояние. Он имеет как теоретико-модельную семантику, так и процедурную. Реализация подмножества логики транзакций доступна в системе Flora-2 [78] . Доступны и другие прототипы .