Программирование на языке пролог (ЛП)

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

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

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