Программирование второго порядка
Программирование на Прологе расширяется введением методов, отсутствующих в модели логического программирования. Эти методы основаны на свойствах языка, выходящих за рамки логики первого порядка. Они названы методами второго порядка, поскольку речь здесь идет о множествах и их свойствах, а не об отдельных элементах. Кроме того, применения ламбда-выражений и предикатных переменных позволяют рассматривать функции и отношения как “первоклассные” объекты данных.
findall(+Var, +Goal, -Bag)
Создает список всех конкретизаций переменной Var, полученных при бэктрекинге при выполнении цели Goal, и унифицирует результат с Bag. Bag - пустой список, когда Goal не имеет решения.
?- findall(X,(member(X,[1,2,3,4,5]),0 is X mod 2),L).
X = G1564
L = [2,4]
Yes
Логика первого порядка позволяет проводить квантификацию по отдельным элементам. Логика второго порядка, кроме того, позволяет проводить квантификацию по предикатам. Включение такого расширения в логическое программирование влечет за собой использование правил с целями, предикатные имена которых являются переменными. Имена предикатов допускают обработку и модификацию.
apply(+Term, +List)
Присоединяет элементы списка List к аргументам терма Term и вызывает полученный терм в качестве цели. Например, `apply(plus(1),[2, X])' вызывает `plus(1, 2, X)'.
?- apply(plus,[1,2,X]).
X = 3 ;
No
?- apply(is,[X,4*6*(3+2)]).
X = 120
Yes
?- apply(=,[X,a*6*(x+2)]).
X = a * 6 * (x + 2)
Yes
?- apply(=(X),[a*6*(x+2)]).
X = a * 6 * (x + 2)
Yes
?- apply(append,[[1,2,3],[6,7,8],X]).
X = [1,2,3,6,7,8]
Yes
checklist(+Pred, +List)
Проверяет все ли элементы списка List удовлетворяют предикату Pred.
?- checklist(number,[1,4,8.9,5/7]).
No
?- checklist(number,[1,4,8.9]).
Yes
?- [user].
| p(2).
| p(3).
| p(5).
| p(7).
| user compiled, 52.34 sec, 388 bytes.
Yes
?- checklist(p,[2,5,2,7]).
Yes
?- checklist(p,[2,5,2,1]).
No
Этой ужасной минуты я не забуду никогда в жизни! – сказал Король.
Забудешь – заметила Королева, - если не запишешь в записную книжку.
Льюис Кэрролл. Алиса в Зазеркалье
7.5. Запоминающие функции
Запоминающие функции сохраняют промежуточные результаты с целью их использования в дальнейших вычислениях. Запоминание промежуточных результатов в чистом Прологе невозможно, поэтому реализация запоминающих функций основана на побочных эффектах.
Исходной запоминающей функцией является предикат lemma(Goal). Операционное понимание состоит в следующем: предпринимается попытка доказать цель Goal, и если попытка удалась, результат доказательства сохраняется в виде леммы. Отношение задается следующим образом:
lemma(P) :- P, asserta((P :- !)).
Следующая попытка доказать цель P приведет к применению нового правила, что позволяет избежать ненужного повторения вычислений. Отсечение введено для того, чтобы воспрепятствовать повторному рассмотрению всей программы. Применение отсечения обосновано лишь в тех случаях, когда цель P имеет не более одного решения.
Использование лемм демонстрируем на примере программы, вычисляющей функцию Аккермана:
f(0,n) = n+1
f(m,0) = f(m-1,1) если m>0
f(m,n) = f(m-1,f(m,n-1)) если m,n>0
Факт do будем использовать в качестве глобального счетчика
для подсчета вызовов функции ackerman, предикат без аргументов inc увеличивает значение счетчика на 1.
ackerman(0,N,N1):-
inc,
N1 is N+1.
ackerman(M,0,Val):-
M>0,
inc,
M1 is M-1,
ackerman(M1,1,Val).
ackerman(M,N,Val):-
M>0,N>0,
inc,
N1 is N-1,
ackerman(M,N1,Val1),
M1 is M-1,
ackerman(M1,Val1,Val).
inc:-
do(X),
X1 is X+1,
retract(do(_)),
assert(do(X1)).
do(0).
?- ackerman(3,2,X),do(Y).
X = 29
Y = 541
Yes
Теперь приведем вариант с запоминающей функцией.
ackerman(0,N,N1):-
inc,
N1 is N+1.
ackerman(M,0,Val):-
M>0,
inc,
M1 is M-1,
lemma(ackerman(M1,1,Val)).
ackerman(M,N,Val):-
M>0,N>0,
inc,
N1 is N-1,
lemma(ackerman(M,N1,Val1)),
M1 is M-1,
lemma(ackerman(M1,Val1,Val)).
lemma(P):-
P,
asserta((P:-!)).
do(0).
?- ackerman(3,2,X),do(Y).
X = 29
Y = 73
Yes
8. МОДИФИКАЦИЯ СИНТАКСИСА (ОПЕРАТОРНАЯ ЗАПИСЬ)
Прологовские операторы суть имена функций и/или предикатов (унарных и/или бинарных), записанных до, после или между аргументами, им свойственны приоритет или ассоциативность:
?- a+b+c = X+Y.
X = a + b
Y = c
Yes
?- a+b*c = X+Y.
X = a
Y = b * c
Yes
?- -a+b+c = X+Y.
X = -a + b
Y = c
Yes
В данных примерах встроенными операторами являются предикат = и функторы +,- и *, но программист может ввести собственные операторы.
Атрибутика оператора:
* предшествование, выраженное натуральным числом (от 0 до 1200): чем больше предшествование, тем меньше приоритет;
* позиция - инфиксная, префиксная или постфиксная;
* ассоциативность.
Предшествование выражают числом, а позицию и ассоциативность - одним из следующих способов:
* префиксность оператора (точнее, префиксная запись оператора): fx или fy;
* постфиксность оператора: xf или yf;
* инфиксность оператора: xfx,xfy,yfx или yfy.
Здесь f - оператор, x и y - операнды:
* запись yfx означает левую ассоциативность
a f b f c f d º ((a f b) f c) f d,
+ и * обладают левой ассоциативностью;
* запись xfy означает правую ассоциативность
a f b f c º a f(b f c),
^ обладает правой ассоциативностью;
* запись x f x говорит, что оператор не обладает ассоциативностью; например, mod, поэтому X is 120 mod 50 mod 2 - синтаксическая ошибка.
Предшествование терма
Если терм заключен в скобки или не является составным, то его предшествование равно 0.
Предшествование структурного терма равно предшествованию его главного функтора.
* Операнд y означает, что “предшествование этого операнда не больше, чем предшествование оператора”.
* Операнд x означает, что “предшествование этого операнда строго меньше, чем предшествование оператора”.
Одноместный минус “-” описан как fx, поэтому --x - синтаксически неправильная запись. С другой стороны, not описан как fy, поэтому not not x - правильно.
Предикат op/3 служит для определения новых операторов и используется как директива компилятору в загружаемой программе:
:- op(+Предшествование,+Тип,+Имя)
В качестве имени может использоваться атом или список атомов, в этом случае оператор именуется различными эквивалентными именами. Предшествование, равное 0, удаляет уже сушествующую декларацию.
Наиболее важный критерий для определения оператора - это удобство чтения программы.
Пример:
:- op(750,xfx,’знает’).
Теперь факты 'знает' можно представлять в программе в инфиксной форме:
‘джейн’ ‘знает’ ‘бетти’.
‘сюзан’ ‘знает’ ‘мэри’.
?- X ‘знает’ ‘мэри’.
X=‘сюзан’
Yes
?- X=and(a,b),op(500,yfx,and).
X = a and b
Yes
?-Y=fact(a),op(700,xf,fact).
Y = a fact
Yes
Имена функций and и fact стали операторами: первый из них - бинарным, второй - унарным постфиксным. Последний раз напоминаем, что речь идет лишь о синтаксисе.
Ни с одним оператором при определении не связывается каких-либо действий над данными.
Некоторые из встроенных операторов показаны в таблице. Все эти операторы можно переопределить.
1200 xfx -->, :-
1200 fx :-, ?-
1150 fx dynamic, multifile, discontiguous
1100 xfy ;, |
1050 xfy ->
1000 xfy ,
954 xfy \\
900 fy \+, not
700 xfx <, =, =.., =@=, =:=, =<, ==, =\=, >,
>=, @<, @=<, @>, @>=, \=, \==, is
600 xfy :
500 yfx +, -, /\, \/, xor
500 fx +, -, ?, \
400 yfx *, /, //, <<, >>
300 xfx mod
200 xfy ^
Первым результатом от преподавания методологии [программирования] – а не распространения знаний – является увеличение способностей уже способных, тем самым увеличивается разброс интеллектуальных возможностей.
Из лекции лауреата премии Тьюринга 1972 г. Э. Дейкстры
