Расширение Prolog для использования в качестве языка логического программирования в ограничениях

Рассмотрим взаимосвязь между языком Prolog и задачей удовлетворения ограни­чений. Базовый Prolog сам может рассматриваться как довольно специфический язык удовлетворения ограничений, в котором все ограничения имеют весьма жест­кую форму. Они представляют собой ограничения равенства между термами. Эти ог­раничения равенства проверяются средствами согласования термов языка Prolog. Хотя ограничения, установленные между параметрами предикатов, также задаются в терминах других предикатов, эти вызовы предикатов в конечном итоге сводятся к согласованию. Prolog может быть расширен до "настоящего" языка CLP путем введе­ния других типов ограничений, кроме согласования. Безусловно, должен быть также усовершенствован интерпретатор Prolog таким образом, чтобы он мог обрабатывать указанные ограничения других типов. Система CLP, способная обрабатывать ариф­метические ограничения равенства и неравенства, позволяет непосредственно решать задачи составления расписаний, подобные приведенным выше.

Программа с ограничениями интерпретируется примерно таким образом. Во вре­мя выполнения списка целей сопровождается множество текущих ограничений CurrConstr. Первоначально это множество является пустым. Цели в списке целей выполняются одна за другой в обычном порядке. Стандартные цели Prolog обрабаты­ваются как обычно. При обработке цели с ограничениями Constr множества ограни­чений Constr и CurrConstr сливаются, в результате чего создается множество NewConstr. Затем процедура решения задач в ограничениях, предназначенная для работы с областью определения данного типа, пытается удовлетворить ограничение MewConstr. При этом возможны два основных результата: а) обнаруживается, что ограничения WewConstr удовлетворить невозможно, что соответствует недостижению цели и вызывает перебор с возвратами; б) не обнаруживается такая ситуации, что ограничения MewCor.str удовлетворить невозможно, и эти ограничения максимально упрощаются процедурой решения задач в ограничениях. Например, два ограниче­ния, X < 3 и X_< 2, упрощаются таким образом, что вместо них вводится одно огра­ничение — X < 2. Степень упрощения зависит от текущего состояния информации о переменных, а также от возможностей конкретной процедуры решения задач в огра­ничениях. Остальные цели в списке выполняются с множеством текущих ограниче­ний, обновленным таким образом.

Глава 14. Логическое программирование в ограничениях

Системы CLP различаются по типам областей определения и типам ограничений, которые они способны обрабатывать. Семейства методов CLP упоминаются под име­нами в форме CLP(A'), где X обозначает область определения. Например, з методах CLP(R) областями определения переменных являются действительные числа, а в ка­честве ограничений применяются операции проверки на равенство и неравенство, а также операции сравнения действительных чисел. К системам CLP(X), используемым в других областях определения, относятся следующие: CLP(Z) — целые числа, CLP(Q) — рациональные числа, CLP(B) — логические области определения и CLP(FD) — задаваемые пользователем конечные области определения. Доступные об­ласти определения и типы ограничений в фактических реализациях в значительной степени зависят от существующих методов решения конкретных типов ограничений. Например, в системах CLP(R) обычно доступны линейные равенства и неравенства, поскольку существуют эффективные методы обработки ограничений этих типов. С другой стороны, нелинейные ограничения имеют очень узкую область применения.

В последней части этой главы подробно рассматриваются системы CLP(R), CLP(Q) и CLP{FD), в которых используются синтаксические соглашения для CLP в версии SICStus Prolog (см. раздел "Дополнительные источники информации" в конце главы).