Книга: ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

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

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

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

Упражнение 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.

Оглавление книги