Программирование на языке пролог

Клоксин У.

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

Второе, и последнее, правило говорит о том, что Xпринадлежит списку при условии, что он входит в хвост этого списка, обозначаемый через Y. И нет лучшего пути, чем использовать тот же самый предикат принадлежитдля того, чтобы определить, принадлежит ли Xхвосту списка! В этом и состоит суть рекурсии. На Прологе это выглядит так:

принадлежит(X,[_ |Y]):- принадлежит(X,Y).

и констатирует, что X является элементом списка, еслиX является элементом хвоста этого списка.Заметим, что мы использовали анонимную

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

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

Как мы можем убедиться в том, что граничные условия будут когда-либо удовлетворены? Для этого необходимо обратить внимание на то, как используется рекурсия во втором правиле для предиката принадлежит. Заметим, что каждый раз, когда при поиске соответствия для целевого предиката принадлежитпроисходит рекурсивное обращение к тому же предикату, новая цель формируется для более короткогосписка. Хвост списка всегда является более коротким списком, чем исходный список. Очевидно, что рано или поздно произойдет одно из двух событий: либо произойдет сопоставление с первым правилом для принадлежит, либо в качестве второго аргумента принадлежитбудет задан список длины 0, т. е. пустой список. Как только возникнет одна из этих ситуаций, прекратится рекуррентное порождение целей для предиката принадлежит. Первое граничное условие распознается фактом, который не вызывает порождения новых подцелей. Второе граничное условие не распознается ни одним из утверждений для принадлежит, так что процесс поиска сопоставимого элемента списка для целевого утверждения принадлежит закончится неудачей. Это демонстрирует следующий пример на Прологе:

принадлежит(Х, [X | _]).

принадлежит(Х,[_|Y]):- принадлежит (X,Y).

?- принадлежит(d,[a,b,с,d,e,f,g]).

да

?- принадлежит(2,[3,a,4,f]).

нет

Предположим, мы введем вопрос

?- принадлежит(clugatе,[curraugh_tiр,music_star,раrk_mill, ortland]).

Так как clygateне сопоставимо с curragh_tip,то происходит сопоставление со вторым правилом для принадлежит.Переменная Y получает значение [music_star, park_mill, portland],и порождается следующая цель: определить, принадлежит ли clygateэтому списку. Опять происходит сопоставление со вторым правилом, и снова выделяется хвост списка. Текущей целью становится принадлежит (clugate,[park_mill,portland])Этот процесс рекурсивно повторяется до тех пор, пока мы не доберемся до цели, у которой Xесть clygate,a Yесть [portland].Происходит еще одно сопоставление со вторым правилом, и теперь Yконкретизируется хвостом списка [portland],который является пустым списком. Следующей целью становится принадлежит(clygate,[]).Ни одно из правил в базе данных не сопоставимо с этой целью, так что цель оказывается ложной и ответ на вопрос будет отрицательным.

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

этого же утверждения.

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

родитель(X,Y):- ребенок(Y,X).

ребенок(A,B):- родитель(B,A).

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

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

человек(X):- человек(Y), мать(Х,Y).

человек(адам).

и ввели вопрос

?- человек(X).

то Пролог сначала использовал бы правило и рекурсивно породил подцель человек (Y).Попытка найти соответствие этой цели вновь привела бы к выбору первого правила и породила бы еще одну новую эквивалентную подцель. И так далее, до тех пор, пока не исчерпались бы вычислительные ресурсы. Конечно, если бы была возможность использовать механизм возврата, то был бы найден сообщенный в определении факт об Адаме и началось бы порождение решений ^[7] . Ошибка заключается в том, что для того, чтобы начался возврат, Пролог должен потерпеть неудачу при проверке первого утверждения. В данном же случае поиск решения оказывается неопределенно длинным, и нет никакой возможности завершить этот поиск с успехом либо с неудачей. Из всего сказанного выше можно извлечь следующую мораль:

7

Это могло бы привести к успеху при соответствующем определении предиката мать.
– Прим. ред.

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

Для приведенного примера имеется простой способ устранения ошибки – поместить факт перед правилом, а не после него. В действительности существует хороший эвристический принцип: помещать, где это возможно, факты перед правилами. Иногда при размещении правил в некотором конкретном порядке может возникнуть ситуация, когда они будут правильно работать для целей одного вида и не будут работать для целей другого вида. Рассмотрим следующее определение предиката список (X),при котором предикат списокявляется истинным, если X– список, последний элемент которого имеет в качестве хвоста пустой список:

список([A|B]):- список(B).

список([]).

Если мы используем эти правила для получения ответов на вопросы, подобные следующим:

?- список ([a,b,c,d]).

?- список([]).

?- список(f(1,2,3))

то данное определение будет работать хорошо. Но если мы сделаем запрос

?- список(X).

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