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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

Расширением синтаксиса и семантики параллельного логического программирования является атомный жест. Когда интерпретатор использует предложение, его защита добавляется в хранилище ограничений. Однако также добавлены ограничения тела. Из-за выполнения этого пункта интерпретатор не выполняет возврат, если ограничения тела несовместимы с хранилищем. Этого условия можно избежать с помощью атомарного сообщения, которое представляет собой вариант, в котором предложение содержит своего рода «вторую охрану», которая проверяется только на согласованность. Такая оговорка написана H: - G: D | B. Это предложение используется для перезаписи литерала, только если г влечет за собой хранилище ограничений и D согласуется с этим. В этом случае оба г и 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. Дои:10.1016/0743-1066(94)90033-7.

Конкретный

1. Frühwirth, Thom. "Теория и практика правил обработки ограничений. »Журнал логического программирования 37.1-3 (1998): 95-138.