Пример иллюстрирующий

Рисунок 2. 10. Пример, иллюстрирующий процедурную семантику
Пролога: шаги вычислений, выполняемых процедурой вычислить.

В главе 1 в разд. "Как пролог-система отвечает на вопросы" мы уже фактически рассмотрели, что делает процедура вычислить. В оставшейся части данного раздела приводится несколько более формальное и систематическое описание этого процесса, которое можно пропустить без серьезного ущерба для понимания остального материала книги.

Конкретные операции, выполняемые в процессе вычисления целевых утверждений, показаны на Рисунок 2.10. Возможно, следует изучить этот рисунок прежде, чем знакомиться с последующим общим описанием.

Чтобы вычислить список целевых утверждений

G1, G2, ..., Gm

процедура вычислить делает следующее:

line();

Если список целей пуст - завершает работу успешно.
Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию 'ПРОСМОТР'.
ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.

Если С найдено и имеет вид

        Н   :-   B1, ..., Вn.

то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком G1, ..., Gm. Пусть С' - это

        Н'   :-   B1', ..., Вn'.

Сопоставляется G1 с H'; пусть S - результирующая конкретизация переменных. В списке целей G1, G2, .... Gm, цель G1 заменяется на список В1', .., Вn', что порождает новый список целей:

        В1', ..., Вn', G2, ..., Gm

(Заметим, что, если С - факт, тогда n=0, и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой, а следовательно, - привести к успешному завершению.)

Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация S, что порождает еще один список целей

        В1'', .... Вn", G2', ..., Gm'
Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением С (С - предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.

line();

Более компактная запись этой процедуры в обозначениях, близких к Паскалю, приведена на Рисунок 2.11.

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

line();

procedure вычислить (Прогр, СписокЦелей, Успех)

Входные параметры:

Прогр: список предложений
СписокЦелей: список целей

Выходной параметр:

        Успех:          истинностное значение; Успех принимает значение
                               истина, если список целевых утверждений
                               (их конъюнкция) истиннен с точки зрения Прогр

Локальные переменные:

        Цель: цель
        ДругиеЦели: список целей
        Достигнуты: истинностное значение
        Сопоставились: истинностное значение
        Конкрет: конкретизация переменных
                Н, Н', B1, B1', ..., Вn , Вn': цели

Вспомогательные функции:

пycтой( L): возвращает истину, если L - пустой список

голoвa( L): возвращает первый элемент списка L

хвост( L): возвращает остальную часть списка L

конкат( L1, L2): создает конкатенацию списков - присоединяет
список L2 к концу списка L1

        сопоставление( T1, T2, Сопоставились, Конкрет): пытается
                сопоставить термы Т1 и T2; если они сопоставимы, то
                Сопоставились - истина, а Конкрет представляет
                собой конкретизацию переменных

подставить( Конкрет, Цели): производит подстановку переменных
в Цели согласно Конкрет

begin
    if пустой( СписокЦелей) then Успех : = истина
    else
        begin
            Цель : = голова( СписокЦелей);
            ДругиеЦели : = хвост( СписокЦелей);
            Достигнута : = ложь;
            while not Достигнута and
                "в программе есть еще предложения" do
                begin
                    Пусть следующее предложение в Прогр есть
                            Н    :-   B1, .... Вn.
                    Создать вариант этого предложения
                            Н'    :-   В1', .... Вn'.
                    сопоставление( Цель, Н',
                                                    Сопоставились, Конкрет)
                    if Сопоставились then
                        begin
                            НовыеЦели : =
                                конкат( [В1', ..., Вn' ], Другие Цели);
                            НовыеЦели : =
                                подставить( Конкрет, НовыеЦели);
                            вычислить( Прогр, НовыеЦели, Достигнуты)
                        end
                    end;
            Успех : = Достигнуты
        end
end;

line();

Содержание раздела