DOMAINS. nondeterm roditel(name, name)

name=string

PREDICATES

nondeterm roditel(name, name)

nondeterm predok(name, name)

CLAUSES

roditel(ivan, oleg).

roditel(inna, oleg).

roditel(oleg, dima).

roditel(oleg, marina).

predok(X, Z): - roditel(X, Z). % нерекурсивная часть правила

predok(X, Z): - roditel(X, Y), predok(Y, Z). % рекурсивная часть правила

GOAL

predok(X, Y), write(“Predok - ”, X, “Ego potomok - ”, Y), nl, fail.

Результат выполнения программы (рис. 1):

Predok - ivan Еgo potomok - oleg

Predok - inna Еgo potomok - oleg

Рredok - oleg Еgo potomok - dima

Рredok - oleg Еgo potomok - marina

Рredok - ivan Еgo potomok - dima

Рredok - ivan Еgo potomok - marina

Рredok - inna Еgo potomok - dima

Рredok - inna Еgo potomok - marina

Рассмотрим следующий пример вычисления факториала.

Пример 2.

Правило для вычисления факториала можно сформулировать следующим образом: если число - 0, то его факториал равен 1, в противном случае факториал числа N - это произведение (N-1)! на N.

Решение:

PREDICATES

nondeterm start

nondeterm fact(integer, integer)

CLAUSES

start: - write(“Vvedite chislo: ”), readint(N), fact(N, Nf), write(“Factorial: ”, Nf).

fact(0, 1): -!. % факториал нуля равен единице

fact(N, Nf): - N1=N-1, % уменьшаем N на единицу

fact(N1, N1f), % вычисляем факториал нового числа

Nf=N1f*N. % а затем умножает его на N

GOAL

start.

Рассмотрим работу программы при вычислении 2!. При вызове предиката fact сначала рассматривается его первый клоз. Однако попытка сопоставления предикатов fact(N, Nf) и fact(0, 1) заканчивается неудачей из-за несовпадения первого аргумента, так как N=2. Рассматривается второй клоз предиката fact. Вычисляется переменная N1=2-1=1, и вызывается предикат fact(N1, N1f), где N1=1 (переменная N1f пока свободна). Таким образом, выполняется рекурсия (предикат fact вызывает сам себя). Рассматривается первый клоз предиката fact, т.е. делается попытка сопоставления предикатов fact(N1, N1f) и fact(0, 1). Сопоставление заканчивается неудачей, так как N1=1. Рассматривается второй клоз предиката fact: происходит успешное сопоставление предикатов fact(N1, N1f) и fact(N, Nf). В результате этого переменная N получает значение 1. Выполняется также унификация переменных N1f и Nf (пока они обе свободны, но когда одна из них получит значение, другой будет присвоено тоже значение). Важно понимать, что при этом в памяти сохраняется информация о том, что обработка предыдущего вызова предиката fact (с аргументом N=2) еще не закончена. Вычисляется переменная N1=N-1=1-1=0, и вызывается предикат fact(N1, N1f). Для его доказательства рассматривается первый fact(0, 1). Сопоставление предикатов fact(N1, N1f) и fact(0, 1) выполняется успешно, так как N1=0, а N1f - свободная переменная. В результате унификации переменная N1f получает значение 1. Так как доказан предикат fact(N1, N1f) (где N1=0, а N1f получила значение 1), доказывается следующий предикат: Nf=N1f*N, где N1f=1 и N=1. Переменная Nf получает значение 1.

Таким образом, доказан предикат fact(N1, N1f), где N1=1, а N1f в результате доказательства получила значение 1. В свою очередь, этот предикат был вызван из тела предиката fact при N=2. Так как предикат fact(N1, N1f) доказан, доказывается следующий предикат: Nf=N1f*N. В результате переменная Nf получает значение 2. Таким образом, доказан предикат fact(N, Nf) с аргументом N=2, вызванный из тела целевого предиката. Переменная Nf получила значение 2.

Примечание: Можно сказать, что рекурсивные вызовы предикатов в рекурсивных программах образуют стек.

Необходимо обратить внимание, что для уменьшения переменной на единицу используется запись N1=N-1. Запись типа N=N-1 в Прологе недопустима, так как она рассматривается как предикат сравнения N и N-1; очевидно, что он всегда принимает значение «ложь». Присвоить связанной переменной новое значение в Прологе невозможно.

Результат выполнения программы:

1-й случай (рис. 2):

N=1

F=1

Рис. 2. Вывод результата программы (1 случай)

2-й случай (рис. 3):

N=2

F=2

Рис. 3. Вывод результата программы (2 случай)

3-й случай (рис. 4):

N=4

F=24

Рис. 4. Вывод результата программы (3 случай)