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

Для представления формализованной схемы поиска решений будут использоваться следующие обозначения: 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}

Успех

5.3. Списки и их представление на Прологе.

1. Основные определения.

В языках, предназначенных для программирования задач искусственного интеллекта, важную роль играют динамические структуры данных, называемые списками. Главное достоинство списков состоит в том, что при их обработке операции вставки, замены и удаления элементов выполняются весьма просто. Списки  структуры данных с последовательным доступом, и поэтому основным средством их обработки является рекурсия.

Список в языке Пролог представляет собой заключенную в квадратные скобки [] последовательность термов, разделенных запятыми: [<терм₁>,<терм₂>,…<терм_n>]. Список это составной терм или структура, главный функтор которой обозначается символом «.» (точка).

Структура Список может быть представлена в виде так называемой точечной пары (H,T), где Н  первый элемент списка, называемый головой списка, а Т  все остальные элементы списка, называемые хвостом списка. Голова списка является термом, а хвост списком.

В языке Пролог список, разделенный на головы и хвост, обозначается следующим образом: [H|T], например [a|[d,b,k,l]]. Возможность разделения списка на голову и хвост играет важную роль в программировании рекурсивных процедур обработки списков.

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

Голова и хвост списка могут быть заполнены константами, числами или символьными термами, например [1|[6,8,12,9]] или [a|[r,t,y,u]].

Голова и хвост списка могут быть переменными, например, [H|LT], здесь Нтерм, а LTпеременная, имеющая значение списка.

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