Программирование на языке пролог
Шрифт:
С помощью предиката 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путем исключения всех импликаций.