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

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

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

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

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

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

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

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

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

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

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

список([]).

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

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

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

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

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

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

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

обобщенный_список([]).

обобщенный_список([_ |_]).

В этом варианте просто проверяется начало списка, а не тот факт, что последний хвост списка является пустым списком ([]). Последнее определение не является таким же строгим тестом правильности списка, как определение предиката список, но оно не приведет к зацикливанию, если аргументом является переменная.

3.4. Пример: преобразование предложений

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

Вы: you are a computer (Вы - ЭВМ)

Пролог: i am not a computer (Я – не ЭВМ)

Вы: do you speak french (Вы говорите по-французски?)

Пролог: no i speak german (Нет, я говорю по-немецки)

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

1. Ввести предложение, набранное пользователем на терминале.

2. Заменить каждое вхождение слова you на слово i.

3. Аналогичным образом заменить are на am not.

4. Заменить french на german.

5. Заменить do на nо.

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

Вы: i do like you (я действительно люблю вас)

Пролог: i no like i (я не люблю себя)

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

Программа на Прологе, преобразующая одно предложение английского языка в другое, может быть реализована следующим образом. Прежде всего необходимо осознать, что имеется отношение между исходным предложением и преобразованным. В связи с этим нам следует определить предикат, называемый преобразовать. Преобразовать(Х, Y) означает, что предложение X может быть преобразовано в предложение Y. Предложения X и Y удобно представлять в виде списков атомов, обозначающих слова, так что предложения могут быть записаны следующим образом: [this,is,a,sentence] (это некоторое предложение). Определив предикат преобразовать, мы могли бы обращаться к Прологу с вопросами вида

?- преобразовать([dо,you,know,french],X). (Знаете ли вы французский)

на что Пролог отвечал бы

X=[no,i,know,german] (нет, я знаю немецкий).

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

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

преобразовать([], [])

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

1. Заменить голову входного списка соответствующим словом и поместить это слово в выходной список в качестве головы.

2. Преобразовать хвост входного списка и сделать его хвостом выходного списка.

3. Если мы достигли конца входного списка, то к выходному списку больше ничего добавлять не надо, и мы можем завершить выходной список пустым списком [].