Декларативное программирование

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]

© 2003 И.А. Дехтяренко

5.5. Абстракции данных.

Абстракция данных - достаточно популярная методология программирования. Основная идея состоит в том, чтобы отделить способ использования составных объектов данных от подробностей того, каким образом они созданы из более простых объектов, подобно тому, как функциональная абстракция разделяет способ использования функции и детали её реализации в терминах более примитивных функций.

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

Последняя фраза нуждается в уточнении. Что означает «тот же самый тип данных»? Что такое вообще «тип данных»? Существует множество подходов к этому вопросу. Давайте рассмотрим в качестве примера набор операций с рациональными числами. Предположим, что нам необходимо складывать, вычитать, умножать, делить и сравнивать рациональные числа. Каждое рациональное число определяется парой целых чисел - числителем и знаменателем. Однако, вряд ли кому-нибудь придет в голову описывать функции типа:

числитель-суммы(числитель1 знаменатель1 числитель2 знаменатель2).

Конечно, мы можем выбрать представление рациональных чисел, например в виде пар целых чисел, и определить функции на парах чисел, но методология абстракции данных предполагает, что наши функции должны оперировать абстрактными объектами типа «рациональное число». Каждое такое число создаётся функцией-конструктором (rat-num n d). Соответственно, функции-селекторы (numer r)и (denom r), позволяют получить числитель и знаменатель рационального числа r. В терминах этих функций мы можем определить основные операции арифметики рациональных чисел.

(define (rat+ r1 r2)
   (rat-num (+ (* (numer r1)(denom r2))
               (* (numer r2)(denom r1)))
            (* (denom r1)(denom r2))))

(define (rat=? r1 r2)
   (= (* (numer r1)(denom r2))
      (* (numer r2)(denom r1))))

и т.д.

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

(define rat-num cons )
(define numer car )
(define denom cdr )

Мы можем представить структуру всей системы следующим образом.

Интерфейсные функции (конструкторы и селекторы) выступают в качестве «барьеров абстракции» разделяющих различные «уровни» системы¹. Программы, использующие рациональные числа, манипулируют ими исключительно в терминах функций «общего пользования» определённых пакетом рациональных чисел: (rat+, rat-... ). Эти функций, в свою очередь, реализованы исключительно в терминах конструкторов и селекторов, которые сами реализованы в терминах пар. Подробности того, как реализованы объекты каждого уровня, несущественны для остальной части системы. Заметьте, что это относится и к парам. Нас не интересует, как устроены пары, мы оперируем ими исключительно в терминах функций cons, car, и cdr.

Использование абстракции данных в Лиспе определяется только методологией. Система же никак не контролирует следование принципам абстракции. Вообще, в сообществе Лисп - программистов эта методология не очень популярна и преобладает тенденция повсеместно использовать списки (ULFE - Use List For Everything).

Идея абстракции данных даёт много преимуществ. Во-первых, она помогает разбить большую систему на меньшие части, которые могут разрабатываться независимо. Во-вторых, значительно облегчается процесс развития программы. Любая сложная структура данных может быть представлена различными способами. Естественно, выбор представления данных влияет на программы, которые работают с этими данными и, таким образом, если представление в дальнейшем будет изменено, соответственно придется изменять все такие программы. Ограничение зависимости от представления несколькими интерфейсными функциями значительно уменьшает объем изменений. Например, предположим, что мы решили хранить числа в сокращённой форме, чтобы избежать возможного роста их составляющих. Всё, что для этого потребуется – изменить функцию-конструктор.

(define (rat-num n m)
   (let ((g (gcd n m)))
      (cons (/ n g) (/ m g))))

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

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

Упражнение.

Реализуйте (или хотя бы спроектируйте) систему символьного дифференцирования, следуя методологии абстракции данных.

Вернёмся к вопросу о «типе данных». Когда мы реализовывали арифметику рациональных чисел, мы не делали никаких предположений об «устройстве» этих чисел. Всё, что мы о них знали, это то что они создаются функцией rat-num из пары целых чисел, и что для любого рационального числа можно получить его числитель и знаменатель функциями numer и denom. Таким образом, наша информация о представлении рациональных чисел сводилась к знанию о трёх функциях: rat-num, numer и denom. Очевидно, не всякий набор из трех функций может использоваться для представления рациональных чисел. Мы должны гарантировать, что если мы создаем рациональное число из пары целых чисел, то полученные из него числитель и знаменатель должны находиться в том же отношении, что и исходные числа. То есть, для любых целых чисел n и m должно выполняться следующее условие.

(numer (rat-num n m)) / (denom (rat-num n  m)) =  n / m

С другой стороны, это единственное условие, которое накладывается на rat-num, numer и denom, и любые три функции ему удовлетворяющие могут быть использованы для осуществления рациональных чисел. Например, мы могли бы представлять рациональное число n/m, как целое число sign(n)*sign(m)*2^|n|*3^|m|.

Итак, мы можем рассматривать тип данных как некоторый набор конструкторов и селекторов вместе с определёнными условиями, которым эти функции должны удовлетворять.

С этой точки зрения можно рассматривать  не только объекты данных высокого уровня, типа рациональных чисел, но и примитивных объекты. Рассмотрим понятие пары. Единственное условие, которому должны удовлетворять операции, cons, car и cdr состоит в том что для любых объектов x и y,

(car (cons x y)) = x и (cdr (cons x y)) = y.

Значит, любая тройка функций, удовлетворяющих этому условию, может использоваться для осуществления пар. Отсюда следует, что мы можем реализовать, cons, car и cdr вообще не используя никаких структур данных!

(define (cons x y)  (lambda (a) (if a x y))
(define (car z) (z #t))
(define (cdr z) (z #f))

Такое использование функций не вполне соответствует нашему интуитивному понятию о данных. Однако, мы можем показать, что это вполне законный способ реализовать пары. Всё, что для этого нужно сделать - проверить, что эти три процедуры удовлетворяют данному выше условию. А если так, наше «функциональное» представление пар ничем не хуже любого другого, и если мы оперируем парами, только посредством cons, car и cdr, мы не сможем отличить это представление от того, которое использует «настоящие» структуры данных.

Упражнение.

Убедитесь в том, что определённые таким образом функции cons, car, cdr удовлетворяют необходимым условиям

Этот пример демонстрирует, что способность обращаться с функциями как с объектами автоматически обеспечивает способность представлять составные данные. Более того, она же обеспечивает способность представлять примитивные данные. Например, как нетрудно убедиться, следующие определения обеспечивают корректную реализацию логического типа данных.

(define true  (lambda (x y) x)
(define false (lambda (x y) y)
(define (if c t f) (c t f)

Упражнение.

Придумайте «функциональное» представление целых чисел.

Конечно, использование такого рода «данных» на практике равносильно попыткам программировать на машине Тьюринга. Смысл последних примеров - показать, что понятие функции является достаточно мощной концепцией, для выражения любых аспектов программирования.

Представления множеств

Иногда реализация данных очевидна. Так, трудно предложить что-нибудь лучшее чем пара для представления рациональных чисел. В других случаях это далеко не так. Рассмотрим такую абстракцию, как множество. Мы можем определить тип «множество», описав операции, которые должны использоваться на множествах. Допустим, нам потребуются следующие операции.

(in? x s)

определяет, является ли данный объект x элементом множества.

(empty)

пустое множество.

(singleton x)

множество, состоящее из единственного элемента x.

(join s x)

множество, которое содержит все элементы множества s, а также добавляемый элемент x.

(union s1 s2)

объединение двух множеств.

(intersect s1 s2)

пересечение двух множеств.

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

Выбор представления для множеств не столь очевиден, как для рациональных чисел. Например мы можем представлять их списками или деревьями, причём различными способами.

«Функциональное» представление множеств.

Начнём с самого, пожалуй, необычного способа. Будем представлять множество предикатом, определяющим принадлежность объекта данному множеству. Тогда операция in? становится тривиальной

(define (in? x s) (s x))

Пустое множество - всюду ложный предикат, а одноэлементное множество - предикат, проверяющий равен ли его аргумент единственному элементу множества.

(define (empty)  (lambda (t) #f))
(define (singleton x)  (lambda (t) (equal? t x)))

Определение остальных операций очевидно.

(define (union s1 s2)
   (lambda (t) (or (s1 t) (s2 t))))

(define (intersect s1 s2)
   (lambda (t) (and (s1 t) (s2 t))))

(define (join s x)
   (union (singleton x) set))

Представление множеств списками.

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

Пустое множество представлено пустым списком, а одноэлементное множество - списком из одного элемента.

(define (empty)  (list))
(define (singleton x) (list x)

Для проверки принадлежности объекта множеству необходимо сравнить его со всеми элементами списка.

(define (in? x s)
   (and (not (null? s))
        (or (equal? x (car s))
            (in? x (cdr s)))

Используя in?, мы можем определить присоединение объекта к множеству. Если объект, который нужно добавить уже принадлежит множеству, мы просто возвращаем множество. Иначе, мы добавляем объект к списку, который представляет множество:

(define (join s x)
  (if (in? x s)
      s
      (cons x s)))

Объединение множеств получается последовательным присоединением элементов одного множества к другому.

(define (union s1 s2)
  (if (null? s2)
      s1
      (union  (join s1 (car s2)) (cdr s2)))))

Для вычисления пересечения множеств мы можем использовать рекурсивную стратегию. Если мы знаем, как найти пересечение  s2 и (cdr s1), то мы должны только решить, включать ли в него (car s1). Но это зависит от того, является ли (car s1) элементом s2. 

(define (intersect s1 s2)
  (cond ((or (null? s1) (null? s2)) nil)
        ((in? (car s1) s2)
            (cons (car s1)
                  (intersect (cdr s1) s2)))
        (else (intersect (cdr s1) s2))))

Выбирая представление, мы часто руководствуемся соображениями эффективности. Попробуем оценить эффективность наших операций. Так как все они используют in?, скорость этой функции определяет эффективность реализации множеств в целом. Чтобы проверить, является ли объект элементом множества, вероятно, придется просматривать весь список представляющий множество. Следовательно, сложность этой процедуры растет как O(n). То же верно и для join, которая использует эту операцию. Функции union и intersect проверяют каждый элемент одного множества на вхождение в другое, поэтому их  сложность растет как произведение размеров множеств, или как O(n²) для двух множеств размера n.

Мы можем ускорить операции присоединения и объединения, если не будем требовать уникальности вхождения в список каждого элемента множества и определим.

(define (join s x) (cons x s))

Упражнение.

Оцените эффективность изменённой таким образом реализации.

Другой способ ускорить операции множествами - изменить представление так, чтобы элементы множества были перечислены в возрастающем порядке. Чтобы сделать это, нам потребуется некоторое отношение порядка между объектами. Для простоты рассмотрим только случай, когда элементы множества суть числа, так что можно сравнивать элементы, используя =, > и <.

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

(define (in? x s)
   (and (not (null? s))
        (or (= x (car s))
            (and (> x (car s)
                 (in? x (cdr s)))

Можно ожидать, что среднее число шагов будет около n/2. Это все еще рост порядка O(n), но всё же это  представление экономит в среднем половину операций по сравнению с предыдущим. Процедура добавления несколько усложняется, но опять же дает среднем ускорение в два раза.

(define (join s x)
  (cond ((null? s) (list x))
        ((= x (car s)) s)
        ((< x (car s)) (cons x s))
        ((> x (car s)) (cons (car s) (join (cdr s) x))))

Более внушительное ускорение мы получаем для объединения и пересечения множеств. Прежде, выполняя эти операции, мы должны были полностью просматривать список s1 для каждого элемента s2. Но с новым представлением, мы можем использовать более быстрые методы. Пусть x1 и x2 - начальные элементы  двух списков s1 и s2 . Если x1 = x2, то объединение получается присоединением x1 к объединению хвостов списков. Пусть теперь x1 < x2. Так как x2 - самый маленький элемент в s2,  x1 не содержится в s2. Следовательно, мы можем построить объединение s1 и s2, присоединяя x1 к объединению (cdr s1) и s2. Рассуждения для случая x1 > x2 аналогичны.

(define (union s1 s2)
   (cond
      ((null? s1) s2)
      ((null? s2) s1)
      (else
         (let ((x1 (car set1)) (x2 (car set2)))
            (cond ((= x1 x2) (cons x1 (union (cdr s1) (cdr s2))))
                  ((< x1 x2) (cons x1 (union (cdr s1)  s2)))
                  ((> x1 x2) (cons x2 (union s1 (cdr s2) ))))))))

Для этой процедуры требуется шагов не более чем сумма размеров s1 и s2, а это уже рост порядка O(n), а не O(n²) как прежде - значительное ускорение, даже для множеств умеренного размера.

Упражнение.

Напишите для данного представления процедуру intersect сложности порядка O(n).

Представление множеств деревьями.

Мы можем добиться ещё большей эффективности, упорядочивая элементы множества в форме двоичного  дерева. Каждый узел дерева содержит один элемент множества (значение или «метку» узла), и два поддерева (возможно пустые). «Левое» поддерево содержит элементы меньшие, а «правое» - большие чем значение узла.

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

(define (node val left right) (list val left right))
(define value car)
(define left cadr)
(define right caddr)
(define empty-tree nil)
(define empty-tree? null?)

Мы представляем множества в терминах деревьев, а деревья в терминах списков, то есть формируем абстракцию данных, используя другую абстракцию данных. Процедуры node, value и т.п. можно рассматривать как определение абстракции «двоичное дерево».

Упражнение.

Придумайте другое представление двоичных деревьев.

Пустое множество представлено пустым деревом, а одноэлементное множество - деревом, содержащим добавляемый элемент и две пустые ветви.

(define (empty)  (empty-tree))
(define (singleton x) (node x empty-tree empty-tree))

Для проверки, содержится ли элемент в множестве, мы сравниваем его со значением вершины. Если элемент  меньше этого значения, мы знаем, что он может находиться только в левом поддереве, если больше - в правом. Если дерево «сбалансировано», размер каждого из поддеревьев будет составлять примерно половину размера дерева. Таким образом, следует ожидать, что число шагов, необходимых для поиска в дереве размера n растет как O(log n). Для больших множеств, это будет существенное ускорение по сравнению с предыдущими представлениями.

Используя описанную стратегию, можем записать процедуру:

(define (in? x s)
   (and (not (empty-tree? s))
        (or (= x (value s))
            (and (< x (value s) (in? x (left s)))
            (and (> x (value s) (in? x (right s)))

Добавление элемента к множеству также требует O(log n) шагов.

(define (join s x)
  (cond ((empty-tree? s) (singleton x))
        ((= x (value s)) s)
        ((< x (value s)) (node (value s) (join (left s) x)  (right s)))
        ((> x (value s)) (node (value s) (left s) (join (right s) x)))))

Упражнение.

Завершите реализацию множеств двоичными деревьями, то есть напишите процедуры объединения и пересечения.

Упражнение.

Скорее всего, полученные процедуры будут иметь сложность O(n*log n). Но это хуже, чем для упорядоченных списков. Нельзя ли получить более эффективные процедуры?

Рассматривая различные способы представления множеств, мы видели, как выбор представления объектов данных может оказать значительное воздействие на эффективность программ. Наше первое представление чрезвычайно неэффективное, но очень простое. Это позволяет использовать его (или другое простое представление, такое как неупорядоченные  списки) для первоначальной реализации. Скорее всего оно окажется неподходящим для реальной системы, но оно позволит проверить остальную часть системы. Позже, представление данных может измениться, на более сложное и эффективное. И если операции с данными производятся только посредством абстрактных селекторов и конструкторов, эта замена представления не потребует никаких изменений в остальной части системы.

Если представить на месте множеств какую-нибудь сложную базу данных, важность абстракции становится очевидной. Многие современные языки содержат явные средства поддержки абстракции данных, но, как мы могли видеть, использование этой методологии возможно и в Лиспе.

¹ В естественных науках словом «interface» обозначают границу раздела между двумя средами.

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]