Інші предикати другого порядку - Студопедія
Логіка першого порядку дозволяє проводити квантифікацію за окремими елементами. Логіка другого порядку, крім того, дозволяє проводити квантифікацію за предикатами. Включення такого розширення в логічне програмування спричиняє використання правил із цілями, предикатні імена яких є змінними. Імена предикатів стають «першокласними» об'єктами даних, що допускають модифікацію та обробку.
Простим прикладом відношення другого порядку є встановлення, чи всі елементи деякого списку мають певну властивість. Для простоти передбачається, що ця властивість описана як унарний предикат. Визначимо відношення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).
Мал. 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має властивістьР.
арр1у (чоловік, Х) ¬ чоловік (Х).
Кожен елемент спискуXsзнаходиться у відношенніР звідповідним йому елементом спискуYs.
map_list([X Xs],P,[Y Ys]) ¬
apply (P, X, Y), map_list (Xs, P, Ys).
Програма 17.8. Предикати другого порядку у мові Пролог.
XsелементаOldна елементNew),як і відношення, що обчислюється програмою 9.3. Для того, щоб коректно виконувати розглянуті дії, пропозиціяapplyшляхом незначних змін має бути приведена до такого вигляду:
Р = .. 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обмежується мовами функціонального програмування, такими, як Лісп, але ми вважаємо, що це положення обумовлено упередженням та наявністю безлічі альтернативних методів програмування. Можливо, що робота з розширення моделі логічного програмування предикатами вищого порядку і з інтеграції логічного і функціонального програмування змінить існуючу картину.
А поки що множинні вирази видаються основними і найкориснішими конструкціями високого рівня в Пролозі.
Чи не знайшли те, що шукали? Скористайтеся пошуком: