Правила обработки ограничений - Constraint Handling Rules

Правила обработки ограничений
Парадигма	Программирование логики ограничений
Разработано	Том Фрювирт
Впервые появился	1991
Под влиянием
	Пролог

Правила обработки ограничений (CHR) это декларативный, основанный на правилах язык, представленный в 1991 году Томом Фрювиртом в то время с ECRC (Европейский центр исследований компьютерной промышленности) в Мюнхене, Германия.^[1]^[2] Первоначально предназначался для программирование в ограничениях, CHR находит применение в грамматическая индукция,^[3] похищающие рассуждения, мультиагентные системы, обработка естественного языка, сборник, планирование, пространственно-временные рассуждения, тестирование и проверка, и системы типов.

Программа CHR, иногда называемая обработчик ограничений, представляет собой набор правил, поддерживающих магазин ограничений, а мульти-набор логических формул. Выполнение правил может добавлять или удалять формулы из хранилища, тем самым изменяя состояние программы. Порядок, в котором правила «запускаются» в данном хранилище ограничений: недетерминированный,^[4] согласно его Абстрактные семантика и детерминированный (применение правила сверху вниз), в соответствии с его уточненная семантика.^[5]

Хотя CHR Тьюринг завершен,^[6] он обычно не используется как самостоятельный язык программирования. Скорее, он используется для расширения принимающий язык с ограничениями. Пролог - безусловно, самый популярный хост-язык, и CHR включен в несколько его реализаций, включая SICStus и SWI-Prolog, хотя реализации CHR также существуют для Haskell, Ява, C,^[7] SQL,^[8] и JavaScript.^[9] В отличие от Prolog, правила CHR являются многоголовыми и выполняются с фиксированным выбором с использованием прямая цепочка алгоритм.

Обзор языка

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

Таким образом, программа CHR состоит из правил, управляющих множеством этих терминов, называемых магазин ограничений. Правила бывают трех типов:^[4]

Правила упрощения имеют вид ${ displaystyle h_ {1}, dots, h_ {n} Longleftrightarrow g_ {1}, dots, g_ {m} , | , b_ {1}, dots, b_ {o}}$ . Когда они соответствуют головы ${ displaystyle h_ {1}, dots, h_ {n}}$ и охранники ${ displaystyle g_ {1}, dots, g_ {m}}$ держать, правила упрощения могут переписать головы в тело ${ displaystyle b_ {1}, dots, b_ {o}}$ .
Правила распространения имеют вид ${ displaystyle h_ {1}, dots, h_ {n} Longrightarrow g_ {1}, dots, g_ {m} , | , b_ {1}, dots, b_ {o}}$ . Эти правила добавляют в магазин ограничения в теле, не убирая головы.
Simpagation правила сочетают в себе упрощение и распространение. Они написаны ${ displaystyle h_ {1}, dots, h _ { ell} , backslash , h _ { ell +1}, dots, h_ {n} Longleftrightarrow g_ {1}, dots, g_ {m } , | , b_ {1}, dots, b_ {o}}$ . Чтобы сработало правило упрощения, хранилище ограничений должно соответствовать всем правилам в голове, а охранники должны выполняться. В ${ displaystyle ell}$ ограничения перед ${ displaystyle backslash}$ сохраняются, как в правиле распространения; остальные ${ displaystyle n- ell}$ ограничения снимаются.

Поскольку правила упрощения включают упрощение и распространение, все правила CHR следуют формату

{ displaystyle H_ {k} , backslash , H_ {r} Longleftrightarrow G , | , B}

где каждый из ${ displaystyle H_ {k}, H_ {r}, G, B}$ сочетание ограничений: ${ displaystyle H_ {k}, H_ {r}}$ и ${ displaystyle B}$ содержат ограничения CHR, в то время как охранники ${ displaystyle G}$ встроены. Только один из ${ displaystyle H_ {k}, H_ {r}}$ не должно быть пустым.

Основной язык также должен определять встроенные ограничения по срокам. Стражи в правилах - это встроенные ограничения, поэтому они эффективно выполняют код основного языка. Встроенная теория ограничений должна включать как минимум истинный (ограничение, которое всегда выполняется), провал (ограничение, которое никогда не выполняется и используется для сигнализации отказа) и равенство условий, т. е. объединение.^[6] Если основной язык не поддерживает эти функции, они должны быть реализованы вместе с CHR.^[7]

Выполнение программы CHR начинается с начального хранилища ограничений. Затем программа продолжается правила соответствия против магазина и применяя их, пока не перестанут совпадать правила (успех) или провал ограничение выводится. В первом случае хранилище ограничений может быть прочитано программой на языке хоста для поиска интересующих фактов. Сопоставление определяется как «одностороннее объединение»: оно связывает переменные только с одной стороны уравнения. Сопоставление с образцом может быть легко реализовано в виде унификации, если ее поддерживает основной язык.^[7]

Пример программы

Следующая программа CHR в синтаксисе Prolog содержит четыре правила, которые реализуют решатель для менее или равно ограничение. Правила помечены для удобства (метки в CHR не обязательны).

 % X leq Y означает, что переменная X меньше или равна переменной Y  рефлексивность  @ Икс leq Икс <=> истинный. антисимметрия @ Икс leq Y, Y leq Икс <=> Икс = Y. транзитивность @ Икс leq Y, Y leq Z ==> Икс leq Z. идемпотентность  @ Икс leq Y \ Икс leq Y <=> истинный.

Правила можно читать двояко. В декларативном чтении три правила определяют аксиомы частичного упорядочения:

Рефлексивность: Икс ≤ Икс
Антисимметрия: если Икс ≤ Y и Y ≤ Икс, тогда Икс = Y
Транзитивность: если Икс ≤ Y и Y ≤ Z, тогда Икс ≤ Z

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

Второй способ читать вышесказанное - это компьютерная программа для поддержки хранилища ограничений, набора фактов (ограничений) об объектах. Хранилище ограничений не является частью этой программы, но должно поставляться отдельно. Правила выражают следующие правила вычислений:

Рефлексивность - это упрощение правило: оно выражает то, что если факт формы Икс ≤ Икс есть в магазине, может быть удален.
Антисимметрия - это тоже правило упрощения, но с двумя головы. Если два факта вида Икс ≤ Y и Y ≤ Икс можно найти в магазине (с соответствием Икс и Y), то их можно заменить одним фактом Икс = Y. Такое ограничение равенства считается встроенным и реализуется как объединение это обычно обрабатывается базовой системой Prolog.
Транзитивность - это распространение правило. В отличие от упрощения, он ничего не удаляет из хранилища ограничений; вместо этого, когда факты в форме Икс ≤ Y и Y ≤ Z (с тем же значением для Y) есть в магазине, третий факт Икс ≤ Z могут быть добавлены.
Идемпотентность, наконец, упрощение правило, комбинированное упрощение и распространение. Когда он находит повторяющиеся факты, он удаляет их из магазина. Дубликаты могут возникать, потому что хранилища ограничений - это множественные наборы фактов.

Учитывая запрос

A leq B, B leq C, C leq A

могут произойти следующие преобразования:

Текущие ограничения	Правило, применимое к ограничениям	Вывод из применения правила
`A leq B, B leq C, C leq A`	транзитивность	`A leq C`
`A leq B, B leq C, C leq A, A leq C`	антисимметрия	`А = С`
`A leq B, B leq A, A = C`	антисимметрия	`А = В`
`А = В, А = С`	никто

В транзитивность правило добавляет A leq C. Затем, применив антисимметрия правило A leq C и C leq A удаляются и заменяются А = С. Теперь антисимметрия правило становится применимым к первым двум ограничениям исходного запроса. Теперь все ограничения CHR устранены, поэтому дальнейшие правила не могут применяться, и ответ А = В, А = С возвращается: CHR правильно сделал вывод, что все три переменные должны ссылаться на один и тот же объект.

Выполнение программ CHR

Чтобы решить, какое правило должно «активироваться» для данного хранилища ограничений, реализация CHR должна использовать некоторые сопоставление с образцом алгоритм. Кандидатские алгоритмы включают СЕТЬ и Лечит, но в большинстве реализаций используется ленивый алгоритм называется ПОПАДАЕТ.^[10]

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

Большинство приложений CHR требуют, чтобы процесс перезаписи был сливаться; в противном случае результаты поиска удовлетворительного задания будут недетерминированными и непредсказуемыми. Установление слияния обычно осуществляется с помощью следующих трех свойств:^[2]

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

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

дальнейшее чтение

Кристиансен, Хеннинг. "CHR грамматики. »Теория и практика логического программирования 5.4-5 (2005): 467-501.

внешняя ссылка

[1] Том Фрювирт. Введение в правила упрощения. Внутренний отчет ECRC-LP-63, ECRC Мюнхен, Германия, октябрь 1991 г., представлен на семинаре Logisches Programmieren, Гузен / Берлин, Германия, октябрь 1991 г. и семинаре по переписыванию и ограничениям, Дагштуль, Германия, октябрь 1991 г.

[chrtheorypractice-2] а ^б Том Фрювирт. Теория и практика правил обработки ограничений. Специальный выпуск по программированию в ограничениях (П. Стаки и К. Марриотт, ред.), Журнал логического программирования, том 37 (1-3), октябрь 1998 г. Дои:10.1016 / S0743-1066 (98) 10005-5

[3] Даль, Вероника и Х. Эмилио Мираллес. "Грамматики матки: решение ограничений для индукции грамматики. "Труды 9-го семинара по правилам обработки ограничений. Том. Технический отчет CW. Том 624. 2012.

[timegoesby-4] а ^б ^c Снейерс, Джон; Ван Верт, Питер; Шрайверс, Том; Де Конинк, Лесли (2009). "Время идет: Правила обработки ограничений - обзор исследований CHR за период с 1998 по 2007 год" (PDF). Теория и практика логического программирования. 10: 1. arXiv:0906.4474. Дои:10.1017 / S1471068409990123.

[chrbook-5] Фрювирт, Том (2009). Правила обработки ограничений. Издательство Кембриджского университета. ISBN 0521877768.

[complexity-6] а ^б Снейерс, Джон; Шрайверс, Том; Демоэн, Барт (2009). «Вычислительная мощность и сложность правил обработки ограничений» (PDF). ACM Trans. Программа. Lang. Syst. 31 (2).

[imperative-7] а ^б ^c Питер Ван Верт; Питер Уилле; Том Шрайверс; Барт Демоэн. «CHR для императивных языков хоста». Правила обработки ограничений - текущие темы исследований. Springer.

[8] ttps://github.com/awto/chr2sql

[9] CHR.js - Транспилятор CHR для JavaScript

[10] Лесли Де Конинк (2008). Контроль выполнения для правил обработки ограничений (PDF) (Кандидатская диссертация). Katholieke Universiteit Leuven. С. 12–14.

[11] Дак, Грегори Дж .; Стаки, Питер Дж .; Гарсиа де ла Банда, Мария; Хольцбаур, Кристиан (2004). «Усовершенствованная операционная семантика правил обработки ограничений» (PDF). Логическое программирование: 90–104. Архивировано из оригинал (PDF) на 2011-03-04. Получено 2014-12-23.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]