Программирование на языке Пролог

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

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

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