Другие предикаты второго порядка

Логика первого порядка позволяет производить квантификацию по отдельным элементам. Логика второго порядка, кроме того, позволяет проводить квантификацию по предикатам. Включение такого расширения в логическое программирование влечет за собой использование правил с целями, предикатные имена которых являются переменными. Имена предикатов становятся «первоклассными» объектами данных, допускающими модификацию и обработку.

Простым примером отношения второго порядка является установление, все ли элементы некоторого списка обладают определенным свойством. Для простоты предполагается, что это свойство описано как унарный предикат. Определим отношение has_property(Xs.P) которое истинно, если элемент из Xs обладает некоторым свойством Р. Расширение синтаксиса Пролога переменными именами предикатов позволяет определить отношение has_property так, как показано на рис. 17.5. Поскольку в определении предиката has_property можно использовать переменные свойства, он является предикатом второго порядка. Пример использования этого предиката - вопрос has_property (Xs,мужчина)?, проверяющий «все ли люди, входящие в список Хs,мужчины?».

Еще один предикат второго порядка – тар_list (Xs.P.Ys). Здесь Ys – отображение списка Xs по предикату Р. Это означает, что для каждого элемента Х из Xs существует соответствующий элемент Y из Ys, такой, что P(X,Y) истинен. В Ys сохраняется порядок элементов списка Xs. Используя предикат map-list, можно переписать некоторые программы из предыдущих глав. Например, программа 7.8, отображающая набор английских слов в слова на французком языке, может быть выражена как предикат map_list(Words,dict,Mots). Предикат map_list, как и предикат has_property, легко определить, используя переменное имя предиката. Это определение дано на рис. 17.5.

has_property([X | Xs],P) ¬ P(X),has_property(Xs,P). has_property([ ],P).

map_list([X | Xs],P,[Y | Ys]) ¬ P(X,Y), map_list(Xs,P,Ys).

map_list([ ],P,[ ]).

Рис. 17.5. Предикаты второго порядка.

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

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

apply(foo,Xl,..,Xn) ¬ foo(Xl,.,Хn).

Два предиката, определенные на рис. 17.5, представлены в программе 17.8 на стандартном Прологе. Определения предложений apply даны здесь для упомянутых в книге примеров.

Предикат apply осуществляет структурный контроль. Полный набор предложений apply может быть обобщен посредством использования примитива структурного контроля univ. Обобщенный предикат apply(P,Xs) применяет предикат Р к списку аргументов Xs:

apply(F,Xs) ¬ Goal =..[F | Xs],Goa1.

Эту функцию можно обобщить так, чтобы ее можно было применять, начиная с имени предиката, т.е. некоторого атома, и кончая термом, параметризованным переменными. Примером является подстановка значения в список. Если допускается параметризация, то отношение Subsiitute/4 в программе 9.3 может рассматриваться как пример предиката map_list. А именно: предикат map_list(Xs, substitute (Old, New).Ys) дает тот же самый результат (список Ys получается в результате замены в списке

has_property (Xs, Р) ¬

Каждый элемент списка Xs обладает свойством Р.

has_property([X | Xs],P) ¬

apply(P.X), has_property(Xs,P).

has_property([ ],P).

арр1у(мужчина, Х) ¬ мужчина(Х).

maplisl(Xs,P.Ys) ¬

Каждый элемент списка Xs находится в отношении Р с соответствующим ему элементом списка Ys.

map_list([X | Xs],P,[Y | Ys]) ¬

apply (P,X,Y), map_list(Xs,P,Ys).

map_list([ ],P,[ ]).

apply(dict,X,Y) ¬ dict(X,Y).

Программа 17.8. Предикаты второго порядка в языке Пролог.

Xs элемента Old на элемент New), что и отношение, вычисляемое программой 9.3. Для того чтобы корректно выполнять рассмотренные действия, предложение apply путем незначительных изменений должно быть приведено к следующему виду:

apply (P,Xs) ¬

Р =.. LI, append (Ll,Xs,L2), Goal =.. L2,Goal.

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

Предикат apply можно также использовать для реализации лямбда-выражений. Лямбда-выражение имеет вид lambda(X...X).Expression. Если заранее известно множество подлежащих использованию лямбда-выражений, то они могут быть поименованы. Например, приведенное выше выражение можно заменить некоторым уникальным идентификатором, скажем идентификатором foo, и определить предложением apply:

apply(foo,Xl,...,X) ¬ Expression.

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

А пока множественные выражения представляются основными и наиболее полезными конструкциями высокого уровня в Прологе.