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

Даже в простейших примерах программ, приведенных в главе 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).

pred2(X.Z):-l)nrcnl(X.Z).

pred2(tom, pat)
-------- 7v---------

parent! torn, v i pred2(Y", pat)

 

Y' = bob

pred2(bob, pat)

parent! bob, Y") pred2(Y",pat)

parent! pat, Y'") pred2(Y",pa«) -------- 77

prod2(jim, pat) 7v-----

par*nt(jlm, V") pr»d2(Y"",pat)

7Г

 

	Y"	=ann	V	^
	prad2[ann, pat)
	ft		i\
parent) ertn. V") pred2(Y'",pat)		parent! ann. pat)

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

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

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