Подразделы

Другие разделы

Дата и время

04/05/2024 00:53:02

Авторизация

Логическое программирование

Логическое программирование и язык Пролог Синтаксис. Операторы. Списки Сопоставление Арифметические и логические выражения Семантика программы на языке Пролог Списки. Обработка списков Предикаты для классификации и обработки термов Предикаты для управления процессом доказательства Предикаты для ввода и вывода данных Предикаты для работы с утверждениями Предикаты порождения Отладка программ на языке Пролог Примеры программ на языке Пролог Логика предикатов. Метод резолюции Верификация программ: основные обозначения и термины Правильность алгоритмов и способ верификации программ Синтез программ

Предикаты для управления процессом доказательства

Предикат repeat/0 обеспечивает повторное согласование уже выполненных целей в процессе возврата. Его поведение полностью соответствует следующему определению:

repeat.          % 1
repeat:-repeat.  % 2

Если мы вставим предикат repeat в одно из правил, то эта цель согласуется с БД, так как имеется факт 1. Если произойдет возврат к согласованию этой цели, Пролог будет использовать утверждение 2, которое будет доказано с помощью факта 1. При повторном возврате Пролог для согласования цели repeat снова выберет правило и так далее.

Обычно предикат repeat используется для зацикливания предикатов, не имеющих альтернатив, например, в правиле

main:-repeat,ввод(Kоманда),выполнить(Команда),Команда=bye.

предикаты ввод и выполнить будут выполняться до тех пор, пока пользователь не введет команду "bye".

Процесс доказательства в Прологе основан на переборе в глубину. Сначала выбирается первая по порядку альтернатива, которая может быть использована для доказательства цели. Если происходит возврат в точку выбора (в случае неуспеха доказательства), то выбирается следующая альтернатива, и так далее. Процесс перебора вариантов будет продолжаться до тех пор, пока не будет доказан запрос. Кроме того, пользователь может инициировать процесс возврата после получения решения, если он захочет получить другой вариант решения. Предикат отсечения, обозначаемый символом "!", позволяет уменьшить пространство поиска и сократить перебор, отбрасывая неиспользованные альтернативы.

Выполнение отсечения приводит к следующим результатам.

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

Пусть программа содержит следующее предложение:

a:-b,c,!,d,e.

После выполнения предиката ! (в случае успешного доказательства целей b и c) альтернативы для a, b и с отбрасываются, но могут рассматриваться в случае возврата альтернативы для d и e. В случае неуспеха доказательства целей d и e альтернативы для c, b, a не рассматриваются, и доказательство цели a завершается неуспехом. Предикат отсечения можно сравнить с барьером, через который не может перейти процесс возврата.

Можно выделить три основных случая использования отсечения.

Подтверждение правильности выбора правила

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

максимум(X,Y,X):-X>=Y,!.
максимум(X,Y,Y):-X<Y,!.

Цель максимум(5,2,X) имеет только одно решение, и отсечение позволяет не проверять второе правило в случае возврата.

Однако отсечение делает программу более детерминированной, менее гибкой, чем программа без отсечения. Например, если предикат сцепления двух списков определить так:

сцепить([],L,L):-!. 
сцепить([H|L1],L2,[H|L3]):-сцепить(L1,L2,L3).

то его нельзя будет применить для получения всех вариантов расщепления списка:

?- сцепить(X,Y,[a,b,c]).
X=[], Y=[a,b,c];
no

Но это не существенно, если с самого начала предполагается использовать программу лишь одним способом.

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

максимум(X,Y,X):-X>=Y,!.
максимум(X,Y,Y).

условие X<Y, опущенное во втором предложении, следует из неудачи при сравнении X>=Y. Устранение дополнительных проверок с очевидным результатом повышает эффективность программы, но поведение такой модифицированной программы не всегда корректно. Например, следующий запрос дает неправильный ответ:

?-максимум(5,2,2).
yes

Чтобы избавиться от ошибки, требуется неявное сопоставление первого и третьего аргумента предиката сделать явным и выполнить его после отсечения.

максимум(X,Y,Z):-X>=Y,!,Z=X.
максимум(X,Y,Y).

В результате программа стала менее понятной. Кроме того, правильность программы стала зависеть от порядка предложений в программе, что противоречит смыслу логического программирования.

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

a:-b,!,c.
a:-d.

преобразуется в

a:-b,c.
a:-\+ b,d.

В некоторых случаях использование красных отсечений является вполне обоснованным. Например, определение для конструкции "если A то B иначе C" с использованием отсечений будет более эффективным, так как двойная проверка истинности цели A не требуется:

если A то B иначе C:-A,!,B;C.
если A то B:-A,!,B;true.

Прекращение доказательства цели

Предикат может быть заведомо ложным для некоторых аргументов или может быть неприменим к аргументам определенного вида. Удобно выделять такие исключения в отдельные правила, уменьшая таким образом сложность определения. Это можно сделать с помощью комбинации "отсечение-неудача". Например, для пустого списка невозможно вычислить среднее значение:

среднее([],R):-!,fail.
среднее(L,R):-среднее(L,0,0,R).
среднее([],S,K,R):-R is S/K.
среднее([H|T],S,K,R):-S1 is S+H, K1 is K+1, среднее(T,S1,K1,R).

Можно определить предикат среднее/2 без использования отсечения:

среднее(L,R):-L\=[],среднее(L,0,0,R).

Предикат not(G), который истинен, если цель G не удалось согласовать с БД, можно определить, используя комбинацию "отсечение-неудача":

not(G):-G,!,fail.
not(G).

Реализация в Прологе отрицания как неудачи при доказательстве цели, может приводить к отрицательным результатам, даже если решение существует. Рассмотрим следующую программу.

студент(билл).
студент(джон).
женат(джон).
неженатый_студент(X):-\+ женат(X), студент(X).
?-неженатый_студент(X).
no

Ответ на запрос отрицательный, несмотря на то, что решение X=билл логически следует из правила и фактов. Это связано с тем, что цель \+ женат(X) ложна из-за решения X=джон. Проблема может быть устранена перестановкой целей в теле правила. В большинстве случаев рекомендуется, чтобы цель под отрицанием не содержала неконкретизированных переменных. Такое же правило относится и к предикату \=.

Завершение последовательности порождения и проверки вариантов

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

Отношение “муж” для БД о родственных связях можно определить так:

муж(X,Y):-мужчина(X),женщина(Y),родитель(X,Z),родитель(Y,Z).

Но при наличии нескольких детей появляются ненужные множественные решения:

?-муж(адам,X).
X=ева;
X=ева;
no

от которых можно избавиться с помощью отсечения:

муж(X,Y):-мужчина(X),женщина(Y),родитель(X,Z),родитель(Y,Z),!.
?-муж(адам,X).
X=ева;
no

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

сортировка(L,R):-перестановка(L,R),упорядочен(R),!.

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

целое(0).
целое(N):-целое(K),N is K+1.
целый_корень(X,R):-целое(R), R*R=<X, X<(R+1)*(R+1),!.

Здесь предикат "целое" генерирует последовательно все целые числа, начиная с 0. В данном случае существует только единственное решение, и ни одно из новых значений, возвращаемых генератором, не будет правильным результатом. Таким образом, отсечение позволяет предотвратить зацикливание при возврате.

Предикат once/1 обеспечивает однократную проверку цели. Его поведение полностью соответствует следующему определению:

once(G):-G,!.

Определение отношения "муж", которое получает все решения для цели муж(X,Y) без повторов будет выглядеть так:

муж(X,Y):-мужчина(X),женщина(Y),once( (родитель(X,Z),родитель(Y,Z)) ).

Логические программы часто состоят из последовательности специальных случаев и правила по умолчанию. Рассмотрим определение предиката чр/2, определяющего число родителей у человека.

чр(адам,0):-!.
чр(ева,0):-!.
чр(X,2).
?-чр(ева,X).
X=0;
no
?-чр(джон,X).
X=2;
no

Отсечение необходимо, чтобы предотвратить появление решения X=2 при возврате. Но данная программа дает неверный ответ для запроса

?-чр(ева,2).
yes

Можно устранить этот эффект, изменив определение:

чр(адам,N):-!,N=0.
чр(ева,N):-!,N=0.
чр(X,2).

Но и это определение не будет работать для запроса

?-чр(X,Y).

Надежное использование отсечения возможно только в случае, если имеется четкое представление о том, как программа будет использоваться. При появлении новых способов использования программы необходимо пересмотреть все случаи употребления отсечения.

Упражнения

1. Определите предикат для удаления всех вхождений указанного элемента в список.