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

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

Этап 1 - исключение импликаций