Требования к исполнению

Основные требования связаны с особенностями языка Пролог. К числу главных особенностей относится так называемая инвертируемость прологовских предикатов (процедур). В процедурах и функциях большинства операторных языков программирования (Паскаль, Си и др.) фиксируется, какие параметры (аргументы) являются входными (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 и другие.