B-Prolog - B-Prolog

B-Prolog это высокопроизводительная реализация стандарта Пролог язык с несколькими расширенными функциями, включая предложения сопоставления, правила действий для обработки событий, решение ограничений конечной области, массивы и хеш-таблицы, декларативные циклы и таблицы. Впервые выпущенный в 1994 году, B-Prolog сейчас широко используется CLP система. Решатель ограничений B-Prolog занял первое место в двух категориях в Второй международный конкурс решателей,[1] а также занял второе место в классе P во втором конкурсе ASP-решателей [2] и второе место в третьем конкурсе решателей ASP.[3] B-Prolog лежит в основе Система PRISM, логическая система вероятностных рассуждений и обучения. B-Prolog - коммерческий продукт, но его можно использовать в учебных и некоммерческих исследовательских целях бесплатно (начиная с версии 7.8 для индивидуальных пользователей, включая коммерческих индивидуальных пользователей, B-Prolog предоставляется бесплатно. [4]).

Соответствующие предложения

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

Предложение соответствия принимает следующую форму:

ЧАС, г => B

где ЧАС атомарная формула, г и B две последовательности атомарных формул. ЧАС называется головой, г охранник, и B тело статьи. Нет звонка г может связывать переменные в ЧАС и все звонки г должны быть поточные тесты. Другими словами, ограждение должно быть плоским. Ниже приводится пример предиката в предложениях сопоставления, который объединяет два отсортированных списка:

слияние([],Ys,Zs) => Zs=Ys.слияние(Хз,[],Zs) => Zs=Хз.слияние([Икс|Хз],[Y|Ys],Zs),Икс<Y => Zs=[Икс|ZsT],слияние(Хз,[Y|Ys],ZsT).слияние(Хз,[Y|Ys],Zs) => Zs=[Y|ZsT],слияние(Хз,Ys,ZsT).

Минусы [Y | Ys] встречается как в главе, так и в теле третьего предложения. Чтобы избежать восстановления термина, мы можем переписать предложение следующим образом:

слияние([Икс|Хз],Ys,Zs),Ys=[Y|_],Икс<Y => Zs=[Икс|ZsT],слияние(Хз,Ys,ZsT).

Звонок Ys = [Y | _] в матчах охраны Ys против шаблона [Y | _].

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

Отсутствие средств программирования «активных» подцелей, которые могут реагировать на окружающую среду, считается одной из слабых сторон логического программирования. Чтобы преодолеть это, B-Prolog предоставляет простой, но мощный язык, называемый Правилами действий (AR), для агентов программирования. Агент - это подцель, которую можно отложить, а затем можно активировать событиями. Каждый раз, когда агент активируется, может выполняться какое-то действие. Агенты - это более общее понятие, чем конструкции задержки в ранних системах Prolog и процессы в языках параллельного логического программирования в том смысле, что агенты могут реагировать на различные виды событий, включая создание экземпляров, предметную область, время и определяемые пользователем события.

Правило действия принимает следующее

ЧАС, г, {E} => B

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

Для программирования распространителей ограничений и интерактивных графических пользовательских интерфейсов предоставляется набор встроенных событий. Например, ins (X) это событие, которое публикуется, когда переменная Икс создается экземпляр. Пользовательская программа может создавать и публиковать свои собственные события и определять агентов для их обработки. Определяемое пользователем событие принимает форму событие (X, O) где Икс это переменная, называемая переменной приостановки, которая связывает событие с его агентами обработки, и О - это термин Пролога, содержащий информацию, которая должна быть передана агентам. Встроенный сообщение (E) публикует событие E.

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

эхо(Икс),{мероприятие(Икс,Mes)}=>Writeln(Mes).пинг(Т),{время(Т)} => Writeln(пинг).

Агент эхо (X) повторяет любое полученное сообщение. Например,

?-эхо(Икс),сообщение(мероприятие(Икс,Здравствуйте)),сообщение(мероприятие(Икс,Мир)).

выводит сообщение Здравствуйте с последующим Мир. Агент пинг (T) реагирует на временные события от таймера Т. Каждый раз, когда он получает событие времени, он печатает сообщение пинг. Например,

?-таймер(Т,1000),пинг(Т),повторение,провал.

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

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

CLP (FD)

Как и многие решатели ограничений конечной области на основе Пролога, решатель конечных областей B-Prolog сильно зависит от ЧИП система. Первый полноценный решатель был выпущен в версии 2.1 B-Prolog в марте 1997 года. Этот решатель был реализован в ранней версии AR, называемой предложениями задержки. В течение последнего десятилетия язык реализации AR был расширен для поддержки широкого класса событий предметной области (ins (X),граница (X),dom (X, E), и dom_any (X, E)) для программирования пропагаторов ограничений, и система была обогащена новыми областями (логические, деревья и конечные множества), глобальными ограничениями и специализированными быстрыми пропагаторами ограничений. Недавно два встроенных модуля дюйм / 2 и notin / 2 были расширены, чтобы разрешить положительные и отрицательные ограничения таблицы (также называемые экстенсиональными).

Благодаря использованию AR в качестве языка реализации, часть решения ограничений B-Prolog относительно мала (3800 строк кода Prolog и 6000 строк кода C, включая комментарии и пробелы), но его производительность очень конкурентоспособна. Язык AR открыт для пользователя для реализации пропагаторов конкретных задач. Например, следующее определяет пропагатор для поддержания согласованности дуги для ограничения X + Y # = C. Всякий раз, когда внутренний элемент Эй исключен из домена Y, этот пропагатор запускается для исключения Ex, аналог Эй, из домена Икс. Для ограничения X + Y # = C, нам нужно сгенерировать два пропагатора, а именно 'X_in_C_Y_ac' (X, Y, C) и 'X_in_C_Y_ac' (Y, X, C), чтобы поддерживать постоянство дуги. В дополнение к этим двум пропагаторам нам также необходимо сгенерировать пропагаторы для поддержания согласованности интервалов, поскольку нет дом (Y, Ey) событие публикуется, если исключенное значение оказывается привязанным. Ограничение необходимо предварительно обработать, чтобы оно было согласованным до создания пропагаторов.

'X_in_C_Y_ac'(Икс,Y,C),вар(Икс),вар(Y),   {дом(Y,Эй)}   =>            Ex является C-Эй,           domain_set_false(Икс,Ex).'X_in_C_Y_ac'(Икс,Y,C) => правда.

Массивы и обозначение индекса массива

В B-Prolog максимальная арность структуры составляет 65535. Это означает, что структура может использоваться как одномерный массив, а многомерный массив может быть представлен как структура структур. Чтобы облегчить создание массивов, B-Prolog предоставляет встроенный, называемый новый_массив (X, Тусклый), где Икс должна быть неустановленной переменной и Тускнеет список положительных целых чисел, определяющий размеры массива. Например, звонок новый_массив (X, [10,20]) связывает Икс в двумерный массив, первое измерение которого имеет 10 элементов, а второе измерение - 20 элементов. Все элементы массива инициализируются как свободные переменные.

Встроенный предикат arg / 3 может использоваться для доступа к элементам массива, но для этого требуется временная переменная для хранения результата и цепочка вызовов для доступа к элементу многомерного массива. Чтобы облегчить доступ к элементам массива, B-Prolog поддерживает обозначение индекса массива X [I1, ..., In], где Икс это структура и каждый II является целочисленным выражением. Однако эта общая нотация для доступа к массивам не является частью стандартного синтаксиса Пролога. Чтобы приспособить эту нотацию, синтаксический анализатор модифицируется для вставки токена ^ между токеном переменной и [. Итак, обозначение X [I1, ..., In] это просто сокращение для X ^ [I1, ..., In]. Эта нотация интерпретируется как доступ к массиву, когда он встречается в арифметическом выражении, ограничении или как аргумент вызова к @=/2. В любом другом контексте это рассматривается как сам термин. Обозначение индекса массива также может использоваться для доступа к элементам списков. Например, nth / 3 предикат можно определить следующим образом:

nth(я,L,E) :- E @= L[я].

Циклы с foreach и понимание списка

Prolog использует рекурсию для описания циклов. Отсутствие мощных конструкций циклов, возможно, сделало Пролог менее приемлемым для новичков и менее продуктивным для опытных программистов, потому что часто бывает утомительно определять небольшие вспомогательные рекурсивные предикаты для циклов. Появление конструкций программирования с ограничениями, таких как CLP (FD) далее раскрыл эту слабость Prolog как языка моделирования. B-Prolog предоставляет встроенный, называемый для каждого, для перебора коллекций и понимание списка обозначение для построения списков.

В для каждого встроенный имеет очень простой синтаксис и семантику. Например,

для каждого(А в [а,б], я в 1..2, записывать((А,я)))

выводит четыре кортежа (а, 1), (а, 2), (б, 1), и (Би 2). Синтаксически, для каждого - это вызов переменной длины, последний аргумент которого указывает цель, которая должна выполняться для каждой комбинации значений в последовательности коллекций. А для каждого Вызов может также предоставить список переменных, локальных для каждой итерации, и список аккумуляторов, которые можно использовать для накопления значений с каждой итерации. С аккумуляторами мы можем использовать для каждого для описания повторений вычислительных агрегатов. Повторения должны быть прочитаны процедурно и поэтому не подходят для Prolog. По этой причине мы заимствуем нотацию понимания списков из функциональных языков. Понимание списка - это список, первый элемент которого имеет функтор ':'. Список этой формы интерпретируется как понимание списка при обращении к @=/2 и арифметические ограничения. Например, запрос

Икс @= [(А,я) : А в [а,б], я в 1..2]

связывает Икс к списку [(a, 1), (a, 2), (b, 1), (b, 2)]. Составление списка рассматривается как для каждого вызов с аккумулятором в реализации.

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

Конструкции петель значительно увеличивают возможности моделирования CLP (FD). Ниже приводится программа для задачи N-ферзей на B-Prolog:

королевы(N):-    длина(Qs,N),    Qs :: 1..N,    для каждого(я в 1..N-1, J в я+1..N,            (Qs[я] #= Qs[J],             пресс(Qs[я]-Qs[J]) #= J-я)),    маркировка([ff],Qs),    Writeln(Qs).

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

для каждого(я в 1..N-1, J в я+1..N,[Ци,Qj],        (nth(Qs,я,Ци),         nth(Qs,J,Qj),         Ци #= Qj,         пресс(Ци-Qj) #= J-я)),

где Ци и Qj объявляются локальными для каждой итерации. Ниже приведена программа для задачи N ферзей, в которой для каждого квадрата на доске используется логическая переменная.

bool_queens(N):-   new_array(Qs,[N,N]),   Варс @= [Qs[я,J] : я в 1..N, J в 1..N],   Варс :: 0..1,   для каждого(я в 1..N,     % один ферзь в каждой строке           сумма([Qs[я,J] : J в 1..N]) #= 1),   для каждого(J в 1..N,     % один ферзь в каждом столбце           сумма([Qs[я,J] : я в 1..N]) #= 1),   для каждого(K в 1-N..N-1, % не более одного ферзя в каждом диагонали слева вниз           сумма([Qs[я,J] : я в 1..N, J в 1..N, я-J=:=K]) #=< 1),   для каждого(K в 2..2*N,   % не более одного ферзя на каждом диагонали слева вверх           сумма([Qs[я,J] : я в 1..N, J в 1..N, я+J=:=K]) #=< 1),   маркировка(Варс),   для каждого(я в 1..N,[Ряд],           (Ряд @= [Qs[я,J] : J в 1..N], Writeln(Ряд))).

Таблинг

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

Идея таблицы состоит в том, чтобы запомнить ответы на внесенные в таблицу вызовы и использовать ответы для решения последующих вариантов вызовов. В B-Prolog, как и в XSB, табличные предикаты явно объявляются объявлениями в следующей форме:

:-Таблица P1/N1,...,Pk/Nk.

Например, следующий табличный предикат определяет переходное закрытие отношения как дано край / 2.

:-Таблица дорожка/2.дорожка(Икс,Y):-край(Икс,Y).дорожка(Икс,Y):-дорожка(Икс,Z),край(Z,Y).

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

По умолчанию все аргументы табличного вызова используются при проверке вариантов, а все ответы представлены для табличного предиката. B-Prolog поддерживает табличные режимы, которые позволяют системе выборочно использовать только входные аргументы при проверке вариантов и табличных ответах. Объявление табличного режима

:-Таблица п(M1,...,Mn):C.

инструктирует систему, как делать таблицы на п / п, где C, называется предел мощности, является целым числом, ограничивающим количество ответов, которые должны быть представлены, и каждый Ми это режим, который может быть мин, Максимум, + (ввод), или - (вывод). Аргумент с режимом мин или Максимум предполагается выводить. Если предел мощности C является 1, его можно опустить с помощью предыдущего символа ':'.

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

:-Таблица зр(+,+,-,мин).зр(Икс,Y,[(Икс,Y)],W) :-    край(Икс,Y,W).зр(Икс,Y,[(Икс,Z)|Дорожка],W) :-    край(Икс,Z,W1),    зр(Z,Y,Дорожка,W2),    W является W1+W2.

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

использованная литература

  1. ^ Итоги Второго Международного конкурса решателей CSP и Max-CSP
  2. ^ http://www.cs.kuleuven.be/~dtai/events/ASP-competition/index.shtml
  3. ^ Решения BPSolver для Третьего Конкурса ASP | Ассоциация логического программирования
  4. ^ «Архивная копия». Архивировано из оригинал на 2014-03-09. Получено 2013-01-30.CS1 maint: заархивированная копия как заголовок (ссылка на сайт)

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