В отличие от традиционных языков программирования, в которых основным средством организации повторяющихся действий являются циклы, в Прологе для этого используются процедура поиска с возвратом (откат - fail) и рекурсия. Рекурсия обычно применяется в ситуациях, когда число возможных решений заранее неизвестно, либо , когда обрабатываются структуры данных с произвольным количеством элементов.
Правила логического программирования чрезвычайно выразительны, поскольку наличие логических переменных и логических связей между атомами делает возможным не конкретное описание предметной области, что в конечном счете влияет на расширенные возможности представления знаний.
Используя рекурсивные правила, т.е. правила, в теле которых может встречаться атом, предикатный символ которого использован в заголовке правила, можно в виде отношения представить чисто процедурные знания из предметной области.
Откат дает возможность получить много решений в одном вопросе к программе, а рекурсия позволяет использовать в процессе определения предиката его самого. При изучении рекурсии частенько вспоминается случай с бароном Мюнхгаузеном, который сам себя за волосы вытаскивал из болота. Любая рекурсивная процедура должна включать в себя базис и шаг рекурсии.
Базис рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии. Так, в приведенной выше процедуре, описывающей предикат предок, базисом рекурсии является первое правило, в котором определено, что ближайшими предками человека являются его родители. Это предложение часто содержит условие, при выполнении которого происходит выход из рекурсии или отсечение.
Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле. В общем виде правило, реализующее шаг рекурсии, будет выглядеть так:
<имя определяемого предиката>:-
[<подцели>],
[<условие выхода из рекурсии>],
[<подцели>],
<имя определяемого предиката>,
[<подцели>].
В некоторых ситуациях предложений, реализующих базис рекурсии, и предложений, описывающих шаг рекурсии, может быть несколько. Как правило, это бывает в сложных случаях, например, когда выполняемые в процессе реализации шага рекурсии действия зависят от выполнения или невыполнения какого-либо условия. Такие задачи встретятся нам в последующих лекциях, когда речь пойдет об обработке рекурсивных структур данных. В этой же лекции мы будем иметь дело в основном с простыми случаями рекурсии, когда рекурсивная процедура имеет один базис и один шаг рекурсии.
Рекурсивное описание правила содержит в своем теле ссылку на заголовок этого же правила. В связи с этим возможны следующие разновидности рекурсии.
1. Правая рекурсия:
правило1():-правило11(), правило12(), . . . , правило1().
2. Левая рекурсия:
правило1():-правило1(), правило21(), . . . , правило2n().
3. Обобщенная рекурсия:
правило1():-правило11(), правило12(), . . . , правило1(), правило21(), правило22(). . .
Для того, чтобы во время выполнения рекурсивного правила не происходило зацикливания нужно условие завершения рекурсии. Их можно реализовать в Прологе двумя случаями:
1. Заданием в программе альтернативного правила, или факта с предикатным атомом правило1, не содержащего рекурсии.
Выход произойдет при успешном выполнении альтернативного правила.
2. Формированием условия выхода одним из предикатов. правило11(), правило12() и т. д. Выход происходит, если в процессе выполнения правила хотя бы один из вышеперечисленных предикатов завершается неуспехом.
Пример. Создадим предикат, который будет вычислять по натуральному числу его факториал. Эта задача допускает рекурсивное решение на многих языках программирования, а также имеет рекурсивное математическое описание:
1!=1 /* факториал единицы равен единице */
N!=(N-1)!*N /* для того, чтобы вычислить факториал
некоторого числа, нужно вычислить
факториал числа на единицу меньшего
и умножить его на исходное число */
Попробуем записать реализацию предиката, эквивалентную математическому определению предиката:
fact(1,1). /* факториал единицы равен единице */
fact(N,F):-
N1=N-1,
fact(N1,F1), /* F1 равен факториалу числа
на единицу меньшего исходного
числа */
F=F1*N. /* факториал исходного числа равен
произведению F1 на само число */
К сожалению, при попытке вычислить факториал произвольного натурального числа с помощью описанного выше предиката fact произойдет переполнение стека ("Stack overflow"). Попробуем разобраться, в чем причина. Рассмотрим, например, что будет происходить, если мы попытаемся вычислить факториал трех.
Соответствующий вопрос можно записать следующим образом:
fact(3,X).
Пролог-система попытается унифицировать цель с заголовком первого предложения (fact(1,1)). Ей это не удастся, поскольку число три не равно единице. При унификации цели с заголовком второго предложения (fact(N,F)) переменная N конкретизируется числом три, а переменная X связывается с переменной F. После этого происходит попытка выполнить подцели, расположенные в теле правила слева направо. Сначала переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть двойкой. Срабатывание следующей подцели (fact(N1,F1)) приводит к рекурсивному вызову предиката, вычисляющего факториал, со значением переменной N1, равным двум.
Так же, как и в случае, когда первый аргумент был равен трем, унификации с головой первого предложения не происходит (единица не равна двум). Сопоставление с головой второго правила происходит успешно. Дальше все происходит почти так же, как для значения переменной N, равного трем. Вычисляется новое значение N1, равное двум без единицы, то есть единице. Пролог снова пытается вычислить подцель fact(N1,F1) (правда, со значением переменной N1, равным единице).
На этот раз происходит сопоставление цели (fact(1,F1)) с заголовком первого предложения, при этом переменная F1 конкретизируется единицей. Пролог-системе наконец-то удалось вычислить вторую подцель второго правила, и она переходит к вычислению третьей подцели (F=F1*N). Переменная N была равна двум, переменная F1 - единице, произведение двух и единицы равно двум и, значит, переменная F конкретизируется двойкой.
Начинается обратный ход рекурсии. После того, как был вычислен факториал двойки, Пролог-система готова вычислить факториал тройки. Для этого нужно умножить факториал двух на три. Переменная F будет конкретизирована числом шесть. Мы получили ответ на вопрос о факториале трех.
Однако вычисления на этом не заканчиваются. Пролог-система обнаруживает, что цель fact(1,F1) может быть сопоставлена не только с заголовком первого предложения, но и с заголовком правила (fact(N,F)). Переменная N конкретизируется единицей, а переменная F1 связывается с переменной F. После этого переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть нулем. Пролог-система пытается вычислить цель fact(0,F1). С заголовком первого предложения (fact(1,1)) сопоставить эту цель не удается, поскольку ноль не равен единице. Зато с заголовком второго предложения (fact(N,F)) цель успешно унифицируется. Переменная N1 становится равна минус единице. После этого делается попытка вычислить цель fact(-1,F1).... Потом fact(-2,F1), fact(-3,F1), fact(-4,F1), fact(-5,F1)... .
Этот процесс будет продолжаться до тех пор, пока не будет исчерпана часть оперативной памяти, отведенная под стек. После этого выполнение программы остановится с сообщением о том, что стек переполнен.
Почему так получилось? Причина в том, что в исходном определении факториала, которое мы использовали, предполагалось, что правило работает только для натуральных чисел, то есть для положительных целых чисел. У нас же в программе произошел выход в отрицательную часть целых чисел, что не было предусмотрено формулой, на которой была основана наша процедура.
Как можно исправить ошибку? У нас есть два варианта корректировки процедуры.
Можно проверить, что число, для которого применяется правило, больше единицы. Для единицы останется факт, утверждающий, что факториалом единицы будет единица. Выглядеть этот вариант будет следующим образом:
fact(1,1). /* факториал единицы равен единице */
fact(N,F):-
N>1, /* убедимся, что число больше единицы */
N1=N-1,
fact(N1,F1), /* F1 равен факториалу числа,
на единицу меньшего исходного
числа */
F=F1*N. /* факториал исходного числа равен
произведению F1 на само число */
В этом случае, хотя и произойдет повторное согласование цели fact(1,F1) с заголовком правила, и переменная N будет конкретизирована единицей, а переменная F связана с переменной F1, первая подцель правила (N>1) будет ложной. На этом процесс оборвется. Попытки вычислять факториал на неположительных числах не произойдет, процедура будет работать именно так, как нам хотелось.
Второй вариант решения проблемы - добавить в первое предложение процедуры отсечение. Напомним, что вызов отсечения приводит к тому, что предложения процедуры, расположенные ниже той, из которой оно было вызвано, не рассматриваются. И, соответственно, после того, как какая-то цель будет согласована с заголовком первого предложения, сработает отсечение, и попытка унифицировать цель с заголовком второго предложения не будет предпринята. Процедура в этом случае будет выглядеть так:
fact(1,1):-!. /* условие останова рекурсии */
fact(N,F):-
N1=N-1,
fact(N1,F1), /* F1 равен факториалу числа,
на единицу меньшего исходного
числа */
F=F1*N. /* факториал исходного числа равен
произведению F1 на само число */
Конечно, с одной стороны, метод рекурсии имеет свои преимущества перед методом итерации, который используется в императивных языках программирования намного чаще. Рекурсивные алгоритмы, как правило, намного проще с логической точки зрения, чем итерационные. Некоторые алгоритмы удобно записывать именно рекурсивно.
С другой стороны, рекурсия имеет большой недостаток: ей, вообще говоря, может не хватать для работы стека.
Другой пример: «Сказка про белого бычка».
goal
clearwindow,
story.
clauses
story : - write (“Хочешь я расскажу сказку про белого бычка?”)
readln ( C ),
C <> “НЕТ”, - это условие выхода
story.
Story.
