Декларативное программирование

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]

© 2003 И.А. Дехтяренко

6.5. Расширения Пролога

Со времени возникновения Пролога было предложено множество идей по его усовершенствованию. Некоторые из них направлены на то, чтобы сделать его более пригодным для промышленной разработки больших проектов. В этой области Прологу не хватает средств структурирования программ и статической проверки типов. И наоборот, такие средства, как динамическая модификация программ или оператор отсечения оказываются слишком опасными. Кроме того, возможность чудесным образом обращать направленность программ оказывается не столь уж важной - как правило, применяются тщательно разработанные и эффективные алгоритмы. Другая область, в которой Пролог себя хорошо зарекомендовал - исследовательское программирование. Здесь важна максимальная гибкость, возможность быстро написать прототип системы и быстро его изменять. Часто алгоритмы решения задач неизвестны, да и сами задачи постоянно уточняются. Требования этих двух сообществ программистов часто противоречивы, но поскольку вторая группа более многочисленна среди пользователей Пролога, именно ее интересы соблюдаются в первую очередь. До недавнего времени подобным образом обстояло дело и в мире функционального программирования, где доминировал Лисп. Ситуация изменилась с выходом функциональных языков из стен лабораторий в область промышленного программирования. Возможно, такие же изменения произойдут и в логическом программировании. В любом случае потребность уменьшить разрыв между процедурной и декларативной семантикой Пролога ощущается уже давно.

Отложенные вычисления

Техника отложенных или ленивых вычислений давно стала обычной в функциональном программировании. Вспомните, как мы применяли ее для организации потоков. Подобный механизм был предложен и для Пролога. Встроенный предикат freeze(X,Goal)¹ подобенен call(Goal), но выполнение цели откладывается ("замораживается") до тех пор, пока   переменная X не получит значение. Это ослабляет строгое правило вычислений слева направо, принятое в Прологе, и дает возможность организовывать выполнение процедур как сопрограмм.

Вспомним задачу о ферзях. Наша первая программа перебирала все перестановки и проверяла каждую из них на предмет соответствия ограничениям.

queens(N,Qs) :-
    range(1,N,Ns),
    length(Qs, N),
    selects(Qs,Ns),
    safe(Qs).

safe([]).
safe([Q|Qs]) :-  noattack(Q,Qs,1), safe(Qs).

noattack(X,[Q|Qs],D) :-
   abs(X-Q) =\= D,
   D1 is D+1, noattack(X,Qs,D1).
noattack(_,[],_).

Чтобы улучшить производительность, мы включили проверку в процедуру генерации. Недостаток этого решения - нарушение модульности программы. Мы объединили две логически раздельные процедуры только из соображений эффективности. Использование отложенных вычислений позволит повысить производительность без ухудшения структуры программы.

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

queens(N,Qs) :-
    range(1,N,Ns),
    length(Qs, N),
    safe(Qs),
    selects(Qs,Ns).

Это выглядит подозрительно, и действительно программа выдаст ошибку при попытке выполнить арифметические вычисления со свободными переменными. Но мы добавим задержки в процедуру проверки.

noattack(X,[Q|Qs],D) :- 
   freeze(X,freeze(Q,abs(X-Q) =\= D)),
   D1 is D+1, noattack(X,Qs,D1).
noattack(_,[],_).

Теперь вычисления "abs(X-Q) =\= D" будут откладываться до тех пор , пока переменные X и Q не получат значений. После завершения safe образуется цепочка задержек (триггеров), которые начнут запускаться при выполнении selects и будут отсекать неподходящие значения.

Некоторые версии Пролога имеют более гибкие средства организации  задержек. Например when(Cond,Goal) в SICStus или в Ciao позволяет отложить выполнение до тех пор, пока не будет выполнено условие Cond. Это условие составляется из элементарных условий nonvar(X)и ground(X)и логических связок.

Другой подход был применен в языках MU-Prolog, NU-Prolog и Goedel. Там описание задержкек входит в определение предиката. Например, процедура noattack отличалась бы от оригинальной версии только дополнителным определением задержек.

delay noattack(X,[Q|_],_) until nonvar(X),nonvar(Q).
noattack(X,[Q|Qs],D) :- 
   abs(X-Q) =\= D,
   D1 is D+1, noattack(X,Qs,D1).
noattack(_,[],_).

Директива задержки delay² указывает на то, что все вызовы noattack должны откладываться, пока переменные X и Q не получат значений.

В этих языках многие встоенные предикаты ожидают пока их аргументы не получат значения. Например, выполнение S is X+Y , в случае если X или Y еще не опредены не приведет к ошибке, а будет отложено. В результате стиль программирования изменяется по сравнению с обычным Прологом - важность логической составляющей программ возрастает, а управление становится все более неявным. Дальнейшее развитие этих идей ведет к языкам параллельного логического программирования, в которых разные цели предложения или разные предложения одной процедуры могут выполняться параллельно, а переменные используются для синхронизации процессов.

Табулирование

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

В качестве примера вспомним древесно-рекурсивную процедуру вычисления чисел Фибоначчи. На Прологе она будет выглядеть так:

fib(1, 1):- !.
fib(0, 1):- !.
fib(N, F):- 
    N1 is N-1, fib(N1,F1),
    N2 is N-2, fib(N2,F2),
    F is F1+F2.

Эту процедуру можно рассматривать как сокращенную запись отношения.

fib(0, 1).
fib(1, 1).
fib(2, 2).
fib(3, 3).
fib(4, 5).
fib(5, 8).
...

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

:-dynamic(tfib/2).
tfib(0, 1).
tfib(1, 1).

fib(N, F) :- tfib(N, F),!.
fib(N, F) :-
    N1 is N-1, fib(N1,F1), 
    N2 is N-2, fib(N2,F2), 
    F is F1+F2, asserta(tfib(N,F)).

Обратите внимание, что мы не просто экономим время при повторных вычислениях того же значения. Каждый вызов fib(N2,F2) использует значение уже вычисленное при вызове fib(N1,F1) и таким образом экспоненциальный процесс превращается в линейный.

Но техника динамического манипулирования базой данных чревата ошибками и противоречит декларативному духу логического программирования. Появившаяся в начале 1990-х система XSB предоставляет встроенную поддержку табулирования (сейчас подобные возможности имеет и B-Prolog). В такой системе мы просто определим fib как табулированное отношение.

:- table fib/2.
fib(0, 1).
fib(1, 1).
fib(N, F):- 
    N1 is N-1, fib(N1,F1),
    N2 is N-2, fib(N2,F2),
    F is F1+F2.

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

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

:-table connected/2.
connected(A,A).
connected(A,B) :- arc(A,C), connected(C,B).

Более того, вполне легальным становится и такое леворекурсивное определение

:-table connected/2.
connected(A,B) :- connected(A,C), arc(C,B).
connected(A,A).

И даже такое

:-table connected/2.
connected(A,B) :- connected(A,C), connected(C,B).
connected(A,A).
connected(A,B) :- arc(A,B).

Упражнение.

Нормальному программисту эти леворекурсивные определения даже не пришли бы в голову. Тем не менее, они оказываются более эффективными для некоторых графов. Найдите примеры таких графов.

Очевидно, далеко не все процедуры имеет смысл табулировать. Во-первых память надо все-таки экономить. Во-вторых табулирование может и ухудшить эффективность процедур (рассмотрите выполнение табулированной версии append). При создании сложных программ определить какие предикаты нуждаются в табулировании - задача утомительная. Система XSB содержит одно средство, облегчающее жизнь программисту. Обнаружив директиву auto_table, компилятор анализирует программу и автоматически табулирует некоторое количество предикатов с тем, чтобы избежать зацикливания программы. Конечно, чудес не бывает и в общем случае задача определения завершаемости программы неразрешима, но для определенного класса программ можно вывести что любой запрос завершится за конечное время. Программы, для которых гарантируется завершение, должны оперировать термами ограниченной глубины вложенности. Важное подмножество этого класса - так называемые Дейталог-программы, оперирующие только простыми термами. А это означает, что можно писать сложные запросы к реляционным базам данных, не опасаясь зацикливания.

С табулированием Пролог становится более дружественным к новичкам, поскольку избавляет их от необходимости учитывать тонкости выполнения программ и заботиться о порядке записи правил и целей. Но табулирование полезно и профессиональным программистам, позволяя создавать более логичные программы. Когда мы писали синтаксический анализатор арифметических выражений, мы вынуждены были изменить правила грамматики, добавив в нее два новых нетерминала "слагаемые" и "множители". Сделали мы это только для того, чтобы избежать левосторонней рекурсии. Но с табулированием у нас уже нет такой необходимости и можно записать правила грамматики в более естественном виде.

:-table expr/3.
:-table term/3.

expr(E)   --> term(E).
expr(E+T) --> expr(E),"+",term(T).
expr(E-T) --> expr(E),"-",term(T).

term(T)   --> factor(T).
term(T*F) --> term(T),"*",factor(F).
term(T/F) --> term(T),"/",factor(F).

Синтаксис высшего порядка.

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

map(P,[],[]).
map(P,[X|Xs],[Y|Ys]) :- call(P,X,Y), map(P,Xs,Ys).

Гораздо лучше бы выглядело, если бы могли записать его явно подчеркивая особую роль аргумента P.

map(P)([],[]).
map(P)([X|Xs],[Y|Ys]) :- P(X,Y), map(P)(Xs,Ys).

Очень небольшое  расширение Пролога под названием HiLog позволяет нам сделать это. Разница между Прологом и HiLog состоит в том, что в последнем можно использовать переменные и сложные термы на месте функтора.

Синтаксис cоставного терма в Прологе

атом(терм₁,терм₂,...терм_n),

а в HiLog

терм₀(терм₁,терм₂,...терм_n).

В вычислительном отношении такие термы эквивалентны термам Пролога. Однако, они поощряют мышление в терминах высшего порядка, таких как параметризованние предикаы или предикатные переменные. Например, мы можем естественно выразить идею рефлексивно-транзитивного замыкания отношения.

closure(P)(A,A).
closure(P)(A,B) :- P(A,C), closure(P)(C,B).

Ранние реализации HiLog представляли собой препроцессор, преобразующий HiLog программу в обычную Пролог программу. Таким образом, его можно было использовать с любой стандартной Пролог-системой.  К сожалению, такой подход приводит к существенной потере эффективности. XSB выполняет  компиляцию HiLog предложений так что разница в скорости, например между двумя определениями map, становится незначительной.

Следующим шагом в этом направлении было бы введение непоименованных абстракций, подобных лямбда-выражениям. И действительно,  в Mercury можно определять предикаты прямо по месту использования.

map((pred(X,Y) :- Y is X*X),List1,List2).

Лямбда-Пролог может даже унифицировать лямбда-термы. Впрочем, эта возможность имеет довольно специфическую область применения.

Декларации видов.

Практически все упомянутые расширения направлены на повышение гибкости языка. К сожалению, за эту гибкость как правило приходится расплачиваться потерей эффективности. Но для промышленного программирования вопросы эффективности немаловажны. И хотя в технике компиляции логических программ, достигнуты определенные успехи, даже лучшие реализации Пролога сильно уступают императивным и функциональным языкам. Впрочем, это утверждение нуждается в уточнении - для задач, связанных со сложным перебором создание эффективного алгоритма может оказаться слишком трудоемким. Но если переписать, скажем, функциональную процедуру на Прологе, она как правило будет выполнятся более медленно. Дело в том, что Пролог "не знает" что это функциональная процедура и автоматически "обобщает" ее так, что мы можем вызывать ее с различными входными и выходными аргументами (вспомните хотя бы разные способы вызова append). Но если процедура предназначена для ограниченного использования, эта общность приводет к бесполезной потере эффективности. Лучшие копиляторы Пролога большую часть времени тратят на глобальный анализ программы в попытке выделить такие фрагменты, которые допускют более эффективную копиляцию. Но, если мы намерены использовать процедуру только определенным образом, мы можем прямо сообщить об этом компилятору. Для этого в Пролог были введены директивы - декларации видов. Правда, в большинстве реализаций они попросту игнорируются и выступают в качестве комментариев. Серьезно относится к декларация видов Turbo Prolog и его потомки (PDC Prolog и Visual Prolog) а также Mercury. В последнем объявление

:- mode append(in, in, out) is det.

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

:- mode append(out, out, in) is nondet.

Теперь компилятор сгенерирует свой код для двух случаев использования процедуры. Но можно учесть еще два варианта использования.

:- mode append(in, out, in) is semidet.
:- mode append(out, in, in) is semidet.

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

Изощренная система определений детерменированности процедур в Mercury позволила сделать радикальный шаг - устранить из языка оператор отсечения. Все полезные применения отсечений можно выразить либо их структуированными вариантами, либо соответствующими декларациями.

Декларативный ввод-вывод.

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

Но у нас остается проблема в декларативности ввода-вывода в целом. Рассмотрим следующий фрагмент программы

read(F,X),read(F,Y).

Два вызова процедуры read с одним и тем же аргументом F возвращают разные результаты. Это именно то, что мы ожидаем от read, но с логической точки зрения очень некрасиво. Программы теряют свойство прозрачности ссылок - важное достоинство декларативного программирования. Мы можем вернуть им это свойство, если переопределим процедуру read так, чтобы она возращала дополнительный результат - новое состояние файла, который и передается следующему вызову read.

read(F,X,F1),read(F1,Y,F2).

Новая версия read имеет декларативный смысл и вполне заслуживает звание предиката. Подобным образом реализован ввод-вывод в Mercury. Только вместо состояния файла используются состояния внешнего мира. Каждая процедура, выполняющая ввод или вывод имеет два дополнительных параметра: состояния "до" и "после". Главная процедура программы (main) также имеет два параметра, определяющие состояния среды до и после выполнения программы. Таким образом программу можно воспринимать как отношение между двумя состояниями. Например

main(In, Out) :-
   io:write_string("Введите X,Y", In, IO1),
   io:read_int(X,IO1,IO2),
   io:read_int(Y,IO2,IO3),
   S = X + Y,
   io:write_string("X+Y=", IO3,IO4),
   io:write_int(S,IO4,IO5),
   io:nl(IO5,Out).

Но что произойдет, если передать процедуре ввода или вывода  уже использованное состояние? По логике вещей она должна еще раз выполнить ввод(вывод). Хотя подобное поведение не лишено смысла, его реализация была бы слишком накладной. Поэтому повторное использованное состояний ввода-вывода не допускается. А чтобы компилятор мог следить за этим, придуманы специальные "уникальные" виды. Типичная декларация вида для процедуры, выполняющей ввод или вывод вылядит примерно так:

:- mode write_string(in,di,uo) is det.

Вид di (destructive input) означает, что данный объект больше не может использоваться в программе, а uo (unique output) указывает что возвращается уникальный объект, который можно использовать только однажды.

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

main -->
   io:write_string("Введите X,Y"),
   io:read_int(X),
   io:read_int(Y),
   {S = X + Y},
   io:write_string("X+Y="),
   io:write_int(S),
   io:nl.

Программирование в ограничениях

Многие практически важные задачи представляют собой задачи на удовлетворение ограничениям. Для их решения придумано множество алгоритмов, начиная с классического метода Гаусса и кончая сложными методами применяемыми в системах доказательства теорем и в системах символьных вычислений. Возникло даже целое направление в программировании - программирование в ограничениях (constraint programming). Идея его чрезвычайно проста - прогаммист определяет некоторое множество переменных и описывает ограничения, которым они должны удовлетворять, а система находит подходящие значения.

Впервые ограничения были применены в графическом пакете Sketchpad в начале 1960-х. В 1970 появился первый язык программирования, который поддерживал эту парадигму -УТОПИСТ (Универсальные Текстовые ОПИСания Терминов) Энна Тыугу. Но систематическое использование ограничений в программировании началось только в 1980-х. С тех пор они успешно применялись во многих областях, таких как компьютерная графика, синтаксический анализ естественных языков, системы управления базами данных, исследование операций, молекулярная биология, электротехника, проектирование интегральных микросхем и т.д. В настоящее время многие крупные компании проявляют интерес к программированию в ограничениях, а ACM признала его одним из стратегических направлений исследований.

Программирование в ограничениях тесно связано с традиционным логическим программированием, в недрах которого оно и сформировалось. Большинство систем программирования в ограничениях представляют собой обычный интерпретатор Пролога со встроенным механизмом для решения определенного класса задач удовлетворения ограничениям. Программирование в таких системах назsвают логическим программированием в ограничениях (Constraint Logic Programming или CLP³), а большинство языков или библиотек называются CLP(X), где X указывает на класс решаемых задач.

Например, CLP(B) означает возможность решать уравнения с булевыми переменными. CLP(Q) - уравнения в рациональных числах, а CLP(R) - в вещественных. Причем последние могут решаться приближенно CLP(R_float), а могут с применением интервальной арифметики CLP(R_int). Но наиболее популярны решатели задач на конечных доменах CLP(FD), то есть на конечных множествах целых чисел. Предпринимались попытки интегрировать ограничения и в объектно-ориентированные, языки. Но успехи на этом пути пока скромные, поскольку декларативные по своей сути ограничения плохо согласуются с императивными особенностями этих языков.

Механизм унификации Пролога также можно рассматривать как средство решения задач в ограничениях, а именно - как решатель уравнений на конечных деревьях - термах Пролога. Например, после выполнения X=f(_) переменная X становится в некотором смысле ограниченной - она уже обозначает не любой терм, а только такой, который содержит f/1 в качестве основного функтора. В системе с поддержкой CLP(FD), этот же принцип распространяется на операции с целыми числами. Рассмотрим несколько примеров работы с B-Prolog.

?- X#>1.
X#>1?
yes

В результате выполнения предиката #> переменная X получает особый статус. Она становится ограниченной и может принимать целые значения большие 1 вплоть до некоторого maxint, установленного по умолчанию.

?- X#>1, X#<3.
X = 2?
yes

Второй предикат #< еще раз ограничивает возможные значения для X. Теперь это множество целых чисел, больших 1 и меньших 3. Но существует только одно такое число. Оно и выдается в качестве результата.

?- X #>= 1, Y #>= 1, X+Y #= 1.
no

?- X #>= 1, Y #>= 1, X+Y #= 2.
X = 1
Y = 1?
yes

?-X#>=1,Y#>=1,X+Y#=3.
X#>=1,Y#>=1,X+Y#=3?
The following goals are still being suspended:
X in C-Y(_81070301:[1,2],3,_81070389:[1,2],$domain_delta(_81070389:[1,2],_10704d4))
X in C-Y(_81070389:[1,2],3,_81070301:[1,2],$domain_delta(_81070301:[1,2],_1070470))
yes

В первом случае система не имеет решений, во втором существует единственное решение (X= 1, Y= 1). Самое интересное происходит в третьем случае. Система ограничений непротиворечива, но указанных ограничений недостаточно для того, чтобы однозначно найти ответ и придется прибегнуть к перебору. Для этого нам потребуется предикат indomain(X), который возвращает все значения из области определения ограниченной переменной.

?- X#>=1,indomain(X).
X = 1?;
X = 2?;
X = 3?;
X = 4?;
X = 5?
yes

Поскольку X в данном случае ограничена "слишком слабо", indomain может выдать очень много значений. Но в предыдущем примере имеется только два варианта ответа.

?- X#>=1, Y#>=1, X+Y#=3, indomain(X).
X = 1
Y = 2?;
X = 2
Y = 1?;
no

Заметим, что достаточно оказалось перебора значений только одной переменной. В общем случае это, конечно, не так. Чтобы упростить организацию перебора, существует встроенный предикат labeling, перебирающий значения списка переменных. Его определение эквивалентно следующему.

labeling([]).
labeling([V|Vs]):- indomain(V),labeling(Vs).

В нашем примере можно применить его следующим образом.

?- X#>=1, Y#>=1, X+Y#=3, labeling([X,Y]).
X = 1
Y = 2?;
X = 2
Y = 1?;
no

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

domain(X,1,100)

ограничивает значения X диапазоном от 1 до 100. То же самое можно сделать посредством

X in 1..100.

Но предикат in допускает и вызов в виде

X in [1,3,5,8]

что ограничивает допустимые значения X указанными числами. Оба предиката позволяют указать домен сразу для целого списка переменных. В результате выполнения

domain([X,Y,Z],1,20).

переменные X, Y и Z будут ограничены диапазоном от 1 до 20.

Наиболее важный вид ограничений - арифметические. Они имеют вид "E₁ r E₂", где E₁ и E₂ - арифметические выражения построенные из переменных, целых чисел и четырех арифметических операций, а r - один из следующих символов.
#=, #\=, #> ,#>=, #<, #=<

Как видно, это обычные знаки арифметических отношений, но имеющие префикс #, указывающий на их особый статус. Арифметические ограничения можно комбинировать с помощью  логических связок (#\, #/\, #\/, #=> и #<=>).

Кроме арифметических, полезными оказываются и другие виды ограничений, такие как:

all_different(L)

Все переменные из списка L имеют разные значения. Например, all_different([X,Y,Z])  эквивалентно совокупности ограничений X#\=Y,X#\=Z,Y#\=Z.

X notin L

X не содержится в списке L.

element(N,L,X)

X является элементом списка L с номером N.

atmost(N,L,X)

Список L содержит не более N вхождений X.

Стандарт на запись ограничений пока не выработан. Например в GNU-Prolog арифметические ограничения записываются так же, а вот предикат для объявления домена называется fd_domain. Аналогично вместо all_different используется fd_all_different, вместо labeling - fd_labeling и т.д. Предиката in нет, но fd_domain можно использовать в виде

fd_domain(X,[1,3,5,8])

добиваясь того же результата.

Типичная программа CLP(FD) состоит из трех частей:

1. объявления переменных и их доменов
2. определения ограничений
3. вызова labeling или аналогичного предиката выполняющего означивание переменных.

Рассмотрим две знакомые задачи на удовлетворение ограничений.

Решение задачи  "SEND + MORE = MONEY" совершенно очевидно.

solve([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y]) :-
%1. объявляем домены переменных 
    Vars = [S,E,N,D,M,O,R,Y],
    domain(Vars,0,9),
%2. устанавливаем ограничения
    S#\=0, M#\=0,
    all_different(Vars),
            1000*S+ 100*E+ 10*N+D
    +       1000*M+ 100*O+ 10*R+E
    #=
    10000*M+1000*O+ 100*N+ 10*E+Y,
%3. находим значения переменных
    labeling(Vars).

Оно не сложнее чем простейшее решение, основанное на методе "образовать и проверить". В то же время, эта программа очень эффективна. Она выполняется быстрее любой из тех, что мы рассматривали.

Чтобы решить задачу о ферзях средствами CLP(FD) вспомним формулировку задачи.

Найти набор (y₁,y₂,...,y_N), 1<y_i<N такой, что для всех различных i и j выполняются условия:

1. y_i =/= y_j
2. |y_i - y_j| =/= | i-j |.

Для первого условия у нас уже есть готовый предикат all_different, второе пока обозначим предикатом safe. Тогда можно записать общую схему решения.

queens(N,Ys) :-
    length(Ys, N),
    domain(Ys,1,N),
    all_different(Ys),
    safe(Ys),
    labeling(Ys).

Определение safe легко получается из процедуры проверки этихусловий,заменой"=\=" на "#\=". Но поскольку язык описания ограничений не содержит функции abs, придется обойтись без нее.

safe([Y|Ys]) :- noattack(Y,Ys,1), safe(Ys).
safe([]).

noattack(_,[],_).
noattack(Q,[Y|Ys],D) :-
    Q-D #\= Y,
    Q+D #\= Y,
    D1 is D+1,
    noattack(Q,Ys,D1).

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

Упражнение.

Напишите универсальный решатель криптоарифметических задач на сложение с применением CLP(FD).

¹ Это предикат под названием geler (заморозить) впервые появился в разработанном группой Колмероэ языке Пролог-II.

² Реально ее синтаксис не совпадает ни с одним из указанных языков, но это не существенно.

³ Эта аббревиатура неудобна тем, что совпадает с другой, такжке популярной и означающей Concurent Logic Programming.

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]