B-Prolog - это высокопроизводительная реализация стандартного языка Prolog с несколькими расширенными функциями, включая предложения сопоставления, правила действий для обработки событий, решение ограничений конечной области, массивы и хеш-таблицы, декларативные циклы и табуляцию. Впервые выпущенный в 1994 году, B-Prolog теперь является широко используемой системой CLP . Решатель В-Prolog занял вершину в двух категориях в Втором Международном конкурсе решателей , [1] , и он также занял второе место в Р классе во втором ASP Solver конкуренции [2] , а второе месте в общем зачете в третьем Конкурс решателей ASP. [3] B-Prolog поддерживает систему PRISM, логическая система вероятностных рассуждений и обучения. B-Prolog - коммерческий продукт, но его можно использовать в учебных и некоммерческих исследовательских целях бесплатно (начиная с версии 7.8 для индивидуальных пользователей, включая коммерческих индивидуальных пользователей, B-Prolog предоставляется бесплатно [4] ).
Соответствующие статьи [ править ]
Предложение сопоставления - это форма предложения, в которой явно указаны детерминированность и унификация ввода / вывода. Компилятор переводит предложения соответствия в деревья соответствия и генерирует индексы для всех входных аргументов. Компиляция предложений сопоставления намного проще, чем компиляция обычных предложений Пролога, потому что не требуется сложный программный анализ или специализация; а сгенерированный код становится более компактным и быстрым. Компилятор B-Prolog и большинство предикатов библиотеки написаны в соответствующих предложениях.
Предложение соответствия принимает следующую форму:
H , G => Bгде H- атомарная формула, Gи B- две последовательности атомарных формул. Hназывается главой, Gохраной и Bосновной частью предложения. Никакой вызов не Gможет связывать переменные, Hи все вызовы Gдолжны быть встроенными тестами. Другими словами, гарда должна быть плоской. Ниже приводится пример предиката в предложениях сопоставления, который объединяет два отсортированных списка:
объединить ([], Ys , Zs ) => Zs = Ys . объединить ( Xs , [], Zs ) => Zs = Xs . объединить ([ X | Xs ], [ Y | Ys ], Zs ), X < Y => Zs = [ X | ZsT ], объединить ( Xs , [ Y | Ys ], ZsT ). объединить (Xs , [ Y | Ys ], Zs ) => Zs = [ Y | ZsT ], объединить ( Xs , Ys , ZsT ).Минусы [Y|Ys]встречаются как в главе, так и в теле третьего предложения. Чтобы избежать реконструкции термина, мы можем переписать предложение следующим образом:
объединить ([ X | Xs ], Ys , Zs ), Ys = [ Y | _ ], X < Y => Zs = [ X | ZsT ], объединить ( Xs , Ys , ZsT ).Вызов Ys=[Y|_]охранника соответствует Ysшаблону [Y|_].
Правила действий [ править ]
Отсутствие средства программирования «активных» подцелей, которые могут реагировать на окружающую среду, считается одной из слабых сторон логического программирования. Чтобы преодолеть это, B-Prolog предоставляет простой, но мощный язык, называемый Правилами действий (AR), для агентов программирования. Агент - это подцель, которую можно отложить, а затем можно активировать событиями. Каждый раз, когда агент активируется, может выполняться какое-то действие. Агенты - это более общее понятие, чем конструкции задержки в ранних системах Prolog и процессы в языках параллельного логического программирования в том смысле, что агенты могут реагировать на различные виды событий, включая создание экземпляров, предметную область, время и определяемые пользователем события.
Правило действия принимает следующее
H , G , { E } => Bгде H- шаблон для агентов, G- это последовательность условий для агентов, E- это набор шаблонов для событий, которые могут активировать агентов, и Bпредставляет собой последовательность действий, выполняемых агентами при их активации. Если шаблон события Eвместе с закрывающими фигурными скобками отсутствует, правило действия превращается в предложение сопоставления.
Для программирования распространителей ограничений и интерактивных графических пользовательских интерфейсов предоставляется набор встроенных событий. Например, ins(X)это событие, которое публикуется при создании переменной X. Пользовательская программа может создавать и публиковать свои собственные события и определять агентов для их обработки. Определяемый пользователь событие принимает форму , event(X,O)где Xявляется переменным, называется переменной подвеска, которая соединяет событие с его обработкой агентов, и Oэто термин Пролога , который содержит информацию, подлежащую передаче к агентам. Встроенные post(E)сообщения о событии E.
Рассмотрим следующие примеры:
echo ( X ), { событие ( X , Mes )} => Writeln ( Mes ). пинг ( Т ), { время ( Т )} => писать ( пинг ).Агент echo(X)повторяет полученное сообщение. Например,
? - эхо ( X ), сообщение ( событие ( X , привет )), сообщение ( событие ( X , мир )).выводит сообщение, helloза которым следует world. Агент ping(T)реагирует на временные события от таймера T. Каждый раз, когда он получает временное событие, он печатает сообщение ping. Например,
? - таймер ( T , 1000 ), пинг ( T ), повтор , сбой .создает таймер, который отправляет событие времени каждую секунду и создает агента ping(T)для ответа на события. Цикл после агента необходим для того, чтобы агент был бессрочным.
AR оказался полезным для программирования простого параллелизма, реализации пропагаторов ограничений и разработки интерактивных графических пользовательских интерфейсов. Он служил промежуточным языком для компиляции правил обработки ограничений (CHR) и программ набора ответов (ASP).
CLP (FD) [ править ]
Как и многие решатели ограничений конечной области на основе Prolog, решатель конечной области 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 строк кода 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 ) => истина .Массивы и индексирование массивов [ править ]
В 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- целочисленное выражение. Однако эта общая нотация для доступа к массивам не является частью стандартного синтаксиса Пролога. Чтобы учесть эту нотацию, синтаксический анализатор модифицируется для вставки токена ^между токеном переменной и [. Итак, обозначение X[I1,...,In]- это просто сокращение для X^[I1,...,In]. Эта нотация интерпретируется как доступ к массиву, когда он встречается в арифметическом выражении, ограничении или как аргумент вызова к@=/2. В любом другом контексте это рассматривается как сам термин. Обозначение индекса массива также может использоваться для доступа к элементам списков. Например, nth/3предикат можно определить следующим образом:
n-й ( I , L , E ) : - E @ = L [ I ].Циклы с foreach и понимание списка [ править ]
Prolog использует рекурсию для описания циклов. Отсутствие мощных конструкций циклов, возможно, сделало Пролог менее приемлемым для новичков и менее продуктивным для опытных программистов, поскольку часто бывает утомительно определять небольшие вспомогательные рекурсивные предикаты для циклов. Появление конструкций программирования с ограничениями, таких как CLP (FD), еще больше выявило эту слабость Prolog как языка моделирования. B-Prolog предоставляет встроенный, называемый foreach, для итерации по коллекциям и нотацию понимания списка для построения списков.
foreachВстроенный имеет очень простой синтаксис и семантику. Например,
foreach ( A в [ a , b ], I в 1..2 , напишите (( A , I )))выходы четыре кортежей (a,1), (a,2), (b,1), и (b,2). Синтаксически foreachэто вызов переменной длины, последний аргумент которого указывает цель, которая должна выполняться для каждой комбинации значений в последовательности коллекций. foreachВызов может также дать список переменных , которые являются локальными для каждой итерации и списка аккумуляторов , которые могут быть использованы для значений накапливаются от каждой итерации. С помощью аккумуляторов мы можем использовать foreachдля описания повторений вычислений агрегатов. Повторения должны быть прочитаны процедурно и поэтому не подходят для Prolog. По этой причине мы заимствуем нотацию понимания списков из функциональных языков. Понимание списка - это список, первый элемент которого имеет функтор ' :'. Список этой формы интерпретируется как понимание списка при обращении к@=/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:
ферзей ( N ): - длина ( Qs , N ), Qs :: 1 .. N , Еогеасп ( я в 1. . N - 1 , J в I + 1. . N , ( Qs [ I ] # \ = Qs [ J ], абс ( Qs [ I ] - Qs [ J ]) # \ = J -I )), маркировка ([ ff ], Qs ), Writeln ( Qs ).Обозначение массивов в списках помогает сократить описание. Без него foreachцикл в программе пришлось бы записать следующим образом:
foreach ( I в 1 .. N - 1 , J в 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 ], Варс :: 0..1 , Еогеасп ( я в 1. . N , % : одна полуторная в каждой строке суммы ([ Qs [ I , J ] : J в 1 .. N ]) # = 1 ), foreach ( J в 1 .. N , % один ферзь в сумме каждого столбца ([ Qs [ I , J ] : I в 1 .. N ]) # = 1 ), foreach ( K в 1 - N .. N - 1 , % не более одного ферзя в каждой сумме диагнозов слева вниз ([ Qs [ I, J ] : I в 1 .. N , J в 1 .. N , I - J =: = K ]) # = < 1 ), foreach ( K в 2..2 * N , % не более одного ферзя в каждой сумме диагнозов слева вверх ([ Qs [ I , J ] : I в 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 ). path ( X , Y ): - путь ( X , Z ), край ( Z , Y ).При использовании табуляции любой запрос к программе гарантированно завершится, пока размеры терминов ограничены.
По умолчанию все аргументы табличного вызова используются при проверке вариантов, а все ответы представлены для табличного предиката. B-Prolog поддерживает табличные режимы, которые позволяют системе выборочно использовать только входные аргументы при проверке вариантов и табличных ответах. Объявление табличного режима
: - таблица р ( М1 , ..., Mn ) : С .инструктирует система , как это сделать на столы 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 ) : - edge ( X , Z , W1 ), sp ( Z, Y , Path , W2 ), W - это W1 + W2 .В табличном режиме указывается, что для каждой пары узлов отображается только один путь с минимальным весом.
Ссылки [ править ]
- ^ Итоги Второго международного конкурса решателей CSP и Max-CSP
- ^ http://www.cs.kuleuven.be/~dtai/events/ASP-competition/index.shtml
- ^ Решения BPSolver для третьих проблем конкуренции ASP | Ассоциация логического программирования
- ^ "Архивная копия" . Архивировано из оригинала на 2014-03-09 . Проверено 30 января 2013 .CS1 maint: заархивированная копия как заголовок ( ссылка )
Внешние ссылки [ править ]
