Иван Братко - Программирование на языке Пролог для искусственного интеллекта

% исходной версии

пред3( X, Z) :-

родитель( X, Z).

пред3( X, Z) :-

пред3( X, Y),

родитель( Y, Z).

% Вариант с: изменение порядка предложений и целей в исходной

% версии

пред4( X, Z) :-

пред4( X, Y),

родитель( Y, Z).

пред4( X, Z):-

родитель( X, Z).

Рис. 2.16. Четыре версии программы предок.

В последнем случае пролог-система не сможет найти ответа. И выведет на терминал сообщение: "Не хватает памяти".

На рис. 1.11 гл. 1 были показаны все шаги вычислений по пред1(в главе 1 она называлась предок), предпринятые для ответа на этот вопрос. На рис 2.17 показаны соответствующие вычисления по пред2, пред3и пред4. На рис. 2.17 (с) ясно видно, что работа пред4 — бесперспективна, а рис. 2.17(а) показывает, что пред2довольно неэффективна по сравнению с пред1: пред2производит значительно больший перебор и делает больше возвратов по фамильному дереву.

Такое сравнение должно напомнить нам об общем практическом правиле при решении задач: обычно бывает полезным прежде всего попробовать самое простое соображение. В нашем случае все версии отношения предокоснованы на двух соображениях:

• более простое — нужно проверить, не удовлетворяют ли два аргумента отношения предокотношению родитель;

• более сложное — найти кого-либо "между" этими двумя людьми (кого-либо, кто связан с ними отношениями родительи предок).

Из всех четырех вариантов отношения предок, пред1использует наиболее простое соображение в первую очередь. В противоположность этому пред4всегда сначала пробует использовать самое сложное. Пред2 и пред3находятся между этими двумя крайностями. Даже без детального изучения процессов вычислений ясно, что пред1следует предпочесть просто на основании правила "самое простое пробуй в первую очередь".

Наши четыре варианта процедуры предокможно далее сравнить, рассмотрев вопрос: "На какие типы вопросов может отвечать тот или иной конкретный вариант и на какие не может?" Оказывается, пред1и пред2оба способны найти ответ на любой вид вопроса относительно предков; пред4никогда не находит ответа, а пред3иногда может найти, иногда нет. Вот пример вопроса, на который пред4ответить не может:

?- пред3( лиз, джим).

Такой вопрос тоже вводит систему в бесконечную рекурсию. Следовательно и пред3нельзя признать верным с точки зрения процедурного смысла.

Рис. 2.17. Поведение трех вариантов формулировки отношения предокпри ответе на вопрос, является ли Том предком Пат?

В предыдущем разделе было показано, что порядок целей и предложений имеет существенное значение. Более того, существуют программы, которые верны в декларативном смысле, но на практике не работают. Такое противоречие между декларативным и процедурным смыслами может вызвать недовольство. Кто-нибудь спросит: "А почему вообще не забыть о декларативном смысле?" Такое пожелание становится особенно сильным, когда рассматриваются предложения типа:

предок( X, Z) :- предок( X, Z).

Это предложение верно в декларативном смысле, но совершенно бесполезно в качестве рабочей программы.

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