Тот же алгоритм, изложенный на Прологе:
преобрспис( [], _, []).
преобрспис( [X | Хвост], F, [НовХ | НовХвост] :-
G =.. [F, X, НовХ],
саll( G),
пpeoбpcпиc( Хвост, F, НовХвост).
Одна из причин того, что рекурсия так естественна для определения отношений на Прологе, состоит в том, что объекты данных часто сами имеют рекурсивную структуру. К таким объектам относятся списки и деревья. Список либо пуст (граничный случай), либо имеет голову и хвост, который сам является списком (общий случай). Двоичное дерево либо пусто (граничный случай), либо у него есть корень и два поддерева, которые сами являются двоичными деревьями (общий случай). Поэтому для обработки всего непустого дерева необходимо сначала что-то сделать с его корнем, а затем обработать поддеревья.
8.2.2. Обобщение
Часто бывает полезно обобщить исходную задачу таким образом, чтобы полученная более общая задача допускала рекурсивную формулировку. Исходная задача решается, тогда как частный случай ее более общего варианта. Обобщение отношения обычно требует введения одного или более дополнительных аргументов. Главная проблема состоит в отыскании подходящего обобщения, что может потребовать более тщательного изучения задачи. В качестве примера рассмотрим еще раз задачу о восьми ферзях. Исходная задача состояла в следующем: разместить на доске восемь ферзей так, чтобы обеспечить отсутствие взаимных нападений. Соответствующее отношение назовем
восемьферзей( Поз)
Оно выполняется (истинно), если Поз — представленная тем или иным способом позиция, удовлетворяющая условию задачи. Можно предложить следующую полезную идею: обобщить задачу, перейдя от 8 ферзей к произвольному количеству — N. Количество ферзей станет дополнительным аргументом:
n_ферзей( Поз, N)
Преимущество такого обобщения состоит в том, что отношение n_ферзей допускает непосредственную рекурсивную формулировку:
(1) Граничный случай: N = 0
Разместить 0 ферзей — тривиальная задача.
(2) Общий случай: N > 0
Для 'безопасного' размещения N ферзей необходимо:
• получить требуемое размещение для (N - 1) ферзей и
• добавить оставшегося ферзя так, чтобы он не бил ни одного из уже поставленных ферзей.
Как только мы научимся решать более общую задачу, решить исходную уже не составит труда:
восемьферзей( Поз) :- n_ферзей( Поз, 8)
8.2.3. Использование рисунков
В поиске идей для решения задачи часто бывает полезным обратиться к ее графическому представлению. Рисунок может помочь выявить в задаче некоторые существенные отношения. После этого останется только описать на языке программирования то, что мы
Использование графического представления при решении задач полезно всегда, однако похоже, что в Прологе оно работает особенно хорошо. Происходит это по следующим причинам:
(1) Пролог особенно хорошо приспособлен для задач, в которых фигурируют объекты и отношения между ними. Часто такие задачи естественно иллюстрировать графами, в которых узлы соответствуют объектам, а дуги — отношениям.
(2) Естественным наглядным изображением структурных объектов Пролога являются деревья.
(3) Декларативный характер пролог-программ облегчает перевод графического представления на Пролог. В принципе, порядок описания 'картинки' не играет роли, мы просто помещаем в программу то, что видим, в произвольном порядке. (Возможно, что из практических соображений этот порядок впоследствии придется подправить с целью повысить эффективность программы.)
8.3. Стиль программирования
Подчиняться при программировании некоторым стилистическим соглашениям нужно для того, чтобы
• уменьшить опасность внесения ошибок в программы и
• создавать программы, которые легко читать, понимать, отлаживать и модифицировать.
Ниже дается обзор некоторых из составных частей хорошего стиля программирования на Прологе. Мы рассмотрим некоторые общие правила хорошего стиля, табличную организацию длинных процедур и вопросы комментирования программ.
8.3.1. Некоторые правила хорошего стиля
• Предложения программы должны быть короткими. Их тела, как правило, должны содержать только несколько целей.
• Процедуры должны быть короткими, поскольку длинные процедуры трудны для понимания. Тем не менее длинные процедуры вполне допустимы в том случае, когда они имеют регулярную структуру (этот вопрос еще будет обсуждаться в данной главе).
• Следует применять мнемонические имена процедур и переменных. Они должны отражать смысл отношений и роль объектов данных.
• Существенное значение имеет расположение текста программы. Для улучшения читабельности программы нужно постоянно применять пробелы, пустые строки и отступы. Предложения, относящиеся к одной процедуре, следует размещать вместе в виде отдельной группы строк; между предложениями нужно вставлять пустую строку (этого не нужно делать, возможно, только в случае перечисления большого количества фактов, касающихся одного отношения); каждую цель можно размещать на отдельной строке. Пролог-программы иной раз напоминают стихи по эстетической привлекательности своих идей и формы.
• Стилистические соглашения такого рода могут варьироваться от программы к программе, так как они зависят от задачи и от личного вкуса. Важно, однако, чтобы на протяжении одной программы постоянно применялись одни и те же соглашения.
• Оператор отсечения следует применять с осторожностью. Если легко можно обойтись без него — не пользуйтесь им. Всегда, когда это возможно, предпочтение следует отдавать 'зеленым отсечениям' перед 'красными'. Как говорилось в гл. 5, отсечение называется 'зеленым', если его можно убрать, на затрагивая декларативный смысл предложения. Использование 'красных отсечений' должно
