Требования к исполнению
Основные требования связаны с особенностями языка Пролог. К числу главных особенностей относится так называемая инвертируемость прологовских предикатов (процедур). В процедурах и функциях большинства операторных языков программирования (Паскаль, Си и др.) фиксируется, какие параметры (аргументы) являются входными (input), какие выходными (output), т.е. фиксируется направление передачи значений этих аргументов. Прологовский же предикат обычно допускает многообразное использование, т.е. один и тот же аргумент может быть как входным (при одних вычислениях), так и выходным (при других вычислениях) - это связано с декларативным пониманием предиката как отношения между объектами. Например, предикат member (E, L), определяемый следующими предложениями
member (E, [E| L]).
member (E, [Z| L]):- member (E, L).
и истинный, если E есть элемент списка L, допускает следующие варианты использования:
?-member (b, [a, b, c]): значения обоих аргументов заданы, результат вычислений есть истинность данного отношения;
?-member (Х, [a, b, c]): задано значение только второго аргумента, результатом вычислений (значение Х) могут быть всевозможные элементы заданного списка;
?-member (b, Y): задан лишь первый аргумент, результат вычислений (Y) - любой список, который можно составить из элементов b.
Зафиксированные направления передачи значений аргументов предиката (внутрь/вовне или input/output) часто называют образцом или прототипом передачи (flow pattern), для его записи используются латинские буквы i и o, а также скобки. Для рассмотренного предиката member соответствующие прототипы записываются так: (i, i), (o, i), (i, o). Таким образом, инвертируемый предикат - это предикат, допускающий несколько образцов передачи.
Другая часто встречающаяся особенность предикатов Пролога - недетерминированность. Предикат называется недетерминированным, если его вычисление может дать более одного решения (результата). Точнее следует говорить о недетерминированность (или детерминированности) вычислений предиката при определенном прототипе передачи значений аргументов. Например, для предиката member недетерминированными являются вычисления при прототипах (o, i) и (i, o).
Перечислим теперь требования к разработке пролог-программы:
1. При программировании и отладке следует определить все возможные прототипы передачи аргументов для всех 20 предикатов программы и поместить в тексте программы рядом с записью каждого предиката строку комментария, содержащую все обнаруженные прототипы. Прототипы, приводящие к недетерминированным вычислениям, необходимо пометить особо.
2. Для недетерминированных предикатов subset, path, short_path, min_path исключить возможность порождения дважды одного и того же результата (решения). Например, недопустимо возникновение дважды одного и того же пути во множестве решений предиката path.
3. Предикаты flatten_tree, short_path, min_path работы с деревьями и графами должны быть запрограммированы эффективно. Для реализации flatten_tree потребуется вместо обычного использовать разностный вариант предиката append или же технику накапливающего параметра; а для реализации предикатов поиска короткого и минимального пути в графе необходим выбор подходящих алгоритмов перебора вершин графа.
4. Для всех предикатов работы с деревьями и графами требуется заготовить тестовые данные, демонстрирующие различные результаты их работы во всех возможных прототипах.
5. При реализации предиката sort допускается любой метод и алгоритм сортировки, кроме метода пузырька: сортировка вставкой (включением), выбором, слиянием, быстрая сортировка и др.
6. Поскольку цель задания - освоение основ логического программирования, то в программе запрещается использовать нелогические предикаты, имеющие побочные эффекты: free, bound, read, assert, retract и другие.