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

Пример 3.6. Печатаются «в столбик» квадраты чисел натурального ряда, пока очередной квадрат не превысит число 1000:

печать_квадратов :– N = 1, квадрат(N, R), write(R), nl,

условие(R), !.

квадрат(N, R) :– R is N^2.

квадрат(N, R) :– N1 is N+1, квадрат(N1, R).

условие(R) :– R > 1000.

UDR-метод (метод «user defined repeat»)

Есть некоторое безвозвратное действие(X), вырабатывающее значение выходного параметра X. Это действие должно многократно повторяться, пока значение параметра X не станет удовлетворять некоторому условию. Для того, чтобы действие стало возвратным, используется встроенный предикат repeat/0. Его семан-

тику поясняет следующее «определение»: repeat.

repeat :– repeat.

Подцель repeat записывается перед подцелью действие(X) в правой части правила, реализующего цикл.

Пример 3.7. Печатаются «в столбик» вводимые пользователем слова, пока не будет введено слово finish:

печать_слов :– repeat, read(W), write(W), nl, условие(W). условие(W) :– W == finish.

Подцель repeat при первом вызове срабатывает без всяких условий. После невыполнения условия осуществляется возврат к этой подцели. Согласно 2-му правилу создаётся новая подцель repeat, которая опять срабатывает без каких-либо условий. И т.д.

4. Встроенный предикат определения новой операции

На предыдущей лекции было отмечено, что кроме структур, для записи которых используются скобки, например f(a, b, c), в языке Пролог используются так называемые бесскобочные структуры инфиксного типа, например a f b. Это бинарные (двухаргументные) бесскобочные структуры. К этому же типу можно условно отнести унарные (одноаргументные) бесскобочные структуры: a f и f a.

51

Использование таких структур облегчает чтение многих запи-

сей, например вместо знает(Джон, Мери) и человек(Сократ) бо-

лее естественны и понятны записи: Джон знает Мери и Сократ человек.

Для инфиксной структуры в языке Пролог есть специальное название: операция. Функтор такой структуры называется оператором, аргументы структуры – операндами.

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

Пусть, например, @ и # – операторы каких-то бинарных операций над числами. Как понимать следующую запись:

2 # 3 @ 4 @ 5 # 6?

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

:- op(700, xfy, #). :- op(600, yfx, @).

В директивах применяется встроенный предикат Пролога op/3, все аргументы которого – входные параметры. 1-й аргумент – значение приоритета определяемой операции, 2-й аргумент – спецификация ассоциативности, 3-й аргумент – знак оператора.

Значение приоритета операции важно только по отношению к значениям приоритета других операций: меньше (выше) или больше (ниже).

Значения второго аргумента означают следующее: yfx – левоассоциативная операция,

xfy – правоассоциативная операция, xfx – неассоциативная операция,

yf и fy – допускающие вложенность

(например: not not true),

xf и fx – не допускающие вложенности

(например: Джон человек человек).

Таким образом, в выражении 2 # 3 @ 4 @ 5 # 6 операции применяются в следующем порядке: ( 2 # ((( 3 @ 4 ) @ 5 ) # 6)).

52

На следующей лекции будут рассмотрены ещё несколько типов встроенных предикатов, а также популярные в Прологе рекурсивные методы программирования. Для более детального знакомства с этими вопросами автор рекомендует книги Дж. Стобо [5] и Дж. Малпаса [6].

53

Лекция 4

Основы программирования на Прологе (продолжение)

В данной лекции, в дополнение к тому, что рассматривалось в предыдущей лекции, представлены ещё две категории встроенных предикатов: 1) для преобразования структур данных и 2) для про-

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

метод исходящей рекурсии.

1. Встроенные предикаты преобразования структур

Рассмотрим только четыре из множества таких предикатов.

Предикат name/2.

Данный предикат преобразует атомоподобный терм (атом, число или строку) в список кодов символов, из которых этот терм состоит. Или наоборот, список кодов – в атомоподобный терм. Например:

Предикат functor/3.

Данный предикат анализирует структуру произвольного вида (1-й аргумент): определяет её имя (2-й аргумент) и её арность (3-й аргумент). Или наоборот – синтезирует структуру произвольного вида (1-й аргумент) по известному имени (2-й аргумент) и арности (3-й аргумент). Например:

54

 Предикат 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