Лекция №11 Программирование второго порядка

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

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

Множественные выражения

Решение какого-либо вопроса в программе на Прологе вызывает поиск некоторого примера вопроса, выводимого из программы. Что произойдет, если осуществлять поиск всех примеров вопроса, выводимых из программы? На декларативном уровне такой вопрос лежит вне модели логического программирования, представленной в гл. 1. Это вопрос второго порядка, поскольку он касается множества элементов с определенными свойствами. В случае операционного толкования он выходит и за рамки вычислительной модели чистого Пролога. В чистом Прологе вся информация относительно определенной ветви вычисления при осуществлении возврата теряется. Поэтому в чистом Прологе не существует простого способа нахождения множества всех решений для некоторого вопроса или даже определения того, сколько существует решений для данного вопроса.

В этом разделе обсуждаются предикаты, позволяющие отвечать на вопросы второго порядка, будем называть такие предикаты множественными. Их можно считать новыми примитивами, однако нельзя трактовать как подлинные расширения Пролога, поскольку они могут быть определены в самом Прологе посредством его внелогических предикатов, особенно таких, как assert и retract. Мы представляем их в языке в виде некоторого расширения более высокого порядка – квантификации по всем решениям – и покажем далее, как они могут быть реализованы. Как и при стандартной реализации отрицания, реализация множественных предикатов лишь аппроксимирует их логическое описание. Однако эта аппроксимация очень полезна во многих применениях, что будет показано в следующем разделе.

Рассмотрим пример применения множественных предикатов, используя представленную на рис. 17.1 часть библейской базы данных программы 1.1.

отец(терах,авраам). отец(аран,лот).

отец(терах,нахор). отец(аран, милка).

отеи(терах,аран). отец(аран,иска).

отец(авраам,исаак).

мужчина(авраам). мужчина(аран). женщина(иска).

мужчина(исаак). мужчина(нахор). женщина(милка).

мужчина(лот).

Рис. 17.1. Часть библейской базы данных.

Пусть требуется отыскать всех детей определенного отца. Естественно представить себе предикат дети(Х,Детки), где Детки – список детей X, которые должны быть «извлечены» из фактов отец, представленных на рис. 17.1. Наивный подход, основанный на применении накопителя, реализуется следующим образом:

дети(Х,Сs)  дети(Х,[ ].Сs), дети(Х,А,Сs) 

отец(Х,С), not mеmber(C,A), !, дети(Х,[С | A],Cs).

дети(X,Cs,Cs).

Эта программа на такой вопрос, как дети (mepax,Xs)?, успешно отвечает Xs=[аран,пахор,авраам]. Однако подход с использованием накопителей имеет два серьезных недостатка, которые препятствуют развитию более общих множественных предикатов. Первый недостаток состоит в том, что всякий раз, когда некоторое решение добавляется в накопитель, полное дерево поиска обходится заново. В общем случае повторные вычисления должны быть запрещены. Второй недостаток связан с тем, что существуют задачи с общностью. На такой вопрос, как дети (X,Cs)?, будет дан ответ Х = терах, Cs = [аран,нахор,авраам], а альтернативное решение при возврате из-за использования отсечения оказывается недоступным. Как только «свободные» переменные конкретизированы, получить альтернативное решение становится невозможно. Удаление же отсечения вызовет некорректное поведение программы при задании вопроса дети (терах, Н).

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

Остановимся на двух примитивных множественных предикатах. Отношение bag_of(Term,Goal,Instances) истинно, если Instances – мультимножество всех примеров терма Term, для которых цель Goal истинна. Кратные тождественные решения сохраняются. Отношение set_of(Term,Goal,Instances) является некоторым усовершенствованием отношения bag-of, где Instances упорядочено, а повторяющиеся элементы удалены.

Отношение дети легко теперь записать следующим образом:

дети(Х,Детки)  set_of(С,отец(Х,С),Детки).

Завершаемость выполнения множественных предикатов зависит от завершения работы с целью, примеры которой собираются. Для этой цели должен быть выполнен обход полного дерева поиска. Следовательно, бесконечная ветвь, встретившаяся в дереве поиска, приведет к незавершаемости поиска.

Множественные предикаты могут иметь кратные решения. Рассмотрим вопрос set_of(Y,omeц(X,Y), Дemки)?. Существует несколько альтернативных решений, соответствующих различным значениям X. Например, {X = терах.Детки = [авраам,нахор,аран]} и [X = авраам, Детки = [исаак]} являются равно законными решениями, которые должны быть получены при поиске с возвратами.

Однако существует другая интерпретация, применимая к вопросу set-off(Y, omeц(X,Y),Дemки)?. Он может рассматриваться как вопрос о всех детях (независимо от отца), упомянутых в фактах программы. В логической интерпретации это означает, что Детки есть множество всех значений У, таких, что существует некоторое X, для которого отношение omец(X,Y) истинно. Для представленных на рис. 17.1 фактов существует единственное решение этого вопроса: Детки = [авраам, нахор, аран, исаак, лот, милка люка]. Чтобы отличать подобные «экзистенциальные» вопросы от обычных, решаемых поиском с возвратами, используем дополнительное обозначение. Наш вопрос в принятой для вопросов второго типа форме запишется так: set_of(Y,X(отец (X,Y), Детки). В общем случае некоторый вопрос VGoal означает, что существует некоторое У, такое, что цель Goal истинна.

Множественные предикаты могут быть вложенными. Например, все отношения отец-дети могут быть вычислены при ответе на вопрос set_of (Отец-Детки, set_of(X,родитель (Отец,Х).Детки),Ys)?. Соответствующим решением будет [терах – [авраам, нахор,аран], авраам – [исаак], аран-[лот, милка,иска]].

Существуют два возможных способа определения поведения предиката set_of(X,Goal,Instances), когда решение цели Goal завершается отказом, т.е. когда она не имеет истинных примеров. Определим предикаты set_of и bag_of так, чтобы их вычисление всегда было успешным; для этого, когда цель Goal не имеет решений, Instances определяется как пустой список. Такое определение предполагает, что «знаниями» в программе является все то, что истинно. Это аналогично аппроксимации отрицания «отрицанием как безуспешным вычислением».

Можно определить варианты предикатов set_of и bag_of, вычисление которых будет приводить к отказу, когда решений не существует. Эти новые отношения обозначим как set_of и bag_of1 и дадим их определения в программе 17.1.

Множественные предикаты

set_of1(X,Goal,Instances)  Instances – это множество примеров Х (если такие существуют), для которых цель Goal истина.

set_of1(X,Goal, Instances) 

set_of(X, Goal. Instances), Instances = [I | Is].

bug_of1 (X,Goal,Instances)  Instances – это мультимножество примеров X (если такие существуют), для которых цель Goal истинна. Кратность элемента мультимножества равна числу различных путей, которыми может быть доказана цель Goal для этого элемента, используемого в качестве примера X.

bag_of1(X, Goal, Instances) 

bag_of(X, Goal, Instances), Instances = [I|Is].

size_of(if(X,Goal.N) N – число различных примеров X. таких, что цель Goal истинна.

size_of(X,Goal,N)  set_of(X,Goal,Instances), length(Instances,N).

length(Xs,N)  См. программу 8.11.

Программа 17.1. Множественные предикаты.

Многие из рассмотренных ранее рекурсивных процедур можно переписать с использованием множественных предикатов. Например, программа 7.9 для удаления из списка повторяющихся элементов легко определяется с помощью предикатов для проверки принадлежности элементов множеству:

no_doubles(Xs,Ys)  set_of(X,member(X, Xs),Ys).

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

Другие вспомогательные предикаты второго порядка можно определить, используя рассмотренные основные множественные предикаты. Так, подсчитать число различных решений можно с помощью программы size_of(X, Goal, N), которая определяет число N решений Х для некоторой цели Goal, Этот предикат представлен в программе 17.1. Если цель Goal не имеет решений, переменная N принимает значение 0. Если требуется, чтобы выполнение предиката size_of при отсутствии решений завершалось отказом, можно вместо предиката set_of использовать предикат set_of1. Если же вместо предиката set_of применить предикат bug_of, то рассматриваемый нами предикат будет определять число решений с учетом кратных решений.

Еще один вспомогательный множественный предикат предназначен для проверки того, все ли решения вопроса удовлетворяют определенному условию. Программой 17.2 определяется предикат for_all (Goal,Condition), истинный, когда условие Condition истинно для всех значений цели Goal. В его определении использована метапеременная Case.

for_all(Goal, Condition)

Для всех решений цели Goal условие Condition истинно.

for_all(Goal, Condition) 

set_of(Condilion, Goal, Cases),check (Cases).

check ([Case | Cases])  Case, check (Caces).

check([ ])

Программа 17.2. Применение множественных предикатов.

С помощью вопроса for_all(отец(Х,С),мужчина(С))? проверяется, какие отцы имеют детей только мужского пола. Ему соответствуют два ответа: Х = терах и Х = авраам.

Более простой и эффективный, но менее универсальный вариант предиката for_all можно написать без использования множественных предикатов. Подобный эффект дает совместное использование недетерминизма и отрицания как безуспешного вычисления. Рассмотрим новое определение

for_all(Goal,Conditon)  not(Goal, notCondition).

Теперь предикат успешно отвечает на такой вопрос, как for_all(отец(терах, X), мужчина (Х))?, однако попытка дать решение вопроса for_all(отец(Х, С), мужчина(С))? приводит к отказу.

В заключение этого раздела покажем, как реализовать простой вариант предиката bag_of. Это обсуждение преследует две цели: оно иллюстрирует определенный стиль реализации множественных предикатов и вводит вспомогательный предикат, который пригодится нам в следующем разделе. Предикат find_all_dl(X, Goal, Instances) истинен, если Instances – мультимножество примеров X, представленных разностным списком, для которых цель Goal истинна. Эта процедура отличается от процедуры bag_of тем, что поиск альтернативных решений происходит без использования возвратов.

Определение предиката find_all_dl дает программа 17.3. Программа имеет только операционное толкование. В ней имеются два этапа, описанные двумя предложениями find_all_dl. Явный отказ в первом предложении гарантирует выполнение второго предложения. Первый этап находит все решения для цели Goal, используя управляемый отказами цикл, добавляющий по мере обработки соответствующие примеры X. Второе предложение выбирает эти решения.

Введение "$mark" существенно для корректного выполнения вложенных множественных выражений заимствования одним множественным выражением решений, полученных другим множественным выражением.

find_all_dl (X,Goal,Instances ) Instances – это мультимножество примеров X, для которых цель Goal истинна. Кратность элемента мультимножества равна числу различных путей, которыми может быть доказана цель Goal для этого элемента, используемого в качестве примера X.

find_all_dl(X, Goat, Xs)

asserta($instances($mark)), Goal,

asserta($instance(X)), fail

find_all_dl(X, Goal, Xs\Ys) 

retract($instance(X)), reap(X,Xs\Ys),!.

reap(X.Xs\Ys) 

X  $mark, retract($instance(Xl)),!,

reap(Xl,Xs\[X|Ys]).

reap($mark,Xs\Xs).

Программа 17.3. Реализация множественного предиката с использованием разностных списков и внелогических предикатов assert и retract.

Применения множественных выражений

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

В разд. 14.2 были рассмотрены три программы 14.8, 14.9 и 14.10 для обхода графа в глубину. Здесь обсуждаются эквивалентные программы для обхода графа в ширину.

connected (X ,Y) 

Связь вершины X с вершиной Y в ориентированном ациклическом графе определяется предложением edge/2.

connected(X,Y)  connected_bfs([X | Xs])\Xs,Y).

connected_bfs([ ] \ [ ], Y)  !, fail.

connected_bfs([X | Xs]\Ys, X).

connected_bfs([X | Xs] \ Ys, Y) 

find_all_dI(N,edge(X,N),Ys\Zs),

connected_bfs(Xs\Zs,Y).

Данные

edge(a,b). edge(a,c). edge(a,d). edge(a,e).

edge(f,i). edge(c,f). edge(c,g). edge(f.h).

edge(e.k). edge(d.j). edge(x,y). edge(y,z).

edge(z,x). edge(y.u). edge(z,v).

Программа 17.4. Программа и тестовые данные для проверки алгоритма обхода в ширину ориентированного ациклического графа.

Основным отношением является connected(X,Y), которое истинно, если вершины Х и Y связны. Это отношение определено в программе 17.4. Поиск в ширину реализуется посредством ведения такой очереди вершин, следуя которой происходит обход графа в ширину. Соответственно предложение connected вызывает отношение connected_bfs(Queue,Y), которое истинно, если Y принадлежит связному компоненту графа, представленному вершинами в очереди Queue.

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

Рассмотрим факты edge в программе 17.4, представляющие граф, показанный на рис. 14.3 слева. Для них вопрос connected(a.X) дает решения b, с, d, e, f, g, j, k, h, i как результат обхода графа в ширину.

Программа 17.4, подобно программе 14.8, пригодна для обхода конечного дерева или ориентированного ациклического графа. В случае циклического графа выполнение программы не завершится.

connected(X. Y) 

Связь вершины Х с вершиной У в графе определяется предложением edge/ 2.

connected(X,Y)  connected(X | Xs]\Xs, Y,[X]).

connected ([ ]\[ ], Y, Visited) !, fail.

connected ([A | Xs]\Ys, A, Visited).

connected ([A | Xs]\Ys,B, Visited) 

set_of(N,edge(A,N),Ns),

filter([Ns, Visited, Visited],Xs\Ys,Xsl),

connected(Xsi, B, Visited1).

filter([N [ Ns], Visited, Visited l,Xs,Xsl)

rnember(N, Visited),

filter(Ns, Visited, Visitedl, Xs, Xs1).

filter([N|Ns],Visited,Xs\[N|Ys],Xs\Ys) 

not rnembcr(N,Visited),

filter(Ns,[N | Visited], Visitedl,Xs\Ys,Xsl).

filter([ ],V,V,Xs, Xs).

Программа 17.5. Проверка связности графа путем обхода в ширину.

По сравнению с программой 17.4 программа 17.5 более совершенна, в ней, в частности, ведется список просмотренных вершин графа. В конец очереди добавляются не все дочерние вершины, а только те, которые еще не просматривались, Такая проверка в программе 17.5 выполняется с помощью предиката filter.

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

Определение пути между двумя вершинами графа представляет собой несколько более сложную задачу, чем поиск в глубину. Вместе с каждой вершиной в очереди здесь необходимо хранить список вершин, по которым проходит путь, связывающий ее с исходной вершиной. Этот метод демонстрируется в программе 18.6 в следующей главе.

(1) Конечные деревья и ориентированные ациклические графы. Чистый Пролог.

(2) Конечные графы.

Чистый Пролог + отрицание.

(3) Бесконечные графы.

Чистый Пролог + множественные выражения + отрицание.

Рис. 17.2. Средства Пролога для решения различных задач поиска на графах.

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

Нахождение ключевых слов в контексте связано с поиском всех вхождений множества ключевых слов в определенный текст и выделением контекстов, в которых они встречаются. Здесь будет рассмотрен следующий вариант этой общей задачи: «Для данного списка заголовков сформировать упорядоченный список всех вхождений в данные заголовки множества ключевых слов вместе с их контекстами».

Пример входных и ожидаемых выходных данных для такой программы представлен на рис. 17.4. Контекст описывается как вращение заголовка, конец которого отмечен вертикальной чертой «|». В рассматриваемом примере использован следующий набор «нетривиальных» ключевых слов: algorithmic, debugging, logic, problem, program, programming, prolog и solving.

В данной задаче подлежит вычислению отношение kwic(Titles,KwicTit1es), где Tub's- список заголовков, из которых должны быть выделены ключевые слова, а КwicTitles – отсортированный список ключевых слов в их контекстах. Предполагается, что входной и выходной тексты представлены в виде списков слов. В более общей программе должны быть предусмотрены предварительный шаг преобразования входного текста в свободной форме в списки слов, а также выдача результатов в удобном для чтения виде.

Вход: programming in prolog logic for problem solving logic programming algorithmic program debugging

Выход: algorithmic program debugging |, debugging | algorithmic program, logic for problem solving |, logic programming, |, problem solving | logic for, program debugging | algorithmic, programming in prolog |. programming | logic, prolog | programming in, solving | logic for problem

Рис17.4. Вход и выход для задачи поиска вхождений ключевых слов в контексте.

Рассмотрим поэтапное представление программы. Основа программы – недетерминированное описание вращения списка слов. С помощью предиката append ему можно дать следующее элегантное определение:

rotate(Xs,Ys)  append(As,Bs,Xs). append! Bs,As.Ys).

Декларативно: Ys – вращение Xs, если Xs состоит из As, за которым следует Bs, а Ys состоит из Bs, за которым следует As.

Следующий этап связан с идентификацией отдельных слов как потенциальных ключевых слов. Это выполняется посредством выбора слова в первом вызове предиката append. Отметим, что следующее новое правило является примером предыдущего правила rotate:

rotate(Xs,Ys)  append(As.[Key | Bs],Xs), append([Key | Bs].As,Ys).

Кроме того, это определение лучше предыдущего, поскольку в нем предусмотрено удаление одинаковых решений, когда один из расщепленных списков пуст, а другой – полон.

Следующее улучшение связано с более детальной проверкой потенциального ключевого слова. Предположим, что каждое ключевое слово Word определяется фактом вида keyword(Word). Решения в процессе rotate могут быть отфильтрованы так, чтобы воспринимались только те слова, которые идентифицированы как ключевые. Соответствующая версия рассматриваемого предложения имеет вид

rotate_and_filter(Xs,Ys) 

append(As,[Key | Bs],Xs), keyword(Key), append([Key | Bs],As,Ys).

Операционное поведение данной процедуры: она рассматривает все ключевые слова, отфильтровывая нежелательные альтернативы. Для максимизации эффективности программы в данном случае важен порядок целей.

В программе 17.7, окончательной версии интересующей нас программы, предусмотрены дополнительные средства для распознавания ключевых слов. Любое слово Word считается ключевым, если оно не специфицировано с помощью факта вида insignificant(Word) как незначащее. Кроме того, в процедуре выполняется вставка в конец заголовка маркера «|», отмечающего контекстную информацию. Это реализуется добавлением дополнительного символа во втором обращении к предикату append. Соответствующее предложение rotate_and_filter содержится в программе 17.7.

Наконец, для получения всех решений использован множественный предикат. Квантификация необходима по всем возможным заголовкам. Явным преимуществом использования предиката set_of является сортировка ответов. Полная программа для решения рассматриваемой задачи (программа 17.7) элегантный пример выразительной мощности Пролога. Для тестирования в программе использован предикат test_kwic/2.

kwic(Tites, КWTitles) 

КWTities – KWIC-индекс списка заголовков Titles.

kwic(Titles.KWTilles)

set_of(Ys,Xs  (member(Xs, Titles),

rotate_and_fiIter(Xs,Ys)),KWTitles).

rotate_and_filter(Xs, Ys) 

Ys – вращение списка Xs, такое, что первое слово Ys значимо, и знак '|' вставлен после последнего слова Xs.

rotate_and_filter(Xs,Ys) 

append (As, [Key | Bs],Xs),

not insignificant(Key),

append([Key,’|’ | Bs],As,Ys).

Словарь незначимых слов

insignificant(a). insignificant(the).

insignificant(in). insignificant (for).

Предложения и данные для тестирования

test_kwic(Books,Kwic) 

titles(Books,Titles),kwic(Titles,Kwic).

titles(lp, [[logic, for, problem,solving],

[logic, programming],

[algorithmic, program, debugging],

[programming, in, prolog]]).

Программа 17.7. Создание индекса в задаче поиска ключевых слов вместе с их контекстами.

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

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

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

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