Модификация программы путем переупорядочения предложений и целей

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

predecessor) Parent, Child! :-parent ( Parent, Child).

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

1. Изменить порядок предложений в программе.

2. Изменить порядок целей в телах предложений.

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

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

Часть I. Язык Prolog

2. В результате перестановки местами целей при каждом выбранном порядке предложений.

Соответствующие четыре процедуры, predl, pred2, pred3 и pred4, приведены в листинге 2.4.

Листинг 2.4. Четыре версии программыpredecessor

% Четыp^li2=Tpграммы predecessor

pa'ren оначалz) .

predK x, Z) :-parent { X, Y), predl ( Y, Z) .

* Версия А: поменять местами предложения первоначальной версии
Dred2( X, Z) :-

pred2 (X, Z) :-parent! X, Z) .

* Версия Б: поменять местами цели во втором предложении первоначальной версии
pred3< X, Z] :-

parent ( x, Z) .

pred3( X, Z) :-pred3( X, Y) ,

parent ( Y, Z) .

■ Версия В: поменять местами цели я предложения первоначальнойверсии pred4i х, Z) :-

pred4{ X, Y) ,

parent ( Y, 2) .

pied4{ X, Z) :-parent( X, Z).

В поведении этих четырех процедур, эквивалентных с декларативной точки зре­ния, наблюдаются важные различия. Для демонстрации этого рассмотрим отношение parent (см. рис. 1.1 в главе 1). Итак, что произойдет при обработке вопроса о том, является ли Том предком Пэг, с использованием четырех вариантов отношения predecessor, как показано ниже.

?- predl { torn, pat; . yes

?- pred2 ( torn, pat) .

yes

?- pted3( torn, pat).

yes

?- pred4( torn, pat).

В последнем случае система Prolog не может найти ответ. Это выражается в том, что система Prolog выводит на терминал примерно такое сообщение, как "More core needed" (Нехватка оперативной памяти) или "Stack overflow" (Переполнение стека).

Трассировка выполнения программы predl (называемой в главе 1 как predecessor), полученная при обработке указанного вопроса, показана на рис. 1.10 в главе 1. На рис. 2.13 приведены соответствующие трассировки для pred2, pred3 и pred4. На рис. 2.13, s наглядно показано, что нельзя надеяться на успешное завер­шение работы программы pred<3, а на рис. 2.13, а видно, что программа pred2 явля­ется довольно неэффективной по сравнению с predl, поскольку она выполняет на­много больше операций поиска и возврата в генеалогическом дереве.

Глава 2. Синтаксис и значение программ Prolog

pred2(X,Z)> parant(X, Y),

pred2l V, Z).