Параллельное программирование логики ограничений

Параллельное логическое программирование с ограничениями — это версия логического программирования с ограничениями, направленная в первую очередь на программирование параллельных процессов, а не (или в дополнение) к решению проблем удовлетворения ограничений . Цели в программировании логики ограничений оцениваются одновременно; Таким образом, параллельный процесс программируется как оценка цели интерпретатором .

Синтаксически программы параллельной логики ограничений аналогичны непараллельным программам, за исключением того, что предложения включают в себя ограничители , которые представляют собой ограничения, которые могут блокировать применимость предложения при некоторых условиях. Семантически параллельное программирование логики ограничений отличается от своих непараллельных версий, поскольку оценка цели предназначена для реализации параллельного процесса, а не для поиска решения проблемы. В частности, это различие влияет на поведение интерпретатора, когда применимо более одного предложения: программирование логики непараллельных ограничений рекурсивно пробует все предложения; параллельное программирование логики ограничений выбирает только одно. Это наиболее очевидный эффект намеренной направленности переводчика, который никогда не пересматривает ранее сделанный выбор. Другими последствиями этого являются семантическая возможность наличия цели, которая не может быть доказана, пока вся оценка не окажется неудачной, а также особый способ приравнивания цели и заголовка предложения.

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

Описание

В программировании логики ограничений цели текущей цели оцениваются последовательно, обычно в порядке LIFO , в котором новые цели оцениваются первыми. Параллельная версия логического программирования позволяет оценивать цели параллельно : каждая цель оценивается процессом, и процессы выполняются одновременно. Эти процессы взаимодействуют через хранилище ограничений: один процесс может добавить ограничение в хранилище ограничений, в то время как другой проверяет, связано ли ограничение с хранилищем.

Добавление ограничения в хранилище выполняется так же, как и в обычном программировании логики ограничений. Проверка следствия ограничения осуществляется через защиту предложений. Для защиты требуется синтаксическое расширение: раздел параллельного программирования логики ограничений записывается как H :- G | B где Gэто ограничение, называемое защитой предложения. Грубо говоря, новый вариант этого предложения можно использовать для замены литерала в цели только в том случае, если защита влечет за собой хранилище ограничений после того, как к нему добавлено уравнение литерала и заголовок предложения. Точное определение этого правила более сложное и приведено ниже.

Основное различие между непараллельным и параллельным программированием логики ограничений состоит в том, что первое нацелено на поиск, а второе — на реализацию параллельных процессов. Эта разница влияет на то, можно ли отменить выбор, разрешено ли процессам не завершаться и как приравниваются цели и заголовки пунктов.

Первое семантическое различие между обычным и параллельным логическим программированием с ограничениями касается условия, когда для доказательства цели можно использовать более одного предложения. Непараллельное логическое программирование перебирает все возможные предложения при переписывании цели: если цель не может быть доказана при замене ее телом нового варианта предложения, доказывается другое предложение, если таковое имеется. Это потому, что цель состоит в том, чтобы доказать цель: испробуются все возможные способы доказать цель. С другой стороны, параллельное программирование логики ограничений направлено на программирование параллельных процессов. В общем параллельном программировании, если процесс делает выбор, этот выбор нельзя отменить. Параллельная версия программирования логики ограничений реализует процессы, позволяя им делать выбор, но фиксируя их, как только они будут приняты. Технически, если для перезаписи литерала в цели можно использовать более одного предложения, непараллельная версия по очереди пробует все предложения, а параллельная версия выбирает одно произвольное. пункт: в отличие от непараллельной версии, другие пункты никогда не будут использоваться. Эти два разных способа обработки множественного выбора часто называют «не знаю недетерминизма» и «не обращаю внимания на недетерминизм».

При переписывании литерала в цели рассматриваются только те предложения, защита которых обусловлена ​​объединением хранилища ограничений и уравнением литерала с заголовком предложения. Охранники позволяют указать, какие пункты вообще не следует учитывать. Это особенно важно, учитывая приверженность единому предложению параллельного программирования логики с ограничениями: как только предложение будет выбрано, этот выбор никогда не будет пересматриваться. Без защит интерпретатор мог бы выбрать «неправильное» предложение для переписывания литерала, в то время как существуют другие «хорошие» предложения. В непараллельном программировании это менее важно, поскольку интерпретатор всегда пробует все возможности. При параллельном программировании интерпретатор фиксирует одну возможность, не пробуя другие.

Второй эффект разницы между непараллельной и параллельной версией заключается в том, что параллельное программирование логики ограничений специально разработано для того, чтобы позволить процессам выполняться без завершения. Незавершающиеся процессы обычно распространены в параллельной обработке; параллельная версия программирования логики ограничений реализует их, не используя условие отказа: если ни одно предложение не применимо для переписывания цели, процесс оценки этой цели останавливается вместо того, чтобы привести к сбою всей оценки, как в непараллельном программировании логики ограничений. В результате процесс оценки цели может быть остановлен, поскольку нет доступных для продолжения предложений, но в то же время другие процессы продолжают работать.

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

Третий эффект разницы между параллельным и непараллельным логическим программированием заключается в том, что цель приравнивается к началу нового варианта предложения. Оперативно это делается путем проверки того, можно ли приравнять переменные в голове к термам таким образом, чтобы голова была равна цели. Это правило отличается от соответствующего правила программирования логики ограничений тем, что оно позволяет добавлять ограничения только в виде переменная=термин, где переменная является одной из голов. Это ограничение можно рассматривать как форму направленности, поскольку цель и заголовок предложения рассматриваются по-разному.

Точнее, правило, говорящее, есть ли свежий вариант H:-G|B предложения можно использовать, чтобы переписать цель Aкак следует. Сначала проверяется, является ли A и Hимеют одинаковый предикат. Во-вторых, проверяется, существует ли способ приравнять $A$ с $H$учитывая текущий магазин ограничений; в отличие от обычного логического программирования, это делается при односторонней унификации , которая позволяет только переменной головы быть равной терму. В-третьих, защита проверяется на наличие последствий из хранилища ограничений и уравнений, сгенерированных на втором этапе; охранник может содержать переменные, которые не упомянуты в заголовке предложения: эти переменные интерпретируются экзистенциально. Этот метод принятия решения о применимости нового варианта предложения для замены цели можно компактно выразить следующим образом: текущее хранилище ограничений предполагает, что существует оценка переменных головы и защиты такая, что голова равна цель и охрана влекут за собой. На практике наличие следствия можно проверить неполным методом.

Расширением синтаксиса и семантики параллельного логического программирования является атомарный телл . Когда интерпретатор использует предложение, его защита добавляется в хранилище ограничений. Однако к этому также добавляются ограничения тела. Благодаря соблюдению этого пункта интерпретатор не делает возврата, если ограничения тела несовместимы с хранилищем. Этого условия можно избежать, используя атомарное сообщение, которое представляет собой вариант, в котором предложение содержит своего рода «вторую защиту», которая проверяется только на согласованность. Такой пункт написан H :- G:D|B. Это предложение используется для перезаписи литерала только в том случае, если G влечет за собой хранилище ограничений и Dсоответствует этому. В этом случае оба G и D добавляются в хранилище ограничений.

История

Изучение параллельного программирования логики с ограничениями началось в конце 1980-х годов, когда некоторые принципы параллельного логического программирования были интегрированы в программирование логики с ограничениями Майклом Дж. Махером . Теоретические свойства параллельного программирования логики с ограничениями позже изучались различными авторами, в том числе Мартином Ринардом и Виджаем А. Сарасватом.

См. также

• Curry — логический функциональный язык программирования, позволяющий программировать параллельные системы [1] .
• ToonTalk
• Янус
• Алиса

Библиография

• Марриотт, Ким; Питер Дж. Стаки (1998). Программирование с ограничениями: Введение . МТИ Пресс. ISBN   0-262-13341-5
• Фрювирт, Том; Слим Абденнадер (2003). Основы программирования в ограничениях . Спрингер. ISBN   3-540-67623-6
• Джаффар, Джоксан; Майкл Дж. Махер (1994). «Программирование логики ограничений: обзор» . Журнал логического программирования . 19/20: 503–581. дои : 10.1016/0743-1066(94)90033-7 .