Процедурная семантика программ Пролога

Близкой к традиционному представлению об алгоритме и его исполнении является процедурная семантика программы Пролога.

Пример: пусть имеем правила: Начальник(Фамилия, Оклад) :- Служащий Фамилия, Оклад), Оклад > 20 000. Процедурное прочтение: запрос

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

Программа — множество правил вида А <— Вь В2,Вт, где Bi — процедуры, вызываемые с головы А, которая является входом в это множество, называемое телом процедуры.

Цели — линейно упорядоченное множество литералов (запросов-вызовов процедур) Сь С2п.

Таким образом, организован порядок вызова процедур исполнения программы, называемый линейной резолюцией (SLD — state linear definition).

Пусть имеется исходное упорядоченное множество целей Ct, С2, ..., Сп. Тогда линейная резолюция состоит в следующем.

  • 1. Найти правило (клауз) и согласовать его аргументы с первым литералом из головы: А <— В{, В2,..., Вт. Клаузы должны иметь различные переменные (переименовать при необходимости).
  • 2. Заменить Сх телом процедуры для первой найденной и согласованной с целью головы: В{, В2>..., ВтУ С2,..., Сп.
  • 3. Продолжать исполнение с Вх.

С процедурной семантикой согласуются встроенные процедуры человеко-машинного интерфейса (графика, клавиатура), структуры данных и численная арифметика, ввод-вывод, работа с файлами, экранами.

Примеры запросов для исполнения процедурами с вводом и выводом:

  • ?-Х is 10 * 4 X = 40
  • 1-Х is 3, X < 4 X = 3

Согласование в процедурном исполнении не совпадает с унификацией в сентенциальном программировании. Отличие в том, что допускается рекурсивное применение подстановки (x/f(x)). Таким образом, разрешено рекурсивное исполнение программы, заменяющее цикл с параметрами в традиционном программировании.

Рекурсивные определения:

Предок(А, Б):- Родитель(В, Б);

Предок(А, В) :- Родитель(В, Б), Предок(А, В).

Для демонстрации вычислений используется диаграмма подстановок.

Рассмотрим следующий пример рекурсии. Предикат, определяющий рекурсию P(J(x)):Р(х)уQ(x). Начальное состояние — исходные данные (высказывания) Q(a), Р(а). Вычисление: ->Р(х). Тогда диаграмма имеет следующий вид:

Если предусмотреть условие завершения рекурсии, то будет представлено все дерево ее исполнения.

Рассмотрим на примере применение языка Пролог в вычислениях с использованием рекурсии.

Пример 5.7

Вычислим /(дг) = х.

Программа состоит из факта fact(0, 1) и одного правила Jact(x, у).

Факт fact(0,1) обозначает базис рекурсии: 0! = 1.

Правило fact(x, у) <— fact(x - 1, f(y, х)), где f(y, х) = у ? х, правило вычисления факториала.

Цель: lfact{8, у) — «вычислить у = 8!».

Исполнение алгоритма, представленного операторами языка Пролог, по правилу линейной резолюции:

Решение f(f(f(f(y, 8), 7),6), ..., 1) при у/1 определяется рекурсивной формулой 8 - 7 - 6 - ... - 1 — формула далее не унифицируется, но возможна обратная подстановка у/1.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >