Материал: Волченков Логическое программирование язык пролог 2015

 Предикат member/2:

member(H, [H|_]).

member(H, [_|T]) :– member(H, T).

 Предикат append/3:

append([], L, L).

append([H|T1], L, [H|T2]) :– append(T1, L, T2).

 Предикат reverse/2:

reverse([], []).

reverse([H|T], R) :– reverse(T, R1), append(R1, [H], R).

 Предикат sort/2:

sort([], []). % Сортировка «вставкой» sort([H|T], S) :– sort(T, T1), insort(H, T1, S).

insort(X, [], [X]).

insort(X, [H|T], [X, H|T]) :– X @=< H, !.

% @=< – сравнение не чисел, а структур insort(X, [H|T], [H|T1]) :– !, insort(X, T, T1).

3. Встроенные предикаты проверки типов

Часто в программах на Прологе приходится проверять такие, например, условия: «Означена или нет данная переменная»; «Является ли данный терм числом»; «Является ли данный терм неатомоподобным термом – структурой (compound)» и т.п.

Для ответов на указанные вопросы служат встроенные предикаты проверки типов. Приведем спецификацию шести таких предикатов без комментариев.

atom/1, atomic/1, number/1, var/1, nonvar/1, compound/1.

Их назначение очевидно – смысл предикатов следует из их названий.

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

56

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

4. Методы исходящей и входящей рекурсии

Вспомним хорошо известное рекурсивное определение факториала:

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

К примеру, в Паскале:

i:=0; b:=1;

while i <> n do begin i:=i+1;

b:=b*i;

end;

r:=b

Здесь n – входной параметр, r – выходной параметр, значение которого – факториал заданного числа.

На Прологе можно решить эту задачу абсолютно так же, «в стиле операторного программирования»:

factorial(N, N, R, R) :- !. factorial(I, N, B, R) :-

I1 is I + 1,

B1 is B * I1, factorial(I1, N, B1, R).

57

Здесь, как и в программе на Паскале, две переменные (N и R) выступают в роли входного и выходного параметров, а две другие переменные – в роли «счётчика» (I) и в роли «накопителя произведения» (B).

Предикат factorial/4 в качестве второго и четвёртого аргумента имеет входной и выходной параметры, а в качестве первого и третьего аргумента – «счетчик» и «накопитель».

В базовом состоянии рекурсии, когда значения счётчика и входного параметра сравняются, значение накопителя «перебросится» в последний аргумент (первое правило определения).

Отметим отличия программы на Прологе от программы на Паскале:

в Прологе нет оператора присваивания, так как «единожды означившись» переменная в пределах одного утверждения уже не может получить другое значение (конструкция i := i+1 заменяется на конструкцию I1 is I+1 и т.п.);

все утверждения, представляющие программу на Прологе,

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

Теперь о рекурсии. Хотя данная программа имитирует операторный «итерационный» метод, в ней, как и практически в любой программе на Прологе, используется рекурсия. Без рекурсии Пролог просто немыслим!

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

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

В качестве примера применения метода исходящей рекурсии рассмотрим также вычисление факториала:

58

factorial(0, 1) :- !. factorial(N, R) :- N1 is N - 1,

factorial(N1, R1), R is R1 * N.

Еще более характерный пример различия методов входящей и исходящей рекурсии можно продемонстрировать на определениях предиката reverse/2. Два аргумента этого предиката – это исходный и «реверсированный» список (список, у которого первый элемент – это последний элемент исходного списка, второй элемент – предпоследний элемент исходного списка и т.д.).

По методу исходящей рекурсии работает следующее определение:

reverse1([], []). reverse1([H|T], R):-

reverse1(T, T1), append(T1, [H], R).

В этом определении используется предикат append/3, работающий весьма медленно, что делает данное определение нежелательным.

Более эффективно работает другое определение, сделанное по методу входящей рекурсии:

reverse2(L1, L2):- reverse2(L1, [], L2).

reverse2([], L, L). reverse2([H|T], B, R):-

reverse2(T, [H|B], R).

Хотя это определение несколько длиннее предыдущего, работает оно эффективнее, так как в нём уже нет предиката append/3.

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

59

5. Примеры решения задач

Встроенные предикаты арифметики и ввода-вывода

С арифметикой в Прологе не всё обстоит благополучно. Например, в Примере 3.6 лекции 3 (печать квадратов натуральных чисел) используется предикат X is N^2. И вместо целых чисел иногда, по- чему-то, печатаются десятичные числа (22^2 = 483.999999…).

Пришлось заменить возведение в степень умножением:

X is N * N. Но можно решить эту проблему и по другому: ввести округление: Y is N^2, cint(Y, X).

Задача 1. Определить предикат cint/2 – округления произвольного десятичного числа.

Решение:

cint(X, Y) :- Z is sign(X), A is abs(X), I is ip(A), F is fp(A),

F > 0.5, !,

Y is Z * (I+1). cint(X, Y) :- Y is ip(X), !.

Можно ли сократить это определение? Автор предлагает слушателям и читателям подумать над этим вопросом.

Задача 2. Посимвольный ввод. Рассмотрим определение:

vv(W):-get0(X), vv1([X],L,X), name(W,L).

vv1(L, L, 122). % 122 – код символа z vv1(B, L, X):- get0(Y), vv1([Y|B], L, Y).

Рассмотрим вызов и ввод нескольких символов:

| ?- vv(W).

|: tyh875654435566778&^%%$%#$#yz

(В конце нажата клавиша Enter.) Каким будет возвращённое значение переменной W? Как изменить определение vv/1, чтобы посимвольно были напечатаны все введённые символы?

60