TURBO PROLOG. Терёхин В.В. - 113 стр.

      Первая попытка удовлетворить правило insert_sort осуществляется с
первым вариантом правила
      insert_sort([],[]).
Для удовлетворения правила оба списка должны быть пустыми. Второй ва-
риант правила insert_sort трактует список как комбинацию головы списка и
его хвоста. Внутренние унификационные процедуры Турбо-Пролога пыта-
ются сделать пустым исходный список. Устранение элементов списка на-
чинается с головы списка и осуществляется рекурсивно.
      Та часть правила, которая производит удаление элементов, выглядит
так:
      insert_sort([X|Tail],Sorted_list) : - insert_sort(Tail, Sorted_Tail).
      По мере того как Турбо-Пролог пытается удовлетворить первое из
правил, происходят рекурсивные вызовы insrt_sort, при этом значениями Х
последовательно становятся все элементы исходного списка, которые затем
помещаются в стек. В результате применения этой процедуры список ста-
новится нулевым. Теперь первый вариант правила insert_sort производит
обнуление выходного списка, и таким образом правилу придается форма
      insert_sort([],[]).
      Далее, после того как удовлетворен первый вариант правила
insert_sort, Турбо-Пролог пытается удовлетворить второе правило из тела
insert_sort - правило insert. Переменной Х сначала присваивается первое взя-
тое из стека значение, 9, а правило insert принимает форму
      insert(9,[],[9]).
      Теперь удовлетворено и второе правило из тела insert_sort - пра-
вило insert (его второй вариант), поэтому происходит возврат на один круг
рекурсии insert_sort. Из стека извлекается следующий элемент, 3, и испы-
тывается первый вариант insert, а значит и правило упорядочивания
      asc_order(X,Y) :- X>Y.
      Переменная Х здесь имеет значение 3, Y - значение 9, само правило
имеет вид
      asc_order(3,9) :- 3>9.
      Так как оно неуспешно (3 на самом деле не больше, а меньше 9), то
вместе с ним неуспешен и первый вариант insert. При помощи второго
варианта insert 3 вставляется в выходной список слева от 9:
      insert(3,[9],[3,9]).
Происходит возврат к insert_sort, теперь оно имеет форму
      insert_sort([3,9],[3,9]).
      На следующем круге рекурсии происходит вставка очередного эле-
мента из стека, а именно 7. В начале работы на этом круге правило insert
имеет вид
      insert(7,[3,9],_).
Сначала происходит сравнение 7 и 3,
      asc_order(7,3):- 7>3.
Так как данное правило успешно, то элемент 3 убирается в стек, и insert
вызывается рекурсивно еще раз, но уже с хвостом списка - [9] :


                                                                         113