Параллельное программирование



              

Реализация языка логического программирования ПРОЛОГ на ВС SPMD-архитектуры - часть 2


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

Т.е. для решения данной задачи необходимо действовать следующим образом.

Находим первый (и единственный) предикат цели дядя (X, Y). Находим в БЗ процедуру с этим именем и заменяем найденный предикат правой частью этой процедуры. Получим трансформируемую цель — фрейм

брат (X, P), родитель (P, Y).

К первому предикату этого фрейма применяем аналогичные действия, получаем фрейм

мужчина (X), родитель (Q, X), родитель (Q, P), X <> P, родитель (P,Y)

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

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

родитель (Q, иван), родитель (Q, P), иван <> P, родитель(P,Y)

Обращаемся к процедуре "родитель", начиная второй уровень ветвления. Первый клоз этой процедуры родитель (марья, иван) определяет дальнейшее связывание переменных:

родитель (марья, Р), иван <> P, родитель (P, Y).

Вновь входим в процедуру "родитель"(третий уровень ветвления), находим клоз shape родитель (марья, иван). Трансформируем цель — получаем новый фрейм:

иван <> иван, родитель (иван, Y).

Имеем противоречие, т.е. не проходит унификация.

Ищем на данном шаге ветвления другой вариант связывания, находим следующий клоз

родитель (марья, василий)

Трансформируем цель:

иван <> василий, родитель (василий, Y)

родитель (василий, Y).

Вновь входим в процедуру "родитель", но не находим там клоза, в котором василий указан как чей-либо родитель.


Содержание  Назад  Вперед