Сюда вошли предлагаемые авторами ответы на некоторые из упражнений, встречающихся в тексте. Для большинства упражнений по программированию редко существует единственный правильный ответ, и, вполне возможно, что у вас получится другой верный ответ, который несколько отличается от предложенного нами. В любом случае следует обязательно опробовать вашу программу на Пролог-системе, имеющейся в вашем распоряжении, чтобы практически проверить, работает она или нет. Но даже в том случае, если вы написали правильную, но отличающуюся от нашей программу, может оказаться поучительным потратить немного времени на изучение альтернативного подхода к решению той же самой задачи.
Упражнение 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.
|
Главная
Каталог файлов
