Логическое программирование — это парадигма программирования , базы данных и представления знаний , основанная на формальной логике . Логическая программа — это набор предложений в логической форме, представляющих знания о некоторой проблемной области. Вычисления выполняются путем применения логических рассуждений к этим знаниям для решения проблем в этой области. Основные семейства языков логического программирования включают Prolog , Answer Set Programming (ASP) и Datalog . Во всех этих языках правила записываются в форме предложений :
A :- B1, ..., Bn.и читаются как повествовательные предложения в логической форме:
A if B1 and ... and Bn.Aназывается головой правила, , ..., называется телом , а называются литералами или условиями. При n = 0 правило называется фактом и записывается в упрощенной форме:B1BnBi
A.Запросы (или цели) имеют тот же синтаксис, что и тела правил, и обычно записываются в форме:
?- B1, ..., Bn.В простейшем случае предложений Хорна (или «определенных» предложений) все A, B 1 , ..., B n являются атомарными формулами вида p(t 1 ,..., t m ), где p — предикатный символ, именующий отношение, например «материнство», а t i — термины, именующие объекты (или индивидуумов). Термины включают как постоянные символы, например «charles», так и переменные, например X, которые начинаются с заглавной буквы.
Рассмотрим, например, следующую программу Хорна:
мать_ребенок ( елизавета , чарльз ). отец_ребенок ( чарльз , уильям ). отец_ребенок ( чарльз , гарри ). родитель_ребенок ( X , Y ) :- мать_ребенок ( X , Y ). родитель_ребенок ( X , Y ) :- отец_ребенок ( X , Y ). дедушка_ребенок ( X , Y ) :- родитель_ребенок ( X , Z ), родитель_ребенок ( Z , Y ). При запросе программа выдает ответы. Например ?- parent_child(X, william), для запроса единственным ответом является
X = ЧарльзМожно задавать различные запросы. Например, программу можно запросить как для генерации дедушек и бабушек, так и для генерации внуков. Ее можно использовать даже для генерации всех пар внуков и дедушек и бабушек или просто для проверки, является ли заданная пара такой парой:
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 ). нет ?- grandparent_child ( elizabeth , harry ). даХотя программы с логическими предложениями Хорна являются полными по Тьюрингу , [1] [2] для большинства практических приложений программы с предложениями Хорна необходимо расширить до «нормальных» логических программ с отрицательными условиями. Например, определение родственного элемента использует отрицательное условие, где предикат = определяется предложением X = X:
брат ( X , Y ) :- родитель_ребенок ( Z , X ), родитель_ребенок ( Z , Y ), а не ( X = Y ).Языки логического программирования, включающие отрицательные условия, обладают возможностями представления знаний немонотонной логики .
В ASP и Datalog логические программы имеют только декларативное чтение, а их выполнение осуществляется посредством процедуры доказательства или генератора моделей, поведение которых не должно контролироваться программистом. Однако в семействе языков Prolog логические программы также имеют процедурную интерпретацию как процедуры сокращения цели. С этой точки зрения предложение A :- B 1 ,...,B n понимается как:
A, решать и... и решать .B1BnОтрицательные условия в тексте предложений также имеют процедурную интерпретацию, известную как отрицание как невыполнение : отрицательный литерал 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]
Кольмероэр и Филипп Руссель использовали процедурную интерпретацию в качестве основы Prolog, которая была реализована летом и осенью 1972 года. Первая программа Prolog, также написанная в 1972 году и реализованная в Марселе, была французской вопросно-ответной системой. Использование Prolog в качестве практического языка программирования получило большой импульс после разработки компилятора Дэвидом HD Уорреном в Эдинбурге в 1977 году. Эксперименты показали, что Edinburgh Prolog может конкурировать по скорости обработки с другими символическими языками программирования , такими как Lisp . [17] Edinburgh Prolog стал фактическим стандартом и оказал сильное влияние на определение стандарта ISO Prolog.
Логическое программирование привлекло международное внимание в 1980-х годах, когда оно было выбрано Министерством международной торговли и промышленности Японии для разработки программного обеспечения для проекта Fifth Generation Computer Systems (FGCS). Проект FGCS был направлен на использование логического программирования для разработки передовых приложений искусственного интеллекта на массивно- параллельных компьютерах . Хотя изначально проект исследовал использование Prolog, позже он принял использование параллельного логического программирования , поскольку оно было ближе к архитектуре компьютера FGCS.
Однако функция обязательного выбора параллельного логического программирования вмешалась в логическую семантику языка [18] и в его пригодность для приложений представления знаний и решения проблем. Более того, параллельные компьютерные системы, разработанные в проекте, не смогли конкурировать с достижениями, происходящими в разработке более обычных компьютеров общего назначения. Вместе эти две проблемы привели к тому, что проект FGCS не смог достичь своих целей. Интерес как к логическому программированию, так и к ИИ пришел в упадок во всем мире. [19]
В то же время, более декларативные подходы к логическому программированию, включая те, которые основаны на использовании Prolog, продолжали развиваться независимо от проекта FGCS. В частности, хотя Prolog был разработан для объединения декларативных и процедурных представлений знаний, чисто декларативная интерпретация логических программ стала фокусом для приложений в области дедуктивных баз данных . Работа в этой области стала заметной около 1977 года, когда Эрве Галлер и Джек Минкер организовали семинар по логике и базам данных в Тулузе. [20] Область в конечном итоге была переименована в Datalog .
Этот акцент на логическом, декларативном чтении логических программ получил дальнейший импульс благодаря развитию программирования логики ограничений в 1980-х годах и программирования набора ответов в 1990-х годах. Он также получает обновленный акцент в недавних приложениях Пролога [21]
Ассоциация логического программирования (ALP) была основана в 1986 году для продвижения логического программирования. Её официальным журналом до 2000 года был The Journal of Logic Programming . Её главным редактором-основателем был Дж. Алан Робинсон . [22] В 2001 году журнал был переименован в The Journal of Logic and Algebraic Programming , а официальным журналом ALP стал Theory and Practice of Logic Programming , издаваемый Cambridge University Press .
Логические программы обладают богатым разнообразием семантики и методов решения задач, а также широким спектром приложений в программировании, базах данных, представлении знаний и решении задач.
Процедурная интерпретация логических программ, которая использует обратные рассуждения для сведения целей к подцелям, является частным случаем использования стратегии решения проблем для управления использованием декларативного, логического представления знаний для получения поведения алгоритма . В более общем смысле, различные стратегии решения проблем могут быть применены к одному и тому же логическому представлению для получения различных алгоритмов. В качестве альтернативы, различные алгоритмы могут быть получены с заданной стратегией решения проблем с использованием различных логических представлений. [23]
Две основные стратегии решения проблем — это обратные рассуждения (уменьшение цели) и прямые рассуждения , также известные как рассуждения сверху вниз и снизу вверх соответственно.
В простом случае пропозициональной программы предложения Хорна и атомарной цели верхнего уровня обратные рассуждения определяют дерево и-или , которое составляет пространство поиска для решения цели. Цель верхнего уровня является корнем дерева. Учитывая любой узел в дереве и любое предложение, заголовок которого соответствует узлу, существует набор дочерних узлов, соответствующих подцелям в теле предложения. Эти дочерние узлы группируются вместе с помощью «и». Альтернативные наборы дочерних узлов, соответствующие альтернативным способам решения узла, группируются вместе с помощью «или».
Для поиска в этом пространстве можно использовать любую стратегию поиска. Prolog использует последовательную стратегию возврата, в которой одновременно рассматриваются только одна альтернатива и одна подцель. Например, подцели можно решать параллельно, а также предложения можно пробовать параллельно. Первая стратегия называетсяи-параллельно и вторая стратегия называетсяили-параллельный . Также возможны другие стратегии поиска, такие как интеллектуальный возврат[24]или поиск по лучшему первому для нахождения оптимального решения[25]
В более общем, непропозициональном случае, когда подцели могут совместно использовать переменные, можно использовать другие стратегии, такие как выбор подцели, которая наиболее инстанциирована или инстанциирована достаточно, чтобы применялась только одна процедура. [26] Такие стратегии используются, например, в параллельном логическом программировании .
В большинстве случаев обратные рассуждения от запроса или цели более эффективны, чем прямые рассуждения. Но иногда при Datalog и программировании набора ответов может не быть запроса, который был бы отделен от набора предложений в целом, и тогда генерация всех фактов, которые могут быть получены из предложений, является разумной стратегией решения проблемы. Вот еще один пример, где прямые рассуждения превосходят обратные рассуждения в более традиционной вычислительной задаче, где цель ?- 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.
Prolog не может выполнять прямые рассуждения напрямую. Но он может достичь эффекта прямых рассуждений в контексте обратных рассуждений с помощью табличного представления : подцели сохраняются в таблице вместе с их решениями. Если подцель встречается повторно, она решается напрямую с использованием решений, уже имеющихся в таблице, вместо повторного решения подцелей избыточно. [27]
Логическое программирование можно рассматривать как обобщение функционального программирования, в котором функции являются частным случаем отношений. [28] Например, функция, мать(X) = Y, (каждый X имеет только одну мать Y) может быть представлена отношением мать(X, Y). В этом отношении логические программы похожи на реляционные базы данных , которые также представляют функции как отношения.
По сравнению с реляционным синтаксисом, функциональный синтаксис более компактен для вложенных функций. Например, в функциональном синтаксисе определение бабушки по материнской линии можно записать во вложенной форме:
материнская_бабушка ( X ) = мать ( мать ( X )).То же самое определение в реляционной нотации необходимо записать в невложенной, сглаженной форме:
maternal_grandmother ( X , Y ) :- мать ( X , Z ), мать ( Z , Y ).Однако вложенный синтаксис можно рассматривать как синтаксический сахар для невложенного синтаксиса. Например, Ciao Prolog преобразует функциональный синтаксис в реляционную форму и выполняет полученную логическую программу, используя стандартную стратегию выполнения Prolog. [29] Более того, то же самое преобразование можно использовать для выполнения вложенных отношений, которые не являются функциональными. Например:
дедушка ( X ) := родитель ( родитель ( X )). родитель ( X ) := мать ( X ). родитель ( X ) := отец ( X ).мать ( Чарльз ) := Элизабет . отец ( Чарльз ) := Филлип . мать ( Гарри ) := Диана . отец ( Гарри ) := Чарльз .?- дедушка ( X , Y ). X = Гарри , Y = Элизабет . X = Гарри , Y = Филлип .Термин реляционное программирование использовался для охвата различных языков программирования, которые рассматривают функции как частный случай отношений. Некоторые из этих языков, такие как miniKanren [28] и реляционное линейное программирование [30], являются языками логического программирования в смысле этой статьи.
Однако реляционный язык RML является императивным языком программирования [31], основной конструкцией которого является реляционное выражение, похожее на выражение в логике предикатов первого порядка.
Другие реляционные языки программирования основаны на реляционном исчислении [32] или реляционной алгебре. [33]
Рассматривая это с чисто логической точки зрения, существует два подхода к декларативной семантике программ логики предложений Хорна: один подход — это исходная логическая семантика следствия , которая понимает решение цели как демонстрацию того, что цель является теоремой, которая верна во всех моделях программы.
В этом подходе вычисление является доказательством теорем в логике первого порядка ; и как обратное рассуждение , как в разрешении SLD, так и прямое рассуждение , как в гиперразрешении, являются правильными и полными методами доказательства теорем. Иногда такие методы доказательства теорем также рассматриваются как предоставляющие отдельную теоретико-доказательную (или операциональную) семантику для логических программ. Но с логической точки зрения они являются методами доказательства, а не семантикой.
Другой подход к декларативной семантике программ с оговорками Хорна — это семантика выполнимости , которая понимает решение цели как демонстрацию того, что цель истинна (или удовлетворена) в некоторой предполагаемой (или стандартной) модели программы. Для программ с оговорками Хорна всегда существует такая стандартная модель: это уникальная минимальная модель программы.
Неформально говоря, минимальная модель — это модель, которая, если ее рассматривать как набор всех (свободных от переменных) фактов, которые истинны в модели, не содержит меньшего набора фактов, который также является моделью программы.
Например, следующие факты представляют минимальную модель примера семейных отношений во введении к этой статье. Все остальные факты без переменных являются ложными в модели:
мать_ребенок ( елизавета , чарльз ) . отец_ребенок ( чарльз , уильям ) . отец_ребенок ( чарльз , гарри ). родитель_ребенок ( елизавета , чарльз ). родитель_ребенок ( чарльз , уильям ). родитель_ребенок ( чарльз , гарри ). дедушка_ребенок ( елизавета , уильям ). дедушка_ребенок ( елизавета , гарри ). Семантика выполнимости также имеет альтернативную, более математическую характеристику как наименее фиксированную точку функции, которая использует правила в программе для выведения новых фактов из существующих фактов за один шаг вывода.
Примечательно, что те же методы решения проблем прямого и обратного рассуждения, которые изначально были разработаны для семантики логического следствия, в равной степени применимы к семантике выполнимости: прямое рассуждение генерирует минимальную модель программы предложения Хорна, выводя новые факты из существующих фактов, пока не останется никаких новых дополнительных фактов. Обратное рассуждение, которое успешно сводит цель к подцелям, пока все подцели не будут решены фактами, гарантирует, что цель истинна в минимальной модели, без явного создания модели. [34]
Разницу между двумя декларативными семантиками можно увидеть в определениях сложения и умножения в арифметике последователей , которая представляет натуральные числа 0, 1, 2, ...как последовательность членов формы 0, s(0), s(s(0)), .... В общем случае, член s(X)представляет собой последователя, X,а именно: X + 1.Вот стандартные определения сложения и умножения в функциональной нотации:
Х + 0 = Х. X + 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)to represent X + Y = Z,и multiply(X, Y, Z)to represent X × Y = Z:
добавить ( X , 0 , X ). добавить ( 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 ). 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не выполняется, уже было особенностью ранних систем Prolog. Результирующее расширение разрешения SLD называется SLDNF . Похожая конструкция, называемая "thnot", также существовала в Micro-Planner .
Логическая семантика NAF оставалась неразрешенной до тех пор, пока Кейт Кларк [35] не показал, что при определенных естественных условиях NAF является эффективным, правильным (а иногда и полным) способом рассуждения с семантикой логического следствия, использующим завершение логической программы в логике первого порядка.
Завершение сводится примерно к рассмотрению набора всех программных предложений с одним и тем же предикатом в заголовке, например:
A :- Body1. ...A :- Bodyk.как определение предиката:
A iff (Body1 or ... or Bodyk)где iffозначает «тогда и только тогда». Завершение также включает аксиомы равенства, которые соответствуют унификации . Кларк показал, что доказательства, сгенерированные SLDNF, структурно похожи на доказательства, сгенерированные естественным дедуктивным стилем рассуждений с завершением программы.
Рассмотрим, например, следующую программу:
должен_получить_санкцию ( X , наказание ) : - является_вором ( X ), а не должен_получить_санкцию ( X , реабилитация ). должен_получить_санкцию ( X , реабилитация ) : является_вором ( X ), является_несовершеннолетним ( X ), а не является_насильником ( X ). вор ( том ).Учитывая цель определения того, следует ли применить к Тому санкцию, первое правило успешно показывает, что Том должен быть наказан:
?- should_receive_sanction ( том , Санкция ). Санкция = наказание .Это потому, что том — вор, и нельзя показать, что том должен быть реабилитирован. Нельзя показать, что том должен быть реабилитирован, потому что нельзя показать, что том — несовершеннолетний.
Однако если мы получаем новую информацию о том, что Том действительно несовершеннолетний, предыдущий вывод о том, что Том должен быть наказан, заменяется новым выводом о том, что Том должен быть реабилитирован:
минор ( том ).?- should_receive_sanction ( том , Санкция ). Санкция = реабилитация .Это свойство отказа от вывода при добавлении новой информации называется немонотонностью, и оно делает логическое программирование немонотонной логикой .
Но если нам сейчас скажут, что Том склонен к насилию, вывод о том, что Том должен быть наказан, будет восстановлен:
жестокий ( том ).?- should_receive_sanction ( том , Санкция ). Санкция = наказание .Завершение этой программы:
should_receive_sanction ( X , Санкция ) тогда и только тогда, когда Санкция = наказание , является_вором ( X ), а не should_receive_sanction ( X , реабилитация ) или Санкция = реабилитация , является_вором ( X ), является_несовершеннолетним ( X ), а не является_насильственным ( X ). является_вором ( X ) тогда и только тогда, когда X = том . является_несовершеннолетним ( X ) тогда и только тогда, когда X = том . является_жестоким ( X ) тогда и только тогда, когда X = том .Понятие завершения тесно связано с семантикой ограничения Джона Маккарти для рассуждений по умолчанию [36] и с предположением о замкнутости мира Рэя Рейтера [37] .
Семантика завершения для отрицания — это логическая семантика следствия, для которой SLDNF обеспечивает реализацию теории доказательств. Однако в 1980-х годах семантика выполнимости стала более популярной для логических программ с отрицанием. В семантике выполнимости отрицание интерпретируется в соответствии с классическим определением истины в предполагаемой или стандартной модели логической программы.
В случае логических программ с отрицательными условиями существует два основных варианта семантики выполнимости: В хорошо обоснованной семантике предполагаемая модель логической программы — это уникальная, трехзначная, минимальная модель, которая всегда существует. Хорошо обоснованная семантика обобщает понятие индуктивного определения в математической логике. [38] XSB Prolog [39] реализует хорошо обоснованную семантику с использованием разрешения SLG. [40]
В альтернативной стабильной семантике модели может не быть предполагаемых моделей или может быть несколько предполагаемых моделей, все из которых минимальны и двузначны. Стабильная семантика модели лежит в основе программирования набора ответов (ASP).
Обе семантики обоснованной и стабильной модели применимы к произвольным логическим программам с отрицанием. Однако обе семантики совпадают для стратифицированных логических программ. Например, программа для санкционирования воров (локально) стратифицирована, и все три семантики для программы определяют одну и ту же предполагаемую модель:
должен_получить_санкцию ( том , наказание ). является_вором ( том ). является_несовершеннолетним ( том ). является_жестоким ( том ).Попытки понять отрицание в логическом программировании также способствовали развитию абстрактных фреймворков аргументации . [41] В интерпретации отрицания аргументации первоначальный аргумент о том, что Том должен быть наказан, потому что он вор, подвергается нападкам со стороны аргумента о том, что он должен быть реабилитирован, потому что он несовершеннолетний. Но тот факт, что Том склонен к насилию, подрывает аргумент о том, что Том должен быть реабилитирован, и восстанавливает аргумент о том, что Том должен быть наказан.
Метапрограммирование , в котором программы рассматриваются как данные, уже было особенностью ранних реализаций Пролога. [42] [43] Например, реализация Пролога в Эдинбурге DEC10 включала «интерпретатор и компилятор, оба написанные на самом Прологе». [43] Простейшей метапрограммой является так называемый « ванильный » метаинтерпретатор:
решить ( истина ). решить (( B , C )):- решить ( B ), решить ( C ). решить ( A ):- предложение ( A , B ), решить ( B ).где true представляет собой пустую конъюнкцию, а (B,C) — составной термин, представляющий конъюнкцию B и C. Предложение предиката (A,B) означает, что существует предложение вида A :- B.
Метапрограммирование — это применение более общего использования металогики или метаязыка для описания и рассуждения о другом языке, называемом объектным языком .
Программирование металогики позволяет объединять представления на уровне объектов и метауровня, как в естественном языке. Например, в следующей программе атомарная формула attends(Person, Meeting)встречается и как формула на уровне объектов, и как аргумент метапредикатов prohibitedиapproved.
запрещено ( посещает ( Человек , Встречу )) :- не ( одобрено ( посещает ( Человек , Встречу ))).should_receive_sanction ( Лицо , ругань ) : - посещает ( Лицо , Собрание ), возвышенный ( Лицо ), запрещенный ( посещает ( Лицо , Собрание )). should_receive_sanction ( Лицо , изгнание ) : - посещает ( Лицо , Собрание ), низший ( Лицо ), запрещенный ( посещает ( Лицо , Собрание )).одобрено ( посещает ( alice , tea_party )). посещает ( mad_hatter , tea_party ). посещает ( sonmouse , tea_party ).возвышенный ( безумный_шляпник ). скромный ( соня ).?- должен_получить_санкцию ( X , Y ). Человек = безумный_шляпник , Санкция = ругань . Человек = соня , Санкция = изгнание .В своем популярном «Введении в когнитивную науку» [44] Пол Тагард включает логику и правила в качестве альтернативных подходов к моделированию человеческого мышления. Он утверждает, что правила, которые имеют форму ЕСЛИ условие ТО действие , «очень похожи» на логические условные предложения, но они проще и имеют большую психологическую правдоподобность (стр. 51). Среди других различий между логикой и правилами он утверждает, что логика использует дедукцию, а правила используют поиск (стр. 45) и могут использоваться для рассуждений как вперед, так и назад (стр. 47). Предложения в логике «должны интерпретироваться как универсально истинные », но правила могут быть значениями по умолчанию , которые допускают исключения (стр. 44).
Он утверждает, что «в отличие от логики, системы на основе правил также могут легко представлять стратегическую информацию о том, что делать» (стр. 45). Например, «ЕСЛИ вы хотите поехать домой на выходные и у вас есть деньги на автобус, ТО вы можете сесть на автобус». Он не замечает, что та же стратегия сведения цели к подцелям может быть интерпретирована, в манере логического программирования, как применение обратного рассуждения к логическому условию:
can_go ( ты , домой ) :- have ( ты , стоимость_автобуса ), catch ( ты , автобус ).Все эти характеристики систем, основанных на правилах, — поиск, прямое и обратное рассуждение, рассуждение по умолчанию и сокращение цели — также являются определяющими характеристиками логического программирования. Это предполагает, что вывод Тагарда (стр. 56) о том, что:
Большая часть человеческих знаний естественным образом описывается в терминах правил, и многие виды мышления, такие как планирование, могут быть смоделированы с помощью систем, основанных на правилах.
также применимо к логическому программированию.
Другие аргументы, показывающие, как логическое программирование может быть использовано для моделирования аспектов человеческого мышления, представлены Кейтом Стеннингом и Михилем ван Ламбалгеном в их книге «Человеческое мышление и когнитивная наука». [45] Они показывают, как немонотонный характер логических программ может быть использован для объяснения человеческой производительности в различных психологических задачах. Они также показывают (стр. 237), что «закрытое мировое рассуждение в его облике логического программирования имеет привлекательную нейронную реализацию, в отличие от классической логики».
В книге «Правильная обработка событий» [46] Михиль ван Ламбальген и Фриц Хамм исследуют использование программирования с использованием логики ограничений для кодирования «временных понятий на естественном языке, рассматривая способ, которым люди конструируют время».
Использование логики для представления процедурных знаний и стратегической информации было одной из основных целей, способствовавших раннему развитию логического программирования. Более того, оно продолжает оставаться важной особенностью семейства языков логического программирования Prolog сегодня. Однако многие приложения логического программирования, включая приложения Prolog, все больше фокусируются на использовании логики для представления чисто декларативных знаний. Эти приложения включают как представление общих знаний здравого смысла , так и представление экспертных знаний, специфичных для предметной области .
Здравый смысл включает в себя знание о причине и следствии, формализованное, например, в исчислении ситуаций , исчислении событий и языках действий . Вот упрощенный пример, который иллюстрирует основные черты таких формализмов. Первое предложение гласит, что факт имеет место сразу после того, как событие инициирует (или вызывает) факт. Второе предложение является аксиомой фрейма , которая гласит, что факт, который имеет место в определенный момент времени, продолжает иметь место в следующий момент времени, если он не будет прекращен событием, которое происходит в этот момент времени. Эта формулировка позволяет происходить более чем одному событию одновременно:
имеет место ( Факт , Время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 зеленый блок перемещается на красный блок. Перемещение объекта на место прекращает тот факт, что объект находится на каком-либо месте, и инициирует тот факт, что объект находится на месте, на которое он перемещен:
удерживает ( на ( зеленый_блок , таблица ), 0 ). удерживает ( на ( красный_блок , зеленый_блок ), 0 ).происходит ( перемещение ( красный_блок , таблица ), 0 ). происходит ( перемещение ( зеленый_блок , красный_блок ), 1 ).инициирует ( перемещение ( Объект , Место ), на ( Объект , Место )). завершает ( перемещение ( Объект , Место2 ), на ( Объект , Место1 )).?- имеет место ( Факт , Время ).Факт = вкл ( green_block , table ), Время = 0. Факт = вкл ( red_block , green_block ), Время = 0. Факт = вкл ( green_block , table ), Время = 1. Факт = вкл ( red_block , table ), Время = 1. Факт = вкл ( green_block , red_block ), Время = 2. Факт = вкл ( red_block , table ), Время = 2.Прямое рассуждение и обратное рассуждение генерируют одни и те же ответы на цель holds(Fact, Time). Но прямое рассуждение генерирует флюенты прогрессивно во временном порядке, а обратное рассуждение генерирует флюенты регрессивно , как в доменно-специфическом использовании регрессии в ситуационном исчислении . [47]
Логическое программирование также оказалось полезным для представления предметно-ориентированной экспертизы в экспертных системах . [48] Но человеческая экспертиза, как и здравый смысл общего назначения, в основном неявная и молчаливая , и часто бывает трудно представить такие неявные знания в явных правилах. Однако эта трудность не возникает, когда логические программы используются для представления существующих явных правил бизнес-организации или юридического органа.
Например, вот упрощенная версия первого предложения Закона о британском гражданстве, в котором говорится, что лицо, родившееся в Великобритании, становится гражданином Великобритании в момент рождения, если родитель этого лица является гражданином Великобритании в момент рождения:
инициирует ( рождение ( Лицо ), гражданин ( Лицо , Великобритания )):- время_рождения ( Лицо ) , Время ) , место_рождения ( Лицо ) , Великобритания ), родитель_ребенок ( Другое_лицо , Лицо ), держит ( гражданин ( Другое_лицо , Великобритания ) , Время ). Исторически сложилось так, что представление значительной части Закона о британском гражданстве в виде логической программы в 1980-х годах [49] оказало «огромное влияние на развитие вычислительных представлений законодательства, показав, как логическое программирование позволяет создавать интуитивно привлекательные представления, которые можно напрямую использовать для генерации автоматических выводов» [50] .
Совсем недавно система PROLEG [51] , инициированная в 2009 году и состоящая из приблизительно 2500 правил и исключений из гражданского кодекса и правил рассмотрения дел Верховным судом Японии, стала, возможно, крупнейшей базой правовых правил в мире. [52]
Правило вывода резолюции SLD нейтрально относительно порядка, в котором подцели в телах предложений могут быть выбраны для решения. Ради эффективности Prolog ограничивает этот порядок порядком, в котором подцели записаны. SLD также нейтрален относительно стратегии поиска в пространстве доказательств SLD. Prolog ищет в этом пространстве сверху вниз, в глубину, пробуя разные предложения для решения одной и той же (под)цели в порядке, в котором предложения записаны.
Эта стратегия поиска имеет преимущество в том, что текущая ветвь дерева может быть эффективно представлена стеком . Когда предложение цели наверху стека сводится к новому предложению цели, новое предложение цели помещается наверх стека. Когда выбранная подцель в предложении цели наверху стека не может быть решена, стратегия поиска возвращается назад , удаляя предложение цели с вершины стека и повторяя попытку решения выбранной подцели в предыдущем предложении цели, используя следующее предложение, которое соответствует выбранной подцели.
Возврат может быть ограничен с помощью подцели, называемой cut , записанной как !, которая всегда успешна, но не может быть возвращена. Cut может использоваться для повышения эффективности, но также может мешать логическому смыслу предложений. Во многих случаях использование cut может быть заменено отрицанием как неудача. Фактически, отрицание как неудача может быть определено в Prolog с помощью cut вместе с любым литералом, скажем, fail , который унифицируется с заголовком no предложения:
не ( P ) :- P , !, неудача . не ( P ).Prolog предоставляет другие возможности, помимо cut, которые не имеют логической интерпретации. Они включают встроенные предикаты assert и retract для деструктивного обновления состояния программы во время ее выполнения.
Например, приведенный выше пример мира игрушечных блоков можно реализовать без аксиом фрейма, используя деструктивное изменение состояния:
на ( зеленый_блок , таблица ). на ( красный_блок , зеленый_блок ).переместить ( Объект , Место2 ) :- отвести ( на ( Объект , Место1 )), утвердить ( на ( Объект , Место2 ).Последовательность событий перемещения и результирующие местоположения блоков можно вычислить, выполнив запрос:
?- переместить ( красный_блок , таблица ), переместить ( зеленый_блок , красный_блок ), на ( Объект , Место ).Объект = красный_блок , Место = таблица . Объект = зеленый_блок , Место = красный_блок .Были разработаны различные расширения логического программирования, чтобы обеспечить логическую основу для такого деструктивного изменения состояния. [53] [54] [55]
Широкий спектр приложений Prolog, как изолированных, так и в сочетании с другими языками, освещается в книге «Год Prolog» [21] , посвященной 50-летию Prolog в 2022 году.
Prolog также внес вклад в развитие других языков программирования, включая ALF , Fril , Gödel , Mercury , Oz , Ciao , Visual Prolog , XSB и λProlog .
Программирование логики ограничений (CLP) объединяет программирование логики предложений Хорна с решением ограничений . Оно расширяет предложения Хорна, позволяя некоторым предикатам, объявленным как предикаты ограничений, появляться как литералы в теле предложения. Предикаты ограничений не определяются фактами и правилами в программе, но предопределены некоторой предметно-специфической теоретико-модельной структурой или теорией.
Процедурно, подцели, предикаты которых определяются программой, решаются с помощью редукции цели, как в обычном логическом программировании, но ограничения упрощаются и проверяются на выполнимость с помощью доменно-специфического решателя ограничений, который реализует семантику предикатов ограничений. Исходная задача решается путем ее редукции к выполнимой конъюнкции ограничений.
Интересно, что первая версия Prolog уже включала в себя предикат ограничения dif(term1, term2) из докторской диссертации Филиппа Русселя 1972 года, который выполняется успешно, если оба его аргумента являются разными терминами, но который задерживается, если какой-либо из терминов содержит переменную. [52]
Следующая программа логики ограничений представляет собой игрушечную временную базу данных john'sистории в качестве учителя:
преподает ( Джон , оборудование , T ) :- 1990 ≤ T , T < 1999. преподает ( Джон , программное обеспечение , T ) :- 1999 ≤ T , T < 2005. преподает ( Джон , логика , T ) :- 2005 ≤ T , T ≤ 2012. ранг ( Джон , инструктор , T ) :- 1990 ≤ T , T < 2010. ранг ( Джон , профессор , T ) :- 2010 ≤ T , T < 2014.Здесь ≤и <являются предикатами ограничений с их обычной предполагаемой семантикой. Следующий целевой пункт запрашивает базу данных, чтобы узнать, когда johnоба обучались logicи были professor:
?- преподаёт ( Джон , логика , Т ), звание ( Джон , профессор , Т ).Решение 2010 ≤ T, T ≤ 2012получается путем упрощения ограничений2005 ≤ T, T ≤ 2012, 2010 ≤ T, T < 2014.
Программирование с использованием логики ограничений использовалось для решения задач в таких областях, как гражданское строительство , машиностроение , проверка цифровых схем , автоматизированное составление расписаний , управление воздушным движением и финансы. Оно тесно связано с программированием с использованием абдуктивной логики .
Datalog — это язык определения баз данных, который сочетает в себе реляционное представление данных, как в реляционных базах данных , с логическим представлением, как в логическом программировании.
Реляционные базы данных используют реляционное исчисление или реляционную алгебру с реляционными операциями , такими как объединение , пересечение , разность множеств и декартово произведение , для указания запросов, которые обращаются к базе данных. Datalog использует логические связки, такие как или , и и не в телах правил, чтобы определить отношения как часть самой базы данных.
На раннем этапе разработки реляционных баз данных было признано, что рекурсивные запросы не могут быть выражены ни в реляционной алгебре, ни в реляционном исчислении, и что этот недостаток можно устранить, введя оператор наименьшей фиксированной точки. [56] [57] Напротив, рекурсивные отношения могут быть определены естественным образом с помощью правил в логических программах, без необходимости в каких-либо новых логических связках или операторах.
Datalog отличается от более общего логического программирования тем, что в качестве терминов используются только константы и переменные. Более того, все факты не содержат переменных, а правила ограничены, так что если они выполняются снизу вверх, то и полученные факты также не содержат переменных.
Например, рассмотрим базу данных семьи:
мать_ребенок ( елизавета , чарльз ). отец_ребенок ( чарльз , уильям ). отец_ребенок ( чарльз , гарри ). родитель_ребенок ( X , Y ) :- мать_ребенок ( X , Y ). родитель_ребенок ( X , Y ) :- отец_ребенок ( X , Y ). потомок_предка ( X , Y ) :- родитель_ребенок ( X , X ). потомок_предка ( X , Y ) :- потомок_предка ( X , Z ), потомок_предка ( Z , Y ).Исполнение снизу вверх выводит следующий набор дополнительных фактов и завершается:
родительский_ребенок ( Элизабет , Чарльз ). родительский_ребенок ( Чарльз , Уильям ). родительский_ребенок ( Чарльз , Гарри ).потомок_предка ( елизавета , чарльз ). потомок_предка ( чарльз , уильям ). потомок_предка ( чарльз , гарри ).потомок_предка ( елизавета , уильям ). потомок_предка ( елизавета , гарри ).Выполнение сверху вниз дает те же ответы на запрос:
?- предок_потомок ( X , Y ).Но затем он переходит в бесконечный цикл. Однако выполнение сверху вниз с табличным представлением дает те же ответы и завершается без зацикливания.
Как и Datalog, программирование Answer Set (ASP) не является полным по Тьюрингу. Более того, вместо того, чтобы отделять цели (или запросы) от программы, которая будет использоваться для решения целей, ASP рассматривает всю программу как цель и решает цель, генерируя стабильную модель, которая делает цель истинной. Для этой цели он использует семантику стабильной модели , согласно которой логическая программа может иметь ноль, одну или несколько предполагаемых моделей. Например, следующая программа представляет собой вырожденный вариант задачи раскраски карты, раскрашивающей две страны в красный или зеленый цвет:
страна ( oz ). страна ( iz ). смежный ( oz , iz ). цвет ( C , красный ) :- страна ( C ), а не ( цвет ( C , зеленый )). цвет ( C , зеленый ) :- страна ( C ), а не ( цвет ( C , красный )).Задача имеет четыре решения, представленные четырьмя устойчивыми моделями:
страна ( oz ). страна ( iz ). смежный ( oz , iz ). цвет ( oz , красный ). цвет ( iz , красный ).страна ( oz ). страна ( iz ). смежный ( oz , iz ). цвет ( oz , зеленый ). цвет ( iz , зеленый ).страна ( oz ). страна ( iz ). смежный ( oz , iz ). цвет ( oz , красный ). цвет ( iz , зеленый ).страна ( oz ). страна ( iz ). смежный ( oz , iz ). цвет ( oz , зеленый ). цвет ( iz , красный ).Для представления стандартной версии проблемы раскраски карты нам нужно добавить ограничение, что две соседние страны не могут быть окрашены в один и тот же цвет. В ASP это ограничение можно записать как предложение в форме:
:- страна ( C1 ), страна ( C2 ), смежная ( C1 , C2 ), цвет ( C1 , X ), цвет ( C2 , X ).С добавлением этого ограничения задача теперь имеет только два решения:
страна ( oz ). страна ( iz ). смежный ( oz , iz ). цвет ( oz , красный ). цвет ( iz , зеленый ).страна ( oz ). страна ( iz ). смежный ( oz , iz ). цвет ( oz , зеленый ). цвет ( iz , красный ).Добавление ограничений формы :- Body.исключает модели, в которых Bodyявляется истинным.
Сбивает с толку то, что ограничения в ASP отличаются от ограничений в CLP . Ограничения в CLP — это предикаты, которые определяют ответы на запросы (и решения целей). Ограничения в ASP — это предложения, которые исключают модели, которые в противном случае удовлетворяли бы целям. Ограничения в ASP похожи на ограничения целостности в базах данных.
Эта комбинация обычных предложений логического программирования и предложений ограничений иллюстрирует методологию «генерируй и проверяй» решения проблем в ASP: обычные предложения определяют пространство поиска возможных решений, а ограничения отфильтровывают нежелательные решения. [58]
Большинство реализаций ASP выполняются в два этапа: сначала они инстанцируют программу всеми возможными способами, сводя ее к программе пропозициональной логики (известной как заземление ). Затем они применяют решатель проблем пропозициональной логики, такой как алгоритм DPLL или решатель Boolean SAT . Однако некоторые реализации, такие как s(CASP) [59], используют целенаправленную, нисходящую, подобную процедуре разрешения SLD без заземления.
Абдуктивное логическое программирование [60] (ALP), как и CLP, расширяет обычное логическое программирование, позволяя телам предложений содержать литералы, предикаты которых не определяются предложениями. В ALP эти предикаты объявляются приводимыми (или предполагаемыми ) и используются как в абдуктивном рассуждении для объяснения наблюдений или, в более общем смысле, для добавления новых фактов в программу (в качестве предположений) для решения задач.
Например, предположим, что нам дано начальное состояние, в котором красный блок находится на зеленом блоке на столе в момент времени 0:
удерживает ( на ( зеленый_блок , таблица ), 0 ). удерживает ( на ( красный_блок , зеленый_блок ), 0 ).Предположим, нам также дана цель:
?- удерживает ( на ( зеленый_блок , красный_блок ), 3 ), удерживает ( на ( красный_блок , таблица ), 3 ).Цель может представлять наблюдение, в этом случае решение является объяснением наблюдения. Или цель может представлять желаемое будущее положение дел, в этом случае решение является планом достижения цели. [61]
Мы можем использовать правила причины и следствия, представленные ранее, для решения этой задачи, рассматривая happensпредикат как выводимый:
имеет место ( Факт , Время2 ) : - происходит ( Событие , Время1 ), Время2 равно Времени1 + 1 , инициирует ( Событие , Факт ). удерживается ( Факт , Время2 ) : происходит ( Событие , Время1 ), Время2 равно Времени1 + 1 , удерживается ( Факт , Время1 ), не ( завершено ( Факт , Время1 )). завершено ( Факт , Время ) : происходит ( Событие , Время ), завершается ( Событие , Факт ).инициирует ( перемещение ( Объект , Место ), на ( Объект , Место )). завершает ( перемещение ( Объект , Место2 ), на ( Объект , Место1 )).ALP решает цель, рассуждая в обратном порядке и добавляя предположения в программу, чтобы решить сводимые подцели. В этом случае есть много альтернативных решений, включая:
происходит ( перемещение ( красный_блок , таблица ), 0 ). происходит ( отметка , 1 ). происходит ( перемещение ( зеленый_блок , красный_блок ), 2 ).происходит ( тик , 0 ). происходит ( перемещение ( красный_блок , таблица ), 1 ). происходит ( перемещение ( зеленый_блок , красный_блок ), 2 ).происходит ( перемещение ( красный_блок , таблица ), 0 ). происходит ( перемещение ( зеленый_блок , красный_блок ), 1 ). происходит ( тик , 2 ).Вот tickсобытие, которое отмечает течение времени, не начиная и не заканчивая никаких флюентов.
Существуют также решения, в которых оба moveсобытия происходят одновременно. Например:
происходит ( перемещение ( красный_блок , таблица ), 0 ). происходит ( перемещение ( зеленый_блок , красный_блок ), 0 ). происходит ( тик , 1 ). происходит ( тик , 2 ).Такие решения, если они нежелательны, можно удалить, добавив ограничение целостности, которое похоже на условие ограничения в ASP:
:- происходит ( перемещение ( Блок1 , Место ), Время ), происходит ( перемещение ( Блок2 , Блок1 ), Время ).Абдуктивное логическое программирование использовалось для диагностики неисправностей, планирования, обработки естественного языка и машинного обучения. Оно также использовалось для интерпретации отрицания как неудачи как формы абдуктивного рассуждения. [62]
Индуктивное логическое программирование (ILP) — это подход к машинному обучению , который индуцирует логические программы как гипотетические обобщения положительных и отрицательных примеров. При наличии логической программы, представляющей фоновые знания и положительные примеры вместе с ограничениями, представляющими отрицательные примеры, система ILP индуцирует логическую программу, которая обобщает положительные примеры, исключая отрицательные.
ILP похож на ALP, в том, что оба могут рассматриваться как генерирующие гипотезы для объяснения наблюдений и как использующие ограничения для исключения нежелательных гипотез. Но в ALP гипотезы являются фактами без переменных, а в ILP гипотезы являются общими правилами. [63] [64]
Например, имея только фоновые знания об отношениях мать_ребенок и отец_ребенок и подходящие примеры отношения бабушка_ребенок, современные системы ILP могут сгенерировать определение бабушки_ребенок, придумав вспомогательный предикат, который можно интерпретировать как отношение родитель_ребенок: [65]
дедушка_ребенок ( 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, ... , GnB1, ..., 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]путем вызова целевого предложения:
Перемешать ([ туз , дама , король ], [ 1 , 4 , 2 ], Объединить ).Программа недетерминированно сгенерирует единственное решение, например Merge = [ace, queen, 1, king, 4, 2].
Карл Хьюитт утверждал [68] , что из-за неопределенности параллельных вычислений параллельное логическое программирование не может реализовать общую параллельность. Однако, согласно логической семантике, любой результат вычисления параллельной логической программы является логическим следствием программы, даже если не все логические следствия могут быть выведены.
Параллельное программирование логики ограничений [69] объединяет параллельное логическое программирование и программирование логики ограничений , используя ограничения для управления параллелизмом. Предложение может содержать охрану, которая является набором ограничений, которые могут блокировать применимость предложения. Когда охрана нескольких предложений удовлетворена, параллельное программирование логики ограничений делает выбор в пользу использования только одного.
Несколько исследователей расширили логическое программирование с помощью функций программирования более высокого порядка , полученных из логики более высокого порядка , таких как предикатные переменные. Такие языки включают расширения Prolog HiLog [70] и λProlog . [71]
Базирование логического программирования на линейной логике привело к разработке языков логического программирования, которые значительно более выразительны, чем те, которые основаны на классической логике. Программы с предложениями Хорна могут представлять изменение состояния только путем изменения аргументов в предикатах. В линейном логическом программировании можно использовать окружающую линейную логику для поддержки изменения состояния. Некоторые ранние разработки языков логического программирования, основанные на линейной логике, включают LO, [72] Lolli, [73] ACL, [74] и Forum. [75] Forum обеспечивает целенаправленную интерпретацию всей линейной логики.
F-logic [76] расширяет логическое программирование с помощью объектов и синтаксиса фреймов.
Logtalk [77] расширяет язык программирования Prolog поддержкой объектов, протоколов и других концепций ООП. Он поддерживает большинство стандартных систем Prolog в качестве бэкэнд-компиляторов.
Логика транзакций [53] является расширением логического программирования с логической теорией обновлений, изменяющих состояние. Она имеет как теоретико-модельную семантику, так и процедурную. Реализация подмножества логики транзакций доступна в системе Flora-2 [78] . Доступны также и другие прототипы .
{{cite journal}}: CS1 maint: DOI неактивен по состоянию на сентябрь 2024 г. ( ссылка )