Логическое программирование

       

Программирование второго порядка


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

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 г. Э. Дейкстры


Содержание раздела