Практическая информатика


Рекурсивные процедуры - часть 2


Одним из возможных способов решения этой проблемы является добавление отсутствующих фактов, например,

больше(слон, обезьяна).

Для нашего маленького примера это означает добавление еще 5 фактов. Однако гораздо лучшим решением будет добавление в программу нового отношения, которое мы назовем больше_2. Животное X больше, чем животное Y, если это определено как факт (первое правило) или существует животное Z, для которого определен факт, что животное X больше, чем животное Z и может быть показано, что животное Z больше, чем животное Y (второе правило). На Прологе это запишется так:

больше_2(X, Y) :- больше(X, Y). больше_2(X, Y) :- больше(X, Z), больше(Z, Y).

Если в цепочке участвуют не три, а большее число объектов, то придется добавить новые правила:

больше_2(X, Y) :- больше(X, Z1), больше(Z1, Z2), больше(Z2, Y). больше_2(X, Y) :- больше(X, Z1), больше(Z1, Z2), больше(Z2, Z3), больше(Z3, Y). ...

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

Поэтому воспользуемся более корректной и элегантной формулировкой. Ключевая идея здесь - определить отношение больше_2 с помощью его самого. Теперь второе (и последнее!) правило выглядит так:

больше_2(X, Y) :- больше(X, Z), больше_2(Z, Y).

Таким образом, итоговая программа будет иметь вид

больше_2(X, Y) :- больше(X, Y). больше_2(X, Y) :- больше(X, Z), больше_2(Z, Y).

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

ERROR: Out of local stack

Если теперь в запросе использовать предикат больше_2 вместо больше, то программа будет работать так, как и предполагалось:

?- больше_2(слон, обезьяна). Yes

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


- Начало -  - Назад -  - Вперед -