- •Лекция №1 Логическая программа: основные конструкции
- •Лекция №2 Программирование баз данных
- •Структурированные и абстрактные данные
- •Логические программы и модель реляционной базы данных
- •Лекция №3 Рекурсивное программирование
- •Построение рекурсивных программ
- •Бинарные деревья
- •Работа с символьными выражениями
- •Лекция №4 Вычислительная модель логических программ
- •Абстрактный интерпретатор логических программ
- •Лекция №5 Теория логических программ Операционная и декларативная семантика. Интерпретация
- •Корректность программы
- •Лекция №6 Анализ структуры термов
- •Типовые предикаты
- •Составные термы
- •Лекция №7 Металогические предикаты
- •Типовые металогические предикаты
- •Сравнение неосновных термов
- •Использование переменных в качестве объектов
- •Доступность метапеременных
- •Лекция №8 Внелогические предикаты
- •Лекция №9 Недетерминированное программирование
- •Недетерминизм с произвольным выбором альтернативы и недетерминизм с неизвестным выбором альтернативы
- •Лекция №10 Неполные структуры данных
- •Лекция №11 Программирование второго порядка
- •Лекция №12 Методы поиска
- •Лекция №13 Нечеткая логика. Обработка нечетких данных
- •Лекция №14 Constraint-пролог: операционная семантика Программирование в ограничениях
- •Лекция №15 Применение логического программирования в задачах искусственного интеллекта. Тест Тьюринга.
- •Лекция №16 Введение в функциональное программирование
- •Лекция №17 Рекурсивные функции и лямбда-исчисление а.Черча
- •Лекция №18 Функциональные языки программирования Свойства функциональных языков
- •Лекция №19 Программирование в функциональных обозначениях Структуры данных и базисные операции
- •Типы в функциональных языках
- •Лекция №20 Представление и интерпретация функциональных программ Программная реализация
Построение рекурсивных программ
До сих пор нами не давалось никаких пояснений, как же строятся примеры логических программ. Можно утверждать, что искусство построения логических программ постигается в процессе обучения и усвоения, во многом определяемом практикой. Для простых отношений наилучшая аксиоматизация обладает эстетическим изяществом, которое делает корректность их записи очевидной. Однако в процессе решения упражнений читатель мог заметить разницу между пониманием и построением изящных логических программ.
В этом разделе приводятся дополнительные примеры программ, обрабатывающих списки. При их обсуждении, однако, основное внимание уделяется тому, как могут быть построены эти программы. Разъясняются два принципа: как совместить процедурное и декларативное понимание и как разрабатывать программы по нисходящей методологии.
Мы приводили два типа понимания предложений: процедурное и декларативное, Как же они сочетаются при построении программ? На практике при программировании пользуются процедурным пониманием. Однако при рассмотрении проблемы истинности и определении значения программы применяется декларативное понимание. Один из способов совмещения этих двух типов понимания в логическом программировании состоит в процедурном построении программ с последующей интерпретацией результата как декларативного утверждения. Мы создаем программу, ориентируясь на предписанное использование программы, и далее выясняем, имеют ли различные использования программы декларативный смысл. Применим эти рассуждения к программе удаления элементов из списка.
Первый и наиболее важный шаг состоит в определении подразумеваемого значения отношения. Для удаления элемента из списка требуются три аргумента: удаляемый элемент 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 понимается аналогично. Исходный факт пустой список разбивается на два пустых списка.