В рамках данной статьи начнем работать над вопросом “что такое данные?”, разберемся с тем, как с помощью абстракции и композиции составлять из простых элементов сложные, и выделим роли, которые данные играют в разработке программного обеспечения.
Введение
Если в нашем распоряжении есть функции, которые являются объектами первого класса, то мы можем формировать уровни абстракции, позволяющие нам строить вычисления, обладающие все более общими свойствами. Этот подход можно перенести и на второй столп программирования – данные. Используя абстракцию и композицию можно строить составные данные, которые обеспечивают большую выразительность и универсальность решения, а также являются инструментом для управления сложностью в проекте.
На сегодняшний день, наиболее мощным инструментом для построения абстракций является ООП. Мы не будем затрагивать эту область. Вместо этого постараемся использовать минимальный набор инструментов.
Материал данной статьи во много опирается на SICP.
Данные
Если попытаться максимально абстрактно посмотреть на процесс работы любой современной программы, то можно сказать, что единственное, что они все делают – это превращают один набор цифр в другой. Да и сами программы тоже являются наборами цифр, которые располагаются в определенном месте в памяти (RAM либо жесткий диск). Чтобы убедиться в этом, достаточно открыть файл с данными, либо программу для их обработки в любом шестнадцатеричном редакторе, и то, что мы увидим, будет просто набор байт. Представленное понимание, того, что есть данные и программы, определяется фон Неймановской архитектурой, которая лежит в основе любого (почти) компьютера, а в теоретическом плане этому подходу близка Машина Тьюринга.
На самом деле все гораздо сложнее и интереснее, о представлении данных в зависимости от теоретической базы, которую мы используем, будет рассказано в следующей статье.
Для наших текущих задач, выбранного описания будет достаточно. Это идею можно представить в виде диаграммы:
Но с таким представлением данных сложно работать. Перешагнув через несколько уровней абстрагирования (набор байт в памяти -> именование ячейки или группы ячеек ->…) мы придем к определению из SICP: “данные – это то, что определяется некоторым набором селекторов и конструкторов, а также некоторыми условиями, которым эти процедуры должны удовлетворять, чтобы быть правильным представлением”. Существует еще более абстрактный подход к тому, как определять, что такое данные: метод абстрактных моделей (Хоар), алгебраическая спецификация (Зиллес, Гоген и др.)), но мы остановимся на приведенном определении.
Из этой формулировки могут быть непонятны слова: селектор и конструктор. Конструктор – это функция для создания экземпляра данных. Селекторы – функции для извлечения составляющих элементов из экземпляра.
Для примера возьмем список из языка Python: в нем конструктор – это функция list(), можно, конечно, объявить набор данных, перечислив элементы в квадратных скобках, но хочется более формально проиллюстрировать принцип. Селектором будет метод __get_item__().
>>> a = list([1, 2, 3]) >>> a [1, 2, 3] >>> a.__getitem__(0) 1 >>> a.__getitem__(2) 3
Если говорить в терминологии ООП, то конструктор – это конструктор класса, а селекторы – это методы.
Абстракция данных
Теперь поговорим более подробно про абстракции данных, которые полезны при разработке программного обеспечения. В зависимости от решаемой задачи абстракция может выполнять ту или иную роль.
Роль первая: Барьеры
Абстракция позволяет нам не думать о внутренней реализации, когда мы работаем с элементам, предоставляемыми ею. То есть мы отделяем место, где данные используются, от места, где они создаются.
В качестве примера рассмотрим работу с комплексными числами. Создадим свою реализацию библиотеки для работы с такого типа числами.
Во-первых, нам нужен конструктор, построим его:
def make_complex(a, b): return (a, b)
В него мы передаем действительную и мнимую части.
Теперь реализуем селекторы, которые извлекают действительную и мнимую части из комплексного числа.
def real(c): return c[0] def img(c): return c[1]
В данном случае мы намеренно опускаем проверки, сейчас нам интересен сам принцип.
Построим операции сложения, вычитания, умножения и деления.
def add_complex(c1, c2): return (real(c1) + real(c2), img(c1) + img(c2)) def sub_complex(c1, c2): return (real(c1) - real(c2), img(c1) - img(c2)) def mul_complex(c1, c2): rl = real(c1) * real(c2) - img(c1) * img(c2) im = real(c1) * img(c2) + img(c1) * real(c2) return (rl, im) def div_complex(c1, c2): if real(c2) == 0 and img(c2) == 0: return None else: den = real(c2) * real(c2) + img(c2) * img(c2) rl_num = real(c1) * real(c2) + img(c1) * img(c2) im_num = img(c1) * real(c2) - real(c1) * img(c2) return (rl_num / den, im_num / den)
Этого набора функций достаточно для того, чтобы строить комплексные числа и выполнять с ними различные арифметические действия:
>>> c1 = make_complex(3, 7) >>> c2 = make_complex(11, 5) >>> real(c1) 3 >>> img(c1) 7 >>> add_complex(c1, c2) (14, 12) >>> sub_complex(c1, c2) (-8, 2) >>> mul_complex(c1, c2) (-2, 92) >>> div_complex(c1, c2) (0.4657534246575342, 0.4246575342465753)
В качестве базовых элементов мы использовали двухэлементные кортежи, которые предоставляет Python.
Может возникнуть необходимость использовать более высокоуровневую абстракцию. Например, в случае, если мы будем строить систему, которая должна уметь выполнять арифметические операции над любыми видами чисел, тогда функции верхнего уровня могут носить имена add, sum, и т.д., а внутри себя распознавать, что за тип числа был им передан (целое число, число с плавающей точкой, комплексное, рациональное и т.п.) и вызывать соответствующую функцию, относящуюся к заданному типу.
Таким образом, мы на каждом следующем уровне возводим барьер, скрывающий реализацию и предоставляющий все более общий интерфейс для работы с данными.
Роль вторая: Интерфейс
Данные могут выступать в роли интерфейса. Как правило, это используется в системах с потоковой обработкой, где имеется большое количество функций для преобразования данных, но при этом тип данных не меняется. Такой подход получил широкое распространение в области машинного обучения и анализа данных. Строить конвейеры вычислений в этой области – это обычная практика.
Приведем пример. Допустим у нас есть какой источник данных: файл на диске или интернет ресурс, наша задача извлечь данные, провести над ними ряд преобразований и отправить в алгоритм обучения модели, в этом случае поток обработки может выглядеть следующим образом:
- извлечение данных
- выделение признаков
- очистка данных
- разделение данных на обучающую и тестовую выборки
- масштабирование данных
- обучение модели
Если мы берем экосистему Python, то скорее всего тип данных будет либо DataFrame из библиотеки Pandas, либо ndarray из Numpy.
Структуры данных
Под структурой данных будем понимать составные данные, полученные из однотипных (атомарных) элементов. В качестве такого элемента возьмем пару.
Пара
Пара является идеальным строительным блоком для представления списковых и иерархических структур данных для демонстрации идей использования абстракции и композиции.
Для наших экспериментов построим конструктор, который создает кортеж из двух элементов:
def pair(x, y): return (x, y)
Теперь нам нужны селекторы – функции, которые будут извлекать первый и второй элементы. По аналогии с языком Haskell назовем их fst и snd:
def fst(p): return p[0] def snd(p): return p[1]
Для того, чтобы не усложнять реализацию мы не будем приводить код проверки того, что преданное значение является парой и т.п.
>>> p = pair(3, 7) >>> fst(p) 3 >>> snd(p) 7
Свойство замыкания
Для начала разберемся со свойством замыкания, которое нам пригодится для построения списковых и иерархических структур данных. Замыкание, в рамках данной статьи, мы будем понимать в математическом смысле. Приведем пример на натуральных числах. Множество натуральных чисел замкнуто относительно операций сложения и умножения. То есть, если мы сложим (или умножим) два натуральных числа, то результат будет натуральное число. Сколько бы раз не повторялась эта процедура, мы не сможет выйти за рамки множества натуральных чисел. В этом случае, говорят, что множество натуральных чисел замкнуто относительно операции сложения (умножения):
1+2 = 3 3+(1+2) = 6
Функциональный вариант:
> add(1, 2) > 3 > add(3, add(1, 2)) > 6
Заметим, что множество натуральных чисел не замкнуто относительно операции вычитания, так, например 5-8=-3, уже не является натуральным числом.
Пары, которые мы определили выше, замкнуты относительно операции конструирования пары, то есть результат примирения конструктора пары к другим конструкторам является парой:
>>> p1 = pair(1,2) >>> p1 (1, 2) >>> p2 = pair(3, p1) >>> p2 (3, (1, 2))
Списковые структуры
Структуру, которую мы сейчас построим, называют связный список. Для наглядности, в качестве элементов пар, будем использовать числа типа int.
На рисунке ниже представлена диаграмма, иллюстрирующая организацию списка, который мы будем собирать из пар.
Построим список, состоящий из чисел [1, 2, 3, 4, 5]:
pair(1, pair(2, pair(3, pair(4, pair(5, None))))
Несмотря на то, что выглядит эта запись довольно громоздко, свою задачу она выполняет. Вопрос производительности не будем рассматривать.
Можно предложить следующий конструктор списка:
def lst(*x): if len(x) == 1: return (x[0], None) else: return pair(x[0], lst(*x[1:]))
Пример использования:
>>> pl = lst(1, 2, 3, 4, 5) >>> pl (1, (2, (3, (4, (5, None)))))
Теперь построим селектор для доступа к произвольному элементу списка.
def lst_sel(ps, n):
if isinstance(p, tuple):
if n == 0:
return fst(ps)
else:
return lst_sel(snd(ps), n-1)
else:
raise Exception("Selector error")
Получим данные из созданного ранее списка:
>>> lst_sel(pl, 0) 1 >>> lst_sel(pl, 3) 4 >>> lst_sel(pl, 10) ... Exception: Selector error
Можно написать довольно много различных полезных утилит для работы с этой структурой данных. Например, функция, которая определяет количество элементов в списке:
def lst_lenght(ps): if snd(ps) is None: return 1 else: return 1 + lst_lenght(snd(ps))
Применим ее к нашему списку:
>>> lst_lenght(pl) 5
Для пользователя, работающего со структурами pair или lst, не важно как они устроены “под капотом” (если не брать в расчет производительность и безопасность), важен только интерфейс (конструкторы и селекторы): pair, fst, snd для пары и lst, lst_sel для списка.
Иерархические структуры
Классическим примером иерархической структуры являются деревья. Воспользуемся парой для построения дерева следующего вида:
>>> t1 = pair((pair(1, 2), 3), pair(4, 5)) >>> t1 (((1, 2), 3), (4, 5))
По аналогии со списком можно построить ряд инструментов для работы с деревьями. Для примера реализуем функцию, определяющую количество листьев в дереве:
def leavs(p): if p is None: return 0 if not is_pair(p): return 1 else: return leavs(fst(p)) + leavs(snd(p))
>>> t1 (((1, 2), 3), (4, 5)) >>> leavs(t1) 5
Заключение
В рамках данной статьи мы постарались проиллюстрировать подход использования абстракции и композиции для построения составных данных и сделали акцент на той роли, которую может играть абстракция в разработке ПО. Изложенные идеи носят скорее иллюстративный характер. Несомненно, уровень абстракций в крупных проектах, достигаемый за счет мощи ООП или ФП подходов, будет гораздо более масштабным.
P.S.
Вводные уроки по “Линейной алгебре на Python” вы можете найти соответствующей странице нашего сайта. Все уроки по этой теме собраны в книге “Линейная алгебра на Python”.
Если вам интересна тема анализа данных, то мы рекомендуем ознакомиться с библиотекой Pandas. Для начала вы можете познакомиться с вводными уроками. Все уроки по библиотеке Pandas собраны в книге “Pandas. Работа с данными”.
