Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


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

Простым примером отношения второго порядка является установление, все ли элементы некоторого списка обладают определенным свойством. Для простоты предполагается, что это свойство описано как унарный предикат. Определим отношение 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 ограничивается языками функционального программирования, такими, как Лисп, но мы полагаем, что это положение обусловлено предубеждением и наличием множества альтернативных методов программирования. Возможно, что активно ведущаяся работа по расширению модели логического программирования предикатами более высокого порядка и по интеграции логического и функционального программирования изменит существующую картину.



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

<== предыдущая лекция | следующая лекция ==>
Применения множественных выражений | Поиск на графах пространства состояний

Дата добавления: 2014-01-07; Просмотров: 447; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.004 сек.