Работа интерпретатора пролога

Интерпретация Пролог-программ. Рассмотрим более детально схему работы интерпретатора Пролог и суть процесса унификации выражений.

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

Рассмотрим следующую БД:

domains

имя=symbol

predicates

отец(имя,имя)

дед(имя,имя)

clauses

/* 1 */ отец(алексей,владимир).

/* 2 */ отец(андрей,алексей).

/* 3 */дед(Х, Y):-

отец(Х, Z),

отец(Z, Y).

Пусть имеется вопрос

/*4*/ дед(Х, Y).

В первом цикле вопросов интерпретатор просматривает фразы программы в последовательности 1-3. Более точно он пытается унифицировать первый литерал из фразы 4 (вначале он единственный) с первым литералом фраз 1-3. В БД только правило 3 может быть унифицировано с фразой 4. Перед унификацией интерпретатор переименовывает переменные правила 3 (X,Y,Z) в X1, Y1, Z1 соответственно. Процесс унификации предполагает замену: X вместо XI, Y вместо Y1. После сравнения литерала из стека с правилом 3 содержимое стека будет:

/* 4а */ отец(Х,Z1),отец(Z1,У).

Во втором цикле первый литерал (4а) унифицируется с фактом 1, "алексей" заменяется X, а "владимир" – Z1. После этого стек содержит:

/* 4b */ отец(владимир, Y).

В третьем цикле литерал (4b) не унифицируется ни с одним из первых литералов фраз 1, 2 или 3. Интерпретатор оказывается в тупике и поэтому выполняет возврат, т.е. содержимое стека, существовавшее до выполнения непосредственно предыдущего цикла, восстанавливается и принимает опять вид состояния 4а.

В четвертом цикле первый литерал (4а) унифицируется с фактом 2, "андрей" заменяется X, а "алексей" - Z1. Стек содержит:

/* 4с */ отец(алексей, Y).

В пятом цикле литерал (4с), оставшийся в стеке, унифицируется с фактом 1 и "владимир" заменяется Y. Стек вопросов становится пустым, что вынуждает интерпретатор выводить значения переменных, указанных в вопросе. В данном случае: Х=андрей, Y =владимир.

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

Описанная схема работы интерпретатора представлена на рис. 11.6.

 

Рис. 11.6. Схема работы интерпретатора Пролог

 

Ниже рассмотрим последовательность операций работы интерпретатора, введя следующие обозначения: В – вопрос к БД пользователя или вопрос, полученный посредством фактов и правил; Н – найден факт или правило в БД; У – фраза в предыдущей строке В унифицируется с фразой в строке Н; П – переименование переменных; д – дед; о – отец; ан – андрей; ал – алексей; вл – владимир. В квадратных скобках указаны точки возврата, откуда начинается поиск, когда соответствующая подцель разрешена:

В д(Х,Y)

Н д(Х,Y) :-o(X,Z),o(Z,Y)

П д(Х1,Y1):-o(X1,Z1),o(Z1,Y1)

У д(Х,1):-o(X,Z),o(Z,Y) [TB0]

Х=Х1, Y=Y1

В o(X1,Z1)

Н о(ал,вл)

У д(ал, Y1):-о(ал,г1),о(вл, Y1) [ТВ1]

Х1 =ал,г1=вл

В о(вл, Y1)

Н Здесь интерпретатор заходит в тупик, так как в БД нет фраз с первым аргументом "вл". Интерпретатор возвращается в ТВО, т.е. содержимое стека восстанавливается:

В o(X1, Z1)

Н о(ан,ал)

У д(ан, Y 1):-о(ан,ал),о(ал, Y1) [ТВ0]

Х1 =ан, Z1 =an

В о(ал, Y 1)

Н о(ал,вл)

У д(ан,вл):-о(ан,ал),о(ал,вл)

Y1 =вл

Правило д разрешено, следовательно, выходим на ТВ0.

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

Рассмотрим более детально процесс отсечения. Мы знаем, что для получения решения нужно проанализировать, как минимум, одну цель, т.е. найти в БД один факт. Также известно, что если правило является конъюнкцией целей, то для получения решения требуется просмотреть, как минимум, две цели. В Прологе это происходит следующим образом:

1) разрешается (если возможно) первая цель для первого соответствующего факта;

2) разрешается (если возможно) вторая цель для всех соответствующих фактов;

3) далее интерпретатор возвращается назад по цепочке целей, как только все факты удовлетворили (или не удовлетворили) второй цели.

С помощью встроенного предиката "!" (восклицательный знак) – средства "отсечения" – можно воспрепятствовать

цель-1,цель-2,!,цель-3,цель-4.

Пролог последовательно анализирует одну за другой четыре цели, а затем: возвращается назад, как только нет решения для цели-4; возвращается назад, как только нет решения для цели-3 (или вновь направляется вперед к цели-4 в случае, если имеется решение для цели-3); после этого интерпретатор останавливается на предикате "!", т.е. возвращение к цели-2 и цели-1 невозможно.

Приведем примеры применения предиката "!".

Рассмотрим следующую программу на Прологе:

отец (а,b).

отец (b,с).

отец (с,d).

предок (Х,Y):-

отец (Х,Y).

/* "1-е правило:", Х, Y. */

предок (Х,У):-

отец(Х,2),

/* "2-е правило, 1-я цель:", Х,Z, */

предок(Z,У).

/* "2-е правило,2-я цель:", Z,У. */

Последовательность выполнения операций следующая:

1-е правило: а,b

X=a,Y=b

1-е правило: b,с

X=b,Y=c

1-е правило: c,d

X=c,Y=d

2-е правило 1 -я цель: а,b

1-е правило: b,с

2-е правило 2-я цель: b,с

X=a,Y=c

2-е правило 1-цель: b,с

1-е правило: c,d

2-е правило 2-я цель: c,d

2-е правило 2-я цель: b,d

X=a,Y=d

На запрос

!,отец(X,Y),отец(Y,Z)

получим

X=a,Y=b,Z=c

X=b,Y=c,Z=d

На запрос

отец(X,Y),!,отец(Y,Z)

получим

X=a,Y=b,Z=c

Предикат "ложь". В Прологе имеется встроенный предикат "fail", который всегда указывает на ложь, т.е. на тупик в процессе анализа целей. Этот предикат полезен в том случае, когда необходимо получить все решения некоторой более ранней цели, прежде чем переходить к анализу последующих целей (обычно Пролог находит первое решение первой цели, а затем последующих целей). Вопрос заключается в том, как пройти к последующим целям, если предикат "fail" систематически осуществляет возврат. Например, на запрос отец(Х,Y), write(X,Y),nl,fail,мать(Z,Y). высвечиваются имена всех отцов и нет возможности достичь предиката "мать". Это можно сделать с помощью логической операции ИЛИ, используя которую можно сказать: ИЛИ имеется следующий факт "отец", ИЛИ осуществляется переход к следующей цели".

Арифметические, логические операции и операции отношения. Рассмотрим следующую БД:

predicates

дорога(symbol,symbol,integer)

связь(symbol, symbol, integer)

clauses

дорога(минск,москва,750).

дорога(москва,свердловск, 1668).

дорога(свердловск,новосибирск, 1675).

связь(Отправление,Прибытие,Расстояние):-

дорога(Отправление,Прибытие,Расстояние).

связь(Отправление,Прибытие,Расстояние):-

дорога(Отправление,Транзит,Расстояние 1),

связь(Транзит,Прибытие,Расстояние2),

Расстояние=Расстояние 1 +Расстояние2.

Введем запрос:

связь(минск,Прибытие,Расстояние)

и получим расстояния от Минска до других городов:

Прибытие=москва, Расстояние=750

Прибытие=свердловск, Расстояние=2418

Прибытие=новосибирск,Расстояние=4093

Можно ввести конкретный запрос связь(минск,новосибирск,Расстояние). Для получения ответа использована арифметическая операция "+".

В Прологе имеются также операции "-", "*", "/". Заметим, что порядок аргументов в выражениях значения не имеет. Так, выражение Х=А*В идентично А*В=Х. В Прологе применяются следующие функции, позволяющие вычислять:

mod, XmodY – остаток от деления X на Y;

div, XdivY – целую часть частного от деления X на Y;

abs(X) – абсолютную часть числа; ехр(Х) – возведение е в степень X;

sqrt(X) – значение квадратного корня от X;

sin(X), cos(X), tg(X), arctg(X) – тригонометрические функции.

Для арифметических операций установлен следующий приоритет:

1)+,-; 2)*,/; 3) mod,div; 4)+,-(одноместные).

Рассмотрим применение арифметических операций "-" и "*" для вычисления факториала числа. Известно, что 1!=1 и n!=n*(n-l)!

В предикате " fact(X,Y) " Y является факториалом числа X.

Первое утверждение на Прологе записывается в виде следующего факта: fact(l,l). Для записи второго утверждения нужно:

1) из n вычесть единицу, получая Z;

2) вычислить факториал Z, получая X1;

3) умножить X1 на n, получая Y.

Таким образом, имеем следующую программу:

predicates

fact(real,real)

clauses

fact(l.l).

fact(X, Y):-

Z=X-1,

fact(Z, X1),

Y=X*X1.

Введем запрос fact(5, X) и получим правильный ответ: Х =120. Но система продолжает поиск других решений и в окне "Message" выдает сообщение о том, что стек переполнен и нужно нажать клавишу ПРОБЕЛ.

Здесь не указано ограничение поиска, система продолжает уменьшать X на единицу и пытается унифицировать этот результат с первым фактом fact(l,l). Для указания останова поиска есть несколько способов. Так, можно задать в первом факте предикат отсечения:

fact(l,l):-!.

или этот предикат указать во втором правиле:

fact(X, Y):-

Z=X-1,

fact(Z, X1),

!, Y=X*X1.

Можно задать условие, чтобы оставшееся значение X превышало единицу:

fact(X, Y):-

Х >1,

Z = X -1,

fact(Z, X1),

Y=X*X1.

Пример.

Вычислить 5!:

5! = 5 * 4! или

4! = 4 * 3! или

3! = 3 * 2! или

2! = 2 * 1! или

= 1! = 1 т.е.

2! = 2 * 1 = 2 т.е.

3! = 3 * 2 = 6 т.е.

4! = 4 * 6 = 24 т.е.

5! = 5 * 24 = 120

В выражениях применяются логические операции: умножение (обозначается знаком ","), сложение (обозначается знаком ";"), отрицание. Так, используя операцию ИЛИ, правила

родители(Х, Y):- отец(Х, Y).

родители(Х, Y):- мать(Х, Y).

можно записать в виде

родители(Х, Y):-

отец(Х, У); мать(Х, У).

Операция отрицание обозначается предикатом "not". Так, утверждение not отец(a,d) истинно, если факт отец(а,d) отсутствует в БД.

Для сравнения значений применяются следующие операции отношений:

“>”, “>=”, “<”, “<=”, “=”, “<>” или “><” (не равно).