5.2. Внутренние дела Пролога

Работу пролог-программы можно сравнить с поиском пути на разветвленной дороге (коей является последовательность и семантика утверждений), когда известны все или часть характеристик искомого объекта, но не неизвестно, где следует свернуть. Если у нескольких объектов совпадают характеристики, то будет найден первый объект на этой дороге. Пролог ищет «первую истину».

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

Как Пролог убеждается, что цель достигнута?

Основной механизм проверки истинности утверждений заключается в подстановке.

Подстановкой или конкретизацией Θ называется всякое множество присваиваний вида x=t, где x - переменная, а t - терм. Каждой переменной присваевается только одно значение.

Результат подстановки иногда называют подстановочным примером. Если применение подстановки Θ к утверждениям (выражениям) E1,E2 дает один и тот же подстановочный пример, такая подстановка называется унификатором, сам подстановочный процесс - унификацией, а утверждения (предикаты) - унифицируемыми.

5.3. Что такое шаблоны?

Шаблон на поток параметров - шаблон, формирующийся в зависимости от того используются ли параметры в предикатном вызове для ввода данных (т.е. данные известны), либо для вывода данных (т.е. данные неизвестны).

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

Множественные описания предиката - отдельно взятый предикат может иметь несколько описаний, каждое из которых содержит различные доменовые спецификации для аргумента (аргументов) релевантного отношения.

5.4. Управление поиском

Для того, чтобы найти все возможные решения, а также для управления поиском, существует ограниченный, но мощный набор явных средств.

1. Операторы сравнения и альтернатива (или: or|;).

2. Множественность правил для одного предиката.

3. Встроенные предикаты fail, (cut | !), котороые порождают искусственный откат и отсечение возможных переборов соотвественно.

4. Рекурсия или самовызов предиката.

5. Комбинация отсечения и искусственного отката.

6. Использование предиката типа repeat. repeat:-repeat

Пример

predicates

search2

search

search3

f1(integer,string)

f2(integer,string)

goal

% Если search3 успешен, то write и выполнить search,

% search2, иначе выполнить search, search2.

% используется метод ОО - отсечение и откат.

search3,!,write("Два первых факта удовлетворяют условию"),fail;

search,

search2;

!.

clauses

f1(1,"String1").

f1(2,"String2").

f1(3,"String3").

f1(4,"String4").

f2(1,"String1").

f2(0,"String2").

f2(-5,"String3").

f2(4,"String4").

% Найти первую комбинацию различных фактов, удовлетворяющих

% условию.

% Используется «естественный откат – бэктрегинг» для поиска

% единственного успешного решения.

search:-

f1(X1,S1),

f2(X2,S2),

X2<X1,write(X1," ",S1," ",X2," ",S2),nl.

% Найти все комбинации разных фактов, удовлетворяющих условию

% Используется ОПН - откат после неудачи.

search2:-

f1(X1,S1),

f2(X2,S2),

X2<X1,write(X1," ",S1," ",X2," ",S2),nl,

fail.

search2:-!.

% Удовлетворяют ли условию 1-ые 2 разных факта

% Здесь важно, в каком месте использован откат. Если он был бы

% поставлен после сравнения, то было бы найдено единственное

% решение, как в предикате search.

search3:-

f1(X1,S1),

f2(X2,S2),!,

X2<X1,write(X1," ",S1," ",X2," ",S2),nl.