Механизм поиска с возвратом.

Для того, чтобы представить работу механизма автоматического возврата удобно воспользоваться понятием маркера. Маркер отмечает текущее утверждение в программе, сопоставимое с целью. Для каждой цели в запросе Пролог¾система создает свой собственный маркер, который будем обозначать значком “Ñ”. Маркеры могут передвигаться только вперед. Однако, когда цель начинает согласовываться сначала, соответствующий маркер устанавливается на первое утверждение, заголовок которого совпадает с именем предиката¾цели.

Рассмотрим этот процесс на примере. Пусть программа «Однокурсники» содержит следующие утверждения:

(1) student_course(X,Y):¾student(X,K1),                    student(Y,K2),X\=Y,K1=K2.

(2) student(‘Иванов’,1).

(3) student(‘Петров’,4).

(4) student(‘Сидоров’,2).

(5) student(‘Кузнецов’,4).

Пусть требуется согласовать запрос:

?¾ student_course(X,Y).

Этот запрос сопоставим с первым утверждением, которое является правилом, поэтому производится редукция цели, и текущая резольвента примет вид:

ТР: student(X,K1), student(Y,K2),X\=Y,K1=K2.

Создадим маркер Ñ1 для первой цели в резольвенте student(X,K1) и маркер Ñ2 для второй цели в резольвенте student(Y,K2).

При просмотре фактов student в программе маркеры будут передвигаться следующим образом:

(2) student(‘Иванов’,1). Ñ1 ¯Ñ2 (no)         ¯Ñ2 (no)

(3) student(‘Петров’,4).         ¯Ñ2 (no) Ñ1 ¯Ñ2 (no)

(4) student(‘Сидоров’,2).       ¯Ñ2 (no)         ¯Ñ2 (no)

(5) student(‘Кузнецов’,4).      ¯Ñ2 (no)         ¯Ñ2 (yes)

                       возврат 1-й цели                        успешный

                                                                      вывод

при подстановке {X=‘Петров’; Y=‘Кузнецов’}.

Таким образом, ответ на запрос будет выдан в следующем виде:

?¾ student_course(X,Y).

X=‘Петров’

Y=‘Кузнецов’¾ >

Получив решение, Пролог¾система предлагает пользователю решить, нужно ли искать другие решения. При нажатии клавиши «;» интерпретатор Пролога выполняет возврат на первую цель и переставляет маркер Ñ1 на предложение 3 программы, а маркер Ñ2 на первое предложение.

(2) student(‘Иванов’,1).         ¯Ñ2 (no)         ¯Ñ2 (no)

(3) student(‘Петров’,4).         ¯Ñ2 (no)         ¯Ñ2(yes)
(4) student(‘Сидоров’,2). Ñ1 ¯Ñ2 (no)             

(5) student(‘Кузнецов’,4).      ¯Ñ2 (no) Ñ1                 
                          возврат 1-й цели                    успешный

                                                                      вывод

при подстановке {X=‘Петров’; Y=‘Кузнецов’}.

Не найдя второкурсников, кроме Сидорова система сама производит возврат и переставляет маркер Ñ1 на предложение 4 программы, а маркер Ñ2 на первое предложение.

Таким образом, ответ на запрос будет выдан в следующем виде:

?¾ student_course(X,Y).

X=‘Кузнецов’

Y=‘Петров’

¾ >;

Если отказаться от этого решения, то система должна будет переставить маркер Ñ1 на предложение, следующее за пятым предложением программы, но поскольку все предложения программы исчерпаны, а маркер Ñ1 может передвигаться только вперед, вычисление запроса завершается, сообщением “no”, которое означает, что больше решений нет.   

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

Рекурсивные правила.

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

· если отношение описывается с помощью такого же отношения;

· когда сложный объект (структура) сам является частью однотипного, сложного объекта.

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

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

В общем случае рекурсивная процедура имеет следующий вид:

<заголовок рекурсивного правила>:¾<предикат условия выхода>, <предикаты>.

<заголовок рекурсивного правила >:¾<предикаты>,

<заголовок рекурсивного правила >,<предикаты>. 

<заголовок рекурсивного правила >:¾<предикаты>,

<заголовок рекурсивного правила >,<предикаты>. 

       …………………………………………..

<заголовок рекурсивного правила >:¾<предикаты>,

<заголовок рекурсивного правила >,<предикаты>. 

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

Чтобы обеспечить проверку условий завершения рекурсивных вызовов, рекомендуется нерекурсивное правило с условием выхода записывать перед рекурсивными правилами.

Рассмотрим примеры рекурсивных процедур.

Пример 1. Программа определения суммы ряда натуральных чисел.

sum_series(1,1).

sum_series(N,S):¾N>0,Next is N-1, sum_series(Next,S1),

                           S is N+S1.

? ¾ sum_series(6,S).

S=21.

YES

Пример 2. Программа генерации ряда натуральных чисел от N до 20.

write_number (20) :¾write(20).

write_number(N):¾ N<20,write(N),nl,Next is N-1, write_number (Next).

? ¾write_number(15).

15

16

17

18

19

20

YES

Схема поиска решений в рекурсивных программах.

Для представления формализованной схемы поиска решений будут использоваться следующие обозначения:
1) ТР ¾текущая резольвента. Первой ТР является исходный вопрос. Каждая следующая резольвента ТР получается путем редукции, т. е. замены самой левой цели в предыдущей резольвенте на тело правила, заголовок которого сопоставим с целью, или путем удаления цели. Если цель сопоставима с фактом, и в том и другом случае вырабатывается подстановка и применяется ко всей ТР.
2) Шаг № ¾ шаг вычисления. Шагом вычислений будем считать действия, выполняемые после определения ТР и заканчивающиеся построением новой ТР или выводом об успехе/неудаче.
3) ТЦ ¾текущая цель. Текущая цель ¾ это цель, подлежащая согласованию на данном шаге.
4) Пр № ¾ правило, применимое для редукции на определенном шаге.
5) Успех¾ вывод об успешном вычислении вопроса. Неудача¾ вывод о неуспешном вычислении вопроса.
6) Откат, Возврат. Отказ ¾ это отказ пользователя от выданного успешного ответа на вопрос, механизм возврата включается принудительно. Возврат ¾ это тупиковая ситуация во время вычисления вопроса, механизм возврата включается автоматически.
7) Так как при рекурсивном обращении к правилу создаются новые экземпляры переменных, будем на каждом шаге добавлять к именам переменных индекс в виде номера шага.

Рассмотрим пример классической рекурсивной процедуры вычисления факториала; эта процедура включает два правила:

fact(1,1). 

fact(N,Res):¾N>1,N1 is N-1,fact(N1,Res1 is N*Res1.

Схема вычисления запроса 

?¾ fact(3, Res).

имеет следующий вид:

ТР: fact(3,Res).

Шаг 1: ТЦ:     fact(3,Res).

    Пр1: 3=1Þno

Пр2: 3>1,N11 is 3-1, fact(N11,Res11),Res is Res11*3.
ТР:   fact(2,Res11), Res is Res11*3.
 Шаг 2: ТЦ:    fact(2,Res11).

    Пр1: 2=1Þno

Пр2: 2>1,N12 is 2-1, fact(N12,Res12),Res11 is Res12*2.
ТР:  fact(1,Res12), Res11 is Res12*2 ,Res is Res11*3.
 Шаг 3: ТЦ:    fact(1,Res12).

Пр1: 1=1Þyes

{Res12=1}

ТР:  Res11 is Res12*2 ,Res is Res11*3.

Шаг 4: ТЦ:     Res11 is 1*2.

{Res11=2}

ТР:  Res is 2*3.
Шаг 5: ТЦ:     Res is Res11*3.

{Res=6}

ТР: ÿ (пустая резольвента)

{Res=6}

Успех