ПРИЛОЖЕНИЕ А. ОТВЕТЫ К НЕКОТОРЫМ УПРАЖНЕНИЯМ

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

Упражнение 1.2.Здесь представлены возможные определения семейных отношений.

явл_матерью(М):- мать(М,Ребенок).

явл_отцом(О):- отец(О, Ребенок).

явл_сыном(Сын):- родитель(Род,Сын), Мужчина(Сын).

явл_сестрой(Сес,Ч):- родитель(Род,Сес), родитель(Род,Ч), женщина(Сес), различ(Сес,Ч).

дедушка, (Дед,X):- родитель(Род,Х), отец(Дед,Род).

брат_или_сестра (S1,S2):- родитель(Род,Б1), родитель(Род, S2), различ(S1,S2).

Заметим, что нам приходится использовать предикат различв определении предикатов явл_сестройи брат_или_сестра. Это гарантирует нам, что система не будет считать, что кто-то может быть сестрой или братом самому себе. Дать определение предиката различна этом этапе вы не сможете.

Упражнение 5.2.Следующая программа циклически считывает символы (из текущего файла ввода) и печатает их, заменяя при этом все строчные буквы 'а' на 'b'.

go:- repeat, get0(C), deal_with(C), fail.

deal_with(97):-!, put(98).

deal_with(X):- put(X).

Наличие «отсечения» в первом правиле предиката deal_withсущественно (почему?). Числа 97 и 98 есть значения кодов ASCII для символов ' а' и ' b' соответственно.

Упражнение 6.2.Почему следующее определение предиката getне работает, если целевое утверждение getзадано с конкретизированным аргументом?

get(X):- new_get(X), X›32.

new_get(X):- repeat, getO(X).

Предположим, мы задали Пролог-системе целевое утверждение get(97) (проверить, является ли следующий печатаемый символ строчной буквой 'а'?), тогда как на самом деле этот следующий символ есть ' b'. Чтобы согласовать get(97),делается попытка согласовать new_get(97).Цель repeatуспешно согласуется, но затем цель get0(97)оказывается несогласуемой (так как следующий символ не 'а'). Тогда начинается возвратный ход. Цель get0не может быть повторно согласована, а цель repeat- может. Итак, целевое утверждение repeatснова согласуется с базой данных, и вновь делается попытка согласовать get0(97). На этот раз, конечно, следующим символом будет тот, что следует за ' b'. Если это не ' а', то цель оказывается несогласуемой, a repeatснова завершается успешно. Теперь будет проверяться следующий символ и так далее. Фактически происходит следующее: программа считывает новые и новые символы до тех пор пока она, наконец, не находит тот, что совпадает с аргументом. Но это не то, что должен делать предикат get.Правильное определение предиката get,которое обходит эту проблему, а также содержит «отсечение», устраняющее возможность повторного согласования repeatвыглядит следующим образом:

get(X):- repeat, get0(Y), 32‹Y,!, X-Y.

Упражнение 7.10.Вот программа, которая порождает пифагоровы тройки.

pythag(X,Y,Z):-  intriple(X,Y,Z), Sumsq is Х*Х + Y*Y, Sumsq is Z*Z.

intriple(X,Y,Z):- is_integer(Sum), minus(Sum,X,Sum1), minus(Sum1,Y,Z).

minus(Sum,Sum,0).

minus(Sum,Dl,D2):- Sum›0, Suml is Sum-1, minus(Suml,Dl,D3), D2 is D3+1.

is_integer(0).

is_integer(N):- is_integer(N1), N is N1 + 1.

С помощью предиката intripleпрограмма порождает все возможные тройки чисел X, Y, Z, а затем проверяет, является ли данная тройка чисел пифагоровой тройкой. Определение intripleгарантирует, что рано или поздно все возможные тройки чисел будут порождены. Прежде всего порождается целое число, являющееся суммой X, Yи Z. Затем с помощью недетерминированного предиката вычитания minusиз него порождаются значения X, Yи Z.

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

?- op(255,xfx,--›).

трансляция ((P1--›P2), (Gl:-G2)):- левая_часть(Р1,S0,S,G1), правая_частъ(Р2,S0,S,G2).

левая_часть(Р0,S0,S,G):- nonvar(PO), tag(P0,S0,S,G).

правая_часть((Pl,P2),S0,S,G):-!, правая_часть(Р1,S0,S1,G1), правая_чacть(P2,S1,S,G2), и(G1, G2,G).

правая_часть(P,S0,S,true):- явл_списком(Р),!, присоединить(Р,S,S0).

правая_часть(P,S0,S,G):- tag(P,S0,S,G).

tag(P,S0,S,G):- atom(P), G =.. [P,S0,S].

и(true,G,G):-!.

и(G,true,G):-!.

и(G1,G2, (G1,G2)).

явл_списком([]):-!.

явл_списком([_ |_]).

присоединить([А|В],C,[A|D]):- присоединить(В,С,D).

присоединить([], Х,Х).

В этой программе переменные, начинающиеся с латинской буквы Р, используются для обозначения описаний словосочетаний (в виде атомов или списков слов) в правилах грамматики. Переменные, начинающиеся с G, обозначают целевые утверждения Пролога. Переменные, начинающиеся с S, обозначают аргументы целевых утверждений Пролога (которые представляют последовательности слов). Для тех, кто заинтересуется, ниже приведена программа, которая способна обрабатывать более общие случаи трансляции правил грамматики. Один из приемов приспособления Пролог-системы к обработке правил грамматики состоит в использовании измененной версии предиката consult, где предложение вида А--›Bтранслируется перед занесением его в базу данных.

?- op(251,fx,{).

?- op(250,fx,}).

?- op(255,XFX,>).

трансляция((Р0--›Q0), (P:- Q)):- левая_часть(P0,S0,S,P), правая_часть(Q0, S0,S,Q1), лин(Q1, Q).

левая_часть((NT,Ts),S0,S,P):- !, nonvar(NT), явл_списком(Тs), tag(NT,S0,Sl,P), присоединить(Ts, S0,S1).

левая_часть (NT,S0,S,P):- nonvar(NT), tag(NT,SO,S,P).

правая_часть((Х1,Х2),S0,S,Р):- правая_часть(Х1,S0,S1,Р1), правая_часть(X2,Sl,S,P2), и(Р1,Р2,Р).

правая_часть((Xl;X2),S0,S,(P1;P2)):-!, или(Xl,S0,S,P1), или(Х2,S0,S,Р2).

правая_часть(Р,S,S,Р):-!.

правая_часть(!,S,S,!):-!.

правая_часть(Ts,SO,S,true):- явл_списком(Тs),!, присоединить(Ts, S,S0).

правая_часть(Х,S0,S,P):- tag(X,S0,S,P).

или(Х,S0,S,Р):- правая_часть(X,S0a,S,Pa), (var(S0a), S0a=S,!, S0=S0a, P=Pa; P=(S0=S0a,Pa)).

tag(X,S0,S,P):- X =..[F|A], присоединить(А,[S0,S],АХ), P =.. [F|AX].

и(true,P,P):-!.

и(P,true,P):-!.

и(P,Q,(P,Q)).

лин(А,А):- var(A),!.

лин((А,В),С):-!, лин1(А,С,R), лин(В,R).

лин(А,А).

лин1(А,(А,R),R):- VAR(A),!.

лин1((А,В),С,R):-!, лин1(А,С,R1), лин1(В,R1,R).

лин1(A,(A,R),R) .

явл_списком([]):-!.

явл_списком([_|_]).

присоединить([А|В],С,[А|D]):- присоединить(В,С,D).

присоединить([], X, X).

Упражнение 9.2.Определение универсальной версии предиката phrase (словосочетание)выглядит следующим образом:

phrase(Cтип,Слова):- Стип =.. [Pred|Args], присоединить(Args,[Слова,[]],Newargs), Цель =.. [Pred|Newargs], call (Цель).

где присоеднитьопределен так же как в разд. 3.6.

ПРИЛОЖЕНИЕ В. ПРОГРАММА ПРИВЕДЕНИЯ ФОРМУЛ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ К СТАНДАРТНОЙ ФОРМЕ

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

translate(X):-

 implout(X,Xl), /* Этап 1 */

 negin(Xl,X2), /* Этап 2 */

 skolem(X2,X3,[]), /* Этап 3 */

 univout(X3,X4), /* Этап 4 */

 conjn(X4,X5), /* Этап 5 */

 clausify(X5,Clauses, []), /* Этап 6 */

 pclauses(Clauses). /* Печать дизъюнктов */

Здесь приведено определение предиката translate, действующего таким образом, что, если выполнить целевое утверждение translate(X), где X– это формула исчисления предикатов, то программа напечатает эту формулу в стандартной форме в виде последовательности дизъюнктов. В этой программе формулы исчисления предикатов представляются в виде структур языка Пролог, как на это указывалось ранее (в гл. 10). Однако мы сделаем некоторое отступление от предыдущего описания и будем представлять переменные, входящие в формулы исчисления предикатов, атомами языка Пролог, с целью облегчить их обработку. Предполагается, что можно отличить переменные в формулах исчисления предикатов от констант, используя некоторое соглашение относительно формы записи имен. Например, можно считать, что имена переменных всегда начинаются с одной из букв х, у, z. В действительности, переменные всегда вводятся в формулу посредством кванторов и, следовательно, их легко можно опознать. Лишь при чтении результата, печатаемого программой, программисту необходимо помнить, какие имена соответствуют переменным формул исчисления предикатов, а какие константам.

Прежде всего, необходимо объявить операторы для логических связок, используемых в формулах:

?- op(30,fx,~).

?- op(100,xfy,#).

?- op(100,xfy,&).

?- op(150,xfy,-›).

?- op(150,xfy,‹-›).

Следует обратить внимание на то, как определены операторы. В частности ~ имеет более низкий приоритет чем # и &. Для начала, необходимо сделать одно важное предположение. Предполагается, что переменные переименованы таким образом, что в обрабатываемой формуле одна и та же переменная никогда не вводится более чем одним квантором. Это необходимо, чтобы предотвратить возможные конфликты в употреблении имен в дальнейшем.

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

Определим предикат imploutтак, что implout(X, Y)означает, что формула Yполучается из формулы Xпутем исключения всех импликаций.

implout((P ‹-› Q), (P1 & Q1) # (~Р1 & ~Q1))):- !, implout(P,Pl), implout(Q,Ql).

implout((P -› Q),(~P1 # Q1)):-!, implout(P,P1), implout(Q,Q1).

implout(all(X,P),all(X,P1)):- !.

implout(exists(X,P),exists(X,P1)):-!, implout(P, P1).

implout((P & Q),(P1 & Q1)):- !, implout(P,P1), implout(Q,Q1).

implout((P # Q),(P1 # Q1)):-!, implout(P,P1), implout(Q,Q1).

implout((-P),(~Pl)):-!, implout(P,P1).

implout(P,P).

Здесь необходимо определить два предиката – neginи neg.Целевое утверждение negin(X, Y)означает, что формула Yполучена из Xв результате применения к ней преобразования «перенос отрицания». Этот предикат является основным и именно к нему производится обращение из программы. Целевое утверждение neg(X, Y)означает, что формула Yполучена из формулы ~X спомощью того же преобразования, что и в negin.В обоих случаях предполагается, что формула прошла обработку на первом этапе и, следовательно, не содержит -› и ‹-›

negin((~P),P1):-!, neg(P,P1).

negin(all(X,P),all(X,P1)):-!, negin(P,P1).

negin(exists(X,P),exists(X,P1)):-!, negin(P,P1).

negin((P & Q),(P1 & Q1)):-!, negin(P,P1), negin(Q,Q1).

negin((P # Q),(P1 # Q1)):-!, negin(P,P1), negin(Q,Q1).

negin(P,P).

neg((~P),P1):-!, negin(P,P1).

neg(all(X,P), exists(X,P1)):-!, neg(P,P1).

neg(exists(X,P),all(X,P1)):-!, neg(P,P1).

neg((P  &Q),(P1 # Q1)):-!, neg(P,P1), neg(Q, Q1).

neg((P # Q),(P1 & Q1)):~!, neg(P,P1), neg(Q, Q1).

neg(P,(~P)).

Предикат skolemимеет три аргумента, соответствующих: исходной формуле, преобразованной формуле и списку переменных, которые на текущий момент были введены посредством кванторов общности.

skolem(all(X,P),all(X,P1),Vars):-!, scolem(P,Pl,[X|Vars]).

skolem(exists(X,P),P2,Vars):-!, gensym(f,F), Sk =..[F|Vars], subst(X,Sk,P,P1), skolem(P1,P2,Vars).

skolem((P # Q),(P1 # Q1),Vars):-!, skolem(P,P1,Vars), skolem(Q,Q1,Vars).

skolem((P & Q),(P1 & Q1), Vars):-!, skoIem(P,P1,Vars), skolem(Q,Q1,Vars).

skolem(P,P,_).

В этом определении используются два новых предиката. Предикат gensymдолжен быть определен таким образом, что целевое утверждение gensym(X, Y)вызывает конкретизацию переменной Yзначением, представляющим новый атом, построенный из атома Xи некоторого числа. Он используется для порождения сколемовских констант, не использовавшихся ранее. Предикат gensymопределен в разд. 7.8 как генатом.Второй новый предикат, о котором уже упоминалось, это subst.Мы требуем, чтобы subst(Vl,V2,F1,F2)было истинно, если формула F2получается на F1в результате замены всех вхождений V1на V2.Определение этого предиката оставлено в качестве упражнения для читателя. Оно аналогично определениям, приведенным в разд. 7.5 и 6.5.

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

univout(all(X,P), P1):- !, univout(P,P1).

univout((P & Q),(P1 & Q1)):-!, univout(P,P1), univout(Q,Q1).

univout((P # Q),(P1 # Q1)):- !, univout(P,P1), univout(Q,Q1).

univout(P,P).

Эти правила определяют предикат univoutтаким образом, что univout(X, Y)означает, что Yполучается из Xв результате вынесения и удаления кванторов общности.

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

Реальная программа для преобразования формулы в конъюнктивную нормальную форму является значительно более сложной по сравнению с последней программой. При обработке формулы вида (Р # Q),где Ри Q– произвольные формулы, прежде всего, необходимо преобразовать Ри Qв конъюнктивную нормальную

форму, скажем P1и Q1. И только после этого можно применять одно из преобразований, дающих эквивалентную формулу. Процесс обработки должен происходить именно в таком порядке, так как может оказаться, что ни Рни Qне содержат& на верхнем уровне, а Р1и Q1содержат. Программа имеет вид:

conjn((P # Q),R):-!, conjn(P,P1), conjn(Q,Q1), conjn1((P1 # Q1),R).

conjn((P& Q),(P1& Q1)):-!, conjn(P,P1), conjn(Q,Q1).

conjn(P,P).

conjn1(((P & Q) # R), (P1 & Q1)):- !, conjn((P # Q), P1), conjn((Q # R), Q1).

conjn1((P # (Q & R)),(P1 & Q1)):-!, conjn((P # Q), P1), conjn((P # R), Q1).

conjn1(P,P).

Здесь представлена последняя часть программы приведения формулы к стандартной форме. Прежде всего, определим предикат clausify, который осуществляет построение внутреннего представления совокупности дизъюнктов. Эта совокупность представлена в виде списка, каждый элемент которого является структурой вида cl(A, В). В этой структуре А– это список литералов без отрицания, а В– список литералов с отрицанием (знак отрицания ~ явно не содержится). Предикат clausifyимеет три аргумента. Первый аргумент для формулы, передаваемой с пятого этапа обработки, Второй и третий аргументы используются для представления списков дизъюнктов. Предикат clausifyсоздает список, заканчивающийся переменной, а не пустым списком ( []) как обычно, и возвращает эту переменную посредством третьего аргумента. Это позволяет другим правилам добавлять элементы в конец этого списка, конкретизируя соответствующим образом указанную переменную. В программе выполняется проверка с целью выявления ситуаций, когда одна и та же атомарная формула входит в дизъюнкт как с отрицанием, так и без него. Если такая ситуация имеет место, то соответствующий дизъюнкт не добавляется к списку, так как подобные дизъюнкты являются тривиально истинными и не дают ничего нового. Выполняется также проверка неоднократного вхождения литерала в дизъюнкт.

clausify((P& Q),C1,C2):-!, clausify(P,C1,C3), clausify(Q,C3,C2).

clausify(P,[cl(A,B)|Cs],Cs):- inclause(P,A,[],B,[]),!.

clausify(_,C,C).

inclause((P # Q), A, A1, B, B1):-!, inclause(P,A2,A1,B2,B1),inclause(Q,A,A2,B,B2).

inclause((~P),A,A,B1,B):-!, notin(P,A), putin(P,B,B1).

inclause(P,A1,A,B,B):- notin(P,B), putin(P,A,A1).

notin(X,[X|_]):-!, fail.

notin(X,[_|L]):-!, notin(X,L).

notin(X,[]).

putin(X,[],[X]):-!.

putin(X,[X|L],L):-!.

putin(X,[Y|L], [Y|L1]):- putin(X,L,L1).

Теперь будет определен предикат pclausesпечатающий формулу, представленную указанным способом, в соответствии с принятой формой записи.

pclauses([]):-!, nl, nl.

pclauses([cl(A,B)|Cs]):- pclause(A,B), nl, pclauses(Cs).

pclause(L,[]):-!, pdisj(L), write('.').

pclause([],L):-!, write(':-'), pconj(L), write('.').

pclause(L1,L2):- pdisj(L1), write(':-'), pconj(L2), write('.').

pdisj([L]):-!, write(L).

pdisj([L|Ls]):- write(L), write(';'), pdisj(Ls).

pconj([Lj):-!, write(L).

pconj([L|Ls]):- write(L), write(','), pconj(Ls).

ПРИЛОЖЕНИЕ С. РАЗЛИЧНЫЕ ВЕРСИИ ЯЗЫКА ПРОЛОГ

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

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

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

У каждого имеются свои представления о том, какая форма синтаксиса наиболее естественна и наглядна. К счастью, синтаксис Пролога довольно прост и не дает большого простора для вариаций. Один из спорных вопросов – как следует отличать переменные от атомов. Здесь для обозначения переменных используются имена, начинающиеся с прописной буквы, а для обозначения атомов – со строчной. Кроме того, мы допускаем атомы, составленные из последовательностей знаков, таких как '*', '.' и '='. Некоторые Пролог-системы придерживаются в отношении использования прописных и строчных букв обратного соглашения (когда имена переменных начинаются со строчной буквы). Другие различают имена переменных за счет того, что начинают их со специальной литеры, как, например, '_PERSON'или '*PERSON'.Это удобно для систем, где прописные и строчные буквы не различаются. Другим моментом, где возможны расхождения, является способ записи утверждений – как заголовок утверждения отделяется от тела, как разделяются отдельные цели в теле и как обозначаются вопросы к системе. Для этого вполне могут употребляться атомы, отличные от ':-', '.' и '?-', или использоваться более сложные методы. В одной из ранних систем заголовок и цели утверждения размещались одно за другим, причем перед заголовком утверждения ставили знак '+', а перед каждой из подцелей – знак '-'. Короче говоря, вам могут встретиться способы записи утверждений, приведенные ниже, а также и отличные от них.

uncle(X,Z):- parent(X,Y), brother(Y,Z).

Uncle(x,z) ‹- Parent(x,y) & Brother(y,z).

UNCLE(_X,_Z):- PARENT(_X,_Y), BROTHER(_Y,_Z).

+UNCLE(*X,*Z) -PARENT(*X,*Y) -BROTHER(*Y,*Z).

((UNCLE X1 ХЗ) (PARENT X1 Х2) (BROTHER X2 ХЗ))

uncle(X,Z): parent(X,Y); brother(Y,Z).

Поскольку на разных ЭВМ управление памятью организовано по-разному, то создатели Пролог-систем не всегда могут позволить неограниченный рост некоторых объектов.