Программирование на языке пролог

Клоксин У.

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

потомок(Х,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: потомок(авраам,иаков)