Costas-Tyros_rus_MS

Глава 10: Как решать это в Прологе

Заголовок этой главы – дань уважению Гельдеру Коэльо (Helder Coelho), первому автору лучшей книги по Прологу из когда либо написанных: [How To Solve It With Prolog]. Эта книга была отпечатана

в Laboratorio Nacional de Engenharia Civil, где Гельдер работал, будучи в Португалии. Позже, Коэльо опубликовал Prolog by Example – «Пролог в примерах» (см. [Coelho/Cotta]), которая тоже хороша, но

не так, как его первая книга.

Книга Коэльо – это коллекция коротких проблем, поставленных и затем решённых великими ма тематиками и компьютерными учёными. Всё это организовано наподобие FAQ1. Поставленные про блемы интересны, а их решения блестящи. Более того, эта книга ещё и очень забавная. Я надеюсь, что скоро мы увидим новое издание, так как она раскрывает историю создателей логического про граммирования, их открытия, их исследования.

Все программы в этой главе будут консольными приложениями. Кроме того, я буду приводить только листинги определения основного класса. Все остальное остаётся за вами. Например, если я дам вам листинг

implement main open core

clauses

classInfo("main", "hello"). clauses

run(): console::init(), stdio::write("Hello, world!\n"). end implement main

goal mainExe::run(main::run).

Вы должны создать консольный проект под названием hello.

10.1.Утилиты

Устное утверждение: найти все элементы списка L. Логическая программа:

implement main open core

class predicates

member:(integer, integer*) nondeterm anyflow. member:(string, string*) nondeterm anyflow. test:(string*) procedure (i). test:(integer*) procedure (i).

clauses

classInfo("main", "utilities").

member(H, [H|_]).

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

test(L) : member(H, L),

stdio::write(H), stdio::nl, fail or succeed().

1 FAQ – Frequently Asked Questions. Вообще то, термин имеет вполне вменяемый перевод («часто задаваемые вопросы», ЧаВо) но в современных текстах почти везде употребляется оригинальное трёхбуквенное сочетание. Я тоже не буду переводить/расшифровывать этот термин.

81

run(): console::init(), L= [2,3,4,5], test(L), S= ["a", "b", "c"], test(S).

end implement main goal

mainExe::run(main::run).

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

есть объявление member/2 для string*, и другое для integer*. То же самое с test/1.

Определение test/1 использует предикат fail для отката, и печатает все решения nondeterm предиката member. Как результат, программа печатает все элементы списка.

Устное утверждение: проверить, является ли U пересечением списков L1 и L2; найти пересече ние списков L1 и L2.

implement main

open core, stdio class predicates

isec:(integer*, integer*, integer*) nondeterm anyFlow. memb:(integer, integer*) nondeterm anyFlow.

tst:(integer*, integer*, integer*, string) procedure(i, i, i, o). findsec:(integer*, integer*, integer*) procedure (i, i, o). length:(integer*, integer) procedure (i, o).

clauses

classInfo("main", "intersection").

memb(H, [H1|T]) : H=H1; memb(H, T).

isec(L1, L2, [H|U]) : memb(H, L1), memb(H, L2), !, isec(L1, L2, U).

isec(_, _, []).

length([], 0) : !.

length([_|R], L+1) : length(R, L).

tst(L1, L2, U, R) : findsec(L1, L2, S), length(U, LU), length(S, LS), LU= LS, isec(L1, L2, U), !, R= "yes"; R= "no".

findsec([H|T], L, [H|U]) : memb(H, L), !, findsec(T, L, U). findsec([_|T], L, U) : findsec(T, L, U), !.

findsec(_L1, _L2, []).

run(): console::init(), L1= [3, 6, 4, 5], L2= [4, 5, 6], U1= [4, 6, 5], U2= [4, 3],

tst(L1, L2, U2, Resp2), tst(L1, L2, U1, Resp1), write(Resp1, ", ", Resp2), nl,

findsec(L1, L2, I), write(I), nl. end implement main

goal mainExe::run(main::run).

82

Устное утверждение: определить отношение append/3 между тремя списками, которое имеет место, если последний список является результатом присоединения второго списка к первому.

implement main open core

class predicates

app:(Elem* L1, Elem* L2, Elem* L3) nondeterm anyFlow. test1:(string*) procedure (i).

test2:(integer*, integer*) procedure (i, i). clauses

classInfo("main", "append"). app([], L, L).

app([H|T], L, [H|U]) : app(T, L, U). test1(U) : app(L1, L2, U),

stdio::write(L1, " ++ ", L2, "= ", U), stdio::nl, fail. test1(_).

test2(L1, L2) : app(L1, L2, U),

stdio::write(L1, " ++ ", L2, ": ", U), stdio::nl, fail. test2(_, _).

clauses

run(): console::init(),

test1(["a", "b", "c", "d"]), stdio::nl, test2([1, 2, 3], [4, 5, 6]).

end implement main goal

mainExe::run(main::run).

Эта задача – фаворит всех времён. Если вы запустите программу, test1/1 найдёт и распечатает все способы разделения списка ["a", "b", "c", "d"]. С другой стороны, test2/2 соединяет два списка. Оба предиката используют app/3, который производит две операции: конкатенацию и разделение списков.

Устное утверждение: написать программу, инвертирующую список [разворачивающую порядок сле дования его элементов в обратную сторону – прим. пер.].

/******************************* Project Name: reverse

UI Strategy: console

********************************/

implement main open core

class predicates

rev:(integer*, integer*) procedure (i, o). rev1:(integer*, integer*, integer*) procedure (i, i, o).

clauses

classInfo("main", "reverse").

rev1([], L, L) : !.

rev1([H|T], L1, L) : rev1(T, [H|L1], L).

rev(L, R) : rev1(L, [], R).

83

run(): console::init(), L= [1, 2, 3, 4, 5],

rev(L, R), stdio::write("Reverse of", L, "= ", R), stdio::nl.

end implement main goal

mainExe::run(main::run).

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

rev([1, 2, 3], R)

Тогда механизм вывода попытается приравнять rev([1, 2, 3], R) к голове одного из находя щихся в программе предложений Хорна. В данном случае, он преуспеет, если сделает L равным [1, 2, 3] в предложении

rev(L, R) : rev1(L, [], R)

Но, если L=[1, 2, 3], это предложение превращается в

rev([1,2,3], R) : rev1([1,2,3], [], R)

Этот процесс сопоставления цели и головы правила называется unification – унификацией, и можно сказать, что rev([1,2,3], R) унифицируется с

rev(L, R) : rev1(L, [], R), для L=[1,2,3]

производя rev1(L, [], R), который равен rev1([1,2,3], [], R), так как L=[1,2,3]. Резуль тат унификации является хвостом Хорнова предложения, потому что вы должны доказать хвост, для того, чтобы доказать заголовок. Например, рассмотрим следующее Хорново предложение в записи по русски:

X дедушка Y если X отец Z и Z отец Y.

Если вы хотите доказать, что X дедушка Y, вы должны доказать, что Y отец Z, и Z отец Y. Короче, нужно доказать хвост, чтобы доказать голову предложения Хорна. Вся эта долгая дискуссия может быть суммирована так:

•rev([1,2,3], R) унифицируется с

rev(L, R) : rev1(L, [], R), для L=[1,2,3] возвращая rev1([1,2,3], [], R).

•rev1([1,2,3], [ ], R) унифицируется с

rev1([H|T],L1,L) : rev1(T,[H|L1],L)/ H=1, L1=[], T=[2,3] производя rev1([2, 3], [1], L).

•rev1([2, 3], [1], L) унифицируется с

rev1([H|T],L1,L) : rev1(T,[H|L1],L)/ H=2, L1=[1], T=[3] возвращая rev1([3], [2,1], L).

•rev1([3], [2,1], L) унифицируется с

rev1([H|T],L1,L) : rev1(T,[H|L1],L)/ H=3, L1=[2,1], T=[] возвращая rev1([], [3,2,1], L).

•rev1([], [3,2,1], L) унифицируется с rev1([], L, L) : ! для L=[3,2,1],

производя результат L=[3,2,1].

84

Лаплас говорил, что Ньютон был не только величайшим учёным всех времён и народов, но ещё и очень удачливым человеком, потому, что родился до Лапласа. Конечно же, Le Marquis мог бы от

крыть Небесную Механику до Ньютона, если бы имел возможность это сделать. Я полагаю, что вы написали бы быстрый алгоритм сортировки до Ван Эмдена (Van Emden), если бы он не был достаточ

но удачлив для того, чтобы положить руку на компилятор Пролога до вас. Быстрый алгоритм сорти ровки был изобретён Тони Хоаре (Tony Hoare), который нуждался в быстром методе сортировки спи сков и векторов. Это было время, когда B+Trees не существовало, и единственный способ совершить быстрый поиск в списке клиентов был иметь его уже сортированным.

Давайте посмотрим, как Ван Эмден объяснил придуманный им алгоритм своему другу Коэльо. Прежде всего, он реализовал алгоритм split/4, который делит список L на два подсписка: S (от Small – маленький) и В (от Big большой). Подсписок S содержит все L, которые меньше или равны P (от Pivot – точка опоры). Подсписок B содержит элементы, которые больше P. Вот как Ван Эмден реа лизовал split/4:

implement main open core

clauses

classInfo("main", "quicksort"). class predicates

split:(E, E*, E*, E*) procedure (i, i, o, o). clauses

split(P, [H|T], S, [H|B]) : H>P, !, split(P, T, S, B). split(P, [H|T], [H|S], B) : !, split(P, T, S, B). split(_, [], [], []).

run(): console::init(),

split(5, [3, 7, 4, 5, 8, 2], Small, Big), stdio::write("Small=", Small, ", Big= ", Big), stdio::nl, split("c", ["b", "a", "d", "c", "f"], S1, B1), stdio::write("Small=", S1, ", Big= ", B1), stdio::nl.

end implement main goal

mainExe::run(main::run).

Если вы запустите эту программу, компьютер напечатает

Small=[3,4,5,2], Big=[7,8]

что он и должен сделать. Теперь, давайте осознаем идею, стоящую за алгоритмом быстрой сор тировки. Предположим, что у вас есть список [5, 3, 7, 4, 5, 8, 2], и вы хотите отсортировать его.

•Берём первый элемент L=[5, 3, 7, 4, 5, 8, 2] как опорную точку и делим список L на

Small=[3,4,5,2] и Big=[7,8].

•Сортируем Small, используя тот же алгоритм; получим

Sorted_small=[2, 3, 4, 5]

•Сортируем Big и получаем Sorted_Big=[7, 8].

•Присоединяем Sorted_small к [Pivot|Sorted_Big]. Вы получите сортированный список:

[2, 3, 4, 5, 5, 7, 8].

Этот алгоритм требует предикат, присоединяющий один список к другому. Вы можете использо

вать app/3, которому научились несколькими страницами выше. Однако, тот алгоритм является non­ determ, что нам не нужно, так как нам не нужна функциональность деления списка на два; всё, что нам надо – чистая конкатенация. Таким образом, вы можете вставить отсечение после первого пред ложения app/3.

85

app([], L, L) : !.

app([H|T], L, [H|U]) : app(T, L, U).

Объявите app как процедуру с двумя входными аргументами и одним выходным.

app:( integer_list, integer_list, integer_list) procedure (i, i, o).

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

implement main open core

clauses

classInfo("main", "quicksort").

class predicates

split:(E, E*, E*, E*) procedure (i, i, o, o). app:(E*, E*, E*) procedure (i, i, o). sort:(E*, E*) procedure (i, o).

clauses

split(P, [H|T], S, [H|B]) : H>P, !, split(P, T, S, B). split(P, [H|T], [H|S], B) : !, split(P, T, S, B). split(_, [], [], []).

app([], L, L) : !.

app([H|T], L, [H|U]) : app(T, L, U).

sort([P|L], S) : !, split(P, L, Small, Big), sort(Small, QSmall), sort(Big, QBig), app(QSmall, [P|QBig], S).

sort([], []).

run(): console::init(), L= [5, 3, 7, 4, 5, 8, 2], sort(L, S),

stdio::write("L=", L , ", S= ", S), stdio::nl, Strs= ["b", "a", "c"], sort(Strs, Qs), stdio::write("Qs= ", Qs), stdio::nl.

end implement main

goal mainExe::run(main::run).

Пролог был изобретён Аланом Колмероэ (Alain Colmerauer), французским лингвистом. Его сту дент Филипп Руссел (Philippe Roussel) реализовал интерпретатор. Похоже, что название «Пролог»

языку программирования дала жена Руссела. Уоррен (Warren) был человеком, реализовавшим ком пилятор. Приведённая ниже проблема была предложена этим самым Уорреном.

Устное утверждение: количество дней в году 366 каждые четыре года; иначе оно 365. Сколько дней в 1975, 1976 и 2000 годах?

implement main open core

class predicates

86

no_of_days_in:(integer, integer) procedure (i, o). member:(integer, integer_list) nondeterm (o, i). test:(integer_list) procedure (i).

clauses

classInfo("numdays", "1.0").

member(H, [H|_T]).

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

no_of_days_in(Y, 366) : 0= Y mod 400, !. no_of_days_in(Y, 366) :

0= Y mod 4,

not(0= Y mod 100), !. no_of_days_in(_Y, 365).

test(L) : member(X, L), no_of_days_in(X, N),

stdio::write("Year ", X, " has ", N, " days."), stdio::nl, fail.

test(_L).

run(): console::init(), test([1975, 1976, 2000]).

end implement main goal

mainExe::run(main::run).

Луис Мониш Перейра (Luis Moniz Pereira) – португалец, работающий с искусственным интеллек

том. Он был одним из первых, использовавших Пролог для искусственного интеллекта. Он также яв ляется соавтором книги How to Solve it in Prolog.

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

Проблема является классической программой создания и проверки. В test(L), вызовы предика

тов

generateColor(A), generateColor(B), generateColor(C), generateColor(D), generateColor(E), generateColor(F),

создают цвета для шести регионов карты. Затем, test(L) строит карту в виде списка соседст вующих стран:

L= [nb(A, B), nb(A, C), nb(A, E), nb(A, F), nb(B, C), nb(B, D), nb(B, E), nb(B, F), nb(C, D), nb(C, F), nb(C, F)],

Наконец, предикат aMap(L) проверяет, является ли L допустимой картой. Она будет допустимой, если не будет двух соседствующих стран, окрашенных одним цветом. Если предикат aMap(L) прова ливается, предложенные цвета не верны. Следовательно, программа откатывается к generateCo lor(X) для получения нового набора цветов.

Проблема четырёх цветов интересна по двум причинам.

1.Схема создания и проверки была одной из первых техник искусственного интеллекта.

2.Есть очень известная теорема, которая утверждает:

87

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

Эта теорема была доказана в 1976 году Кеннетом Эппелом (Kenneth Appel) и Вольфгангом Хаке ном (Wolfgang Haken), двумя математиками из университета Иллинойса.

implement main open core

domains

colors= blue;yellow;red;green. neighbors= nb(colors, colors). map= neighbors*.

class predicates

aMap:(map) nondeterm anyFlow. test:(map) procedure anyFlow. generateColor:(colors) multi (o).

clauses

classInfo("main", "fourcolors").

generateColor(R) :

R= blue; R= yellow; R= green; R= red.

aMap([]). aMap([X|Xs]) :

X= nb(C1, C2), not(C1 = C2), aMap(Xs).

test(L) :

generateColor(A), generateColor(B), generateColor(C), generateColor(D), generateColor(E), generateColor(F),

L= [ nb(A, B), nb(A, C), nb(A, E), nb(A, F), nb(B, C), nb(B, D), nb(B, E), nb(B, F), nb(C, D), nb(C, F), nb(C, F)],

aMap(L), !; L= [].

run(): console::init(), test(L), stdio::write(L), stdio::nl.

end implement main

goal mainExe::run(main::run).

Устное утверждение: написать программу для игры в Ним (Nim). Состояние в игре Ним может быть представлено как набор кучек спичек; мы будем отображать каждую кучку как список целых чисел.

[1, 1, 1, 1, 1]

Следовательно, набор кучек будет списком списков; например,

88

[ [1,1,1,1,1], [1, 1], [1,1,1,1] ]

Два игрока, вы и компьютер, по очереди делаете ходы. Как только игрок не сможет сделать ход, игра заканчивается, и этот игрок проигрывает. Ход состоит из изъятия из какой либо одной кучки как минимум одной спички. В данном примере, если вы возьмёте три спички из третьей кучки, вы сде лаете допустимый ход, и доска станет выглядеть так:

[ [1,1,1,1,1], [1, 1], [1] ]

где вы убрали три спички из третьей кучки. Чтобы реализовать этот проект, мы будем использо вать технику программирования, называемую incremental development of systems – пошаговая разра ботка систем. Сначала вы реализуете и протестируете программу, которая соединяет два списка. Так как вы собираетесь использовать эту программу и для разделения, и для конкатенации списков, вам нужно протестировать обе эти возможности. Фактически, если вы запустите программу, приведён ную (на этой странице), вы получите

[[1],[1],[1],[1],[1],[1],[1],[1]]

[][[1],[1],[1,1]]

[[1]][[1],[1,1]]

[[1],[1]][[1,1]]

[[1],[1],[1,1]][]

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

implement main open core

domains

ms= integer*. hs= ms*.

class predicates

append:(E*, E*, E*) nondeterm anyFlow.

clauses

classInfo("main", "nimgame").

append([], Y, Y).

append([U|X], Y, [U|Z]) : append(X, Y, Z).

clauses run():

console::init(),

append([[1],[1],[1],[1],[1]], [[1],[1],[1]], L), !, stdio::write(L), stdio::nl; succeed().

end implement main

goal mainExe::run(main::run).

89

Следующий шаг – написать предикат, который забирает как минимум одну спичку из кучки; ко нечно, он может забрать более одной спички. После удаления одной или более спичек из кучки, takesome/3 вставляет измененную кучку во множество кучек. Если вы протестируете программу, она напечатает следующий результат:

[[1,1,1,1],[1,1]]

[[1,1,1],[1,1]]

[[1,1],[1,1]]

[[1],[1,1]]

[[1,1]]

NB: первое предложение takesome/3 заверяет, что предикат не вставит пустую кучку во множе ство кучек.

implement main open core

domains

ms= integer*. hs= ms*.

class predicates

append:(E*, E*, E*) nondeterm anyFlow. test:() procedure.

takesome:(ms, hs, hs) nondeterm anyFlow.

clauses

classInfo("main", "nimgame").

append([], Y, Y).

append([U|X], Y, [U|Z]) : append(X, Y, Z).

takesome([_X], V, V).

takesome([_X, X1|Y], V, [[X1|Y]|V]). takesome([_X|T], V, Y) : takesome(T, V, Y).

test() : L= [1, 1, 1, 1, 1], V= [[1,1]],

takesome(L, V, Resp), stdio::write(Resp), stdio::nl, fail; succeed().

clauses

run(): console::init(), test().

end implement main

goal mainExe::run(main::run).

Теперь вы готовы создавать все возможные ходы с заданной позиции. Если вы запустите тесто вую программу, она выдаст следующий экран:

Possible moves from [[1,1,1],[1,1]]: [[1,1],[1,1]]

90