Пролог с процедурной точки зрения.

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

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

1) Обращение к некоторой цели на Прологе равносильно вызову процедуры, а порядок высказываний, составляющих цели или правила, соответствует последовательности операторов:

A:- B1, B2, …, Bn.

Procedure A()

begin

call B1

call B2

…

call Bn

end.

2) Рекурсивный вызов цели на Прологе подобен рекурсивной функции в обычных языках.

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

4) В Прологе используются логические переменные, которые соотносятся с некоторыми объектами, а не с ячейками памяти.

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

5) В логическом программировании обработка данных полностью заложена в алгоритме унификации.

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

Predicates

Z

clauses

Z:- nl, love(anna, flowers), write(“Yes”).

Z:- nl, not(love(anna, flowers)), write(“No”).

Z:- nl, write(“Unknown”).

7) Так же, как в операторе выбора CASE процедурных языков, в Прологе можно задавать множество альтернативных определений. Пролог перебирает альтернативы, сопоставляя их запросу, пока не найдет тот вариант, который представляет решение, заданное правило.

Predicates

action(integer)

clauses

action(1):- nl, write(“1”), nl,!.

action(2):- nl, write(“2”), nl,!.

action(N):- nl, N<>1, write(“Unknown”).

goal

write(“Select 1 or 2”),

readint(C),

action(C).

Примечание 1: В предикате action переменная С должна быть связанной (иметь значение, которое определяется в предикате readint). Если бы переменная С была свободной, т.е. ее значение было не определено, то Пролог выдал бы ошибку компиляции.

Примечание 2: Предикат «!» задает отсечение, прекращая поиск других альтернатив, если текущая альтернатива сработала. В данном примере используется «зеленое» отсечение, которое не дает большого выигрыша при поиске, но исключает риск ошибок поиска. Другой вариант – «красное» отсечение, которое меняет логику работы программы.

Например:

action(1):-!, nl, write(“1”).

action(2):-!, nl, write(“2”).

action(N):- nl, write(“Unknown”).

Предикат отсечения соответствует оператору Goto в процедурах языков программирования.

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

Если нужно найти все возможные решения, даже если цель достигнута хотя бы один раз, то используют специальный предикат fail, который ставит очередной запрос в состояние “false” и автоматически инициализирует поиск с возвратом.

9) Организация циклов в программах на Прологе возможна по аналогии с рекурсией или при откате (срабатывает fail). Операторы for, while, repeat отсутствуют.

Пример 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).