Пример 3.1

Predicates % ax² + bx + c = 0

zapros % цель

povtor % рекурсия

kvur(real, real, real)

clauses

kvur(A, B, C) :– B*B–4*A*C>0,

X1 = (-B+sqrt(B*B–4*A*C))/2/A,

X2 = (-B-sqrt(B*B–4*A*C))/2/A,

write(“X1=”, X1),

write(“X2=”, X2), nl.

kvur(A, B, C) :– B*B–4*A*C=0,

X = (-B)/(2*B),

write(“X=”, X), nl.

kvur(A, B, C) :– B*B–4*A*C<0,

write(“No Solutions”).

zapros :– write(“Input A, B, C”),

povtor,

write(“A=”), Readreal(A), A<>0, nl,

write(“B=”), Readreal(B), nl,

write(“C=”), Readreal(C), nl,

kvur(A, B, C),

write(“Press Q for Exit”), nl,

Readchar(S), S=’Q’, !.

povtor.

povtor :– povtor.

goals

makewindow(1, 15, 1, “ax² + bx + c = 0”, 0, 0, 25, 80),

zapros.

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

Пример 3.2

Распечатка фактов из базы фактов.

Predicates

country(symbol).

print.

clauses

% база фактов

country(“England”).

country(“Russia).

…

print :- country(X), write(X), nl, fail.

print.

goal

print.

Пример 3.3

Найти сумму чисел ряда 0 .. N.

S = 0

for i = 1 to N do

S = S + i;

write(S)

S = 0, i = 1

while i<=N do

begin

S = S + i;

i = i + 1;

end;

write(S).

Predicates

summa(integer, integer).

count(N, Res, I, S).

clauses

summa(N, Res) :- count(N, Res, 1, 0).ю

count(N, Res, I, S) :- I <= N, !,

NewS = S + I,

NewI = I + 1,

count(N, Res, NewI, NewS).

count(N, Res, I, S) :- I > N, Res = S,

write(“S=”), write(S).

3.2 Передача параметров и возврат значений в предикат.

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

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

Пример 3.4

predicates

like(symbol, symbol).

clauses

like(tom, july).

like(bill, mary).

goal

like(bill, X).

Первый параметр запроса является входным, т.к. имеет значение, равное “bill”, второй параметр – X – свободная переменная, значение которой необходимо уточнить.

В процессе поиска Пролог выдаст сообщение X = mary, при этом переменная X становится связанной и выступает как входной параметр для последующих целей.

goal

like(bill, X).

like(Y, X).

like(X, Z).

В Прологе список входных и выходных аргументов для заданного предиката называется потоком параметров. Для предиката с двумя аргументами возможны 4 варианта потоков параметров:

like(i, i).

like(i, o).

like(o, i).

like(o, o).

i – input

o – output

Правила могут возвращать свободную переменную и результаты вычислений. Запрос типа like(X, Y), имеющий поток параметров (о, о), передает в алгоритм поиска две последовательные задачи унификации. Если в базе фактов есть информация, соответствующая запросу, и указан предикат fail, требующий поиска всех возможных альтернатив для переменных X и Y, то Пролог выдаст множество вариантов:

X = tom, Y = july.

X = bill, Y = mary.

При этом после определения значения переменной X Пролог меняет поток параметров:

like(tom, Y), т.е. (i, o).

На 3-ем шаге происходит откат назад: (о, о).

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

goal

cursor(R, C),

R1 = R+1,

cursor(R1, C).

Это – составная цель с последовательным выводом трех подцелей.

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

Переменная R1 является свободной.

Если же в 1-ом предикате значение переменной R не было найдено, и она осталась свободной переменной, то Пролог выдал бы ошибку и остановил поиск.

После вычисления R1 3-ий предикат вызывается с потоком параметров (i, i).

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

Примечание 1: Предикат not, вызываемый как самостоятельный предикат или как составной элемент правил, не работает, если он вызывается с выходным потоком параметров.

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

init(X) :- X = .,

или в процессе унификации как сопоставление цели некоторым фактам в разделе

init(X) :- write(X).

goal

X = 5, init(X).