Семантические модели пролога

В Прологе обычно применяются две семантические модели: декларативная и процедурная. Семантические модели предназначены для объяснения смысла программы.

В декларативной модели рассматриваются отношения, определенные в программе. Для этой модели порядок следования предложений в программе и условий в правиле не важен.

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

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

В отличие от традиционных языков программирования, в которых основным средством организации повторяющихся действий являются циклы, в прологе используются процедура поиска с возвратом (откат) и рекурсия. Откат даёт возможность получить много решений в одном вопросе к программе, а рекурсия позволяет использовать в процессе определения предиката его самого. Рекурсию используют не только в прологе, но и в остальных языках программирования. Но в прологе в отличие от остальных языков рекурсия является основным приемом программирования.

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

предок(Предок,Потомок):- родитель(Предок,Потомок). /* предком является родитель */предок(Предок,Потомок):- родитель(Предок,Человек), предок(Человек,Потомок). /* предком является родитель предка */

Отношение предок является транзитивным замыканием отношения родитель, то есть это наименьшее отношение, включающее отношение родитель и обладающее свойством транзитивности.

Базис рекурсии – это предложение, определяющее некоторую начальную ситуацию или ситуацию в момент прекращения.

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

<имя определяемого предиката>:- [<подцели>], [<условие выхода из рекурсии>], [<подцели>], <имя определяемого предиката>, [<подцели>].

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

Пример. Создадим предикат, который будет вычислять по натуральному числу его факториал. Эта задача допускает рекурсивное решение на многих языках программирования, а также имеет рекурсивное математическое описание:

1!=1 /* факториал единицы равен единице */N!=(N-1)!*N /* для того, чтобы вычислить факториал некоторого числа, нужно вычислить факториал числа на единицу меньшего и умножить его на исходное число */

Попробуем записать реализацию предиката, эквивалентную математическому определению предиката:

fact(1,1). /* факториал единицы равен единице */fact(N,F):- N1=N-1, fact(N1,F1), /* F1 равен факториалу числа на единицу меньшего исходного числа */ F=F1*N. /* факториал исходного числа равен произведению F1 на само число */

Данных пример с ошибкой – переполнится стек.

Можно проверить, что число, для которого применяется правило, больше единицы. Для единицы останется факт, утверждающий, что факториалом единицы будет единица. Выглядеть этот вариант будет следующим образом: fact(1,1). /* факториал единицы равен единице */fact(N,F):- N>1, /* убедимся, что число больше единицы */ N1=N-1, fact(N1,F1), /* F1 равен факториалу числа, на единицу меньшего исходного числа */ F=F1*N. /* факториал исходного числа равен произведению F1 на само число */

Второй вариант решения проблемы - добавить в первое предложение процедуры отсечение.

fact(1,1):-!. /* условие останова рекурсии */fact(N,F):- N1=N-1, fact(N1,F1), /* F1 равен факториалу числа, на единицу меньшего исходного числа */ F=F1*N. /* факториал исходного числа равен произведению F1 на само число */

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

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

fact2(N,F,N,F):-!. /* останавливаем рекурсию, когда третий аргумент равен первому*/fact2(N,F,N1,F1):- N2=N1+1, /* N2 - следующее натуральное число после числа N1 */ F2=F1*N2, /* F2 - факториал N2 */ fact2(N,F,N2,F2). /* рекурсивный вызов с новым натуральным числом N2 и соответствующим ему посчитанным факториалом F2 */

Остановить рекурсию можно, воспользовавшись отсечением в базисе рекурсии, как мы это делали ранее или добавив в начало второго предложение сравнение N1 с N.

Если мы решим, что вызвать предикат с 3 тремя аргументами неудобно, можно ввести дополнительный двухаргументный предикат, который будет запускать исходный предикат:

factM(N,F):- fact2(N,F,1,1). /* вызываем предикат с уже заданными начальными значениями */

Циклы в прологе:

w:- <условие>,p,w.w:-!.

Пример. Числа Фибоначчи. Базисов рекурсии в данном случае два. Первый будет утверждать, что первое число Фибоначчи равно единице. Второй базис - аналогичное утверждение про второе число Фибоначчи. Шаг рекурсии также будет необычным, поскольку будет опираться при вычислении следующего числа Фибоначчи не только на предшествующее ему число, но и на предшествующее предыдущему числу. В нем будет сформулировано, что для вычисления числа Фибоначчи с номером N сначала нужно вычислить и сложить числа Фибоначчи с номерами N-1 и N-2.

fib(1,1):-!. /* первое число Фибоначчи равно единице */fib(2,1):-!. /* второе число Фибоначчи равно единице */fib(N,F):- N1=N-1, fib(N1,F1), /* F1 это N-1-е число Фибоначчи */ N2=N-2, fib(N2,F2), /* F2 это N-2-е число Фибоначчи */ F=F1+F2. /* N-е число Фибоначчи равно сумме N-1-го и N-2-го чисел Фибоначчи */

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

fib2(1,1,1):-!. /* первые два числа Фибоначчи равны единице */fib2(N,FN,FN1):- N1=N-1,fib2(N1,FN_1,FN), /* FN_1 это N-1-е число Фибоначчи, FN это N-е число Фибоначчи */FN1=FN+FN_1. /* FN1 это N+1-е число Фибоначчи */

Несмотря на то, что предикат fib2 находит, в отличие от предиката fib, не одно число Фибоначчи, а сразу два, он использует намного меньше стекового пространства и работает во много раз быстрее. Для вычисления числа Фибоначчи с номером N (а заодно и N+1-го числа Фибоначчи) необходимо всего лишь N рекурсивных вызовов предиката fib2.

Если нам не нужно след. число, можно сделать последним аргументом анонимною переменную, и добавить след. предикат:

fib2(N,FN):- fib2(N,FN,_).

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

предок2(Предок,Потомок):- родитель(Предок,Потомок). /* предком является родитель */предок2(Предок,Потомок):- предок2(Человек,Потомок), /* предком является родитель предка */родитель(Предок,Человек).

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

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

Дата добавления: 2014-01-07