Информатика и выч. техника \ Программирование

Механизм вывода в системе Пролог, страница 3

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

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

В дед (Х,Y)

Н дед (Х,Y) :- отец(X,Z), отец(Z,Y)

П дед (Х1,Y1) :- отец(X1,Z1), отец(Z1,Y1)

У дед (Х,Y) :- отец(X,Z), отец(Z,Y) [TB0]
X=X1,Y=Y1

В  отец(X1,Z1)

Н   отец(алексей, владимир)

У дед (ал,Y1) :- отец(алексей,Z1), отец(алексей,Y1) [TB1] Х1= алексей , Y1=владимир

В   отец(владимир,Y1)

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

В  отец(X1,Z1)

Н   отец(андрей, алексей)

У дед (ан,Y1) :- отец(андрей, алексей), отец(ал,Y1) [TB0]
Х1=андрей, Z1=алексей

В   отец(алексей,Y1)

Н   отец(алексей, владимир)

У дед (андрей, владимир) :-
отец(андрей, алексей), отец (алексей, владимир)

Y1=владимир

Правило «дед» разрешено, следовательно, выходим на TB0.

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

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

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

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

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

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

Например, на запрос

отец(Х,Y),!.

Пролог находит первое решение:

X = a, Y = b и переходит ко второй цели, которая указыва­ет, что невозможно возвращаться назад, и процесс прекраща­ется.

Пусть имеется четыре цели:

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

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

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

Пример 4.5

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

отец(а,b).

отец(b,c).

отец(c,d).

предок(Х,Y) :- отец(Х,Y).                    /* 1-е правило X,Y */

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

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

предок(Z,Y).                                          /* 2-е правило, 2-я цель:",Z,Y.*/

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

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

X=a,Y=b

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

X=b,Y=c

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

X=c,Y=d

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

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

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

X=a,Y=c

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

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

На запрос

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

получим

X=a, Y=b, Z=c

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

Арифметические, логические операции и операции отношения.

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

predicates

дopoгa(symbol, symbol, integer)

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

clauses

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Можно ввести конкретный запрос

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

Для получения ответа использована арифметическая операция "+".

Скачать файл