У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ
conjn((P # Q),R):-!, conjn(P,P1), conjn(Q,Q1), conjn1((P1 # Q1),R).
conjn((P& Q),(P1& Q1)):-!, conjn(P,P1), conjn(Q,Q1).
conjn(P,P).
conjn1(((P & Q) # R), (P1 & Q1)):- !, conjn((P # Q), P1), conjn((Q # R), Q1).
conjn1((P # (Q & R)),(P1 & Q1)):-!, conjn((P # Q), P1), conjn((P # R), Q1).
conjn1(P,P).
Этап 6 - выделение множества дизъюнктовЗдесь представлена последняя часть программы приведения формулы к стандартной форме. Прежде всего, определим предикат clausify, который осуществляет построение внутреннего представления совокупности дизъюнктов. Эта совокупность представлена в виде списка, каждый элемент которого является структурой вида cl(A, В). В этой структуре А – это список литералов без отрицания, а В – список литералов с отрицанием (знак отрицания ~ явно не содержится). Предикат clausify имеет три аргумента. Первый аргумент для формулы, передаваемой с пятого этапа обработки, Второй и третий аргументы используются для представления списков дизъюнктов. Предикат clausify создает список, заканчивающийся переменной, а не пустым списком ([]) как обычно, и возвращает эту переменную посредством третьего аргумента. Это позволяет другим правилам добавлять элементы в конец этого списка, конкретизируя соответствующим образом указанную переменную. В программе выполняется проверка с целью выявления ситуаций, когда одна и та же атомарная формула входит в дизъюнкт как с отрицанием, так и без него. Если такая ситуация имеет место, то соответствующий дизъюнкт не добавляется к списку, так как подобные дизъюнкты являются тривиально истинными и не дают ничего нового. Выполняется также проверка неоднократного вхождения литерала в дизъюнкт.
clausify((P& Q),C1,C2):-!, clausify(P,C1,C3), clausify(Q,C3,C2).
clausify(P,[cl(A,B)|Cs],Cs):- inclause(P,A,[],B,[]),!.
clausify(_,C,C).
inclause((P # Q), A, A1, B, B1):-!, inclause(P,A2,A1,B2,B1),inclause(Q,A,A2,B,B2).
inclause((~P),A,A,B1,B):-!, notin(P,A), putin(P,B,B1).
inclause(P,A1,A,B,B):- notin(P,B), putin(P,A,A1).
notin(X,[X|_]):-!, fail.
notin(X,[_|L]):-!, notin(X,L).
notin(X,[]).
putin(X,[],[X]):-!.
putin(X,[X|L],L):-!.
putin(X,[Y|L], [Y|L1]):- putin(X,L,L1).
Печать утверждений
Теперь будет определен предикат pclauses печатающий формулу, представленную указанным способом, в соответствии с принятой формой записи.
pclauses([]):-!, nl, nl.
pclauses([cl(A,B)|Cs]):- pclause(A,B), nl, pclauses(Cs).
pclause(L,[]):-!, pdisj(L), write('.').
pclause([],L):-!, write(':-'), pconj(L), write('.').
pclause(L1,L2):- pdisj(L1), write(':-'), pconj(L2), write('.').
pdisj([L]):-!, write(L).
pdisj([L|Ls]):- write(L), write(';'), pdisj(Ls).
pconj([Lj):-!, write(L).
pconj([L|Ls]):- write(L), write(','), pconj(Ls).
ПРИЛОЖЕНИЕ С. РАЗЛИЧНЫЕ ВЕРСИИ ЯЗЫКА ПРОЛОГ
В настоящее время существует много различных версий Пролога, которые можно встретить во многих организациях. Разнообразие версий отчасти объясняется разнообразием имеющихся ЭВМ. Нет двух ЭВМ, для которых с одинаковой легкостью писались бы все возможные программы. Это нашло отражение в том, что различные реализации Пролога отличаются друг от друга по своим возможностям. Но даже две ЭВМ одного и того же типа могут работать с разными операционными системами. Операционная система – это программа, осуществляющая общее управление работой ЭВМ, в том числе контроль за эффективным распределением ресурсов между пользователями ЭВМ. Одни операционные системы разрешают программисту использовать широкий набор возможностей, обеспечиваемых ЭВМ. Набор допустимых средств других более скромен. Отсюда и различия между Пролог-системами. Наконец, создатели Пролог-систем часто расходятся в представлениях о том, какие возможности являются лишь эстетически приятными, а какие действительно необходимы. В результате никакие две Пролог-системы не совпадают полностью по возможностям, и не похоже, что эта ситуация вскоре изменится, поскольку относительно реализаций Пролога постоянно возникают новые идеи и усовершенствования.
В этой книге описана версия Пролога, которая не соответствует в точности никакой существующей системе. Скорее наоборот, она была задумана как описание «базового» Пролога, который похож на все системы сразу. Если вы усвоили идеи, изложенные в этой книге, то вам не составит большого труда приспособиться к какой-либо конкретной Пролог-системе, с которой вам придется работать. Синтаксис языка и некоторые встроенные предикаты могут отличаться, но в остальном это будет все тот же базовый Пролог, который описан здесь.
Лучший способ изучения Пролог-системы, которой вы располагаете,- это чтение руководства пользователя, входящего в комплект ее документации. Правда, изложение там может быть сжатым, однако, имея общее представление о языке, вы без особого труда сможете разобраться, чем данная система отличается от того, с чем вы знакомы. В данном приложении отмечается несколько моментов, на которые стоит обратить внимание, а также сообщаются подробные сведения о двух конкретных Пролог-системах, которые довольно широко распространены. При этом мы хотели бы еще раз подчеркнуть, что многие существующие Пролог-системы постепенно меняются, и поэтому ничто не заменит вам изучения свежей версии руководства по Пролог-системе для вашей ЭВМ. Ниже рассматриваются характеристики Пролог-систем, различия в которых наиболее вероятны для разных реализаций Пролога.
СинтаксисУ каждого имеются свои представления о том, какая форма синтаксиса наиболее естественна и наглядна. К счастью, синтаксис Пролога довольно прост и не дает большого простора для вариаций. Один из спорных вопросов – как следует отличать переменные от атомов. Здесь для обозначения переменных используются имена, начинающиеся с прописной буквы, а для обозначения атомов – со строчной. Кроме того, мы допускаем атомы, составленные из последовательностей знаков, таких как '*', '.' и '='. Некоторые Пролог-системы придерживаются в отношении использования прописных и строчных букв обратного соглашения (когда имена переменных начинаются со строчной буквы). Другие различают имена переменных за счет того, что начинают их со специальной литеры, как, например, '_PERSON' или '*PERSON'. Это удобно для систем, где прописные и строчные буквы не различаются. Другим моментом, где возможны расхождения, является способ записи утверждений – как заголовок утверждения отделяется от тела, как разделяются отдельные цели в теле и как обозначаются вопросы к системе. Для этого вполне могут употребляться атомы, отличные от ':-', '.' и '?-', или использоваться более сложные методы. В одной из ранних систем заголовок и цели утверждения размещались одно за другим, причем перед заголовком утверждения ставили знак '+', а перед каждой из подцелей – знак '-'. Короче говоря, вам могут встретиться способы записи утверждений, приведенные ниже, а также и отличные от них.
uncle(X,Z):- parent(X,Y), brother(Y,Z).
Uncle(x,z) ‹- Parent(x,y) & Brother(y,z).
UNCLE(_X,_Z):- PARENT(_X,_Y), BROTHER(_Y,_Z).
+UNCLE(*X,*Z) -PARENT(*X,*Y) -BROTHER(*Y,*Z).
((UNCLE X1 ХЗ) (PARENT X1 Х2) (BROTHER X2 ХЗ))
uncle(X,Z): parent(X,Y); brother(Y,Z).
Различные ограниченияПоскольку на разных ЭВМ управление памятью организовано по-разному, то создатели Пролог-систем не всегда могут позволить неограниченный рост некоторых объектов. Среди характеристик, которые подвержены изменениям при переходе от одной ЭВМ к другой, можно указать максимальную величину целого числа в Прологе, возможность использования чисел с плавающей точкой, максимально допустимое число аргументов функтора, максимальное количество литер в атоме, максимальное число утверждений в определении предиката и т. д.
Возможности окруженияИз-за различий в возможностях отдельных операционных систем в некоторых Пролог-системах можно прервать программу в ходе ее выполнения, отредактировать файл на диске без потери текущего состояния сеанса работы с Пролог-системой, одновременно выполнять несколько Пролог-программ, получать входные и передавать выходные данные через специальные устройства, Однако нельзя ожидать, чтобы какая-то из этих возможностей обеспечивалась на всех системах, поэтому здесь также могут встретиться различия. Как и в вопросе допустимого набора указанных возможностей, конкретная операционная система на вашей ЭВМ может отличаться тем, что некоторым вводимым литерам она будет придавать специальное значение. Например, литера, которая вводится для обозначения «конец файла» в конце предиката consult(user) в разных ЭВМ различна. Другие литеры могут рассматриваться как запросы на выдачу информации о состоянии ЭВМ или как запросы на изменение последней введенной литеры. Подобные возможности не являются частью Пролог-системы, но тем не менее, важны для того, кто решил практически использовать эту систему.
КомпиляцияБольшинство Пролог-систем работает с представлением утверждений, которое близко к их исходному тексту. Когда какое-либо утверждение в такой системе начинает выполняться система должна проанализировать утверждение и предпринять соответствующие действия. Такая система называется интерпретатором. Другая возможность состоит в том, что система транслирует ваши предложения в последовательности инструкций, которые могут непосредственно исполняться ЭВМ. Такая система называется компилятором. Использование компилятора дает то преимущество, что ваша программа выполняется непосредственно, а не проходит процесс интерпретации. Это означает, что вы вправе ожидать, что ваша программа будет выполняться быстрее. Но, с другой стороны, поскольку при использовании компилятора текст программы не сохраняется в исходном виде, не следует надеяться на получение той же информации при ее отладке (например, вам нельзя будет запросить выдачу текстов ваших предложений). В некоторых системах имеется возможность выбора между компиляцией и интерпретацией утверждений. В этом случае следует тщательно взвесить преимущества каждого подхода.
