chapter01.tex

\chapter{Введение}
\label{ch:1}

Когда программисту на C для решения определенной задачи требуется
эффективная структура данных, часто он или она могут просто найти
подходящее решение в одном из многих учебников или справочников. К
сожалению, для программистов на функциональных языках вроде
Стандартного ML или Haskell такая роскошь недоступна.  Хотя большинство
справочников стараются быть независимы от языка, независимость эта
получается только в смысле Генри Форда: программисты свободны выбрать
любой язык, если язык этот императивный.\footnote{%
  Генри Форд однажды сказал о цветах автомобилей Модели T:
  <<[Покупатели] могут выбрать любой цвет, при условии, что он черный.>>
}
Чтобы несколько исправить этот дисбаланс, в этой книге я рассматриваю
структуры данных с функциональной точки зрения. В примерах программ я
использую Стандартный ML, однако эти программы нетрудно перевести на
другие функциональные языки, например, Haskell или Lisp. Версии наших
программ на Haskell можно найти в Приложении~\ref{app:A}.

\section{Функциональные и императивные структуры данных}

Методологические преимущества функциональных языков хорошо известны
\cite{Backus1978,Hughes1989,HudakJones1994}, но тем не менее
большинство программ по-прежнему пишутся на императивных языках вроде
C. Кажущееся противоречие легко объяснить тем, что исторически
функциональные языки проигрывали в скорости своим более традиционным
аналогам, однако этот разрыв сейчас сужается.  По широкому фронту
задач был достигнут впечатляющий прогресс, начиная от базовой техники
построения компиляторов и заканчивая глубоким анализом и оптимизацией
программ.  Однако одну особенность функционального программирования не
исправить никакими ухищрениями со стороны авторов компиляторов~---
использование слабых или несоответствующих задаче структур данных. К
сожалению, имеющаяся литература содержит относительно мало рецептов
помощи в этой области.

Почему оказывается, что функциональные структуры данных труднее
спроектировать и реализовать, чем императивные? Здесь две основные
проблемы. Во-первых, с точки зрения проектирования и реализации
эффективных структур данных, запрет функционального программирования
на деструктивное обновление (т.,~е., присваивание) является
существенным препятствием, подобно запрету для повара использовать
ножи. Как и ножи, деструктивные обновления при неправильном
употреблении опасны, но, будучи пущены в дело должным образом,
чрезвычайно эффективны.  Императивные структуры данных часто
существенным образом полагаются на присваивание, так что в
функциональных программах приходится искать другие подходы.

Второе затруднение состоит в том, что от функциональных структур
ожидается большая гибкость, чем от их императивных аналогов.  В
частности, когда мы производим обновление императивной структуры
данных, мы, как правило, принимаем как данность, что старая версия
данных более недоступна, в то время как при обновлении функциональной
структуры мы ожидаем, что как старая, так и новая версия доступны для
дальнейшей обработки. Структура данных, поддерживающая несколько
версий, называется \term{устойчивой}{persistent}, в то время как
структура данных, позволяющая иметь лишь одну версию в каждый момент
времени, называется \term{эфемерной}{ephemeral}
\cite{Driscoll-etal1989}. Функциональные языки программирования обладают тем
интересным свойством, что \emph{все} структуры данных в них
автоматически устойчивы. Императивные структуры данных, как правило,
эфемерны. В тех случаях, когда требуется устойчивая структура,
императивные программисты не удивляются, что она получается более
сложной и, возможно, даже асимптотически менее эффективной, чем
эквивалентная эфемерная структура.

Более того, теоретики установили нижние границы, которые показывают,
что в некоторых ситуациях функциональные языки по своей природе менее
эффективны, чем императивные \cite{BenAmramGalil1992, Pippenger1996}.  В свете
перечисленного, функциональные структуры данных иногда кажутся
похожими на танцующего медведя, о котором говорится: <<поразительна не
красота его танца, а то, что он вообще
танцует!>> Однако на практике ситуация совсем не так безнадежна. Как
мы увидим, часто оказывается возможным построить функциональные
структуры данных, асимптотически столь же эффективные, как лучшие
императивные решения.

\section{Энергичное и ленивое вычисление}

Большинство (последовательных) функциональных языков программирования
можно отнести либо к \term{энергичным}{strict}, либо к
\term{ленивым}{lazy}, в зависимости от порядка вычислений.  Какой из
этих порядков предпочтительнее~--- тема, обсуждаемая функциональными
программистами подчас с религиозным жаром.  Различие между двумя
порядками вычисления наиболее ярко проявляется в подходах к вычислению
аргументов функции. В энергичных языках аргументы вычисляются
прежде тела функции. В ленивых языках вычисление аргументов управляется
потребностью; исходно они передаются в функцию в невычисленном виде, и
вычисляются только тогда, когда (и если!) их значение нужно
для продолжения работы.  Кроме того, после однократного вычисления
значение аргумента кэшируется, так что если оно потребуется снова, его
можно получить из памяти, а не перевычислять заново.  Такое
кэширование называется \term{мемоизация}{memoization}
\cite{Michie1968}.

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

Оба порядка вычисления влияют на проектирование и анализ структур
данных. Как мы увидим, энергичные языки могут описать структуры с
жёсткой оценкой времени выполнения в худшем случае, но не с амортизированной
оценкой, а в ленивых языках описываются амортизированные структуры
данных, но не рассчитанные на худший случай. Чтобы описывать обе
разновидности структур, требуется язык, поддерживающий оба
порядка вычислений. Мы получаем такой язык, расширяя Стандартный ML
примитивами для ленивого вычисления, как описано в Главе~\ref{ch:4}.

\section{Терминология}

Любой разговор о структурах данных содержит опасность возникновения путаницы,
поскольку у термина \term{структура данных}{data structure} есть по
крайней мере четыре различных связанных между собой значения.

\begin{itemize}
\item \emph{Абстрактный тип данных} (то есть,
  \emph{тип и набор функций над этим типом}). Для этого значения мы
  будем пользоваться словом \term{абстракция}{abstraction}.
\item \emph{Конкретная реализация абстрактного типа данных}. Для этого
  значения мы используем слово
  \term{реализация}{implementation}. Однако от реализации мы не требуем
  воплощения в коде~--- достаточно детального проекта.
\item \emph{Экземпляр типа данных, например, конкретный список или
    дерево}. Для такого экземпляра мы будем использовать слово
  \term{объект}{object} или \term{версия}{version}. Впрочем,
  для конкретных типов часто бывает свой термин. Например, стеки и
  очереди мы будем называть просто стеками и очередями.
\item \emph{Сущность, сохраняющая свою идентичность при
    изменениях}. Например, в интерпретаторе, построенном на основе
  стека, мы часто говорим о <<стеке>>, как если бы это был один
  объект, а не различные версии в различные моменты времени. Для этого
  значения мы будем использовать выражение \term{устойчивая
    сущность}{persistent identity}.  Нужда в этом возникает прежде
  всего при разговоре об устойчивых структурах данных; когда мы
  говорим о различных версиях одной и той же структуры, мы имеем в
  виду, что они все имеют одну и ту же устойчивую сущность.
\end{itemize}
Грубо говоря, абстракциям в Стандартном ML соответствуют сигнатуры,
реализациям~--- структуры или функторы, а объектам или версиям~---
значения. Хорошего аналога понятию устойчивой сущности в Стандартном
ML нет.\footnote{%
  Устойчивая сущность эфемерной структуры данных может быть
  реализована как ссылочная ячейка, но для моделирования устойчивой
  сущности устойчивой структуры данных такого подхода недостаточно.
}

Термин \term{операция}{operation} перегружен подобным же образом; он
обозначает и функции, предоставляемые абстрактным типом данных, и
конкретные применения этих функций. Мы пользуемся словом
\emph{операция} только во втором значении, а для первого употребляем
слова \term{функция}{function} или \term{оператор}{operator}.

\section{Наш подход}

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

\section{Обзор книги}

Книга состоит из трех частей. Первая (Главы~\ref{ch:2} и \ref{ch:3})
служит введением в функциональные структуры данных.
\begin{itemize}
\item В Главе~\ref{ch:2} обсуждается, как функциональные структуры
  данных добиваются устойчивости.
\item Глава~\ref{ch:3} описывает три хорошо известных структуры
  данных~--- левоориентированные кучи,
  биномиальные кучи и красно-черные деревья,~--- и показывает, как их
  можно реализовать на Стандартном ML.
\end{itemize}
Вторая часть (Главы~\ref{ch:4}--\ref{ch:7}) посвящена соотношению
между ленивым вычислением и амортизацией.
\begin{itemize}
\item В Главе~\ref{ch:4} кратко рассматриваются основные понятия
  ленивого вычисления и вводится синтаксис, которым мы пользуемся для
  описания ленивых вычислений в Стандартном ML.
\item Глава~\ref{ch:5} служит введением в основные методы
  амортизации. Объясняется, почему эти методы не работают при
  анализе устойчивых структур данных.
\item Глава~\ref{ch:6} описывает связующую роль, которую ленивое
  вычисление играет при сочетании амортизации и устойчивости, и дает
  два метода анализа амортизированной стоимости структур данных,
  реализованных через ленивое вычисление.
\item В Главе~\ref{ch:7} демонстрируется, какую выразительную мощь дает
  сочетание энергичного и ленивого вычисления в одном языке.
  Мы показываем, как во многих случаях можно получить структуру данных
  с жёсткими характеристиками производительности из структуры с
  амортизированными характеристиками, если систематически запускать
  преждевременное вычисление ленивых компонент структуры.
\end{itemize}
В третьей части книги (Главы~\ref{ch:8}--\ref{ch:11}) исследуется
несколько общих методик построения функциональных структур данных.
\begin{itemize}
\item В Главе~\ref{ch:8} описывается \term{ленивая перестройка}{lazy
    rebuilding}, вариант идеи \term{глобальной перестройки}{global
    rebuilding} \cite{Overmars1983}.  Ленивая перестройка значительно
  проще глобальной, но в результате получаются структуры с
  амортизированными, а не с жёсткими характеристиками.  Сочетание
  ленивой перестройки с методиками планирования из Главы~\ref{ch:7}
  часто позволяет восстановить жёсткие характеристики.
\item В Главе~\ref{ch:9} исследуются \term{числовые
    представления}{numerical representations}~--- представления
  данных, построенные по аналогии с представлениями чисел (как
  правило, двоичных чисел). В этой модели нахождение эффективных
  процедур вставки и изъятия соответствует выбору таких вариантов
  двоичных чисел, где добавление или вычитание единицы занимает
  константное время.
\item Глава~\ref{ch:10} рассматривает \term{развёртку структур
    данных}{data-structural bootstrapping} \cite{Buchsbaum1993}. Эта
  методика существует в трех вариантах: \term{структурная
    декомпозиция}{structural decomposition}, когда решения без
  ограничений строятся на основе ограниченных решений,
  \term{структурная абстракция}{structural abstraction}, когда
  эффективные решения строятся на основе неэффективных, и
  \term{развёртка до составных типов}{bootstrapping to aggregate
    types}, когда реализации с атомарными элементами развёртываются до
  реализаций с составными элементами.
\item В Главе~\ref{ch:11} описывается \term{неявное рекурсивное
    замедление}{implicit recursive slowdown}, ленивый вариант метода
  \term{рекурсивного замедления}{recursive slowdown} Каплана и
  Тарьяна \cite{KaplanTarjan1995}.  Подобно ленивой перестройке,
  неявное рекурсивное замедление значительно проще обычного
  рекурсивного замедления, но вместо жёстких характеристик дает лишь
  амортизированные. Как и в случае ленивой перестройки, часто жёсткие
  характеристики можно восстановить с помощью расписаний.
\end{itemize}

Наконец, Приложение~\ref{app:A} включает в себя перевод большинства
программных реализаций этой книги на Haskell.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "pfds"
%%% End: