2. 4.    Процедурная семантика

Назовем эту процедуру вычислить. Как показано на рис. 2.9, входом и выходом этой процедуры являются:

    входом - программа и список целей,
    выходом - признак успех/неуспех и подстановка переменных.

Рис. 2. 9.  Входы и выходы процедуры вычисления списка целей.

Смысл двух составляющих выхода такой:

(1)    Признак успех/неуспех принимает значение "да", если цели достижимы, и "нет" - в противном случае. Будем говорить, что "да" сигнализирует об успешном завершении и "нет" - о неуспехе.

(2)    Подстановка переменных порождается только в случае успешного завершения; в случае неуспеха подстановка отсутствует.

ПРОГРАММА

большой( медведь).                % Предложение 1
большой( слон).                       % Предложение 2
маленький( кот).                    % Предложение 3
коричневый ( медведь).        % Предложение 4
черный ( кот).                         % Предложение 5
серый( слон).                           % Предложение 6

темный( Z) :-                           % Предложение 7:
           черный( Z).                   % любой черный
                                                   % объект является темным
темный( Z) :-                           % Предложение 8:
           коричневый( Z).           % Любой коричневый
                                                    % объект является темным

ВОПРОС

?-  темный( X), большой( X)    % Кто одновременно темный
                                                     % и большой?

ШАГИ  ВЫЧИСЛЕНИЯ

(1)    Исходный список целевых утверждений:

            темный( X),  большой( X).

(2)    Просмотр всей программы от начала к концу и поиск предложения, у которого голова сопоставима с первым целевым утверждением

            темный( X).

        Найдена формула 7:

            темный( Z) :- черный( Z).

Замена первого целевого утверждения конкретизированным телом предложения 7 - порождение нового списка целевых утверждений.

            черный( X),  большой( X)

(3)    Просмотр программы для нахождения предложения, сопоставимого с черный( X). Найдено предложение 5: черный ( кот). У этого предложения нет тела, поэтому список целей при соответствующей конкретизации сокращается до

            большой( кот)

(4)    Просмотр программы в поисках цели большой( кот). Ни одно предложение не найдено. Поэтому происходит возврат к шагу (3) и отмена конкретизации Х = кот. Список целей теперь снова

            черный( X),  большой( X)

Продолжение просмотра программы ниже предложения 5. Ни одно предложение не найдено. Поэтому возврат к шагу (2) и продолжение просмотра ниже предложения 7. Найдено предложение (8):

           темный( Z) :- коричневый( Z).

Замена первой цели в списке на коричневый( Х), что дает

           коричневый( X), большой( X)

(5)    Просмотр программы для обнаружения предложения, сопоставимого коричневый( X). Найдено предложение коричневый( медведь). У этого предложения нет тела, поэтому список целей уменьшается до

            большой( медведь)

(6)    Просмотр программы и обнаружение предложения большой( медведь). У него нет тела, поэтому список целей становится пустым. Это указывает на успешное завершение, а соответствующая конкретизация переменных такова:

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

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

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

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

        G1, G2, ..., Gm

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

• Если список целей пуст - завершает работу успешно.
• Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию 'ПРОСМОТР'.
• ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью 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'
  
• Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением  С   (С  -  предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.

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

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

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;

Рис. 2. 11.  Вычисление целевых утверждений Пролога.

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

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

Упражнение

2. 9.    Рассмотрите программу на рис. 2.10 и по типу того, как это сделано на рис. 2.10, проследите процесс вычисления пролог-системой вопроса

        ?-  большой( X),   темный( X).

Сравните свое описание шагов вычисления с описанием на рис. 2.10, где вычислялся, по существу, тот же вопрос, но с другой последовательностью целей:

        ?-  темный( X),   большой( X).

В каком из этих двух случаев системе приходится производить большую работу для нахождения ответа?