Назад | Содержание| Вперёд 2. 7. Замечания о взаимосвязимежду Прологом и ло...

Назад | Содержание| Вперёд

2. 7.    Замечания о взаимосвязимежду Прологом и логикой

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

.

Синтаксис Пролога - это синтаксис предложений логики предикатов первого порядка,записанных в так называемой форме предложений(форме, при которой кванторы не выписываются

явно), а точнее, в виде частного случаятаких предложений - в виде

формулХорна

(предложений, имеющих самое большееодин положительный литерал). Клоксин и Меллиш (1981г.) приводят пролог-программу, котораяпреобразует предложения исчисления предикатов

первого порядка в форму предложений.Процедурный смысл Пролога основывается на

принципе резолюций

, применяющемсядля автоматического доказательства теорем,который был предложен Робинсоном в егоклассической статье (1965 г.). В Прологеиспользуется особая стратегия доказательстватеоремы методом резолюций, носящая название SLD.Введение в исчисление предикатов первогопорядка и доказательство теорем, основанное наметоде резолюций, можно найти у Нильсона (1981 г.).Математические вопросы, касающиеся свойствпроцедурной семантики Пролога в их связи слогикой, проанализированы Ллойдом (1984 г.)

.

Сопоставление в Прологе соответствуетнекоторому действию в логике, называемому унификацией. Мы, однако, избегаемслова "унификация", так как по соображениямэффективности внести в большинствепролог-систем сопоставление реализовано такимобразом, что оно не полностью соответствуетунификации (см. упражнение 2.10). Тем не менее, спрактической точки зрения, такая приближеннаяунификация вполне допустима.

Упражнение

2. 10.    Что будет, еслипролог-системе задать такой вопрос:

        ?-   Х  =  f(X).

Успешным или неуспешным будет здесьсопоставление? По определению унификации влогике, сопоставление должно быть неуспешным, ачто будет в соответствии с нашим определениемсопоставления из раздела 2.2? Попробуйтеобъяснить, почему многие реализации Прологаотвечают на вышеприведенный вопрос так:

        X  =  f(f(f(f(f(f(f(f(f(f(f(f(f(f(f( ...

Посмотреть ответ

Резюме

К настоящему моменту мы изучили нечтовроде базового Пролога, который называют еще "чистый Пролог". Он "чист",потому что довольно точно соответствуетформальной логике. Расширения, преследующие цельприспособить язык к некоторым практическимнуждам, будут изучены дальше (гл. 3, 5, 6. 7). Важнымимоментами данной главы являются следующие:

Простые объекты в Прологе - это атомы, переменные и числа. Структурные объекты, или структуры, используются для представления объектов, которые состоят из нескольких компонент.

Структуры строятся посредством функторов. Каждый функтор определяется своими именем и арностью.

Тип объекта распознается исключительно по его синтаксической форме.

Область известности (лексический диапазон) переменных - одно предложение. Поэтому одно и то же имя в двух предложениях обозначает две разные переменные.

Структуры могут быть естественным образом изображены в виде деревьев. Пролог можно рассматривать как язык обработки деревьев.

Операция сопоставление берет два терма и пытается сделать их идентичными, подбирая соответствующую конкретизацию переменных в обоих термах.

Сопоставление, если оно завершается успешно, в качестве результата выдает наиболее общую конкретизацию переменных.

Декларативная семантика Пролога определяет, является ли целевое утверждение истинным, исходя из данной программы, и если оно истинно, то для какой конкретизации переменных.

Запятая между целями означает их конъюнкцию. Точка с запятой между целями означает их дизъюнкцию.

Процедурная семантика Пролога - это процедура достижения списка целей в контексте данной программы. Процедура выдает истинность или ложность списка целей и соответствующую конкретизацию переменных. Процедура осуществляет автоматический возврат для перебора различных вариантов.

Декларативный смысл программ на "чистом Прологе" не зависит от порядка предложений и от порядка целей в предложениях.

Процедурный смысл существенно зависит от порядка целей и предложений. Поэтому порядок может повлиять на эффективность программы; неудачный порядок может даже привести к бесконечным рекурсивным вызовам.

Имея декларативно правильную программу, можно улучшить ее эффективность путем изменения порядка предложений и целей при сохранении ее декларативной правильности. Переупорядочивание - один из методов предотвращения зацикливания.

Кроме переупорядочивания существуют и другие, более общие методы предотвращения зацикливания, способствующие получению процедурно правильных программ.

В данной главе обсуждались следующие понятия: