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

Программирование второго порядка

Лекция №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.

Дата добавления: 2014-01-07