Упражнения. 8.1. Во всех процедурах, показанных ниже (subl, sub2 и sub3), реализовано от­ношение, обеспечивающее выделение подсписка

8.1. Во всех процедурах, показанных ниже (subl, sub2 и sub3), реализовано от­ношение, обеспечивающее выделение подсписка. Процедура subl имеет "более процедурное" определение, а процедуры sub2 и sub3 написаны в "более дек­ларативном" стиле. Изучите поведение этих трех процедур на примере не­скольких списков, обращая особое внимание на их эффективность. Две из них по своему действию являются примерно одинаковыми и имеют аналогичную эффективность. Каковы эти две процедуры? Почему третья является менее эффективной?

subl! List, Sublist) :-

prefix] List, Sublist). sublt [ | Tail], Sublist) :-

subH Tail, Sublist). % Sublist является подсписком списка Tail

prefix) _ , []) .

prefix! [X I Listl], [XI ListZ]> :-prefix! Listl, List2) .

sub2{ List, Sublist]:-

cone' Listl, List2, List) , cone! List3, Sublist, Listl) .

sub3! List, Sublist) :-concf Listl, List2, List»,

conct Sublist, .. List2) .


Глава 8, Стиль и методы программирования



8.2. Определите отношение
add_at_end{ List, Item,EfewList>

для добавления элемента Item к концу списка List и получения списка NewList, Предусмотрите возможность представления обоих списков с помо­щью разностных пар.

8.3. Определите отношение

reverse ( List, ReversedList)

в котором оба списка представлены с помощью разностных пар.

8.4. Переоформите процедуру collect, приведенную в разделе 8.5.2, с использова­нием представления для списков с помощью разностных пар, чтобы операция конкатенации могла быть выполнена более эффективно.

8.5. Приведенная ниже процедура вычисляет максимальное значение в списке чисел, тах( [XI , X) .

тах( [X | Rest], Max) :-тах( Best, MaxRest), [ MaxRest >= X, !, Max = MaxRest

Max = X).

Преобразуйте ее в процедуру с хвостовой рекурсией. Подсказка: введите нака­пливающий параметр Max So Fa г.

8.6. Переоформите программу 3 для задачи с восемью ферзями (см. листинг 4.4} с использованием массивов, моделируемых с помощью предиката arg, для пред­ставления множеств свободных диагоналей, как описано в разделе *8. 5.5. Про­ведите измерения быстродействия, чтобы узнать, насколько повысилась эф­фективность.

8.7. Реализуйте операцию обновления значения элемента в массиве, моделируемом с помощью предикатов functor и arg, используя вакансии для будущих зна­чений, в соответствии с указаниями, приведенными в разделе 6.5.5.

Резюме

• Для оценки качества программ применяются следующие критерии:

• правильность;

• дружественность;

• эффективность;

• удобство для чтения;

• модифицируемость;

• надежность;

• документировашюсть.

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

• В языке Prolog перечисленные ниже методы часто позволяют находить идеи
для усовершенствований.

• Использование рекурсии. Выявление граничных и общих случаев рекуреив-ного определения.

• Обобщение, Формулировка общей задачи, которая может оказаться более простой для решения по сравнению с первоначальной.

190 Часть!. Язык Prolog


• Использований графических схем. Графическое изображение условий зада­
чи может помочь выявить важные отношения.

Необходимо придерживаться определенных стилистических соглашении для уменьшения вероятности программистских ошибок, повышения удобства про­грамм для чтения, отладки и модификации.

В системах Prolog обычно предусмотрены средства отладки программ. К чис­лу наиболее полезных из них относятся средства трассировки.

Существует много методов повышения эффективности программы. Наиболее простыми из этих методов являются следующие:

• переупорядочение целей и предложений;

• управление перебором с возвратами путем вставки операторов отсечения;

• запоминание (с помощью предиката asserta) решений, которые в ином случае пришлось бы вычислять повторно.

В результате применения более развитых методов создаются лучшие алгорит­мы (к числу особенно ярких примеров относятся алгоритмы, способствующие повышению эффективности поиска) и лучшие структуры данных. Часто ис­пользуемыми методами программирования такого типа являются следующие;

• разностные списки;

• хвостовая рекурсия, оптимизация последнего вызова;

• накапливающие параметры;

• моделирование массивов с помощью предикатов functor иагд.