Книга: ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

FAIL

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

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

Обратимся к примеру. Рассмотрим следующее определение предиката потомок:

потомок(Х,Y):- отпрыск(Х,Y).

потомок(X,Z):- отпрыск(Х,Y), потомок(Y,Z).

Этот фрагмент программы находит прямых потомков некоторого лица по заданным в базе данных фактам отпрыск, например:

отпрыск(авраам,измаил).

отпрыск(авраам,исаак).

отпрыск(исаак,исав).

. . .

Первое утверждение программы указывает, что Y является потомком X если Y есть отпрыск X, а второе утверждение указывает, что Z является потомком X если Y есть отпрыск X и если Z является потомком Y. Рассмотрим вопрос:

?- потомок(авраам,Ответ), fail.

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

В заданном вопросе после первой цели следует fail. Это сделано для того, чтобы инициировать механизм возврата и тем самым, получить все возможные решения для цели потомок. Таким образом, в целом вопрос никак не может иметь положительного ответа. Однако цель нашей трассировки состоит в том, чтобы наглядно представить себе ход выполнения программы, вызванный несогласуемостью второй цели (fail).

В начале мы имеем прямоугольники, обозначающие две цели, в которые пока не входила стрелка, представляющая цепочку доказательств (см. рис. 8.1). Первое событие состоит в ВЫЗОВе (CALL) цели потомок. Это - обращение номер 1.

Риc. 8.1

(1) CALL: потомок(авраам,Ответ)

(2) CALL: отпрыск(авраам,Ответ)

Мы сопоставили с целью первое утверждение процедуры потомок и это привело к ВЫЗОВ цели отпрыск. В результате возникла ситуация, где стрелка движется вниз (см. рис. 8.2). Мы продолжаем:

Рис. 8.2.

(2) EXIT: отпрыск (авраам,измаил)

Сразу успешно согласуется первое утверждение и следует ВЫХОД (EXIT) из цели.

(1) EXIT: потомок(авраам,измаил)

Таким образом, мы согласовали первое утверждение процедуры потомок.

(3) CALL: fail

(3) FAIL: fail

(1) REDO: потомок(авраам,измаил)

Затем мы пытаемся согласовать fail, и, как и следовало ожидать, эта попытка завершается НЕУДАЧЕЙ (FAIL). Стрелка возвращается из прямоугольника fail назад выше в прямоугольник потомок. Изображение этой ситуации приведено на рис. 8.3. Стрелка движется вверх. Продолжаем:

Рис. 8.3.

(2) REDO: отпрыск(авраам,измаил)

(2) EXIT: отпрыск(авраам,исаак)

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

(1) EXIT: потомок(авраам,исаак)

(4) CALL: fail

(4) FAIL: fail

(1) REDO: потомок(авраам,исаак)

И снова fail заставляет нас отвергнуть это решение и начать возвратный ход. Заметим, что это было совершенно новое обращение к fail (мы вошли в него заново «сверху»).

(2) REDO: отпрыск(авраам,исаак)

(2) FAIL: отпрыск(авраам,Ответ)

На этот раз мы не можем предложить другое сопоставление для цели отпрыск, и потому продолжаем возвратный ход, стрелка отступает вверх, покидая прямоугольник отпрыск.

(5) CALL: отпрыск(авраам,Y)

Здесь произошло следующее: мы выбрали второе утверждение процедуры потомок и выполнили совершенно новое обращение к отпрыск, соответствующее первой подцели (рис. 8.4). Стрелка теперь снова движется вниз. Продолжаем:

Рис. 8.4.

(5) EXIT: отпрыск(авраам,измаил)

(6) CALL: потомок(измаил,Ответ)

Это дает решение, с которым мы теперь уже рекурсивно вызываем потомок. Следует новое обращение к потомок.

(7) CALL: отпрыск(измаил,Ответ)

(7) FAIL: отпрыск(измаил,Ответ)

(8) CALL: отпрыск(измаил, Y2)

(8) FAIL: отпрыск(измаил,Y2)

(6) FAIL: потомок(измаил,Ответ)

У Измаила нет детей (в данном примере) поэтому в обоих утверждениях процедуры потомок подцель отпрыск завершается неудачей, что приводит к неудаче всей цели потомок.

(5) REDO: отпрыск(авраам,измаил)

Мы возвращаемся назад для выбора новой альтернативы.

(5) EXIT: отпрыск(авраам.исаак)

(9) CALL: потомок(исаак,Ответ)

(10) CALL: отпрыск(исаак,Ответ)

(10) EXIT: отпрыск(исаак,исав)

Запускаем новое обращение к потомок и попытка согласовать подцель отпрыск завершается удачно (рис. 8.5). Продолжаем:

(9) EXIT: потомок(исаак,исав)

(1) EXIT: потомок(авраам,исав)

(11) CALL: fail

(11) FAIL: fail

(1) REDO: потомок(исаак,исав)

(9) REDO: потомок(исаак,исав)

Это дает окончательное решение исходного вопроса, однако fail вновь вынуждает включиться механизм возврата, поэтому мы возвращаемся назад по событиям REDO:

(10) REDO: отпрыск(исаак,исав)

(10) EXIT: отпрыск(исаак,иаков)

(9) EXIT: потомок(исаак,иаков)

(1) EXIT: потомок(авраам,иаков)

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

(12) CALL: fail

(12) FAIL: fail

(1) REDO: потомок(авраам,иаков)

(9) REDO: потомок(исаак,иаков)

(10) REDO: отпрыск(исаак,иаков)

(10) FAIL: отпрыск(исаак,Ответ)

(13) CALL: отпрыск(исаак,YЗ)

Теперь мы пытаемся применить второе утверждение процедуры потомок.

(13) EXIT: отпрыск(исаак,исав)

(14) CALL; потомок(исав, Ответ)

Еще одна рекурсия

(15) CALL: отпрыск(исав,Ответ)

(15) FAIL: отпрыск(исав,Ответ)

(16) CALL: отпрыск(исав,Y4)

(16) FAIL: отпрыск(исав,Y4)

(14) FAIL: потомок(исав,Ответ)

(13) REDO: отпрыск(исаак,исав)

(13) EXIT: отпрыск(исаак,иаков)

(17) CALL: потомок(иаков,Ответ)

Пытаемся использовать Иакова.

(18) CALL: отпрыск (иаков,Ответ)

(18) FAIL: отпрыск (иаков, Ответ)

(19) CALL: отпрыск(иаков,Y5)

(19) FAIL: отпрыск (иаков, Y5)

(17) FAIL: потомок(иаков,Ответ)

(13) REDO: отпрыск(исаак,иаков)

(13) FAIL: отпрыск(исаак,YЗ)

(9) FAIL: потомок(исаак,Ответ)

(1) FAIL: потомок(авраам,Ответ) нет

Наконец мы закончили. Надеемся, что этот утомительный пример дал вам возможность понять последовательность событий, происходящих при выполнении Пролог-программы. Вы, вероятно, уже заметили, что для любой цели всегда бывает только один ВЫЗОВ (событие CALL) и одна НЕУДАЧА (событие FAIL), хотя может быть сколько угодно ПЕРЕДЕЛОК (событие REDO) и соответствующих ВЫХОДов (событие EXIT). В следующем разделе мы рассмотрим процесс трассировки для более сложного примера – предиката присоединить.

Упражнение 8.1. В приведенной выше модели ничего не говорится о том, как обрабатывается цель – отсечение '!'. Расширьте эту модель, включив туда учет действия отсечения.

Оглавление книги