Построение рекурсивных программ

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

В этом разделе приводятся дополнительные примеры программ, обрабатывающих списки. При их обсуждении, однако, основное внимание уделяется тому, как могут быть построены эти программы. Разъясняются два принципа: как совместить процедурное и декларативное понимание и как разрабатывать программы по нисходящей методологии.

Мы приводили два типа понимания предложений: процедурное и декларативное, Как же они сочетаются при построении программ? На практике при программировании пользуются процедурным пониманием. Однако при рассмотрении проблемы истинности и определении значения программы применяется декларативное понимание. Один из способов совмещения этих двух типов понимания в логическом программировании состоит в процедурном построении программ с последующей интерпретацией результата как декларативного утверждения. Мы создаем программу, ориентируясь на предписанное использование программы, и далее выясняем, имеют ли различные использования программы декларативный смысл. Применим эти рассуждения к программе удаления элементов из списка.

Первый и наиболее важный шаг состоит в определении подразумеваемого значения отношения. Для удаления элемента из списка требуются три аргумента: удаляемый элемент X, список L1, в который может входить X, и список L2, из которого удалены все вхождения элемента X. Подходящей реляционной схемой является delete (L1,X,L2), Естественное значение состоит из всех основных примеров, в которых список L2 получен из списка L1 удалением всех вхождений X.

При построении программы проще всего рассматривать некоторое конкретное использование. Рассмотрим вопрос delete([a.b.c.b],b,X]), типичный пример нахождения результата удаления элемента из списка. Ответом служит Х=[а,с] Программа будет рекурсивной по первому аргументу. Начнем с процедурного подхода.

Рассмотрим рекурсивную часть. Обычный вид рекурсивного аргумента для списка есть [Х | Xs]. Следует рассмотреть две возможности: Х является удаляемым элементом и Х отличен от удаляемого элемента. В первом случае искомым результатом будет рекурсивное удаление Х из Xs. Подходящим правилом является

delete([X | Xs],X,Ys)  delete(Xs,X,Ys).

Сменим подход на декларативный: “Удаление Х из списка [X | Xs] приводит к Ys, если удаление Х из Xs приводит к Ys”. Условие совпадения головы списка и удаляемого элемента задано с помощью общей переменной в заголовке правила,

Второй случай, в котором удаляемый элемент отличен от головы списка – X, подобен первому. Искомым результатом будет список, голова которого X, а хвост получен рекурсивным удалением элемента. Нужное правило:

delete([X | Xs],Z, [X [ Ys])  X  Z, delete(Xs,Z,Ys).

Декларативное понимание: “Удаление Z из списка [Х \ Xs] равно [X | Ys], если Z отлично от Х и удаление Z из Xs приводит к Ys. В отличие от предыдущего правила условие неравенства головы списка и удаляемого элемента явно задано в теле правила.

Исходный случай задается непосредственно. Из пустого списка не удаляется ничего. результатом будет также пустой список. Это выражается фактом delete([ ],Х,[ ]). Полная программа скомпонована в виде программы 3.18.

delete (List.X.HasNoXs) 

список HasNoXs получен в результате удаления всех вхождений элемента Х из списка List.

delete([X | Xs],X,Ys)  delete(Xs,X,Ys).

delete([X Xs],Z,[X | Ys])  X  Z, delete(Xs,Z,Ys).

delete([ ],X,[ ]).

Программа 3.18. Удаление всех вхождений элемента из списка.

Давайте взглянем на написанную программу и рассмотрим другие возможности формулировок. Опуская условие Х = Z во втором правиле программы 3.18, получим иной вариант отношения delete. Значение этого варианта менее естественно, так как в этом случае может быть удалено любое количество вхождений. Например, все цели delete([a,b,c,b],b.[a,c]), delele([a,b,c],[a,c,b]), delete([a,b,c,b] ,b,[a,b,c]) и delete([a,b,b],b,[a,b,с,b]) принадлежат значению этого варианта.

И значение программы 3,18, и значение указанного выше варианта содержат примеры, в которых удаляемый элемент вообще не входит в исходный список, например, выполнено delete([a],b,[a]). Существуют приложения, в которых это нежелательно. Программа 3.19 определяет отношение select (X,L1,L2), в котором случай списка, не содержащего элемент X, рассматривается иным образом. Значением отношения select (X,L1,L2) является множество всех основных примеров, в которых список L2 получается из списка L1 удалением ровно одного вхождения X.

select(X,HasXs,OnelessXs) 

список OneLessXs получен в результате удаления одного вхождения Х из списка HasXs.

select(X,[X|Xs],Xs).

select(X,[Y | Ys],[Y | Zs])  select(X,Ys,Zs).

Программа 3.19. Выделение элемента из списка.

Эта программа является гибридом программы 3.12 для отношения member и программы 3.18 для отношения delete. Декларативное понимание программы: «Выделение элемента Х из списка [X | Xs] приводит к Xs или выделение Х из списка [Y|Ys] приводит к [Y|Zs], если выделение Х из списка Ys приводит к Zs». Мы используем отношение select как вспомогательное отношение в приводимой далее “наивной” программе сортировки списков.

Основное внимание при программировании следует уделять нисходящей методологии разработки, совмещаемой с пошаговым уточнением. Говоря нестрого, данная методология состоит в постановке общей задачи, разделении ее на подзадачи и решении отдельных частей. Программирование “сверху вниз” – один из наиболее естественных методов построения логических программ. Наше описание программ, на протяжении всей книги будет в основном соответствовать этой методологии Оставшаяся часть раздела посвящена описанию построения двух программ сортировки списков: сортировка перестановкой и быстрая сортировка. Внимание будет сосредоточено на применении нисходящей методологии.

Логическая спецификация сортировки списка состоит в нахождении упорядоченной перестановки исходного списка. Эта спецификация может быть непосредственно записана в виде логической программы. Основная реляционная схема – sort(Xs,Ys), здесь Ys – список, содержащий элементы списка Xs, расположенные в порядке возрастания:

sort(Xs,Ys)  permutation (Xs,Ys), ordered (Ys).

Цель верхнего уровня – сортировка – теперь разделена. Далее нам следует определить отношения permutation и ordered.

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

ordered([X]).

ordered([X,Y | Ys])  X  Y, ordered ([Y | Ys]).

Программа для отношения permutation сложнее. Один из способов перестановки списка состоит в недетерминированном выделении того элемента, который будет первым в переставленном списке, и рекурсивной перестановке остатка списка. Мы выразим этот способ в виде логической программы для отношения permutation, использовав программу 3.19 для отношения select. Факт утверждает, что единственная перестановка пустого списка совпадает с ним самим:

permutation(Xs,[Z | Zs]) 

select (Z,Xs,Ys), permutation (Ys,Zs),

permutation([ ],[ ]).

Другой процедурный подход к порождению перестановок списков состоит в рекурсивной перестановке хвоста списка и вставке головы списка в произвольное место. Этот подход тоже допускает прямую запись. Исходный факт совпадает с фактом предыдущей версии:

permutation ([X | Xs],Zs)  permutation(Xs,Ys),

insert(X,Ys,Zs).

permutation([ ],[ ]).

Предикат insert может быть определен в терминах программы 3.19.

insert(X,Ys,Zs)  select(X,Zs,Ys).

Обе процедурные версии отношения permutation имеют ясную декларативную интерпретацию.

Скомпонованная программа 3.20 – это программа “наивной” сортировки (так мы назвали сортировку перестановкой). Она является примером подхода “порождения и проверки”, который будет подробно обсужден в гл. 14.

Проблема сортировки списков глубоко изучена. На практике сортировка перестановкой не является хорошим методом сортировки списков. Применение стратегии “разделяй и властвуй” приводит к намного лучшим алгоритмам. Идея состоит в

sort(Xs.Ys) 

список Ys – упорядоченная перестановка списка Xs.

sort(Xs,Ys)  permutation(Xs,Ys),ordered(Ys).

permutation(Xs,[Z | Zs]) 

select(Z.Xs,Ys),permutation(Ys,Zs).

permutation([ ],[ ]).

ordered([X]).

ordered([X,Y | Ys])  X  Y, ordered([Y | Ys]).

Программы 3.20. Сортировка перестановкой.

сортировке списка путем разделения его на две части, рекурсивной сортировке частей и последующем объединении частей для получения отсортированного списка. Методы разделения и объединения должны быть уточнены. Имеются два крайних случая. В первом разделение производится сложно, зато объединение просто. Этот подход и принят в алгоритме быстрой сортировки. Ниже приведена соответствующая логическая программа быстрой сортировки. Во втором случае объединение производится сложно, зато разделение просто. Этот подход используется в сортировке слиянием, которая приведена в качестве упражнения (4) в конце раздела, и в сортировке вставкой, представленной программой 3.21.

sorl(Xs,Ys) 

список Ys – упорядоченная перестановка списка Xs.

sort([X I Xs],Ys)  sort(Xs,Zs),insert(X,Zs,Ys).

sort([ ],[ ]).

insert(X,[ ],[X]).

insert(X,[Y | Ys],[Y | Zs])  X > Y,insert(X,Ys,Zs).

insert(X,[Y | Ys].[X,Y | Ys])  X  Y.

Программа 3.21. Сортировка вставкой.

В сортировке вставкой один элемент (обычно первый) удаляется из списка. Остаток списка сортируется рекурсивно, затем элемент вставляется в список с сохранением порядка в списке.

Идея быстрой сортировки состоит в разделении списка путем выбора произвольного элемента списка и дальнейшего разбиения списка на элементы, меньшие выбранного, и элементы, большие выбранного. Отсортированный список состоит из меньших элементов, за которыми следует выбранный элемент и далее -большие элементы. В описываемой программе в качестве основы разбиения берется первый элемент.

Программа 3.22 определяет отношение sort с помощью алгоритма быстрой сортировки. Рекурсивное правило для sort означает: “Уs есть отсортированный вариант [X | Xs], если списки Littles и Bigs – результат разбиения списка Xs на элементы, меньшие Х и большие Х соответственно; Ls и Bs – результаты рекурсивной сортировки Littles и Bigs, и Ys есть результат соединения Ls и [X |Bs]”.

Программа разбиения списка описывается непосредственно и подобна программе удаления элементов. Следует рассматривать два случая: голова текущего списка (1) меньше и (2) больше элемента, определяющего разбиение. Декларативное понимание первого предложения partition: “Разбиение списка с головой Х и хвостом Xs в соо тветствии с элементом У дает списки [Х | Litlles} и Bigs, если Х не больше У,

sort(Xs.Ys)

список Ys – упорядоченная перестановка Xs

quicksort([X | Xs],Ys) 

partition(Xs,X,Littles,Bigs),

quicksort(Littles,Ls),

quicksort(Bigs,Bs),

append(Ls,[X | Bs],Ys). Quicksort([ ],[ ]).

partition([X | Xs],Y,[X | Ls],Bs)  X  Y, partition(Xs,Y,Ls,Bs).

partition([X | Xs],Y,Ls,[X | Bs]) 

X > Y,partition(Xs.Y,Ls,Bs).

partition([ ],Y,[ ],[ ]).

Программа 3.22. Быстрая сортировка.

и разбиение списка Xs в соответствии с Y дает списки Littles и Bigs”. Второе предложение для отношения partition понимается аналогично. Исходный факт пустой список разбивается на два пустых списка.