Выполнение и трассировка программы

Алгоритм выполнения Пролог-программы основан на механизме прямого перебора с возвратом и операции сопоставления (унификации).

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

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

Если при поиске решения обнаружено несколько вариантов доказательства истинности цели, то Пролог-система запоминает альтернативные варианты решения - точки возврата.

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

РАССМОТРИМ ПРИМЕР ВЫПОЛНЕНИЯ ПРОЛОГ-ПРОГРАММЫ

База знаний:

?- a(X),b(X),e.

a(1).

a(Y):- c(Y),d(Y).

b(2).

c(1).

c(2).

d(2).

e.

Запрос

?- a(X),b(X),e.

ДЕРЕВО ВЫВОДА

На рисунках представлено дерево вывода. Жирными линиями в дереве обозначены И-деревья – для доказательства такого дерева необходимо, чтобы каждая его ветка «опиралась» на истинное утверждение. ИЛИ-деревья исходят из вершин с точками возврата, такое дерево истинно, если хотя бы одна ветка опирается на истинное утверждение. Пунктирные линии – альтернативные ветки, не рассматриваемые на данном этапе (либо ложные, либо еще не рассмотренные).

В данном примере получение решения складывается из трех этапов. Вначале рассматривается первая подцель – она имеет два предложения в базе, заголовки которых сопоставимы с ней, поэтому она является точкой возврата. Выбирается первое сверху предложение – это факт a(1), при этом свободная переменная X получает значение 1. Первая цель запроса доказана. Вторая цель - b(1) (X уже связана со значением 1) не сопоставляется ни с одним правилом базы, следовательно, является ложной.

Бэктрекинг – возврат к ближайшей точке возврата, т.е. a(X). На втором дереве отображен вывод по второй альтернативе. Связываются две переменные X из запроса и Y из правила для предиката a. Фактически запрос ?-a(X),b(X),e подменяется на новый набор целей ?‑c(Y),d(Y),b(Y),e. Первая подцель – это c(Y) – она является новой точкой ветвления, так как унифицируется с двумя предложениями в базе. Первое предложение – факт приводит к унификации Y с 1, но следующая в наборе подцель d(1) – ложна.

Третье дерево отражает альтернативу для c(Y) с унификацией Y=2. Для этой альтернативы истинны все последующие цели из набора (они унифицируются с соответствующими фактами).

ЗАДАНИЕ 1.3

Загрузите Пролог-программу из задания 1.2.

В SWI/PROLOG есть два вида отладчиков: командный[2] и графический[3], в последнем трассировка выглядит более наглядно.

Для перехода в режим трассировки необходимо набрать встроенный предикат debug. Для выхода из режима трассировки – предикат nodebug [4].

Перейдите в режим трассировки. Для трассировки необходимо указать контрольные точки (Spy points) в меню Debug -> Edit spy points -> Predicate, где указать имена предикатов. В данном случае укажите предикат любит. Обратите внимание, что справа внизу находятся три кнопки, где указываются как контрольные точки, так и точки трассировки. Контрольные точки (Spy points) позволяют вызвать графический отладчик. Точки трассировки (Trace points)— консольный отладчик. Третий выбор — просмотр и редактирование файла программы, содержащей, введенный в поле Predicate, предикат. Внешний вид изображен на снимке ниже.

ЗАМЕЧАНИЕ. На момент написания методички графический отладчик не поддерживал русских предикатов (не работает корректно указание контрольных точек и точек трассировки через графический интерфейс). В связи с этим опишем предикаты относящиеся к отладке программы с использованием командной строки.

Предикат	Описание
trace	Включить режим трассировки. Если не указаны точки трассировки, будет производиться полная пошаговая трассировка.
tracing	Успешен, если вызывается из режима трассировки.
notrace	Выход из режима трассировки.
guitracer, gtrace	Включить графического режима трассировки. Окно графического режима трассировки включается при встрече первой контрольной точки (spy-point).
noguitracer	Отключить графического режима трассировки.
trace(Pred)	Установить точку трассировки предиката с именем Pred (то есть отображаться при трассировке будет каждое событие связанное с предикатом Pred).
trace(Pred,Ports)	Установить точку трассировки предиката с именем Pred и активирующейся по событиям (при прохождении по портам) Ports. События могут быть следующих типов: 1. fail – событие соответствующее неудачному вызову предиката с именем Pred; 2. call – событие соответствующее первому вызову предиката с именем Pred; 3. redo – событие соответствующее повторному вызову предиката с именем Pred; 4. exit – событие соответствующее успешному окончанию вызова предиката с именем Pred. Сам же параметр Ports может принимать значения типов сообщений с префиксами соответствующими добавлению и удалению события (порта) из точки трассировки а так же списки таких значений. Например, запрос ?- trace(foo/2, +fail), trace(foo/2, [+call,-fail]). добавляет в точку трассировки связанную с предикатом foo/2 событие fail. Для добавления события используют префикс +, для изъятия -. Кроме того можно оперировать сразу со всеми типами событий, используя обозначение all. Пример: trace(foo/2, +all).
debug	Включить режим отладки. При запросах к программе в режиме отладки выводятся все события, происходящие при выполнении запроса, связанные с установленными точками отладки.
nodebug	Отключить режим отладки.
debugging	Показать отслеживающиеся точки трассировки и контрольные точки
spy(Pred)	Установить контрольную точку, связанную с предикатом Pred.
nospy(Pred)	Убрать контрольную точку, связанную с предикатом Pred.
nospyall	Убрать все контрольные точки.

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

Задайте запрос

?-любит(X,теннис),любит(X,компьютеры).

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

В левой верхней части окна графического отладчика отображены текущие значения переменных текущего выполняемого предиката, справа стек вызовов предикатов, в нижней части факты и правила, где цветом отмечен следующий вызываемый предикат. Внешний вид графического отладчика изображен на рисунке. Сверху, в виде кнопок, находятся допустимые действия. Вторая кнопка (стрелка вправо) позволяет выполнять программу пошагово (предикат за предикатом). Цвет выделения также имеет значение. Красный цвет обозначает неудачу, ложность решения.

ЗАДАНИЕ 1.4

Используя команды внешнего редактора, заменить всюду 'Eric' на 'Tom'. Построить дерево вывода для построенной в задании 1.2 базы данных и запроса

?-sportsman('Mark').

ЗАДАНИЕ 1.5

Построить базу знаний на основе текста:

Живет зебра на земле. Живет собака на земле. Живет карп в воде. Живет кит в воде. Кошка живет там же, где живет собака. Живет крокодил в воде и на земле. Живет лягушка в воде и на земле. Живет утка в воде, на земле и в воздухе. Живет орел в воздухе и на земле. Живет буревестник в воде и в воздухе.

Задайте к этой базе запросы (воспользуйтесь предикатом help для поиска отношения "неравно").

Кто где живет?

Кто живет на земле, но не является собакой?

Кто живет и на земле, и в воде?