B-Пролог

B-Prolog был высокопроизводительной реализацией стандартного языка 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.

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

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

Н ,  Г  =>  Б

где 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 ).

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

объединить ([ X | Xs ], Ys , Zs ), Ys = [ Y | _ ], X < Y  =>  Zs = [ X | ZsT ], объединить ( Xs , Ys , ZsT ).

Звонок Ys=[Y|_]в охрану соответствует Ysшаблону [Y|_].

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

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

Н ,  Г ,  { Э }  =>  Б

где 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)повторяет любое сообщение, которое он получает. Например,

?- эхо ( X ), пост ( событие ( X , привет )), пост ( событие ( X , мир )).

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

?- таймер ( T , 1000 ), пинг ( T ), повтор , неудача .

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

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

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

Благодаря использованию AR в качестве языка реализации часть B-Prolog, решающая ограничения, относительно невелика (3800 строк кода Prolog и 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  равно  C - Ey ,  domain_set_false ( X , Ex ). 'X_in_C_Y_ac' ( X , Y , C )  =>  true .

В B-Prolog максимальная арность структуры составляет 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— целочисленное выражение. Однако эта общая нотация для доступа к массивам не является частью стандартного синтаксиса Prolog. Чтобы разместить эту нотацию, синтаксический анализатор модифицируется для вставки токена ^между токеном переменной и [. Таким образом, нотация X[I1,...,In]является просто сокращением для X^[I1,...,In]. Эта нотация интерпретируется как доступ к массиву, когда она встречается в арифметическом выражении, ограничении или в качестве аргумента вызова @=/2. В любом другом контексте она рассматривается как сам термин. Нотация индекса массива также может использоваться для доступа к элементам списков. Например, nth/3предикат можно определить следующим образом:

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

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

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

foreach ( A  in  [ a , b ],  I  in  1..2 ,  написать (( A , I )))

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

X  @=  [( A , I )  :  A  в  [ a , b ],  I  в  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  в  1. . N ,  J  в  1. . N ],  Vars  ::  0..1 ,  foreach ( I  in  1. . N ,  % один ферзь в каждой строке  сумма ([ Qs [ I , J ]  :  J  in  1. . N ])  #=  1 ),  foreach ( J  in  1. . N ,  % один ферзь в каждом столбце  сумма ([ Qs [ I , J ]  :  I  in  1. . N ])  #=  1 ),  foreach ( K  in  1 - N .. N - 1 ,  % не более одного ферзя в каждой левой нижней диагонали  сумма ([ Qs [ I , J ]  :  I  in  1. . N ,  J  in  1. . N ,  I - J =:= K ])  #=<  1 ),  foreach ( K  in  2..2 * N ,  % не более одного ферзя в каждой левой верхней диагонали  сумма ([ Qs [ I , J ]  :  I  in  1. . N ,  J  в  1. . N ,  I + J =:= K ])  #=<  1 ),  маркировка ( Vars ),  foreach ( I  в  1. . N ,[ Row ],  ( Row  @=  [ Qs [I , J ]  :  J  в  1. . N ],  writeln ( Строка ))).

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

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

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

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

:- путь к таблице  / 2. путь ( X , Y ):- ребро ( X , Y ). путь ( X , Y ):- путь ( X , Z ), ребро ( Z , Y ).

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

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

:- таблица  p ( M1 ,..., Mn ) : C .

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

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

:- таблица  sp ( + , + , - , min ). sp ( X , Y ,[( X , Y )], W )  :-  ребро ( X , Y , W ). sp ( X , Y ,[( X , Z )| Путь ], W )  :-  ребро ( X , Z , W1 ),  sp ( Z , Y , Путь , W2 ),  W  равно  W1 + W2 .

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

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

• Официальный сайт
• Как решить с помощью B-Prolog
• Возможности языка и архитектура B-Prolog
• Сравнение производительности систем Prolog и CLP(FD)
• Производительность Logtalk