Параллельное программирование логики ограничений — это версия программирования логики ограничений, направленная в первую очередь на программирование параллельных процессов , а не (или в дополнение к) решению проблем удовлетворения ограничений . Цели в программировании логики ограничений оцениваются параллельно; параллельный процесс, таким образом, программируется как оценка цели интерпретатором .
Синтаксически параллельные программы с логикой ограничений похожи на непараллельные программы, единственным исключением является то, что предложения включают защитные элементы , которые являются ограничениями, которые могут блокировать применимость предложения при некоторых условиях. Семантически параллельное программирование с логикой ограничений отличается от своих непараллельных версий, поскольку оценка цели предназначена для реализации параллельного процесса, а не для поиска решения проблемы. В частности, это различие влияет на то, как ведет себя интерпретатор, когда применимо более одного предложения: непараллельное программирование с логикой ограничений рекурсивно пробует все предложения; параллельное программирование с логикой ограничений выбирает только одно. Это наиболее очевидный эффект преднамеренной направленности интерпретатора, который никогда не пересматривает сделанный ранее выбор. Другими эффектами этого являются семантическая возможность наличия цели, которая не может быть доказана, пока вся оценка не терпит неудачу, и особый способ уравнивания цели и заголовка предложения.
Правила обработки ограничений можно рассматривать как форму параллельного программирования логики ограничений [1], но они используются для программирования упростителя или решателя ограничений, а не параллельных процессов.
В программировании логики ограничений цели в текущей цели оцениваются последовательно, обычно в порядке LIFO , в котором новые цели оцениваются первыми. Параллельная версия логического программирования позволяет оценивать цели параллельно : каждая цель оценивается процессом, и процессы выполняются одновременно. Эти процессы взаимодействуют через хранилище ограничений: процесс может добавить ограничение в хранилище ограничений, в то время как другой проверяет, влечет ли хранилище ограничение.
Добавление ограничения в хранилище выполняется так же, как в обычном программировании логики ограничений. Проверка следствия ограничения выполняется с помощью охранников к предложениям. Охранники требуют синтаксического расширения: предложение параллельного программирования логики ограничений записывается как , H :- G | Bгде Gесть ограничение, называемое охранником предложения. Грубо говоря, новый вариант этого предложения может использоваться для замены литерала в цели, только если охранник следует из хранилища ограничений после того, как уравнение литерала и заголовок предложения добавлены к нему. Точное определение этого правила более сложное и приведено ниже.
Основное различие между неконкурентным и конкурентным программированием логики ограничений заключается в том, что первое нацелено на поиск, а второе — на реализацию конкуренциальных процессов. Это различие влияет на то, можно ли отменить выбор, разрешено ли процессам не завершаться и как приравниваются цели и заголовки предложений.
Первое семантическое различие между обычным и параллельным программированием логики ограничений заключается в условии, когда для доказательства цели можно использовать более одного предложения. Непараллельное логическое программирование пробует все возможные предложения при переписывании цели: если цель не может быть доказана при замене ее телом нового варианта предложения, доказывается другое предложение, если таковое имеется. Это связано с тем, что цель состоит в том, чтобы доказать цель: пробуются все возможные способы доказательства цели. С другой стороны, параллельное программирование логики ограничений направлено на программирование параллельных процессов. В общем параллельном программировании, если процесс делает выбор, этот выбор не может быть отменен. Параллельная версия программирования логики ограничений реализует процессы, позволяя им делать выбор, но принимая их после того, как они были сделаны. Технически, если для переписывания литерала в цели можно использовать более одного предложения, непараллельная версия пробует по очереди все предложения, в то время как параллельная версия выбирает одно произвольное предложение: в отличие от непараллельной версии, другие предложения никогда не будут пробоваться. Эти два разных способа обработки множественных выборов часто называют «не знаю, неопределенность» и «неважно, неопределенность».
При переписывании литерала в цели рассматриваются только те предложения, охрана которых вытекает из объединения хранилища ограничений и уравнения литерала с заголовком предложения. Охранники предоставляют способ указать, какие предложения вообще не следует рассматривать. Это особенно важно, учитывая приверженность единственному предложению программирования логики параллельных ограничений: как только предложение выбрано, этот выбор никогда не будет пересмотрен. Без охранников интерпретатор может выбрать «неправильное» предложение для переписывания литерала, в то время как существуют другие «хорошие» предложения. В непараллельном программировании это менее важно, поскольку интерпретатор всегда пробует все возможности. В параллельном программировании интерпретатор принимает одну возможность, не пробуя другие.
Вторым следствием разницы между параллельной и непараллельной версиями является то, что параллельное программирование логики ограничений специально разработано для того, чтобы процессы могли работать без завершения. Незавершающиеся процессы распространены в целом в параллельной обработке; параллельная версия программирования логики ограничений реализует их, не используя условие отказа: если ни одно предложение не применимо для переписывания цели, процесс, оценивающий эту цель, останавливается вместо того, чтобы сделать всю оценку неудачной, как в непараллельном программировании логики ограничений. В результате процесс, оценивающий цель, может быть остановлен, поскольку ни одно предложение не доступно для продолжения, но в то же время другие процессы продолжают работать.
Синхронизация между процессами, решающими разные цели, достигается с помощью использования защит. Если цель не может быть переписана, поскольку все предложения, которые могут быть использованы, имеют защиту, которая не вытекает из хранилища ограничений, процесс, решающий эту цель, блокируется до тех пор, пока другие процессы не добавят ограничения, необходимые для вытекания защиты хотя бы одного из применимых предложений. Эта синхронизация подвержена взаимоблокировкам : если все цели заблокированы, новые ограничения не будут добавлены, и, следовательно, ни одна цель никогда не будет разблокирована.
Третий эффект разницы между параллельным и непараллельным логическим программированием заключается в способе, которым цель приравнивается к заголовку нового варианта предложения. Оперативно это делается путем проверки того, можно ли приравнять переменные в заголовке к термам таким образом, чтобы заголовок был равен цели. Это правило отличается от соответствующего правила для программирования логики ограничений тем, что оно позволяет добавлять ограничения только в форме переменная=терм, где переменная является одним из заголовка. Это ограничение можно рассматривать как форму направленности, в которой цель и заголовок предложения обрабатываются по-разному.
Точнее, правило, сообщающее, H:-G|Bможно ли использовать новый вариант предложения для переписывания цели, Aвыглядит следующим образом. Во-первых, проверяется, имеют ли Aи Hтот же предикат. Во-вторых, проверяется, существует ли способ уравнивания с заданным текущим хранилищем ограничений; в отличие от обычного логического программирования, это делается при односторонней унификации , которая позволяет только переменной заголовка быть равной термину. В-третьих, сторож проверяется на вывод из хранилища ограничений и уравнений, сгенерированных на втором шаге; сторож может содержать переменные, которые не упомянуты в заголовке предложения: эти переменные интерпретируются экзистенциально. Этот метод принятия решения о применимости нового варианта предложения для замены цели можно компактно выразить следующим образом: текущее хранилище ограничений влечет, что существует оценка переменных заголовка и сторожа, такая, что заголовок равен цели, а сторож выводится. На практике вывод может быть проверен неполным методом.
Расширением синтаксиса и семантики параллельного логического программирования является атомарный tell . Когда интерпретатор использует предложение, его охранник добавляется в хранилище ограничений. Однако также добавляются ограничения тела. Из-за приверженности этому предложению интерпретатор не возвращается назад, если ограничения тела несовместимы с хранилищем. Этого состояния можно избежать, используя атомарный tell , который является вариантом, в котором предложение содержит своего рода «второго охранника», который проверяется только на согласованность. Такое предложение записывается H :- G:D|B. Это предложение используется для перезаписи литерала только в том случае, если Gвлечет за собой хранилище ограничений и Dсогласуется с ним. В этом случае Gи Dдобавляются в хранилище ограничений.
Изучение параллельного программирования логики ограничений началось в конце 1980-х годов, когда некоторые принципы параллельного программирования логики были интегрированы в программирование логики ограничений Майклом Дж. Махером. Теоретические свойства параллельного программирования логики ограничений позднее изучались различными авторами, включая Мартина Ринарда и Виджая А. Сарасвата. [2]
