Б-Пролог

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 больше не разрабатывается активно, но он составляет основу языка программирования Picat.

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

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

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

H, G => B

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

merge([],Ys,Zs) => Zs=Ys.
merge(Xs,[],Zs) => Zs=Xs.
merge([X|Xs],[Y|Ys],Zs),X<Y => Zs=[X|ZsT],merge(Xs,[Y|Ys],ZsT).
merge(Xs,[Y|Ys],Zs) => Zs=[Y|ZsT],merge(Xs,Ys,ZsT).

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

merge([X|Xs],Ys,Zs),Ys=[Y|_],X<Y => Zs=[X|ZsT],merge(Xs,Ys,ZsT).

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

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

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

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

H, G, {E} => B

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

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

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

echo(X),{event(X,Mes)}=>writeln(Mes).
ping(T),{time(T)} => writeln(ping).

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

?-echo(X),post(event(X,hello)),post(event(X,world)).

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

?-timer(T,1000),ping(T),repeat,fail.

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

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

CLP(ФД)

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

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

'X_in_C_Y_ac'(X,Y,C),var(X),var(Y),
   {dom(Y,Ey)}
   =>         
   Ex is C-Ey,        
   domain_set_false(X,Ex).
'X_in_C_Y_ac'(X,Y,C) => true.

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

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

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

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

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

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

The foreach встроенный имеет очень простой синтаксис и семантику. Например,

foreach(A in [a,b], I in 1..2, write((A,I)))

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

X @= [(A,I) : A in [a,b], I in 1..2]

связывает X в список [(a,1),(a,2),(b,1),(b,2)]. Понимание списка рассматривается как foreach вызов с аккумулятором в реализации.

Звонки в foreach а понимание списков преобразуется в предикаты хвостовой рекурсии. Таким образом, использование этих конструкций не имеет или имеет небольшие последствия по сравнению с использованием рекурсии.

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

queens(N):-
    length(Qs,N),
    Qs :: 1..N,
    foreach(I in 1..N-1, J in I+1..N,
            (Qs[I] #\= Qs[J],
             abs(Qs[I]-Qs[J]) #\= J-I)),
    labeling([ff],Qs),
    writeln(Qs).

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

foreach(I in 1..N-1, J in I+1..N,[Qi,Qj],
        (nth(Qs,I,Qi),
         nth(Qs,J,Qj),
         Qi #\= Qj,
         abs(Qi-Qj) #\= J-I)),

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

bool_queens(N):-
   new_array(Qs,[N,N]),
   Vars @= [Qs[I,J] : I in 1..N, J in 1..N],
   Vars :: 0..1,
   foreach(I in 1..N,     % one queen in each row
           sum([Qs[I,J] : J in 1..N]) #= 1),
   foreach(J in 1..N,     % one queen in each column
           sum([Qs[I,J] : I in 1..N]) #= 1),
   foreach(K in 1-N..N-1, % at most one queen in each left-down diag
           sum([Qs[I,J] : I in 1..N, J in 1..N, I-J=:=K]) #=< 1),
   foreach(K in 2..2*N,   % at most one queen in each left-up diag
           sum([Qs[I,J] : I in 1..N, J in 1..N, I+J=:=K]) #=< 1),
   labeling(Vars),
   foreach(I in 1..N,[Row],
           (Row @= [Qs[I,J] : J in 1..N], writeln(Row))).

Таблица

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

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

:-table P1/N1,...,Pk/Nk.

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

:-table path/2.
path(X,Y):-edge(X,Y).
path(X,Y):-path(X,Z),edge(Z,Y).

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

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

:-table p(M1,...,Mn):C.

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

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

:-table sp(+,+,-,min).
sp(X,Y,[(X,Y)],W) :-
    edge(X,Y,W).
sp(X,Y,[(X,Z)|Path],W) :-
    edge(X,Z,W1),
    sp(Z,Y,Path,W2),
    W is W1+W2.

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

См. также

Ссылки

^ «Итоги Второго Международного конкурса решателей CSP и Max-CSP» . www.cril.univ-artois.fr . Проверено 20 февраля 2024 г.
^ «Соревнования по программированию второго набора ответов» . dtai.cs.kuleuven.be . Проверено 20 февраля 2024 г.
^ Решения BPSolver для проблем конкуренции третьего ASP | Ассоциация логического программирования
^ «[bp-users]Компилятор SAT в B-Prolog версии 7.8» . Архивировано из оригинала 9 марта 2014 г. Проверено 30 января 2013 г.

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

[1] «Итоги Второго Международного конкурса решателей CSP и Max-CSP» . www.cril.univ-artois.fr . Проверено 20 февраля 2024 г.

[2] «Соревнования по программированию второго набора ответов» . dtai.cs.kuleuven.be . Проверено 20 февраля 2024 г.

[3] Решения BPSolver для проблем конкуренции третьего ASP | Ассоциация логического программирования

[4] «[bp-users]Компилятор SAT в B-Prolog версии 7.8» . Архивировано из оригинала 9 марта 2014 г. Проверено 30 января 2013 г.

[1]

[2]

[3]

[4]