Программирование параллельной логики ограничений - Concurrent constraint logic programming

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

История

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

Смотрите также

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

Ссылки

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