Готовый перевод Concepts, Techniques and Models of Computer Programming / Концепции, Техники и Модели Компьютерного Программирования: Глава 3 - Техники Декларативного Программирования

“S’il vous plaˆıt... dessine-moi un arbre!”
"Пожалуйста, нарисуй мне дерево!"
- Свободная адаптация "Маленького принца" Антуана де Сент-Экзюпери
(1900 - 1944)

"Приятная черта в декларативном программировании в том, что вы можете написать описание и запустить его как программу. Противная черта в декларативном программировании заключается в том, что некоторые хорошие описания дают невероятно плохие программы. На декларативное программирование возлагается надежда на то, что вы можете перейти от описания к полезной программе не покидая сам язык."
- The Craft of Prolog, Richard O'Keefe (? - )

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

1 Концепцию "без состояний" иногда называют "иммутабельностью".

Почему декларативное программирование является важным

Декларативное программирование является важным из-за двух его свойств:

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

Аргументы

Декларативная операция

Результаты

Остальное вычисление

Рисунок 3.1: Декларативная операция внутри общего вычисления.

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

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

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

В декларативной программе взаимодействие между компонентами определяется исключительно входами и выходами компонентов. Рассмотрим программу с декларативным компонентом. Этот компонент можно понять основываясь только на нём самом и не понимая остальную программу. Усилия, затраченные на понимание всей программы равны сумме усилий затраченных на понимание этого и оставшихся других декларативных компонентов.

Определение

Программирование с рекурсией

Абстракция

Реальный мир

Модель

Процедурная

На данных

Что такое декларативность?

Итеративное и рекурсивное вычисление
Программирование со списками и деревьями

Управляющие абстракции
Высокоуровневое программирование

Абстрактные типы данных
Безопасные абстрактные типы данных

Эффективность по памяти и по времени
Структура программ с большой масштабируемостью
Недекларативные нужды

Ограничения и расширения
Отношения к остальным декларативным моделям

Рисунок 3.2: Структура главы

Если между компонентом и остальной программой существует более тесная связь, то компоненты нельзя понять независимо. Их нужно изучать вместе, и усилия, затраченные на понимание будут большими. Они могут быть (примерно) пропорциональными произведению усилий, затраченных на каждую часть. Для программ с большим числом тесно взаимодействующих компонентов сложность понимания растёт лавинообразно, делая понимание трудным или невозможным. Примером подобного тесного взаимодействия является многопоточная программа с разделяемым состоянием, как это показано в Главе 8.

Часто тесные взаимодействия оказываются необходимыми. Их нельзя "запретить законодательно" программируя в модели прямо не поддерживающей их (подробно освещено в Разделе 4.7). Но важный принцип в том, что они должны использоваться только при необходимости и никак иначе. Для соблюдения этого принципа необходимо чтобы компоненты были по возможности декларативными.

Написание декларативных программ

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

Другой пример декларативной комбинации - стандартное правило алгебры "равенство может быть замещено равенством". В языках программирования это свойство называется ссылочной прозрачностью. Оно очень сильно упрощает рассуждения о программах. Например, если мы знаем, что f(a) = a^2, то мы можем заменить f(a) выражением a^2 вне зависимости от того, где встречается f(a). Тогда равенство b = 7f(a)^2 преобразуется в b = 7a^4. Такое возможно из-за декларативности f(a); f(a) зависит только от его аргументов и не зависит от другого состояния вычисления.

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

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

Описательно

Программируемо

Наблюдательно

Определительно

Декларативная модель

Функциональное программирование

Логическое программирование

Рисунок 3.3: Классификация декларативного программирования

Структура главы

Эта глава описывает как писать практичные декларативные программы. Глава условно разделена на шесть частей, показанных на Рисунке 3.2. Первая часть определяет "декларативность". Вторая часть даёт обзор техник программирования. Третья и четвёртая части описывают процедурные абстракции и абстракции на данных. Пятая часть показывает как декларативное программирование взаимодействует с остальной средой вычисления. Шестая часть делает отступление для того, чтобы показать пользу декларативной модели и расположение декларативной модели по отношению к остальным моделям.

Пустой оператор

Последовательность операторов

Создание переменной

Привязка переменная-переменная

Создание значения

Таблица 3.1: Описательно-декларативный язык ядра

3.1 Что такое декларативность?

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

3.1.1 Классификация декларативного программирования

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

Описательная декларативность. Наименее выразительна. Декларативная "программа" только определяет структуры данных. Таблица 3.1 описывает язык такого уровня. Этот язык может определять только записи! Он содержит только первые пять определений языка ядра из Таблицы 2.1. Раздел 3.8.2 показывает как использовать этот язык для описания графического интерфейса пользователя. Другие примеры: язык форматирования, например, HTML дающий структуру документа и ничего не говорящий о том как его форматировать, или язык обмена информацией, например, XML, используемый для обмена информацией в открытом формате и всем легко доступный для чтения. Уровень описательности слишком слаб для написания общих программ. Но почему он интересен? Потому что он состоит из легко вычисляемых структур данных. Записи Таблицы 3.1, HTML и XML документы, и декларативный интерфейс пользователя в Разделе 3.8.2 могут быть легко созданы и изменены программой.

Программируемая декларативность. Выразительна также, как и машина Тьюринга 2. Например, Таблица 2.1 описывает язык этого уровня. Если хотите узнать больше о взаимосвязи между описательными и программируемыми уровнями, то смотрите введение в Главу 6.

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

Есть две фундаментально отличающиеся точки зрения на программируемую декларативность:

Описательная точка зрения, где декларативность является свойством реализации компонента. Например, для программ, написанных в декларативной модели гарантирована декларативность, поскольку здесь декларативность является свойством модели.

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

Эта книга использует обе точки зрения: описательную и наблюдательную. Когда нам будет интересно заглянуть внутрь компонента, тогда мы используем описательную точку зрения. Когда нам будет интересно поведение компонента, тогда мы используем наблюдательную точку зрения.

Особенно популярными стали два стиля описательного декларативного программирования: функциональное и логическое. В функциональном стиле мы говорим, что компонент определён и декларативен как математическая функция. Такие функциональные языки как Haskell и Standard ML следуют этому подходу. В логическом стиле мы говорим, что компонент определён и декларативен как логическое отношение. Логические языки, такие как Prolog и Mercury следуют этому подходу. Функциональными или логическими программами труднее манипулировать чем декларативными программами, но они всё также следуют простым алгебраическим законам 3. Декларативная модель, используемая в этой главе включает в себя и функциональный и логический стили.

3 Для программ не использующих не декларативные особенности этих языков.

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

3.1.2 Языки описаний

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

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

Языки спецификаций лежат за пределами этой книги.

3.1.3 Реализация компонент в декларативной модели

Комбинирование декларативных операций в соответствии с операциями декларативной модели всегда даёт в результате декларативную операцию. Этот раздел посвящён изучению этой особенности. Сначала мы более точно определим что значит декларативность для определений. Возьмём любое определение в декларативной модели. Разделим свободные идентификаторы переменных в определении на ввод и вывод. Затем возьмём любую привязку входных идентификаторов к частичным значениям и привязку идентификаторов выхода к не привязанным переменным, исполнение определения приведёт к одному из трёх результатов: (1) некоторые привязки выходных переменных, (2) приостановку работы или (3) исключение. Если определение декларативно, то для одних и тех же привязок входа результат всегда будет одним и тем же.

Например, рассмотрим определение Z=X. Положим что X - это вход и Z - это выход. Для любой привязки X к частичному значению исполнение этого определения привяжет Z к тому же частичному значению. Поэтому это определение декларативно.

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

if X>Y then Z=X else Z=Y end

декларативно. Три свободных идентификатора высказывания, X, Y, Z делятся на два входных идентификатора X и Y и на один выходной идентификатор Z. Далее, если X и Y будут привязаны к каким-либо частичным значениям, то произойдёт либо блокирование исполнения высказывания, либо привязка Z к тому же частичному значению. То есть, высказывание декларативно.

Мы можем применить такое рассуждение для всех операций в декларативной модели:

Первое, все базовые операции в декларативной модели декларативны. Сюда входят все операции для базовых типов, рассмотренные в Главе 2.

Второе, комбинирование декларативных операций с конструкциями декларативной модели даёт декларативную операцию. Следующие пять составных высказываний существуют в декларативной модели:

Последовательность высказывания.

Оператор local.

Оператор if.

Оператор case.

Объявление процедуры, то есть, высказывание <x>=<v>, где <v> - значение процедуры.

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

3.2 Итеративное вычисление

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

3.2.1 Общая схема

Важный класс итеративных вычислений начинается с начального состояния S0, далее выполняется столько трансформаций состояния, сколько необходимо для достижения конечного состояния Sfinal:

S0 → S1 → · · · → Sfinal

Итеративное вычисление этого класса может быть записано такой общей схемой:

fun {Sqrt X}
Guess=1.0
in
{SqrtIter Guess X}
end
fun {SqrtIter Guess X}
if {GoodEnough Guess X} then Guess
else
{SqrtIter {Improve Guess X} X}
end
end
fun {Improve Guess X}
(Guess + X/Guess) / 2.0
end
fun {GoodEnough Guess X}
{Abs X-Guess*Guess}/X < 0.00001
end
fun {Abs X} if X<0.0 then ̃X else X end end

Рисунок 3.4: Нахождение корней с помощью метода Ньютона (первая версия)

fun {Iterate Si }
if {IsDone Si } then Si
else Si+1 in
Si+1 ={Transform S i}
{Iterate Si+1 }
end
end

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

Положим исходный семантический стек равным [R={Iterate S0}].

Допустим, что {IsDone S0} возвращает false. Сразу после исполнения if, семантический стек станет таким: [S1={Transform S0}, R={Iterate S1}].

После выполнения {Transform S1}, семантический стек станет [R={Iterate S1}].

Мы увидели, что в семантическом стеке находится только один элемент в каждом рекурсивном вызове, а именно [R={Iterate Si+1}].

3.2.2 Итерации с числами

Хорошим примером итеративного вычисления является метод Ньютона для вычисления квадратного корня из вещественного положительного числа x. Идея заключается в том, чтобы начать с предположения g в качестве квадратного корня и итеративно улучшать предполагаемое число до тех пор, пока оно не станет достаточно точным. Улучшенное предполагаемое число g' - это среднее между g и x/g:

g0 = (g + x/g)/2.

Для того, чтобы убедиться, в том, что улучшенное предполагаемое число лучше, изучим разницу между предполагаемым числом и x:

√
 = g − x

Тогда разница между g' и x:

√
√
 0 = g 0 − x = (g + x/g)/2 − x = 2 /2g

Для сходимости, e' должно быть меньше чем e. Посмотрим, какие условия это налагает на x и на g. Условие e'<e это то же самое, что и e^2/2g<e, что то же самое, что и e<2g. (Предполагаем, что e>0, если это не так, то начинаем с e', которое всегда больше чем 0.) Подставляя определение e, мы получаем условие x+g>0. Если x>0 и инициализационное предполагаемое число g>0, то x+g>0 всегда истинно. Поэтому алгоритм всегда сходится.

Рисунок 3.4 показывает один способ определения метода Ньютона как итеративное вычисление. Функция {SqrtIter Guess X} вызывает {SqrtIter {Improve Guess X} X} до тех пор, пока Guess не станет удовлетворять условию {GoodEnough Guess X}. Очевидно, что это экземпляр общей схемы, поэтому данный алгоритм является итеративным вычислением. Улучшенное предполагаемое число вычисляется по формуле, данной выше. Проверкой на "достаточную пригодность" является |x - g^2|/x < 0.00001, то есть, квадратный корень должен быть точным до пятого знака. Проверка относительна, то есть, погрешность делится на x. Также мы можем использовать абсолютную проверку, например, что-то вроде |x - g^2| < 0.00001, где величина погрешности должна быть меньше чем некоторая константа. Почему применение относительной погрешности лучше при вычислении квадратных корней?

3.2.3 Использование локальных процедур

В Рисунке 3.4, описывающем реализацию метода Ньютона, определены несколько "вспомогательных" процедур: SqrtIter, Improve, GoodEnough и Abs. Эти процедуры используются как строительные блоки для главной функции Sqrt. В этом разделе мы обсудим где создавать вспомогательные процедуры. Базовый принцип в том, что вспомогательная процедура определяется как часть другой процедуры и не должна быть видимой отовсюду. (Мы используем слово "процедура" и для функции и для процедур.)

В этом примере Ньютона, SqrtIter нужен только внутри Sqrt, Improve и GoodEnough нужны только внутри SqrtIter, а функция-утилита Abs может использоваться всюду. Есть два основных способа для выражения этой видимости, с несколько отличающимися семантиками. Первый способ показан на Рисунке 3.5: вспомогательные процедуры определены внутри Sqrt в операторе local. Второй способ показан на Рисунке 3.6: каждая вспомогательная процедура определена внутри процедуры, которой требуется данная вспомогательная процедура

4 Мы не стали упоминать определение Abs для того чтобы избежать повторения.

local
fun {Improve Guess X}
(Guess + X/Guess) / 2.0
end
fun {GoodEnough Guess X}
{Abs X-Guess*Guess}/X < 0.00001
end
fun {SqrtIter Guess X}
if {GoodEnough Guess X} then Guess
else
{SqrtIter {Improve Guess X} X}
end
end
in
fun {Sqrt X}
Guess=1.0
in
{SqrtIter Guess X}
end
end

Рисунок 3.5: Нахождение корней с помощью метода Ньютона (вторая версия)

На Рисунке 3.5 есть компромисс между читаемостью и видимостью: Improve и GoodEnough можно определить локально только для SqrtIter. Что приведёт к двум уровням локальных определений, а это труднее для чтения. Мы приняли решение вставить все три вспомогательные процедуры в одно локальное определение.

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

Есть компромисс между вставкой вспомогательных определений извне и вставкой их внутрь главной процедуры.

Вставка снаружи (Рисунки 3.6 и 3.7) позволяет им видеть аргументы главных процедур как внешние ссылки в соответствии с правилом лексической области видимости (смотрите Раздел 2.4.3). Отсюда им требуется передавать меньше аргументов. Но при каждом вызове главной процедуры создаются новые вспомогательные процедуры. А значит, создаются новые значения процедур.

Вставка снаружи (Рисунки 3.4 и 3.5) означает, что значения процедур создаются единожды и для всех вызовов главной процедуры. Но тогда требуется больше аргументов для того, чтобы главная процедура могла передать информацию вспомогательным процедурам.

fun {Sqrt X}
fun {SqrtIter Guess X}
fun {Improve Guess X}
(Guess + X/Guess) / 2.0
end
fun {GoodEnough Guess X}
{Abs X-Guess*Guess}/X < 0.00001
end
in
if {GoodEnough Guess X} then Guess
else
{SqrtIter {Improve Guess X} X}
end
end
Guess=1.0
in
{SqrtIter Guess X}
end

Рисунок 3.6: Нахождение корней с помощью метода Ньютона (третья версия)

fun {Sqrt X}
fun {SqrtIter Guess}
fun {Improve}
(Guess + X/Guess) / 2.0
end
fun {GoodEnough}
{Abs X-Guess*Guess}/X < 0.00001
end
in
if {GoodEnough} then Guess
else
{SqrtIter {Improve}}
end
end
Guess=1.0
in
{SqrtIter Guess}
end

Рисунок 3.7: Нахождение корней с помощью метода Ньютона (четвёртая версия)

fun {Sqrt X}
fun {Improve Guess}
(Guess + X/Guess) / 2.0
end
fun {GoodEnough Guess}
{Abs X-Guess*Guess}/X < 0.00001
end
fun {SqrtIter Guess}
if {GoodEnough Guess} then Guess
else
{SqrtIter {Improve Guess}}
end
end
Guess=1.0
in
{SqrtIter Guess}
end

Рисунок 3.8: Нахождение корней с помощью метода Ньютона (пятая версия)

На Рисунке 3.7, новые определения Improve и GoodEnough создаются для каждой итерации SqrtIter, где само SqrtIter создаётся только единожды. Здесь предлагается хороший компромисс, где SqrtIter локален для Sqrt, а Improve и GoodEnough расположены внутри SqrtIter. Что в конечном итоге приводит к окончательному определению на Рисунке 3.8, которое мы считаем лучшим как со стороны эффективности, так и со стороны видимости.

3.2.4 От общей схемы к управляющей абстракции

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

fun {Iterate Si }
if {IsDone Si } then Si
else Si+1 in
Si+1 ={Transform S i}
{Iterate Si+1 }
end
end

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

fun {Iterate S IsDone Transform}
if {IsDone S} then S
else S1 in
S1={Transform S}
{Iterate S1 IsDone Transform}
end
end

Для использования этой абстракции, аргументы IsDone и Transform даны как одноаргументные функции. Передача функций как аргументов к функциям является частью множества программных техник под названием высокоуровневого программирования. Эти техники будут рассмотрены позже в Разделе 3.6. Мы можем сделать так, чтобы Iterate вела себя так же, как и SqrtIter передав ей функции GoodEnough и Improve. Эту идею можно записать так:

fun {Sqrt X}
{Iterate
1.0
fun {$ G} {Abs X-G*G}/X<0.00001 end
fun {$ G} (G+X/G)/2.0 end}
end

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

3.3 Рекурсивное вычисление

Итеративные вычисления - это частный случай более общей разновидности вычисления называемой как рекурсивное вычисление. Рассмотрим различия между ними. Напомним, что итеративное вычисление может рассматриваться как простой цикл, в котором отдельное действие повторяется некоторое число раз. Раздел 3.2 реализует это в декларативной модели вводя управляющую абстракцию, функцию Iterate. Эта функция вначале выполняет проверку. Если условие оказалось ложным, то выполняется действие и функция вызывает саму себя.

Рекурсия более общая концепция. Рекурсивная функция может вызывать себя в любом месте тела и может вызывать себя больше одного раза. В программировании, рекурсия проявляется в двух главных случаях: в функциях и в типах данных. Функция рекурсивна если её определение обладает хотя бы одним вызовом самой себя. Простой пример - абстракция итерации из Раздела 3.2. Тип данных рекурсивен если определён в терминах самого себя. Например, список определён в терминах более маленького списка. Эти две формы рекурсии сильно связаны между собой поскольку рекурсивные функции могут использоваться для вычислений с рекурсивными типами данных.

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

0! = 1
n! = n · (n − 1)! if n > 0

Это рекуррентное уравнение, то есть, факториал n! определён в терминах факториала с более маленьким аргументом, а именно, (n-1)!. Наивная программа следует этому математическому определению. Для вычисления {Fact N} есть две возможности, а именно N=0 или N>0. В первом случае возвращается 1. Во втором случае вычисляется {Fact N-1}, умножается на N и возвращается результат. Следующая программа выполняет этот алгоритм:

fun {Fact N}
if N==0 then 1
elseif N>0 then N*{Fact N-1}
else raise domainError end
end
end

Факториал большого числа определяется в терминах факториала меньшего числа. Поскольку все числа неотрицательны, то они больше нуля и вычисление будет заканчиваться.

Имейте ввиду, что данный факториал - частичная функция. Она не определена для отрицательных N. Программа отразит этот факт выдав исключение для отрицательного N. Определение в Главе 1 содержит ошибку поскольку для отрицательных N программа уйдёт в бесконечный цикл.

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

3.3.1 Рост размера стека

Данное определение факториала даёт вычисление, у которого максимальный размер стека пропорционален аргументу функции N. Воспользовавшись семантикой мы можем убедиться в этом. Вначале транслируем Fact в язык ядра:

proc {Fact N ?R}
if N==0 then R=1
elseif N>0 then N1 R1 in
N1=N-1
{Fact N1 R1}
R=N*R1
else raise domainError end
end
end

Сразу же мы можем сказать, что размер стека должен расти, поскольку умножение следует после рекурсивного вызова. Это значит, что в процессе рекурсивного вызова стек должен хранить информацию о множителе до тех пор, пока не будет возвращён рекурсивный вызов. Проследим за семантикой и вручную подсчитаем что случится при вычислении вызова {Fact 5 R}. Для ясности мы слегка упростим представление абстрактной машины подставив значение хранилища переменной в среду. Таким образом, среда {..., N -> n, ...} запишется как {..., N -> 5, ...} если в хранилище содержится {..., n = 5, ...}.

* Начальный семантический стек такой: [({Fact N R}, {N → 5, R → r0 })].

* При первом вызове:

[ ({Fact N1 R1}, {N1 → 4, R1 → r1 , ...}),
(R=N*R1 , {R → r0 , R1 → r1 N → 5, ...})]

* При втором вызове:

[ ({Fact N1 R1}, {N1 → 3, R1 → r2 , ...}),
(R=N*R1 , {R → r1 , R1 → r2 , N → 4, ...}),
(R=N*R1 , {R → r0 , R1 → r1 , N → 5, ...})]

* При третьем вызове:

[ ({Fact N1 R1}, {N1 → 2, R1 → r3 , ...}),
(R=N*R1 , {R → r2 , R1 → r3 , N → 3, ...}),
(R=N*R1 , {R → r1 , R1 → r2 , N → 4, ...}),
(R=N*R1 , {R → r0 , R1 → r1 , N → 5, ...})]

Ясно, что при каждом вызове стек возрастает на один оператор. Последним рекурсивным вызовом будет пятый вызов, непосредственно возвращающийся с r5 = 1. Когда завершится перемножение пяти множителей то мы получим окончательный результат r0 = 120.

3.3.2 Абстрактная машина, основанная на подстановках

Этот пример покажет, что абстрактная машина из Главы 2 может быть довольно громоздкой для ручного подсчёта. Причиной является то, что она хранит и идентификаторы переменных и переменные хранилища, используя среды для отображения из одного в другое. Что соответствует реальности; так абстрактная машина реализуется на настоящем компьютере. Но такой подход не очень хорош для ручного подсчёта.

В абстрактной машине мы можем сделать маленькое изменение, значительно упрощающее ручное вычисление. Идея заключается в том, чтобы заменить идентификаторы в определениях значениями на которые ссылаются эти идентификаторы. Такая операция называется подстановкой. Например, определение R=N*R1 преобразуется в r2=3*r3 после следующей подстановки: {R->r2, N->3, R1->r3}.

В абстрактной машине основанной на подстановке нет сред. Она непосредственно подставляет идентификаторы из хранилища в определения. Для примера с рекурсивным факториалом мы получим следующее:

[{Fact 5 r0}] - начальный семантический стек.

При первом вызове: [{Fact 4 r1 }, r0 =5*r1 ].

При втором вызове: [{Fact 3 r2}, r1 =4*r2 , r0=5*r1 ].

При третьем вызове: [{Fact 2 r3 }, r2 =3*r3, r1=4*r2 , r0 =5*r1].

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

Абстрактная машина на основе среды, определённая в Главе 2, верна реализации на настоящем компьютере, использующем среды. Однако, среды привносят дополнительный уровень косвенности, поэтому они трудны в ручном подсчёте.

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

Обе версии выполняют одни и те же привязки в хранилище и одни и те же манипуляции в семантическом стеке.

3.3.3 Конверсия рекурсивного вычисления в итеративное

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

R=(5*(4*(3*(2*(1*1)))))

достаточно поменять порядок чисел:

R=(((((1*5)*4)*3)*2)*1)

После чего вычисление можно выполнять инкрементально, начиная с 1*5. Получим 5, затем 20, затем 60, затем 120 и наконец 120. Итеративное определение факториала работающего по этому алгоритму будет таким:

fun {Fact N}
fun {FactIter N A}
if N==0 then A
elseif N>0 then {FactIter N-1 A*N}
else raise domainError end
end
end
in
{FactIter N 1}
end

Функция, выполняющая итерацию, FactIter, обладает вторым аргументом A. Этот аргумент имеет очень важное значение; без него невозможен итеративный факториал. Второй аргумент не появлялся в первом простом математическом определении факториала. Для внесения второго аргумента нам пришлось проделать некоторые рассуждения.

3.4 Программирование с рекурсией

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

Первый шаг - определение рекурсивных типов данных. В разделе 3.4.1 даны простые примечания, позволяющие нам определить самые важные рекурсивные типы данных.

Самый важный рекурсивный тип данных - это список. В Разделе 3.4.2 даны базовые техники программирования для списков.

Эффективные декларативные программы определяют итеративные вычисления. В Разделе 3.4.3 вводится понятие аккумуляторов, системной техники, позволяющей получить итеративное вычисление.

Довольно часто при вычислениях структуры данных строятся инкрементально. В Разделе 3.4.4 представлены списки различия - эффективная техника, применяемая в итеративных вычислениях.

Очередь - важный тип данных, родственный спискам. Раздел 3.4.5 показывает как эффективно реализовать очереди. Также вводится базовая идея амортизирующей эффективности.

Дерево - второй самый важный тип рекурсивных данных следующий за такими линейными структурами как списки и очереди. Раздел 3.4.6 даёт базовые техники программирования для деревьев.

Разделы 3.4.7 и 3.4.8 содержат два жизненных примера, алгоритм создания дерева и парсер, в этих примерах использованы много техник, описанных в этом разделе.

3.4.1 Нотация типа

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

Список Xs будет представлять либо nil, либо X|Xr, где Xr - это список. Также полезны другие подмножества типа запись. Например, бинарное дерево может быть определено как leaf(key:K value:V) или tree(key:K value:V left:LT right:RT), где LT и RT - оба бинарные деревья. Как нам записать эти типы сокращённым образом? Создадим нотацию, основанную на нотации контекстно-свободной грамматики использующейся для определения синтаксиса языка ядра. Нетерминалы будут представлять либо типы, либо значения. В качестве основы используем иерархию типов из Рисунка 2.16: все типы в этой иерархии будут доступны как предопределённые нетерминалы. Так <Value> и <Record> оба существуют, и поскольку они оба являются множествами значений, то мы можем сказать что <Record> c <Value>. Теперь мы можем определить списки:

hListi ::= hValuei ́| ́ hListi
| nil

Это означает, что значение <List> имеет одну или две формы. Либо X|Xr, где X - это <Value>, а <Xr> - это <List>. Либо атом nil. Данное определение является рекурсивным определением <List>. Оно может быть доказано, поскольку существует только один набор <List> являющийся меньшим множеством, удовлетворяющим этому определению. Доказательство лежит за пределом этой книги, но его можно найти в любой вводной в семантики книге, например [208]. Мы принимаем это меньшее множество как значение <List>. Интуитивно <List> может быть сконструирован начиная с nil и повторно применяя грамматическое правило к построению всё больших и больших списков.

Также мы можем определить списки, элементы которых являются заданными типами:

hList Ti ::= T ́| ́ hList Ti
| nil

Здесь T - это переменная типа и <List T> - это тип функции. Применение типа функции к любому типу возвращает тип списка для данного типа. Например, <List <Int>> - это список целочисленного типа. Заметим, что <List <Value>> равносилен <List> (поскольку они оба имеют одинаковые определения).

Определим бинарное дерево, ключи которого являются литералам и элементы являются типом T:

hBTree Ti::=
|
tree(key: hLiterali value: T
left: hBTree Ti right: hBTree Ti)
leaf(key: hLiterali value: T )

Типом процедуры является <proc $ {T1, ..., Tn}>, где T1, ..., Tn - типы аргументов. Тип процедуры иногда называют сигнатурой процедуры, поскольку она даёт некоторую ключевую информацию о процедуре в краткой форме. Типом функции является <fun {$ T1, ..., Tn}: T> что эквивалентно <proc {$ T1, ..., Tn, T}>. Например, тип <fun {$ <List> <List>}: <List>> - это функция, с двумя списковыми аргументами, возвращающая список.

Ограничения нотации

Этот тип нотации может определять много полезных наборов значений, но его выразительность определённо ограничена. Вот несколько случаев, когда нотация не достаточно хороша:

Нотация не может определять положительные целые числа, то есть, подмножество <Int> где все элементы больше нуля.

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

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

5 Очень похоже на тот способ, с помощью которого мы определили синтаксис языка в Разделе 2.1.1: контекстно-свободная нотация с дополнительными условиями по мере необходимости.

3.4.2 Программирование со списками

Значения списков очень краткие для создания и для работы с ними, к тому же они достаточно мощные для хранения любой разновидности комплексных структур данных. Язык Лисп изначально получил большую часть своей мощи из этой идеи [120]. Декларативное программирование со списками наследует мощь и простоту самих списков. В этом разделе описаны базовые техники программирования со списками:

Рекурсивное мышление: базовый подход заключается в решении проблем в терминах более маленьких версий проблемы.

Преобразование рекурсивных вычислений в итеративные: наивные списковые программы часто бывают затратными поскольку их размер стека растёт вместе с размером входных данных. Мы покажем как использовать трансформации состояний для практичных программ.

Корректность итеративных вычислений: простым и мощным способом рассуждения об итеративных вычислениях является использование инвариантов состояния.

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

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

Мыслить рекурсивно

Список - рекурсивная структура данных: она определена в терминах меньшей версии самой себя. Для написания функции производящей вычисления со списками нам нужно следовать этой рекурсивной структуре. Функция состоит из двух частей:

Базовый случай. Для малых списков (скажем, состоящей из нуля, одного или двух элементов) функция прямо вычисляет ответ.

Рекурсивный случай. Для больших списков функция вычисляет результат в терминах результатов меньших списков.

В качестве первого примера мы возьмём простую рекурсивную функцию, вычисляющую длину списка по следующей технике:

fun {Length Ls}
case Ls
of nil then 0
[] _|Lr then 1+{Length Lr}
end
end
{Browse {Length [a b c]}}

Сигнатура её типа - <fun {$ <List>}: <Int>>, функция принимает один список и возвращает целое число. Базовый случай - это пустой список nil, для которого функция возвращает 0. Рекурсивным случаем будет любой другой список. Если длина списка n, то длина хвоста списка равна n-1. Хвост меньше чем исходный список, поэтому программа конечна.

Наш второй пример - это функция, которая складывает вместе два списка Ls и Ms и, таким образом, получает третий список. Вопрос в том, на каком списке нам использовать индукцию? На первом или на втором? Мы считаем, что индукция должна быть выполнена на первом списке. Функция выглядит так:

fun {Append Ls Ms}
case Ls
of nil then Ms
[] X|Lr then X|{Append Lr Ms}
end
end

Сигнатура её типа - <fun {$ <List> <List>}: <List>>. Эта функция точно следует таким свойствам сложения:

• append(nil, m) = m

• append(x|l, m) = x | append(l, m)

При рекурсивном случае всегда будет вызываться Append с меньшим первым аргументом, поэтому программа завершится.

Рекурсивные функции и их предметная область

Определим функцию Nth для того, чтобы получить n-й элемент списка.

fun {Nth Xs N}
if N==1 then Xs.1
elseif N>1 then {Nth Xs.2 N-1}
end
end

Его тип <fun {$ <List> <Int>}: <Value>>. Не забывайте, что Xs либо nil, либо кортеж X|Y с двумя аргументами. Xs.1 даёт X и Xs.2 даёт Y. Что случится, если мы введём следующее выражение:

{Browse {Nth [a b c d] 5}}

Список содержит только четыре элемента. Попытка запросить пятый элемент равносильна попытке выполнить Xs.1 или Xs.2, в то время, когда Xs=nil. Результатом будет вызов исключения. Также исключение будет вызвано при не положительном N, например, когда N=0. Всё происходит потому, что в операторе if нет ветки else.

Пример общей техники при определении функций: всегда используйте операторы вызывающие исключения когда заданные значения находятся за пределы их предметных областей. Такой подход позволит повысить шансы того, что в целом функция породит исключение при её вызове с входными данными, лежащими за пределом предметной области. Мы не можем гарантировать что исключение всегда будет вызываться, например, в этом случае: {Nth 1|2|3 2} вернёт 2, в то время, когда 1|2|3 - не список. Трудно давать такие гарантии. Иногда их можно получить в статически типизированных языках.

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

fun {SumList Xs}
case Xs
of nil then 0
[] X|Xr then X+{SumList Xr}
end
end

Его тип <fun {$ <List <Int>>}: <Int>>. Поскольку SumList внутри использует целочисленный 0, то на вход должен подаваться список из целых чисел. Следующий вызов:

{Browse {SumList [1 2 3]}}

отобразит 6. Поскольку Xs может быть одним из двух значений, а именно nil или X|Xr, то естественно использовать оператор case. Как и в примере с Nth, неиспользование else породит исключение если аргумент будет находиться за предметной областью функции. Например:

{Browse {SumList 1|foo}}

вызовет исключение поскольку 1|foo не список, а определение SumList предполагает в качестве входных данных список.

Наивные определения часто медленны

Определим функцию для реверсирования элементов списка. Начнём с рекурсивного определения реверсированного списка:

Реверсирование nil равно nil.

Реверсирование X|Xs равно Z, где

реверсирование Xs даёт Ys и сложение Ys и [X] даёт Z.

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

fun {Reverse Xs}
case Xs
of nil then nil
[] X|Xr then
{Append {Reverse Xr} [X]}
end
end

Его тип <fun {$ <List>}: <List>>. Функция эффективна? Для нахождения ответа мы можем подсчитать время её исполнения на входном списке длины n. Мы можем выполнить такой подсчёт строго следуя техникам из Раздела 3.5. Но даже без этих техник мы можем интуитивно увидеть что происходит. Произойдёт n рекурсивных вызовов с последующими n вызовами Append. Каждый вызов Append получит список со средней длиной n/2. Общее время исполнения пропорционально n(n/2), а именно n2. Это довольно медленно. Мы могли бы ожидать, что реверсирование списка, не являющегося сложным вычислением, должно занять время пропорциональное длине входных данных, а не его квадрату.

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

Преобразование рекурсивных вычислений в итеративные вычисления

Рассмотрим как преобразовать рекурсивные вычисления в итеративные вычисления. Вместо использования Reverse мы возьмём более простую функцию, вычисляющую длину списка:

fun {Length Xs}
case Xs of nil then 0
[] _|Xr then 1+{Length Xr}
end
end

Обратите внимание, что функция SumList имеет ту же структуру. Время исполнения функции линейно, но размер стека пропорционален глубине рекурсии, равной длине Xs. Почему возникла эта проблема? Потому что сложение 1+{Length Xr} происходит после рекурсивного вызова. Рекурсивный вызов не последний, поэтому среда функции не может быть восстановлена после вызова.

Как мы можем посчитать длину списка с помощью итеративного вычисления с ограниченным размером стека? Для этого мы должны сформулировать проблему как последовательность трансформаций состояния. То есть, мы начинаем с состояния S0 и последовательно трансформируем его, получая S1, S2, ..., пока не достигнем конечного состояния Sfinal, которое будет содержать ответ. Для вычисления длины списка мы можем взять за состояние длину i уже просмотренной части списка. Вообще это только часть состояния. Вторая часть состояния - это ещё не просмотренный остаток списка Ys. Тогда полное состояние будет представлять пару (i, Ys). В общем промежуточном случае для состояния Si (где полный список Xs равен [e1 e2 ... en]) картина будет такая:

z
Xs
}|
{
e1 e 2 · · · ei ei+1 · · · en
|
{z
}
Ys

При каждом рекурсивном вызове, i будет увеличиваться на 1, а Ys будет уменьшаться на один элемент. Отсюда мы получаем функцию:

fun {IterLength I Ys}
case Ys
of nil then I
[] _|Yr then {IterLength I+1 Yr}
end
end

Его тип <fun {$ <Int> <List>}: <Int>>. Обратите внимание на разницу с предыдущим определением. Здесь сложение I+1 выполняется до рекурсивного вызова IterLength, являющегося последним вызовом. Мы определили итеративное вычисление.

В вызове {IterLength I Ys}, начальное значение I равно 0. Мы можем скрыть это значение определив IterLength как локальную процедуру. Таким образом конечное определение Length будет таким:

local
fun {IterLength I Ys}
case Ys
of nil then I
[] _|Yr then {IterLength I+1 Yr}
end
end
in
fun {Length Xs}
{IterLength 0 Xs}
end
end

Так определяется итеративное вычисление длины списка. Обратите внимание, что мы определили IterLength снаружи Length. Так мы обошли создание значения новой процедуры при каждом вызове Length. В определении IterLength внутри Length нет никаких преимуществ, поскольку он не использует аргумент Length-а Xs.

Для Reverse мы можем применить ту же технику что и для Length. В случае Reverse состояние использует реверс уже обработанной части списка вместо его длины. Обновление состояния выполняется просто: мы всего лишь вставляем новый элемент в голову списка. Начальное состояние равно nil. Что даёт нам следующую версию Reverse:

local
fun {IterReverse Rs Ys}
case Ys
of nil then Rs
[] Y|Yr then {IterReverse Y|Rs Yr}
end
end
in
fun {Reverse Xs}
{IterReverse nil Xs}
end
end

Эта версия Reverse обладает линейным временем работы, а также использует итеративное вычисление.

Корректность с инвариантами состояния

Докажем, что IterLength работает корректно. Мы используем общую технику, хорошо работающую для IterReverse и других итеративных вычислений. Идея в определении свойства P(Si) состояния для которого мы могли бы доказать его постоянную истинность, то есть, это свойство является инвариантом состояния. Если P выбрано правильно, то корректность вычисления следует из P(Sfinal). Для IterLength мы определяем P таким образом:

P ((i, Ys)) ≡ (length(Xs) = i + length(Ys))

где length(L) возвращает длину списка L. Здесь комбинируются i и Ys таким образом, что мы полагаем эту комбинацию инвариантом состояния. Для доказательства используем индукцию:

Для начала докажем P(S0). Доказательство непосредственно следует из S0=(0, Xs).

Предполагая что P(Si) и Si не является конечным состоянием, докажем P(Si+1). Доказательство следует из семантики оператора case и вызова функции. Запишем Si=(i, Ys). Мы находимся не в конечном состоянии, поэтому Ys не нулевой длины. Из семантики следует, что I+1 добавляет 1 к i и оператор case удаляет один элемент из Ys. Поэтому сохраняется P(Si+1).

Поскольку Ys уменьшается на один элемент при каждом вызове, то мы в конце концов достигнем конечного состояния Sfinal=(i, nil) и функция вернёт i. Поскольку length(nil)=0, то для P(Sfinal) следует что i=length(Xs).

Трудным шагом в этом доказательстве является выбор свойства P. Оно должно удовлетворять двум условиям. Первое, оно должно так комбинировать аргументы итеративного вычисления, что результат не должен меняться в процессе вычисления. Второе, оно должно быть достаточно устойчивым чтобы корректность вытекала из P(Sfinal). Практическое правило нахождения хорошего P - это ручное выполнение программы на нескольких малых случаях, после этого описать то, что произойдёт в общем случае.

Конструирование программ через следование типу

В предыдущих примерах списковых функций есть любопытное свойство. У них всех есть аргумент список, <List T>, определяемый так:

hList Ti
::=
nil
|
T ́| ́ hList Ti

и все они используют оператор case с такой формой:

case Xs
of nil then hexpri % Основной случай
[] X|Xr then hexpri % Рекурсивный случай
end

Что здесь происходит? Рекурсивная структура списковых функций точно следует рекурсивной структуре определения типа. Мы обнаружили, что это свойство почти всегда истинно для списковых функций.

Мы можем использовать это свойство как вспомогательное для написания списковых функций. Это свойство может оказать огромную помощь когда определения типов становятся усложнёнными. Например, напишем функцию, подсчитывающую количество элементов во вложенном списке. Вложенный список - это список, в котором каждый элемент сам может быть списком, например, [[1 2] 4 nil [[5] 10]]. Мы определим тип <NestedList T> следующим образом:

hNestedList Ti
::=||nil
hNestedList Ti ́| ́ hNestedList Ti
T ́| ́ hNestedList Ti

Для избежания двусмысленности, мы должны добавить условие: T не может быть ни nil, ни cons. Теперь напишем функцию {LengthL <NestedList T>}: <Int> подсчитывающую число элементов вложенного списка. Следуя определению типа мы получаем такой скелет:

fun {LengthL Xs}
case Xs
of nil then hexpri
[] X|Xr andthen {IsList X} then
hexpri % Рекурсивные вызовы для X и Xr
[] X|Xr then
hexpri % Рекурсивный вызов для Xr
end
end

(В третьем случае мы явно не говорим {Not {IsList X}} поскольку это следует из отрицания второго случая.) Здесь {IsList X} - это функция, которая проверяет является ли X nil-ом или cons-ом:

fun {IsCons X} case X of _|_ then true else false end end
fun {IsList X} X==nil orelse {IsCons X} end

После дополнения скелета мы получим следующую функцию:

fun {LengthL Xs}
case Xs
of nil then 0
[] X|Xr andthen {IsList X} then
{LengthL X}+{LengthL Xr}
[] X|Xr then
1+{LengthL Xr}
end
end

Два примера вызовов:

X=[[1 2] 4 nil [[5] 10]]
{Browse {LengthL X}}
{Browse {LengthL [X X]}}

Каким будет результат этих вызовов?

Использование различных типов определений для вложенных списков даст различные по размеру функции определения длины. Например, определим тип <NestedList2 T> таким образом:

hNestedList2 Ti
::= nil
| hNestedList2 Ti ́| ́ hNestedList2 Ti
| T

Опять же, мы должны добавить условие, что T не является ни nil-ом и ни cons-ом. Заметьте тонкую разницу между <NestedList T> и <NestedList2 T>! Следование определению <NestedList2 T> даст отличную и более простую функцию LengthL2:

fun {LengthL2 Xs}
case Xs
of nil then 0
[] X|Xr then
{LengthL2 X}+{LengthL2 Xr}
else 1 end
end

Какая разница между LengthL и LengthL2? Мы можем вывести эту разницу сравнив типы <NestedList T> и <NestedList2 T>. <NestedList T> всегда будет списком, в то время как <NestedList2 T> может также быть типом T. Поэтому вызов {LengthL2 foo} допустим (вернёт 1), в то время как {LengthL foo} недопустим (породит исключение). Такое поведение разумно рассмотреть как ошибку в LengthL2.

Здесь мы изучили важный урок. Важно определить рекурсивный тип до написания, использующей его, рекурсивной функции. Иначе можно легко обмануться, казалось бы, простой и в то же время неверной функцией. Это остаётся в силе даже для таких функциональных языков выполняющих выведение типа, как Standard ML и Haskell. Выведение типа может проверить что рекурсивный тип используется корректно, но ответственность за архитектуру рекурсивного типа несёт программист.

Сортировка слиянием

Мы определяем функцию, получающую список чисел или атомов и возвращающую новый список, элементы которого отсортированы в порядке возрастания. Он использует оператор сравнения <, поэтому все элементы должны быть одного типа (все целочисленные, все вещественные или все атомы). Мы используем алгоритм сортировки слиянием, он эффективен и легко может быть запрограммирован в декларативной модели. Алгоритм сортировки слиянием основан на простой стратегии названной как "разделяй-и-властвуй".

Разделить список на два меньших списка примерно одинаковой длины.

Рекурсивно применить сортировку слиянием для сортирования двух меньших списков.

Слить вместе два отсортированных списка для получения конечного результата.

Рисунок 3.9 показывает рекурсивную структуру. Сортировка слиянием эффективна поскольку операции разделения и слияния являются итеративными вычислениями с линейным временем исполнения. Вначале мы определяем операции слияния и разделения, после чего определяем сортировку слиянием:

Список на входе

Разделение

Слияние

Отсортированный список

fun {Merge Xs Ys}
case Xs # Ys
of nil # Ys then Ys
[] Xs # nil then Xs
[] (X|Xr) # (Y|Yr) then
if X<Y then X|{Merge Xr Ys}
else Y|{Merge Xs Yr}
end
end
end

Его тип <fun {$ <List T> <List T>}: <List T>>, где T либо <Int>, <Float> или <Atom>. Мы определяем разделение как процедуру поскольку в ней содержится два вывода. Также она может быть определена как функция возвращающая пару как единственный вывод.

proc {Split Xs ?Ys ?Zs}
case Xs
of nil then Ys=nil Zs=nil
[] [X] then Ys=[X] Zs=nil
[] X1|X2|Xr then Yr Zr in
Ys=X1|Yr
Zs=X2|Zr
{Split Xr Yr Zr}
end
end

Тип <proc {$ <List T> <List T> <List T>}>. Определение сортировки слиянием:

fun {MergeSort Xs}
case Xs
of nil then nil
[] [X] then [X]
else Ys Zs in
{Split Xs Ys Zs}
{Merge {MergeSort Ys} {MergeSort Zs}}
end
end

Его тип <fun {$ <List T>}: <List T>> с тем же ограничением на T что и в Merge. Непосредственно отсортированными могут быть расщепления списков нулевой и единичной длин.

3.4.3 Аккумуляторы

Мы узнали как программировать простые списковые функции и как преобразовывать их в итеративные. В реалистичном декларативном программировании, обычно, это делается по-другому, а именно, через написание функции итеративной с самого начала. Идея заключается в том, чтобы всё время переносить состояние вперёд никогда не выполнять возвратных вычислений. Состояние S представлено добавлением пары аргументов, S1 и Sn, к каждой процедуре. Эта пара называется аккумулятором. S1 представляет входное состояние, а Sn представляет выходное состояние. Тогда каждое определение процедуры выглядит примерно так:

В базовом случае не выполняется никаких вычислений, поэтому выходное состояние является тем же, что входным состоянием (Sn=S1). В рекурсивном случае состояние проходит через каждый рекурсивный вызов (P1, P2 и P3) и в конечном итоге возвращается в P. На Рисунке 3.10 дана иллюстрация. Каждая стрелка представляет переменную с одним состоянием. Значение состояния дано в хвосте стрелки и передаётся в начало стрелки. Под прохождением состояния мы обозначаем что каждый вывод процедуры является вводом следующей процедуры. Техника передачи состояния через вложенные вызовы процедуры называется программированием с помощью аккумулятора.

Базовый случай

Рекурсивный случай

Рисунок 3.10: Принцип работы с передаваемым состоянием

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

Несколько аккумуляторов

Рассмотрим следующую процедуру, которая получает выражение содержащее идентификаторы, целые числа и операцию сложения (используя метку plus). Она вычисляет два результата: транслирует выражение в машинный код для простой стековой машины и эта машина вычисляет число инструкций в получившемся коде.

Эта процедура содержит два аккумулятора: один для постройки списка машинных инструкций и другой для хранения числа инструкций. Вот пример исполнения:

Будет отображено:

Обычно более сложные программы требуют большего числа аккумуляторов. Обычно мы при написании большой декларативной программы одновременно используем с пол десятка аккумуляторов. В таком стиле был написан компилятор Пролога Aquarius [198, 194]. Некоторые из его процедур содержат целых 12 аккумуляторов. Это обозначает 24 дополнительных аргумента! Подобное трудно выполнить без помощи техники. Мы использовали расширенный препроцессор DCG 6 получающий описания аккумуляторов и автоматически складывающий аргументы [96].

6 DCG (Definite Clause Grammar - Грамматика, построенная на Определённых Предложениях) - это обозначение грамматики используемой для сокрытия явной передачи аккумуляторов.

Мы больше не программируем в этом стиле; мы обнаружили, что программирование с явным состоянием проще и более эффективно (смотрите Главу 6). Разумно использовать несколько аккумуляторов в декларативной программе; вообще декларативные программы которым не нужны аккумуляторы встречаются достаточно редко. С другой стороны, использование большого количества аккумуляторов обозначает что, возможно, было бы лучше написать программу с явным состоянием.

Сортировка слиянием с помощью аккумулятора

В предыдущем определении сортировки слиянием мы вначале вызвали функцию Split для разделения входного списка на две половины. Есть более простой способ выполнить сортировку слиянием - воспользуемся аккумулятором. Параметр обозначает "часть списка всё ещё должна быть отсортирована". Определение MergeSortAcc:

S#L2={MergeSortAcc L1 N} получает входной список L1 и целое число N. Возвращает два результата: S, отсортированный список первых N элементов L1 и L2, оставшиеся элементы L1. Два результата спарены с помощью конструктора кортежей #.

Аккумулятор определён через L1 и L2. А это даёт нам следующее определение:

Функция Merge остаётся неизменной. Отметим, что эта сортировка слиянием выполняет другое разбиение, чем предыдущая. В этой версии разбиение отделяет первую половину входного списка от второй половины. В предыдущей версии, разбиение отделяло нечётные элементы списка от чётных.

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

3.4.4 Списки различия

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

% Представляет пустой список
% то же самое
% то же самое
% Представляет [a b c]
% то же самое
% то же самое

Список различия - это представление стандартного списка. Иногда мы будем говорить о списке различия как о содержащейся в ней структуре данных, а иногда как о представлении стандартного списка. Будьте внимательны и не путайте эти две точки зрения. Список различия [a b c d]#[d] может содержать списки [a b c d] и [d], но его смысл не такой. Его смысл - список [a b c].

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

Преимущество в использовании списков различия заключается в том, что когда второй список - это непривязанная переменная, то другой список различия может быть добавлен к первому за неизменное время. Для сложения (a|b|c|X)#X и (d|e|f|Y)#Y достаточно привязать X к (d|e|f|Y). Получится список различия (a|b|c|d|e|f|Y)#Y. Мы только что сложили списки [a b c] и [d e f] за одну привязку. Вот функция, складывающая любые два списка различия:

Она может быть использована как сложение списка:

Будет отображено (1|2|3|4|5|Y)#Y. Стандартная функция сложения списка определённая таким образом:

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

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

Описанные здесь списки различия взяты из Пролога и логического программирования [182]. Они база для многих расширенных техник программирования на Прологе. Как концепция, списки различия живут где-то между концепцией значения и концепцией состояния. Они обладают хорошими свойствами значения (использующие их программы декларативны), но также они обладают некоторой мощью состояния поскольку могут выполнить сложение за постоянное время.

Преобразование вложенного списка в плоский список

Рассмотрим задачу преобразования вложенного списка в плоский список, то есть, вычисление списка обладающего всеми элементами вложенного списка, но не являющегося вложенным. Вначале мы дадим решение, использующее списки, после чего покажем улучшенное решение, возможное с помощью списков различия. Решение с помощью списка мы начнём с рассуждения с использованием математической индукции, основанной на типе <NestedList>, определённый нами ранее. Рассуждение будет проводиться так же, как и для функции LengthL.

Плоский вид nil-а - это сам nil.

Плоский вид X|Xr где X - это вложенный список даёт Z где

плоский X - это Y,
плоский Xr - это Yr, и
сложение Y и Yr равно Z.

Плоский вид X|Xr, где X - не список равен Z, где

плоский Xr равен Yr, и
Z - это X|Yr.

Следуя этому рассуждению, мы получим следующее определение:

Вызов:

отобразит [a b c d e f]. Эта программа очень неэффективна поскольку ей требуется выполнять много операций сложения (смотрите Упражнения). Теперь мы будем рассуждать тем же способом, но вместо обычных списков используем списки различия:

Плоский вид nil-а равен X#X (пустой список различия).

Плоский X|Xr, где X - вложенный список, равен Y1#Y4 где

плоский X равен Y1#Y2,
плоский Xr равен Y3#Y4, и
приравниваем Y2 к Y3 для сложения списков различия.

Плоский X|Xr где X - не список, даёт (X|Y1)#Y2 где

плоский Xr равен Y1#Y2.

Мы можем записать второй случай таким образом:

Плоский X|Xr где X - вложенный список равен Y1#Y4 где

плоский X равен Y1#Y2 и
плоский Xr равен Y2#Y4.

Что даёт нам следующую программу:

Эта программа эффективна, она выполняет единственную cons операцию для каждого не-списка во входных данных. Мы конвертируем список различия возвращённый FlattenD в обычный список привязав его второй аргумент к nil. Мы написали FlattenD как процедуру поскольку его вывод является частью его последнего аргумента, а не весь аргумент (смотрите Раздел 2.5.2). Общим стилем записи списка различия является запись в двух аргументах:

В качестве последующего упрощения мы можем записать FlattenD как функцию. Для этого мы используем тот факт, что S является выводом:

Какова роль E? Он возвращает "остаток" вывода, то есть, когда вызов FlattenD исчерпает свой вклад в вывод.

Реверс списка

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

Реверс nil возвращает X#X (пустой список различия).

Реверс X|Xs возвращает Z, где

реверс Xs возвращает Y1#Y2 и
сложение Y1#Y2 и (X|Y)#Y вместе возвращает Z.

Перепишем последний случай с помощью сложения таким образом:

Реверс X|Xs равен Y1#Y, где

реверс Xs равен Y1#Y2 и
Y2 равен X|Y.

Очень удобно сместить равенство перед реверсом (почему?). Получим:

Реверс X|Xs возвращает Y1#Y, где

реверс Xs равен Y1#(X|Y).

Окончательное определение:

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

3.4.5 Очереди

Очередь - важная базовая структура данных. Очередь - последовательность элементов с операцией вставки и удаления. Операция вставки добавляет элемент в конец очереди, а операция удаления удаляет элемент с другого конца. Мы говорим что очередь обладает поведением FIFO (First-In-First-Out - "Первым пришёл - Первым ушёл"). Рассмотрим как программировать очереди в декларативной модели.

Наивная очередь

Использование списков - очевидный способ реализовать очереди. Если L представляет содержимое очереди, то вставка X даст новую очередь X|L и удалённый X будет получен вызовом {ButLast L X L1}, где X будет привязан к удалённому элементу, а возвращённая новая очередь к L1. ButLast возвращает последний элемент L в X и все элементы за исключением последнего в L1. Эту процедуру можно определить так:

Проблема этой реализации в том, что ButLast медлен: его время выполнения пропорционально числу элементов в очереди. Нам же, напротив, хочется что бы операции вставки и удаления происходили за постоянное время. То есть, выполнение операции на заданной реализации и машине всегда должно занимать меньше времени, чем некоторое постоянное число секунд. Значение постоянной зависит от реализации и машины. Достигнем мы или не достигнем постоянных по времени операций - зависит от выразительности вычислительной модели:

В строгих функциональных языках программирования, например, в декларативной модели без переменных потока данных (смотрите Раздел 2.7.1), мы не можем этого достигнуть. Лучшее что мы сможем сделать - это получить амортизированные операции с постоянным временем исполнения [138]. То есть, общее время исполнения любой последовательности из n операций вставок и удалений пропорционально некоторой константе умноженной на n. Однако любая отдельно взятая операция может и не исполняться за постоянное время.

В декларативной модели, которая расширяет строгую функциональную модель переменными потока данных, мы можем достигнуть постоянного времени исполнения.

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

7 Как правило, очереди, реализованные с явным состоянием (смотрите Главы 6 и 7) также эфемерны.

Эфемерная очередь с амортизированным постоянным временем

Здесь мы приведём определение очереди, в которой операции вставки и удаления обладают некоторым постоянным амортизированным временем исполнения. Определение взято у Окасаки [138]:

Здесь используется пара q(F R) представляющая очередь. F представляет начало очереди и R представляет остаток очереди в реверсированной форме. В любом примере содержимое очереди дано как {Append F {Reverse R}}. Элемент может быть вставлен добавлением его в начало R и удаляется стиранием с начала F. Например, допустим, что F=[a b] и R=[d c]. Удаление первого элемента возвращает a, после чего F=[b]. После вставки элемента e: R=[e d c]. Обе операции исполняются за постоянное время.

Для того, чтобы это представление работало, каждый элемент в R рано или поздно должен быть перемещён в F. Когда следует выполнять перемещение? Выполнять его элемент за элементом - не эффективно, поскольку это означает что каждый раз приходится выполнять замещение F с помощью {Append F {Reverse R}}, а это, по-крайней мере, пропорционально длине F. Уловка в том, чтобы выполнять это периодически. Мы выполняем это тогда, и только тогда, когда F становится пустым, отсюда F не-nil только в том случае, когда очередь не пуста. Эта постоянность поддерживается функцией Check, перемещающей содержимое R в F каждый раз, когда F становится равен nil.

Функция Check выполняет операцию реверса над R. Время, затрачиваемое на реверс пропорционально длине R, то есть, числу реверсируемых элементов. Каждый элемент проходящий через очередь передаётся только единожды от R к F. Поэтому время, затрачиваемое на реверс каждого элемента, в целом, является постоянным. В этом и заключается амортизация очереди.

Эфемерная очередь с наихудшим постоянным временем исполнения

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

Для представления очереди здесь используется тройка q(N S E). В каждом случае содержимое очереди задано списком различия S#E. N - число элементов в очереди. Для чего нужно N? Без него мы не знали бы сколько элементов находится в очереди.

Пример использования

Следующий пример работает с любым из вышеуказанных определений:

Здесь вставляются и удаляются три элемента. Каждый элемент вставляется до его удаления. Теперь рассмотрим что может делать один элемент и чего не может другой элемент.

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

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

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

8 Для того, чтобы увидеть почему так происходит рассмотрим последовательность из n операций над очередью. Для сохранения амортизированного постоянного времени общее время для всех операций в последовательности должно быть пропорционально n. Но что случится если последовательность повторяет "дорогостоящие" операции во многих версиях? Это возможно, поскольку мы говорим о любой последовательности. Поскольку и время на дорогостоящие операции, и число версий могут быть пропорциональны n, то общее время привязки растёт как n2.

И Q3 и Q4 вычисляются из их общего предка Q2. Q3 содержит peter и paul. Q4 содержит peter и mary. Что отобразят два вызова Browse?

Постоянные очереди

Оба вышеприведённых определения были эфемерными. Что мы можем сделать если нам требуется использовать несколько версий и одновременно сохранить постоянное по времени исполнение? Очередь, которая поддерживает одновременно несколько версий называется постоянной.9 Некоторым приложениям требуются постоянные очереди. Например, если при вычислении мы передадим значение очереди в другую процедуру:

9 Это значение постоянности не следует путать с постоянностью, используемой в транзакциях и базах данных (Разделы 8.5 и 9.6), которая является совершенно другой концепцией.

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

Сейчас мы предложим простой обходной путь, который часто оказывается достаточным для того, чтобы сделать постоянной очередь с наихудшим вариантом. Она работает для случая когда не очень много одновременных версий. Мы определим операцию ForkQ, получающую очередь Q и создающую две идентичные версии Q1 и Q2. Предварительно мы определим процедуру ForkD создающую две версии списка различия:

Вызов {ForkD D E F} получает список различия D и возвращает две его новые копии, E и F. Append используется для конвертации списка в новый список различия. Учтите, что ForkD потребляет D, то есть, после ForkD нельзя использовать D в следствии привязки его хвоста. Теперь мы можем определить ForkQ, использующий ForkD для создания двух версий очереди:

ForkQ изменяет Q и время работы пропорционально размеру очереди. С помощью ForkQ пример можно переписать таким образом:

Программа работает хорошо, за исключением дороговизны ForkQ.

3.4.6 Деревья

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

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

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

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

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

Упорядоченное двоичное дерево

Упорядоченное двоичное дерево (ordered binary tree) <OBTree> - это двоичное дерево, в котором каждый узел включает пару значений:

Каждый не-листовой узел включает значения <OValue> и <Value>. Первое значение <OValue> любой подтип строго упорядоченного <Value>, то есть, в дереве содержатся булевы функции сравнения. Например, <Int> (целочисленный тип) - один из возможностей. Второе значение <Value> используется для последующей работы. В дереве нет никаких частичных условий.

Будем называть упорядоченное значение ключом, а второе значение - информацией. Тогда двоичное дерево будет упорядоченным, если для любого не-листового узла, все ключи в первом поддереве меньше чем ключ узла и все ключи во втором поддереве больше чем ключ узла.

Сохранение информации в деревьях

Упорядоченное двоичное дерево, если мы определим три операции: поиск, вставка и удаление, может быть использовано в качестве репозитория информации.

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

Вызов {Lookup X T} вернёт found(V) если найден узел, содержащий X, и notfound в противном случае. Другой способ написания Lookup - это использование andthen в операторе case:

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

Для вставки или удаления информации в упорядоченном двоичном дереве мы сконструируем новое дерево идентичное исходному за исключением большего или меньшего количества информации в дереве. Вот операция вставки:

Рисунок 3.11: Удаление узла Y, содержащего в качестве листа одно поддерево (простой случай)

Вызов {Insert X V T} возвращает новое дерево, содержащее пару (X V), вставленное в нужных местах. Если T уже содержит X, то новое дерево замещает старую информацию на V.

Удаление и реорганизация дерева

Операция удаления содержит в себе сюрприз. Вот первая попытка:

Вызов {Delete X T} должен вернуть новое дерево, не содержащее узел с ключом X. Если T не содержит X, то T возвращается без изменений. Удаление выглядит достаточно просто, но данное определение некорректно. Вы можете увидеть причину?

Оказывается, что Delete не так прост как Lookup или Insert. Ошибка в этом определении заключается в X==Y, в этом случае удаляется всё поддерево, а требуется удаление единственного узла. Определение будет корректным только в случае вырожденного дерева, то есть, если T1 и T2 являются листьями узла. Решение не совсем очевидно: в случае X==Y нам нужно реорганизовать поддерево таким образом, чтобы оно не имело ключа Y, но по прежнему являлось упорядоченным двоичным деревом. Возможны два случая, продемонстрированные на Рисунках 3.11 и 3.12.

Рисунок 3.11: Удаление узла Y, содержащего в качестве листа одно поддерево (простой случай)

Удаление Y

Сдвиг вверх Yp

Наименьший ключ T2

T2 минус Yp

Рисунок 3.12: Удаление узла Y, когда ни одно из поддеревьев не является листом (трудный случай)

Рисунок 3.11 - это простой случай, когда один из поддеревьев является листом. Реорганизованное дерево - это просто другое поддерево. Рисунок 3.12 - это тяжёлый случай, когда оба поддерева не являются листьями. Как мы заполним пробел после удаления Y? Другой ключ займёт место Y, "просочившись" изнутри одного из поддеревьев. Идея в том, чтобы взять наименьший ключ T2, назовём его Yp и сделать его корнем реорганизованного дерева. Оставшиеся узлы T2 создают меньшее поддерево, назовём его Tp, которое вставлено в реорганизованное дерево. Таким образом реорганизованное дерево остаётся упорядоченным, поскольку, исходя из конструкции, все ключи T1 меньше чем Yp, меньшего чем все ключи Tp.

Интересно рассмотреть что случится если мы поочерёдно будем удалять корни дерева. Дерево будет "опустошаться" изнутри, удаляя всё больше и больше левую часть T2. Настанет момент, когда левое поддерево T2 удалится полностью и правое поддерево займёт его место. При продолжении операции удаления, T2 будет сжиматься всё больше и больше, проходя через промежуточные состояния, в которых он является полноценным, но малым упорядоченным двоичным деревом. И наконец, он полностью исчезнет.

Для реализации исправления, мы используем функцию {RemoveSmallest T2} возвращающую наименьший ключ из T2, ассоциированное с ним значение, и новое дерево недостающее этому ключу. С помощью этой функции мы можем написать корректную версию Delete:

Функция RemoveSmallest возвращает тройку Yp#Vp#Tp или атом none. Мы определим её рекурсивно:

Вместо наименьшего элемента T2 можно взять наибольший элемент T1. Результат будет тем же самым.

Дополнительная сложность Delete по сравнению с Insert или Lookup часто возникает из-за алгоритмов деревьев. Сложность возникает из-за того, что упорядоченное дерево удовлетворяет глобальному состоянию, а именно - оно упорядочено. Многие разновидности деревьев удовлетворяют глобальным условиям. Алгоритмы для таких деревьев сложны поскольку они должны удовлетворять глобальному состоянию. В дополнение, алгоритмы деревьев сложнее писать чем алгоритмы списка из-за того, что рекурсия должна комбинировать результаты из нескольких меньших проблем, а не из одной.

Проход по дереву

Проход по дереву обозначает выполнение операций над узлами дерева согласно некоторому заданному порядку. Существует много способов прохода по дереву. Многие из них - это разновидности одного из двух базовых проходов: по глубине и по ширине. Рассмотрим эти проходы.

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

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

10 Browse не определён в декларативной модели.

Второй базовый проход - по ширине. Вначале все узлы проходятся по глубине 0, затем все узлы по глубине 1 и так далее, с каждым разом уровень глубины увеличивается на единицу. На каждом уровне проход по узлам идёт слева на право. Глубина узла - это длина пути с корня до текущего узла не включая сам узел. Для реализации прохода по ширине нам нужна очередь для хранения всех узлов заданной глубины. На Рисунке 3.13 показано как это сделать. Здесь используется тип данных очереди, определённый нами ранее в предыдущем разделе. Следующий посещаемый узел поступает с головы очереди. Два поддерева узла добавлены в хвост очереди. Проход пройдёт по ним тогда, когда будут обработаны остальные узлы очереди, то есть, все узлы текущей глубины.

Рисунок 3.13: Проход по ширине

В декларативной модели проход по ширине, также как и проход по глубине, полезен только если реализован с аккумулятором. На Рисунке 3.14 дан пример вычисляющий список всех пар ключей/значений в дереве.

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

Рисунок 3.14: Проход по ширине с аккумулятором

Рисунок 3.15: Проход по глубине с явным стеком

Как выглядит новая версия DFS по сравнению с оригиналом? Обе версии используют стек для запоминания обработанных поддеревьев. В исходной версии стек был скрыт: это был семантический стек. Есть два рекурсивных вызова. Когда исполняется первый вызов, то второй вызов ждёт своей очереди в семантическом стеке. В новой версии стек явный. Новая версия с хвостовой рекурсией, как и BFS, поэтому семантический стек не растёт. В новой версии вместо семантического стека расходуется хранилище (под вопросом корректность!).

Рассмотрим как используют память алгоритмы DFS и BFS. Положим что у нас есть дерево с глубиной n с 2^n листовыми узлами и 2^n-1 не листовыми узлами. Сколько аргументов будет в стеке и в очереди? Мы можем доказать, что в стеке будет максимум n элементов, а в очереди - максимум 2^(n-1). Отсюда можно сделать вывод, что DFS гораздо экономичнее: его потребление памяти пропорционально глубине дерева. Количество памяти потребляемой BFS пропорционально размеру дерева.

3.4.7 Отображение деревьев

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

Ограничения на отображение дерева

Вначале мы определяем тип дерева:

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

1. Горизонтальное расстояние между обеими поддеревьями каждого узла минимально. Если быть точным, узел справа левого поддерева расположен на минимальной дистанции от левого узла правого поддерева.

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

3. Если узел имеет только одного потомка, то потомок располагается сразу после предка.

4. Вертикальная позиция узла пропорциональна его уровню в дереве.

В дополнение, для предотвращения беспорядка будут отображаться только узлы с типом tree. Рисунок 3.16 графически демонстрирует эти ограничения в терминах координат каждого узла. Демонстрационное дерево из Рисунка 3.17 отображается так, как это показано на Рисунке 3.19.

1. Расстояние d между поддеревьями минимально

2. Если существуют оба потомка, то a - это среднее между b и c

3. Если существует только один потомок, то он следует непосредственно за родителем

4. Вертикальная позиция y пропорциональна уровню в дереве

Рисунок 3.16: Ограничения, накладываемые на отображение дерева

Рисунок 3.17: Демонстрационное дерево

Вычисление позиций узла

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

Алгоритм отображения дерева выполняет проход по глубине и в процессе прохода вычисляет координаты (x, y) каждого узла. В качестве подготовки к запуску алгоритма мы расширим каждый узел дерева полями x и y:

Функция AddXY возвращает новое дерево с двумя полями x и y добавленными ко всем узлам. Здесь используется функция Adjoin, которая может добавить новые поля к записям и перезаписывать старые. За подробностями читайте Приложение B.3.2. Алгоритм отображения дерева заполнит эти два поля координатами каждого узла. Если два поля существуют где-либо в записи, то не возникнет никакого конфликта с информацией, содержащейся в записи.

Для реализации алгоритма отображения дерева, мы расширим проход по глубине передачей двух аргументов вниз (а именно, уровнем в дереве и пределом на самой левой позиции поддерева) и двумя аргументами вверх (а именно, горизонтальной позицией корня поддерева и крайней правой позицией поддерева). Аргументы передаваемые вниз иногда называют наследуемыми аргументами. Аргументы передаваемые вверх иногда называются синтезируемыми аргументами. С такими дополнительными аргументами у нас есть вся информация для вычисления позиций всех узлов. На Рисунке 3.18 дан завершённый алгоритм отображения дерева. Параметр Scale обозначает базовую единицу измерения отображаемого дерева, то есть, минимальное расстояние между узлами. Level=1 и LeftLim=Scale - инициализирующие аргументы. Возможны четыре случая: когда узел имеет два поддерева, одно поддерево (левое или правое) или ноль поддеревьев. Сопоставление с шаблоном в операторе case служит для выбора соответствующих действий. Используется преимущество в том, что проверки выполняются по порядку.

Рисунок 3.18: Алгоритм отображения дерева

3.4.8 Разбор

В качестве второго учебного примера по декларативному программированию, мы напишем парсер для маленького императивного языка с синтаксисом, подобным Паскалю. Здесь будет использовано большое количество ранее рассмотренных техник, в частности, будут применены аккумуляторы и построены деревья.

Что такое парсер

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

Токенизатор. Токенизатор считывает последовательность символов и возвращает последовательность лексем.

Парсер. Парсер считывает последовательность лексем и возвращает абстрактное синтаксическое дерево (abstract syntax tree). Иногда это дерево называется деревом разбора.

Генератор кода. Генератор кода проходит по синтаксическому дереву и генерирует низкоуровневые инструкции для настоящей или абстрактной машины.

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

Парсер: языки на входе и выходе

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

Пусть, к примеру, нам нужно разобрать <Term>. Он состоит из не пустых последовательностей <Fact> разделённых <TOP> лексемами. Для того, чтобы разобрать эту конструкцию нам нужно вначале разобрать <Fact>. После чего мы проверяем следующую лексему. Если следующей лексемой окажется <TOP>, то мы делаем вывод, что последовательности продолжаются. Если лексемой окажется не <TOP>, то мы делаем вывод, что последовательности закончились, то есть, <Term> завершился. Для работоспособности подобной стратегии требуется отсутствие пересечений между лексемами <TOP> и другими возможными лексемами следующими после <Fact>. Изучив грамматические правила мы увидим, что другие лексемы должны быть взяты из {<EOP>, <COP>, ;, end, then, do, else, )}. Мы подтвердили, что все лексемы, определённые этим набором отличаются от лексем определённых в <TOP>.

В Таблице 3.2 есть две разновидности символов: нетерминалы (nonterminals) и терминалы (terminals). Нетерминальный символ - это символ, в дальнейшем раскрываемый с помощью грамматического правила. Терминальный символ прямо соответствует лексеме входных данных. Он не расширяем. Нетерминальные символы - это <Prog> (вся программа), <Stat> (оператор), <Comp> (сравнение), <Expr> (выражение), <Term> (терм), <Fact> (коэффициент), <COP> (оператор сравнения), <EOP> (оператор выражения) и <TOP> (оператор терма). Разбор программы начинается с <Prog> и расширение проводится до тех пор, пока не будет найдена последовательность лексем соответствующая входным данным.

Рисунок 3.19: Демонстрационное дерево иллюстрирующее алгоритм отображения дерева

Вывод парсера - дерево (то есть, вложенная запись) с синтаксисом из Таблицы 3.3. На первый взгляд Таблицы 3.2 и 3.3 обладают очень похожим содержимым, но они на самом деле весьма отличаются: первая определяет последовательность лексем, а вторая определяет дерево. Первая не показывает структуру входной программы - мы говорим, что она плоская. Вторая отображает структуру - мы говорим, что она вложенная. Поскольку она отображает структуру программы, мы называем вложенную запись абстрактным синтаксическим деревом (abstract syntax tree). Она абстрактна поскольку закодирована как и структуры данных в языке, а не как термы лексем. Роль парсера заключается в извлечении структуры из плоских входных данных. Без такой структуры задача написания генератора кода и оптимизаторов кода чрезвычайно усложняется.

Таблица 3.2: Входной язык парсера (являющийся последовательностью лексем)

Программа парсера

Главный парсер вызывает функцию {Prog S1 Sn}, где S1 - входной список лексем, а Sn - весь список после разбора. Этот вызов возвращает разобранный вывод. Например:

отобразит:

Мы прокомментировали код программы завершённого парсера. Prog написан следующим образом:

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

В T вставляется первая лексема. С помощью оператора case производится поиск корректной ветки грамматического правила для Stat. Последовательности операторов (окружённые begin - end-ом) разбираются процедурой Sequence. Это общая процедура, предназначенная для обработки последовательностей сравнения, последовательностей выражения и последовательностей лексем. Она написана таким образом:

Она получает две функции, NonTerm, пропускающую все нетерминалы, и Step, определяющий символ разделения в последовательности. Сравнения, выражения и лексемы разбираются Sequence-м таким образом:

Каждая из этих трёх функций имеет свою собственную функцию для определения разделителей:

И наконец, коэффициенты и идентификаторы разбираются следующим образом:

Целые числа представлены как встроенные целочисленные значения и определяются с помощью встроенной функции IsInt.

Эта технология разбора работает для грамматик, где для однозначного определения достаточна одна первая лексема. Некоторые грамматики, называемые неоднозначными грамматиками, требуют просмотра более чем одной лексемы для определения соответствующего грамматического правила. Простым способом разбора таких грамматик является недетерминированный выбор описанный в Главе 9.

3.5 Эффективность по времени и памяти

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

3.5.1 Время исполнения

Используя язык ядра и его семантику мы можем вычислить время исполнения с точностью до постоянного множителя. Например, для алгоритма сортировки слиянием мы можем сказать, что время исполнения пропорционально n log n, где n - длина входного списка. Асимптотическая временная сложность алгоритма - это предельная верхняя граница его времени исполнения как функции от размера входных данных с точностью до постоянного множителя. Иногда этот показатель называется худшей временной сложностью.

Для нахождения постоянного множителя необходимо подсчитать шаги выполненные программой. Подсчёт постоянного множителя априори чрезвычайно сложен. Всё потому, что современные компьютерные системы обладают сложной структурой аппаратного и программного обеспечения значительно увеличивающего непредсказуемость при работе программы: они осуществляют управление памятью (смотрите Раздел 3.5.2), они обладают сложными системами памяти (с виртуальной памятью и несколькими уровнями кеширования), они содержат сложные конвееры и широко масштабируемые архитектуры (множество инструкций одновременно находятся в различных состояниях исполнения; время исполнения инструкции часто зависит от присутствия других инструкций) и переключение контекстов, осуществляемое операционной системой происходит в непредсказуемое время. Такая непредсказуемость повышает среднюю производительность ценой увеличения флуктуаций производительности. За дополнительной информацией о замерах производительности и её подводных камнях мы рекомендуем обратиться к [91].

Нотация Большое-О

Мы будем обозначать время исполнения программы в терминах нотации "большое-О" O(f(n)). Эта нотация позволяет нам говорить о времени исполнения без необходимости определения постоянного множителя. Пусть T(n) будет функцией показывающей время исполнения некоторой программы, измеренной в размере входного n. Пусть f(n) будет некоторой функцией, определённой для неотрицательных целых чисел. Тогда мы говорим что T(n) является O(f(n)) (произносится как T(n) - порядок f(n)) если T(n) <= c.f(n) для некоторой положительной константы c, для всех n за исключением малых значений n <= n0. То есть, при росте n существует такая точка, после которой T(n) никогда не будет больше чем c.f(n).

Иногда встречается запись вида T(n) = O(f(n)). Будьте осторожны! Подобное использование равенства является злоупотреблением нотацией, поскольку не влечёт за собой равенства. Если g(n) = O(f(n)) и h(n) = O(f(n)), то может быть ложным высказывание g(n) = h(n). Лучше всего следует понимать нотацию большое-О в терминах множества и членства: O(f(n)) - это множество функций, и утверждение T(n) является O(f(n)) просто обозначает, что T(n) - это член множества.

Подсчёт времени исполнения

Мы используем язык ядра как руководство. Каждая инструкция ядра имеет чётко определённое время исполнения, которое может быть функцией от размера его аргументов. Предположим, что у нас есть программа, содержащая p функций: F1, ..., Fp. Нам может понадобится вычислить p функций TF1, ..., TFp. Это можно выполнить за три шага:

1. Транслировать программу в язык ядра.

2. Использовать количество выполненных операций ядра для определения набора уравнений, содержащих TF1, ..., TFp. Мы называем эти уравнения рекуррентными уравнениями, поскольку они определяют результат для n в терминах результатов для значений, меньших чем n.

3. Решить рекуррентные уравнения для TF1, ..., TFp.

Таблица 3.4 содержит время исполнения T(s) для каждого оператора ядра <s>. В этой таблице, s - целое число и аргументы yi = E(<yi>) для 1 <= i <= n, для соответствующей среды E. Каждый экземпляр k - это отдельная положительная вещественная константа. Функция Ix({y1, ..., yn}) возвращает подмножество аргументов процедуры, используемых в качестве входных данных.11 Функция sizex({y1, ..., yk}) - это "размер" входных аргументов для процедуры x. Мы вольны определять размер так, как мы этого хотим; если размер будет плохо определён, то рекуррентное уравнение не будет иметь решения. Для инструкций <x>=<y> и <x>=<v> существуют редкие случаи, когда их продолжительность работы может быть большей чем константное время, а именно, когда два аргумента привязаны к большим частичным значениям. В этом случае, время пропорционально размеру общей части двух частичных значений.

11 Иногда возникают отличия от вызова к вызову. Например, когда процедура используется для выполнения различных задач в различных вызовах.

Таблица 3.4: Время исполнения инструкций ядра

Пример: Функция Append

Дадим простой пример, иллюстрирующий работу этого подхода. Рассмотрим функцию Append:

Для неё существует следующая трансляция в язык ядра:

Используя Таблицу 3.4, мы получим следующее рекуррентное уравнение для рекурсивного вызова:

(Здесь не требуются индексы для размера и I.) Упростим это выражение. Мы знаем, что I({Xs, Ys, Zs}) = {Xs} и мы полагаем, что size({Xs}) = n, где n - длина Xs. Получаем:

Получаем после следующего упрощения:

Мы обрабатываем базовый случай взяв частичное значение Xs для которого мы можем сразу посчитать результат. Возьмём Xs = nil. Что даёт:

Решая два уравнения получаем:

Отсюда TAppend(n) - это O(n).

Рекуррентные уравнения

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

* Уравнение, определяющее функцию T(n) в терминах T(m1), ..., T(mk), где m1, ..., mk < n.

* Уравнение прямо задающее T(n) для некоторого значения n, например, T(0) или T(1).

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

Уравнение

Решение

Существует много техник для вывода этих решений. Ниже мы увидим несколько примеров. В рамке описаны два наиболее общих способа решения рекуррентных уравнений.

Решение рекуррентных уравнений

Следующие техники часто оказываются полезными:

* Простая трёхшаговая техника, почти всегда срабатывающая на практике. Первое, возьмём конкретные числа для некоторых малых входных данных (например: T(0) = k, T(1) = k + 3, T(2) = k + 6). Второе, предположим форму результата (T(n) = an + b, для некоторых неизвестных a и b). Третье, подставим предполагаемую форму в уравнения. В нашем примере мы получим b = k и (an + b) = 3 + (a.(n - 1) + b). Откуда a = 3, для конечного результата T(n) = 3n + k. Трёхшаговая техника сработает если предположенная форма является корректной.

* Гораздо более мощная техника называется производящими функциями, они позволяют получить конечную форму или асимптотические результаты в широком диапазоне задач без необходимости угадывания формы. Они требуют некоторых технических знаний о бесконечных последовательностях и математическом анализе, но не более чем то, что изучается по данным дисциплинам на первом курсе обучения в университетах. Хорошее введение в производящие функции вы найдёте у Кнута [102] и Вилфа [207].

Пример: FastPascal

В Главе 1, мы ввели функцию FastPascal и достаточно голословно утверждали, что сложность {FastPascal N} - это O(n^2). Посмотрим, получится ли у нас вывести это утверждение более строго. Напомним определение:

Мы можем вывести уравнения непосредственно изучая это определение, без трансляции функции в процедуры. Изучая определение легко заметить, что сложность ShiftRight - O(1), то есть, постоянное время. Используя подобные рассуждения для Append мы можем вывести, что сложность AddList и ShiftLeft - O(n), где n - длина L. Это даст нам следующее рекуррентное уравнение для рекурсивного вызова:

где n - это значение аргумента N. После упрощения получим:

Для базового случая мы возьмём N=1. Получим:

Для решения этих двух уравнений мы вначале "предположим" что решением является форма:

Это предположение исходит из интуитивного аргумента, как это было дано в Главе 1. Затем мы подставим эту форму в два уравнения. Если мы получим решения для a, b и c, то это означает, что наше предположение было корректным. Подставив форму в два уравнения мы получим следующие три уравнения для a, b и c:

Мы не решили эту систему до конца; здесь не хватает проверки что a != 0.12 Следовательно, TFastPascal(n) = O(n^2).

12 Если мы предположим a.n^2 + b.n + c и решением будет форма b.n + c, то тогда мы получим a = 0.

Пример: MergeSort

В предыдущем разделе мы увидели три mergesort алгоритма. У всех них одинаковое время исполнения с различными постоянными множителями. Подсчитаем время исполнения первого алгоритма. Опять приведём его главную функцию:

Пусть T(n) обозначает время исполнения {MergeSort Xs}, где n - длина Xs. Допустим, что Split и Merge обладают сложностью O(n) в зависимости от длины их входных данных. Мы знаем, что Split выводит два списка длинами n/2 и n/2. Исходя из определения MergeSort мы можем определить следующие рекуррентные уравнения:

Здесь используются несколько более сложные функции округления в большую и меньшую сторону. Для того, чтобы избавиться от них предположим, что n - это степень двойки, то есть, n = 2^k для некоторых k. Тогда уравнение примет вид:

Раскрыв последнее уравнение получим (где L(n) = k3 + k4n):

Заменив L(n) и T(1) их значениями получим:

Произведя суммирование получим:

Мы пришли к выводу, что T(n) = O(n log n). Для значений n не являющихся степенями двойки мы используем легко доказуемый факт, что n <= m -> T(n) <= T(m) для того, чтобы показать, что граница большого-О по-прежнему соблюдается. Граница не зависит от содержимого входного списка. Это означает, что граничное O(n log n) также является границей самого худшего случая.

3.5.2 Потребление памяти

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

* Размер мгновенной активной памяти ma(t), измеряется в словах памяти. Это число обозначает количество памяти, необходимое программе для благополучного продолжения работы. Связанное с ним число - это максимальный размер активной памяти Ma(t) = max0 <= u <= t ma(u). Это число нужно для нахождения количества физической памяти, которой должен обладать компьютер для благополучного исполнения программы.

* Мгновенное потребление памяти mc(t), измеряется в словах/секунда. Это число показывает сколько памяти выделяет программа в процессе исполнения. Большое значение этого числа обозначает большое количество работы, выполняемое управлением памяти, например, более частый вызов сборщика мусора. В этом случае будет увеличиваться время исполнения. Со всем этим связано число общего потребления памяти, Mc(t) = mc(u) du, показывающее общее количество работы, выполняемое управлением памяти при работе программы.

Эти два числа не следует путать. Первое число более важно. Программа может очень медленно выделять память (например, 1 KB/секунда) и в то же время занимать большой объём памяти (например, 100 MB). Например, большая база данных расположенная в памяти и обрабатывающая только простые запросы. Возможно и противоположное. Уровень потребления памяти программой может быть очень высоким (например, 100 MB/секунду) и в то же время занимать достаточно маленький объём памяти (например, 10 KB). Примером может служить симуляционный алгоритм, запущенный в декларативной модели.13

13 По этой причине декларативная модель не удобна для запуска симуляций если в этой модели нет отличного сборщика мусора!

Мгновенный размер активной памяти

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

Общее потребление памяти

Общее потребление памяти можно подсчитать с помощью техники, подобной той, что использовалась во время исполнения. Каждая операция языка ядра обладает точно определённым потреблением памяти. В Таблице 3.5 дано потребление памяти M(s) для каждого оператора ядра <s>. Используя эту таблицу можно составить рекуррентные уравнения для программы, из этого уравнения можно вычислить общее потребление памяти программой как функцию от размера входных данных. К этому числу нужно добавить потребление памяти семантическим стеком. Для инструкции <x> = <v> существует редкий случай, когда потребление памяти будет меньшим чем memsize(v), а именно, когда <x> частично определён. В этом случае следует считать память, затраченную на новые объекты. С учётом типа и значения v функция memsize(v) будет определена так:

* Для целых чисел: 0 для малых целых чисел, в противном случае пропорционально величине целого числа. Подсчёт числа битов требуется для представления целого числа в двойной дополнительной форме. Если это число меньше чем 28, то 0. Иначе разделить на 32 и округлить до ближайшего целого числа.

* Для числа с плавающей запятой: 2.

* Для списковой пары: 2.

* Для кортежа или записи: 1 + n, где n = length(arity(v)).

* Для значения процедуры: k + n, где n - это число внешних ссылок на тело процедуры и k - константа, зависящая от реализации.

В таблице все данные показаны для чисел с 32-битным словом в памяти, справедливым для Mozart 1.3.0. Для вложенных значений возьмите сумму всех его значений. Для значений записей и процедур есть разовая временная цена. Для каждой отдельной записи дополнительная цена грубо пропорциональна n (поскольку арность хранится в таблице символов). Для каждой отдельной процедуры в исходном коде, дополнительная цена зависит от размера скомпилированного кода, который грубо пропорционален общему числу выражений и идентификаторов в теле процедуры. В большинстве случаев эти разовые временные цены добавляют константу в общее потребление памяти; обычно они могут игнорироваться в подсчёте.

3.5.3 Амортизированная сложность

Иногда нас интересует не сложность отдельных операций, но общая сложность последовательности операций. И поскольку нам важна общая сложность, то мы можем не заботиться о том, что отдельные операции могут быть более дорогими. В Разделе 3.4.5 дан пример с очередями: так, как последовательность из n операций вставки и удалений обладает общим временем исполнения равным O(n), то мы можем не заботиться о том, некоторые отдельные операции всегда выражаются через O(1). Иногда они оказываются более дорогими, настолько, насколько нечасто это случается. В общем случае, если последовательность n операций обладает общим временем исполнения O(f(n)), то мы говорим, что она обладает амортизированной сложностью O(f (n) / n).

Амортизированность против наихудшей сложности

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

Промышленные системы реального времени удовлетворяют строгим ограничениям на продолжительность вычислений. Отсутствие таких ограничений может привести к серьёзным последствиям, включая лишение жизни. Такие системы используются, например, в кардиостимуляторах и для предотвращения столкновения поездов (также смотрите Раздел 4.6.1).

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

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

Метод банкира и метод физика

Подсчёт амортизированной сложности немного более сложная задача, чем подсчёт наихудшей сложности. (Ещё больше подсчёт осложняется при введении ленивых вычислений в Разделе 4.5.) В целом пользуются двумя методами, названными как метод банкира и метод физика.

Метод банкира заключается в подсчёте кредитов, где "кредит" представляет единицу времени исполнения или пространства памяти. Каждая операция откладывает несколько кредитов. Исполнение дорогой операции будет завершено тогда, когда будет отложено столько кредитов, чтобы покрыть всё её исполнение.

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

За дополнительной информацией об этих методах и большого количества примеров их использования с декларативными алгоритмами мы рекомендуем книгу Окасаки [138].

3.5.4 Отражение на производительности

С начала компьютерной эры 1940-х, и память и производительность удешевляются в экспоненциальной степени (постоянный показатель улучшения в каждый год). Сейчас они очень дешёвы, и объективно и субъективно: персональный компьютер низшей ценовой категории 2000 года обладает по крайней мере 64MB памяти со случайным доступом и 4 GB постоянного хранилища на диске, с производительностью в несколько сотен миллионов инструкций в секунду, где каждая инструкция может выполнять все 64-битные операции включая плавающую запятую. Это сравнимо или даже быстрее чем Cray-1, быстрейший суперкомпьютер мира в 1975 году. Суперкомпьютер - это один из быстрейших компьютеров, существующих в данный момент времени. Первый Cray-1 имел тактовую частоту 80 MHz и мог выполнять несколько 64-битных операций с плавающей запятой за один цикл [178]. Сохраняя прежнюю цену, производительность персонального компьютера по прежнему улучшается в соответствии с Законом Мура (то есть, удваивается каждые два года), и предсказано, что этот закон будет выполняться по крайней мере в течении первого десятилетия 21-го века.

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

Хотя не все задачи оказываются решаемыми. Существуют вычислительно дорогие задачи, например, в области комбинаторной оптимизации, операционного исследования, научных вычислений и симуляций, машинного обучения, распознавания речи и образов, и компьютерной графики. Некоторые из этих задач дороги из-за того, что им приходится выполнить много работы. Например, игры с реалистичной графикой, которые по определению всегда находятся на грани возможного. Другие задачи дороги из-за более фундаментальных причин. Например, NP - полные задачи. Эти задачи принадлежат NP, то есть, легко проверить предложенное решение.14 Но нахождение решения может быть гораздо более сложным. Простым примером будет задача выполнимости схемы. Дана комбинационная цифровая схема состоящая из шлюзов And, Or и Not. Существует ли такой набор входных значений, при котором на выходе будет получен результат 1? Эта задача NP-полная [41]. NP - полная задача - это особая разновидность NP задач с таким свойством, что если вы можете решить одну задачу за полиномиальное время, то вы можете решить их все за полиномиальное время. Многие научные работники тратили больше нескольких десятилетий в поисках решений за полиномиальное время для NP - полных задач, и никто не добился успеха. Поэтому многие научные работники подозревают, что NP - полные задачи нельзя решить за полиномиальное время. В этой книге мы больше не будем разговаривать о вычислительно-дорогих задачах. Поскольку наша цель - показать как программировать - то мы ограничимся решаемыми задачами.

14 NP расшифровывается как "недетерминированное полиномиальное время".

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

У оптимизации есть как хорошая, так и плохая сторона. Хорошая сторона в том, что в целом время исполнения большинства приложений значительно определено очень малой частью текста программы. Отсюда оптимизация производительности, если это необходимо, может почти всегда выполняться переписыванием только этой малой части (иногда достаточно нескольких строк). Плохая сторона в том, что это не очевидно, даже для опытных программистов, где эта часть априори. Следовательно, эта часть должна быть определена после запуска приложения и только если возникла проблема с оптимизацией. Если такая проблема не возникла, то никаких оптимизаций производительности выполнять не следует. Лучшей техникой для идентификации "мест перегрева" является профилирование - приложение-инструмент для замера характеристик во время работы программы.

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

3.6 Высокоуровневое программирование

Высокоуровневое программирование - это коллекция техник программирования, которые становятся возможными при использовании значений процедур в программах. Значения процедур также известны как замыкания лексической области видимости. Термин высокоуровневой появился из концепции порядка процедуры. Процедура, в которой все аргументы не являются процедурами, имеет нулевой порядок. Порядок равен единице если процедура, по-крайней мере, имеет одну процедуру нулевого порядка в качестве аргумента. И так далее: порядок процедуры равен n+1 если есть хотя бы один аргумент порядка n и нет другого более высокого порядка. Высокоуровневое программирование просто обозначает что процедуры могут быть любого порядка, а не только нулевого.

3.6.1 Базовые операции

Есть четыре базовых операций на которых строятся техники высокоуровневого программирования:

* Процедурная абстракция: способность конвертировать любую конструкцию в значение процедуры.

* Обобщённость: способность передавать значения процедуры как аргументы в вызов процедуры.

* Возврат новых экземпляров: способность возвращать значения процедуры как результат вызова процедуры.

* Встраивание: способность разместить значения процедуры в структуры данных.

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

Процедурная абстракция

Мы только что ввели процедурную абстракцию. Кратко повторим базовую идею. Любой оператор может быть "запакован" в процедуру с помощью записи proc {$} <stmt> end. Здесь оператор не выполняется, но взамен создаётся значение процедуры (замыкание). Поскольку значение процедуры содержит контекстную среду, то его исполнение даст точно такой же результат, как и исполнение <stmt>. Решение об исполнении оператора заключается не там, где определён оператор, а где то в другом месте программы. Рисунок 3.20 отображает два варианта: немедленное выполнение <stmt> и выполнение с задержкой.

Исполнение оператора

Обычное исполнение

"Пакет" оператора

Исполнение оператора

Отложенное исполнение

Рисунок 3.20: Отложенное исполнение значения процедуры

Значения процедур позволяют больше чем просто исполнение оператора. Они могут иметь аргументы, которые позволяют управлять поведением под влиянием вызова. Как мы увидим на протяжении книги, процедурная абстракция чрезвычайно мощна. Она лежит в основе высокоуровневого и объектно-ориентированного программирования, и очень полезна для построения абстракций. Рассмотрим определение:

Здесь вычисляются решения квадратного уравнения x^2 + 3x + 2 = 0. Здесь используется квадратичная формула, которая даёт два решения уравнения ax^2 + bx + c = 0. Значение d = b^2 - 4ac называется дискриминантом: если он положителен или равен нулю, то есть два вещественных решения. В противном случае два решения сопряжены с комплексными числами. Вышеприведённое определение может быть конвертировано в процедуру с помощью использования его как тела определения процедуры и передачей трёх переменных как аргументов:

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

Общие ограничения

Многие старые императивные языки имеют ограниченную форму процедурной абстракции. Для того, чтобы понять это взглянем на Pascal и C [94, 99]. В C, все определения процедур глобальны (они не могут быть вложенными). Это означает, что может существовать только одно значение процедуры соответствующее каждому определению процедуры. В Pascal определения процедур могут быть вложенными, но значения процедур могут быть использованы только в той же области видимости, что и определение процедуры и только тогда, когда программа исполняется в этой области видимости. Из-за этих ограничений невозможно в общем виде "запаковать" оператор и выполнить его где-либо ещё.

Это означает, что многие высокоуровневые техники программирования становятся невозможными. Например, невозможно запрограммировать новые управляющие абстракции. Вместо этого каждый язык предоставляет предопределённый набор управляющих абстракций (таких как циклы, условия и исключения). Всё ещё возможны некоторые высокоуровненвые техники. Например, пример с квадратным уравнением работает поскольку он не содержит внешних ссылок: он может быть определён как глобальная процедура в C и Pascal. Также, из-за этих причин часто работают общие операции (смотрите ниже).

Ограничения C и Pascal являются следствием управления памятью этими языками. В обоих языках, реализация вставляет часть хранилища в семантический стек. Эта часть хранилища обычно называется локальными переменными. Выделение выполняется в соответствии с порядком стека. Например, некоторые локальные переменные выделяются при каждом входе в процедуру и очищаются при соответствующем выходе. Эта форма автоматического управления памятью значительно проще в реализации чем сборка мусора. К несчастью, при таком подходе легко создать зависшие ссылки. Очень трудно отлаживать большую программу, которая периодически начинает вести себя некорректно из-за зависших ссылок.

Теперь мы можем описать ограничения. В C и Pascal создание значения процедуры ограничено, поэтому контекстная среда никогда не будет иметь зависших ссылок. Есть некоторые языко-специфичные техники, которые можно использовать для смягчения этого ограничения. Например, в таких объектно-ориентированных языках как C++ или Java у объектов есть возможность играть роль процедурных значений. Эта техника описана в Главе 7.

Обобщённость

Мы уже видели пример высоко-уровневого программирования в предыдущих разделах. Они были введены так плавно, что возможно вы не заметили что имеете дело с высокоуровневым программированием. Это была управляющая абстракция Iterate из Раздела 3.2.4, использующая два процедурных аргумента, Transform и IsDone.

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

Взглянем на второй пример обобщённой функции. Рассмотрим функцию SumList:

Эта функция обладает двумя определёнными сущностями: число ноль (0) и операция плюс (+). Ноль - нейтральный элемент для операции плюс. Эти две сущности можно абстрагировать. Возможны любой нейтральный элемент и любая операция. Мы зададим их как параметры. Получим следующую обобщённую функцию:

Эта функция обычно называется FoldR поскольку она ассоциирует направо. Мы можем определить SumList как специальный случай FoldR:

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

Вот другая функция, возвращающая true если в списке есть, по-крайней мере, одно true:

FoldR - это пример цикличной абстракции. В Разделе 3.6.2 рассматриваются другие разновидности цикличной абстракции.

Обобщение Mergesort

Алгоритм сортировки слиянием, который мы увидели в Разделе 3.4.2, в качестве функции сравнения использует исключительно '<'. Обобщим сортировку слиянием передав в качестве аргумента функцию сравнения. Мы изменим функцию Merge для того, чтобы она ссылалась на аргумент-функцию F и функцию MergeSort чтобы она ссылалась на новый Merge.

Здесь используется старое определение Split. Мы разместили определения Merge и MergeSort внутрь новой функции GenericMergeSort. Так мы избежали передачи функции F как аргумента в Merge и MergeSort. Вместо этого при каждом вызове GenericMergeSort определяются две процедуры. Мы можем определить исходную сортировку слиянием через GenericMergeSort:

Вместо fun {$ A B} A < B end, мы можем написать Number.'<' поскольку сравнение '<' является частью модуля Number.

Возврат новых экземпляров

Примером возврата новых экземпляров будет функция MakeSort возвращающая сортирующую функцию. Функции, такие как MakeSort иногда называются "фабриками" или "генераторами". MakeSort получает функцию булевого сравнения F и возвращает сортирующую процедуру, использующую F как функцию сравнения. Рассмотрим как построить MakeSort, используя обобщённую сортирующую процедуру Sort. Допустим, что Sort принимает два выходных данных, список L и булеву функцию F и возвращает отсортированный список. Теперь мы можем определить MakeSort:

Мы можем рассматривать MakeSort как спецификацию множества возможных сортирующих процедур. Вызов MakeSort порождает спецификацию. Он возвращает элемент множества, который мы можем называть экземпляром спецификации.

Встраивание

Значения процедур могут быть вставлены в структуры данных. Этому есть много применений:

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

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

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

3.6.2 Абстракции Цикла

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

Целочисленный цикл

Рисунок 3.21: Определение целочисленного цикла

Определим целочисленный цикл, то есть, цикл, который повторяет операцию с последовательностью целых чисел. Процедура {For A B S P} вызывает {P I} для целых чисел I, которые начинаются с A и продолжаются до B, с шагом S. Например, выполнение {For 1 10 1 Browse} напечатает целые числа 1, 2, ..., 10. Выполнение {For 10 1 ~2 Browse} напечатает 10, 8, 6, 4, 2. Цикл For определён на Рисунке 3.21. Это определение работает как для положительных, так и для отрицательных шагов. Оно использует LoopUp для положительных S и LoopDown для отрицательных S. Из-за лексической области видимости, каждому LoopUp и LoopDown требуется только один аргумент. Они видят B, S и P как внешние ссылки.

Списковой цикл

Рисунок 3.22: Определение спискового цикла

(если S > 0: продолжать до тех пор, пока A + n*S =< B

(если S < 0: продолжать до тех пор, пока A + n*S >= B

(где L = [X1 X2 ... Xn])

Рисунок 3.23: Простые циклы поверх целых чисел и списков

Определим простой цикл, то есть, цикл, который повторяет операции для всех элементов списка. Процедура {ForAll L P} вызывает {P X} для всех элементов X списка L. Например, {ForAll [a b c] Browse} отобразит a, b, c. Цикл ForAll определён на Рисунке 3.22. На Рисунке 3.23 приведено графическое сравнение For и ForAll.

Аккумулирующие циклы

Рисунок 3.24: Определение циклов с аккумуляторами

Цикл с аккумулятором поверх целых чисел

(если S > 0: продолжать пока A + n*S =< B)

(если S < 0: продолжать пока A + n*S >= B)

Цикл с аккумулятором поверх списка

(где L = [X1 X2 ... Xn])

Рисунок 3.25: Циклы с аккумуляторами поверх целых чисел и списков

Циклы For и ForAll просто повторяют действия на различных аргументах, но они не вычисляют никакого результата. Это свойство делает их весьма бесполезными в декларативной модели. Они раскроют свою ценность только в модели с состояниями в Главе 6. Для того, чтобы быть полезными в декларативной модели, циклы могут быть расширены аккумуляторами. Таким образом, они могут вычислять результат. Рисунок 3.24 определяет ForAcc и ForAllAcc, являющиеся расширенными For и ForAll с помощью аккумуляторов.15 ForAcc и ForAllAcc - это рабочие лошадки декларативной модели. Они оба определены с переменной Mid, используемой для передачи текущего состояния аккумулятора в оставшуюся часть цикла. На Рисунке 3.25 приведено графическое сравнение ForAcc и ForAllAcc.

15 В системе Mozart ForAcc и ForAllAcc вызываются как ForThread и FoldL.

Свёртка списка

Есть другая точка зрения на циклы с аккумуляторами поверх списков. На них можно смотреть как на операцию "сворачивания" списка, где свёртка обозначает вставку инфиксного оператора между элементами списка. Рассмотрим список l = [x1 x2 x3 ... xn]. Тогда свёртка l с помощью инфиксного оператора f даст:

Для того, чтобы однозначно вычислить это выражение мы добавим скобки. Есть две возможности. Вначале мы можем выполнить левосторонние операции (ассоциирование слева):

или выполнить первыми правосторонние операции (ассоциирование справа):

В качестве последнего штриха, мы слегка модифицировали эти выражения так, что каждое использование f включает в себя только один элемент l. Такая модификация позволяет облегчить вычисление и рассуждения. Для этого мы добавим нейтральный элемент u. Что в свою очередь даёт нам следующие два выражения:

Для вычисления этих выражений мы определяем две функции {FoldL L F U} и {FoldR L F U}. Функция {FoldL L F U} выполняет следующее:

Функция {FoldR L F U} выполняет следующее:

Цикл с аккумулятором поверх целых чисел

(если S>0: до тех пор, пока A+n*S=<B)
(если S<0: до тех пор, пока A+n*S>=B)

Цикл с аккумулятором поверх списка

(где L=[X1 X2 ... Xn])

Рисунок 3.25: Циклы с аккумуляторами поверх целых чисел и списков

Свёртка слева

Свёртка справа

Рисунок 3.26: Свёртка списка

Рисунок 3.26 показывает FoldL и FoldR в графическом виде. Мы можем обнаружить родство FoldL и FoldR с ранее увиденными циклами с аккумуляторами. Сравнивая Рисунок 3.25 и Рисунок 3.26 мы можем увидеть, что FoldL - это лишь другое имя для ForAllAcc.

Итеративные определения свёртки

Рисунок 3.24 определяет итеративный ForAllAcc и, таким образом, FoldL. Вот то же определение в функциональной нотации:

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

Что насчёт FoldR? Дискуссия об обобщённости в Разделе 3.6.1 даёт рекурсивное определение, а не итеративное. На первый взгляд, итеративно определить FoldR - не так просто. Вы можете дать итеративное определение FoldR? Способ сделать это - определить промежуточное состояние и функцию трансформации состояния. Посмотрите на выражение выше: что является промежуточным состоянием? Как вы получите следующее состояние? Прежде чем подсмотреть ответ мы рекомендуем вам отложить книгу и попытаться определить итеративный FoldR. Вот один из возможных определений:

Поскольку FoldR начинает вычисление с Xn, последнего элемента L, то идея заключается в итерации поверх реверсированного L. Ранее мы увидели как определить итеративный реверс.

3.6.3 Лингвистическая поддержка циклов

Из-за того, что циклы настолько полезны, то они - идеальный кандидат на лингвистическую абстракцию. В этом разделе определяется декларативный цикл for, являющийся одним из способов реализации лингвистической абстракции. Цикл for определён как часть системы Mozart [47]. Цикл for очень близок к циклическим абстракциям из предыдущего раздела. Использование циклов for часто оказывается проще чем использование циклических абстракций. При написании циклов мы рекомендуем вначале испытать for.

Итерации через целые числа

Общая операция - это итерация по последовательным числам с нижней границы I до верхней границы J. Без синтаксиса цикла, стандартным декларативным способом выполнения этой операции будет использование абстракции {For A B S P}:

Это эквивалент следующего цикла for:

когда шаг S равен 1, или:

когда S отличается от 1. Цикл for определяет счётчик цикла I, переменная, чья область видимости распространяется на тело цикла <stmt>.

Декларативные циклы против императивных

Есть фундаментальная разница между декларативным циклом и императивным циклом, то есть, циклом, в таких императивных языках как C или Java. В последнем счётчик цикла - это переменная с присваиваемым значением, где значение отличается для каждой итерации. Декларативный цикл достаточно отличается: для каждой итерации он определяет новое значение. Декларативный цикл достаточно отличается: для каждой итерации он определяет новую переменную. Ссылка на все эти переменные осуществляется через один идентификатор. Для всех переменных не выполняется разрушающее присваивание. Это отличие может привести к важным последствиям. Например, итерации декларативного цикла полностью независимы друг от друга. Следовательно, возможен их параллельный запуск не приводящий к изменению конечного результата цикла. Например:

параллельно запускаются все итерации, но каждая из них по-прежнему будет иметь доступ к правильному значению I. Вставка <stmt> внутрь определения thread ... end запускает его как независимое действие. Это пример декларативного параллелизма, что в является темой Главы 4. Выполнение подобного действия в императивном цикле приведёт к разрушению, поскольку каждая итерация больше не может быть уверена в том, что она имеет доступ к правильному значению I. Инкремент счётчика цикла больше не будет синхронизирован с итерациями.

Итерация через списки

Цикл for может быть расширен для того, чтобы выполнять итерацию через списки также, как и через целочисленные интервалы. Наприер, вызов:

эквивалентен

Также, как и с ForAll, список может быть потоком элементов.

Образцы

Цикл loop может быть расширен для содержания шаблонов, неявно определяющих переменные. Например, если элементы L - тройка в форме obj(name:N price:P coordinates:C), то мы можем пройтись по ним циклом следующим образом:

Здесь определяются и привязываются новые переменные N, P и C для каждой итерации. Их область видимости распространяется на всё тело цикла.

Сбор результатов

Полезное расширение цикла for, предназначенное для сбора результатов. Например, создадим список всех целых чисел с 1 до 1000 не делящихся ни на 2 и ни на 3:

Цикл loop - это выражение, которое возвращает список. Объявление "collect:C" определяет процедуру сбора C, которое может быть использовано в любом месте тела цикла. Процедура сбора использует аккумулятор для сбора элементов. Предыдущий пример эквивалентен такому:

В целом цикл loop более выразителен чем этот пример поскольку процедура сбора может быть вызвана из глубоко вложенных циклов и других процедур без явного использования аккумулятора в нити. Вот пример с двумя вложенными циклами:

Как это достигается в цикле loop без применения в нити аккумулятора? Как мы увидим в Главе 6, цикл использует явное состояние.

Другие полезные расширения

Приведённые выше примеры дают некоторые наиболее используемые идиомы в синтаксисе декларативного цикла. Возможно большое количество идиом циклирования. Например: незамедлительный выход из цикла (break), незамедлительный выход и явный возврат результата (return), незамедлительное продолжение со следующей итерации (continue), несколько итераторов, расширяющих шаг цикла, и другие процедуры сбора (например, append и prepend для списков и sum и maximize для целых чисел). За другими примерами архитектур декларативных циклов мы рекомендуем изучить макрос loop из Common Lisp [181] и пакет тредов с состоянием из SICStus Prolog [96].

3.6.4 Техники, управляемые данными

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

Техники на основе списка

Высокоуровневое программирование часто используется совместно со списками. Некоторые из цикличиских абстракций этого вида мы уже видели, например, FoldL и FoldR. Рассмотрим некоторые другие техники на основе списков.

Общая списковая операция - это Map, которая вычисляет новый список из старого списка через применение функции к каждому элементу. Например, {Map [1 2 3] fun {$ I} I*I end} вернёт [1 4 9]. Он определён следующим образом:

Его тип <fun {$ <List T> <fun {$ T} : U>} : <List U>>. Map может быть определён с помощью FoldR. Выходной список сконструирован с использованием аккумулятора FoldR:

Что случится если мы будем использовать FoldL вместо FoldR? Другая общая списковая операция - это Filter, которая применяет булеву функцию к каждому элементу списка и возвращает список всех элементов, для которых булева функция вернула true. Например, {Filter [1 2 3 4] fun {$ A B} A<3 end} возвращает [1 2]. Filter определён следующим образом:

Его тип <fun {$ <List T> <fun {$ T T} : <bool>>} : <List T>>. Также Filter можно определить с помощью FoldR:

Оказывается, что FoldR чрезвычайно гибкая функция. Этот факт не должен для вас быть сюрпризом поскольку FoldR - просто for цикл с аккумулятором! Сам FoldR может быть реализован в терминах обобщённого итератора Iterate из Раздела 3.2:

Поскольку Iterate - это while цикл с аккумулятором, то он является самой гибкой цикличной абстракцией из всех увиденных нами. Все другие цикличные абстракции могут быть запрограммированы в терминах Iterate. Например, для того, чтобы запрограммировать FoldR мы только правильно закодировали состояние и функцию окончания. Здесь мы закодировали состояние как пару Xr#A, где Xr - это недостаточно использованная часть входного списка и A - это аккумулированный результат FoldR. Осторожно с деталями: начальный вызов Reverse и .2 в конце для получения аккумулированного результата.

Техники на основе деревьев

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

Рассмотрим n-ичное дерево, являющееся более обобщённым чем двоичное дерево уже увиденное нами. N-ичное дерево можно определить следующим образом:

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

Мы можем "декорировать" эту процедуру для того чтобы выполнять что-либо в каждом посещаемом узле. Например, будем вызывать {P T} для каждого узла T. Получим следующую обобщённую процедуру:

Чуть более сложный проход - это вызов {P Tree T} для каждой связи отец-сын между отцовским узлом Tree и одним из его сыновей T:

Эти две обобщённые процедуры были использованы для отрисовки деревьев Раздела 3.4.7 после вычисления позиций узлов. VisitLinks рисует линии между узлами, а VisitNodes рисует сами узлы.

Следуя разработке из Раздела 3.4.6, мы расширили эти проходы аккумулятором. Способов аккумулирования столько же, сколько и способов прохода. Техники аккумулирования могут идти сверху-вниз (результат вычисляется через переход от отца к его сыновьям), снизу-вверх (от сыновей к отцу) или через использование какого-либо другого порядка (например, по ширине дерева, прохода по ширине). В сравнении со списками, сверху-вниз похож на FoldL и снизу-вверх похож на FoldR. Выполним аккумулирование снизу-вверх. Вначале вычислим свёрнутое значение для каждого узла. Тогда свёрнутое значение для отца будет представлять функцию от отцовского узла и значений для сыновей. Есть две функции: LF для свёртки вместе всех сыновей данного отца и TF для свёртки их результата вместе с отцом. Всё вместе даёт следующую обобщённую функцию с аккумулятором:

Вот пример вызова:

Будет отображено 10, сумма значений всех узлов.

3.6.5 Явное ленивое вычисление

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

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

Для реализации ленивого исполнения потребитель должен иметь механизм, запрашивающий новые элементы. Мы называем такой механизм триггером. Есть два естественных пути выражения триггеров в декларативной модели: как переменную потока данных или с помощью высокоуровневого программирования. Раздел 4.3.3 описывает работу с переменной потока данных. Здесь мы опишем как работать с высокоуровневым программированием. Пользователь имеет функцию, которую он вызывает при надобности в новом элементе списка. Вызов функции возвращает пару: элемент списка и новую функцию. Новая функция представляет новый триггер: её вызов возвращает следующий экземпляр данных и другую новую функцию. И так далее.

3.6.6. Каррирование

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

можно переписать следующим образом:

Здесь содержится то же тело функции. Оно вызывается как {{Max 10} 20}, возвращает 20. Преимущество использования каррирования в том, что промежуточные функции могут быть полезны сами по себе. Например, функция {Max 10} возвращает результат, который никогда не будет меньше чем 10. Это называется частично применённой функцией. Мы можем дать ей название LowerBound10:

Во многих функциональных языках программирования, в частности, Standard ML и Haskell, все функции неявно каррированы. Для использования максимальных преимуществ каррирования, эти языки дают простой синтаксис и эффективную реализацию. Они определяют синтаксис так, что каррируемая функция может быть определена без вставки каких-либо ключевых слов и вызываема без скобок. Если возможен вызов функции max 10 20, то также возможен и max 10. Реализация делает каррирование настолько дешёвым, насколько это возможно. Она не создаёт никаких расходов если ей не пользоваться и конструирования частично применяемых функций можно избежать там, где это возможно.

Декларативная вычислительная модель этой главы не содержит никакой специальной поддержки каррирования. Система Mozart не содержит ни синтаксическую ни реализационную поддержку каррирования. Большая часть каррирования в Mozart - проста. Однако, интенсивное использование высокоуровневого программирования, как это сделано в функциональных языках, может служить оправданием для поддержки каррирования. В Mozart частично применяемые функции определяются явно. Например, функция max 10 может быть определена следующим образом:

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

3.7 Абстрактные типы данных

Тип данных, или просто тип, - это набор значений совместно с набором операций над этими значениями. Декларативная модель изначально дана с предопределённым набором типов, называемых базовыми типами (смотрите Раздел 2.3). В дополнение к ним, пользователь волен определять новые типы. Мы говорим, что тип абстрактен если он полностью определён его набором операций, невзирая на реализацию. Сокращается как ADT (Abstract data type - Абстракный тип данных). Это означает, что возможно изменить реализацию типа без изменения способа его использования. Исследуем как пользователь может определять новые абстрактные типы.

3.7.1 Декларативный стек

Для того, чтобы начать этот раздел, дадим простой пример абстрактного типа данных, стек <Stack T>, где его элементы принадлежат типу T. Допустим, что стек обладает четырьмя операциями с следующими типами:

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

* {IsEmpty {NewStack}}=true. Новый стек всегда пуст.

* Для любого E и S0, сохраняются S1={Push S0 E} и S0={Pop S1 E}. Вставка и извлечение элемента даст тот же элемент.

* {Pop {EmptyStack}} вызовет ошибку. Из пустого стека невозможно извлечь никакой элемент.

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

Вот другая реализация удовлетворяющая законам:

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

Вид функционального программирования

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

что возвращает два вывода как пару, но мы решили не делать этого. Написание {Pop S E} - это пример программирования с функциональным видом, где используется функциональный синтаксис для операций не обязательно являющихся математическими функциями. Мы считаем, что это оправдано для программ, которые имеют ясную направленность в потоке данных. Может быть интересным выделить направленность даже если программа не функциональна. В некоторых случаях такой подход может сделать программу менее длинной и более читаемой. Но функциональный вид следует использовать осторожно и только в случаях, где ясно, что операция не математическая функция. Иногда мы будем использовать функциональный вид на протяжении всей книги, если мы решим, что он будет уместен.

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

3.7.2 Декларативный словарь

Дадим другой пример, чрезвычайно полезный абстрактный тип данных под названием словарь. Словарь - это конечное отображение из множества простых констант во множество сущностей языка. Каждая константа отображается в одну сущность языка. Константы называются ключами поскольку они разблокируют путь к сущности в некотором интуитивном смысле. В качестве констант мы будем использовать атомы или целые числа. Нам бы хотелось иметь возможность создавать динамическое отображение, то есть, с помощью добавления новых ключей во время исполнения. Получаем следующий набор базовых функций на новом типе <Dict>:

* <fun {NewDictionary} : <Dict>> возвращает новый пустой словарь.

* <fun {Put <Dict> <Feature> <Value>}: <Dict>> получает словарь и возвращает новый словарь, который добавляет отображение <Feature> -> <Value>. Если <Feature> уже существует, то новый словарь замещает его значением <Value>.

* <fun {Get <Dict> <Feature>}: <Value>> возвращает значение соответствующее <Feature>. Если его нет, то порождается исключение.

* <fun {Domain <Dict>}: <List <Feature>>> возвращает список ключей в <Dict>.

Для этого примера мы определили тип <Feature> как <Atom>|<Int>.

Реализация на основе списка

Рисунок 3.27: Декларативный словарь (с линейным списком)

Рисунок 3.27 показывает реализацию в котором словарь представлен как список пар Key#Value отсортированный по ключу Key. Вместо Get мы определим слегка более обобщённую операцию доступа, CondGet:

* <fun {CondGet <Dict> <Feature> <Value>1}: <Value>2> возвращает значение, соответствующее <Feature>. Если <Feature> не существует, то возвращается <Value>1.

CondGet почти так же лёгок в реализации, как и Get и, как мы увидим в следующем примере, очень удобен.

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

Реализация на основе деревья

Рисунок 3.28: Декларативный словарь (с упорядоченным бинарным деревом)

Более эффективная реализация словарей получается при использовании упорядоченного двоичного дерева, пример двоичного дерева дан в Разделе 3.4.6. Put - это просто Insert и CondGet очень похож на Lookup. Получаем определения, данные на Рисунке 3.28. В этой реализации, операции Put и CondGet занимают время равное O(log n) и память на дерево с n узлами с учётом того, что дерево "разумно сбалансировано". То есть, для каждого узла размеры правого и левого поддеревьев не должны "сильно отличаться".

Реализация на основе состояния

Мы можем создать реализацию даже более лучшую чем на основе дерева если оставим декларативную модель и используем явное состояние (смотрите Раздел 6.5.1). Так мы получим словарь с состоянием, его тип будет слегка отличаться от декларативного словаря. Но его функционал будет тем же. Использование состояния даёт нам преимущество, поскольку он сокращает время исполнения операций Put и CondGet до амортизированного постоянного значения.

3.7.3 Приложение для подсчёта частоты появления слов

Рисунок 3.29: Частота слова (с декларативным словарём)

Для сравнения наших четырёх реализаций словарей, используем их в простом приложении. Напишем программу для подсчёта частоты слов в строке. Позже мы увидим как использовать эту программу для подсчёта слов в файле. Рисунок 3.29 определяет функцию WordFreq, которая получает список символов Cs и возвращает список пар W#N, где W - это слово (максимальная букв и цифр) и N - это число, обозначающая сколько раз это слово было встречено в Cs. Функция WordFreq определена в терминах следующих функций:

* {WordChar C} возвращает true если C является буквой или цифрой.

* {WordToAtom PW} конвертирует реверсированный список символов слова в атом, содержащий эти символы. Функция StringToAtom использована для создания атома.

* {IncWord D W} получает словарь D и атом W. Возвращает новый словарь, в котором поле W увеличено на 1. Отметим насколько просто это написать с помощью CondGet, который заботится о случае, когда W ещё не находится в словаре.

* {CharsToWords nil Cs} получает список символов Cs и возвращает список атомов, где символы в каждом напечатанном имени атома формируют слово в Cs. Функция Char.toLower используется для конвертации букв в верхнем регистре в нижний регистр, таким образом "The" и "the" считаются одним и тем же словом.

* {CountWords D Ws} получают пустой словарь и вывод CharsToWords. Возвращается словарь, в котором каждый ключ отображается в количество встреченного слова.

Вот пример работы. Следующий ввод:

отобразит количество слов:

Рисунок 3.30: Внутренняя структура двоичного дерева словаря в WordFreq (некоторая часть)

Мы запустили WordFreq на более существенном тексте, а именно на ранней версии этой книги. Текст содержал 712626 символов, в целом давших 110457 слов из них 5561 разных слов. Мы запускали WordFreq с тремя реализациями словарей: используя списки (смотрите предыдущий пример), используя двоичное дерево (смотрите Раздел 3.7.2) и используя состояние (встроенная реализация словарей; смотрите Раздел 6.8.2). Рисунок 3.30 показывает часть внутренней структуры двоичного дерева словаря, нарисован с помощью алгоритма из Раздела 3.4.7. Замер кода приведён в Разделе 3.8.1. Запуск реализаций дал следующие временные показатели (точность 10%): 16

16 Использовался Mozart 1.1.0 под Red Hat Linux выпуск 6.1 на компьютере ноутбуке Dell Latitude CPx с процессором Pentium III 500 MHz.

Реализация словаря
С использованием списков
С использованием упорядоченного двоичного дерева
С использованием состояния

Время исполнения
620 секунд
8 секунд
2 секунды

Временная сложность
O(n)
O(log n)
O(1)

Время - это физическое время, затраченное на выполнение всех операций, то есть, чтение текстового файла, запуск WordFreq и запись в файл сведений о количестве слов. Разница между тремя затраченными количествами времени связана с различными реализациями словаря. Сравнение времени даёт хороший пример практического эффекта от использования различных реализаций важных типов данных. Сложность показывает как зависит время, затрачиваемое на вставку или поиск одного элемента, от размера словаря.

3.7.4 Безопасные абстрактные типы данных

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

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

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

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

* Программа подвержена вмешательству злоумышленника. Это более тонкая проблема, которая имеет отношение к безопасности. Она не возникает в программах, написанных людьми, доверяющими друг-другу. Чаще она проявляется в открытых программах. Открытая программа - это программа, которая взаимодействует с другой программой известной только во время исполнения. Что если другая программа была написана злоумышленником и её цель - в нарушении исполнения открытой программы? В связи с эволюцией Интернета пропорции открытых программ увеличиваются.

Как мы решим эти проблемы? Основная идея - в защите внутреннего представления значений абстрактного типа данных, например, значений стека от неправомочного вмешательства. Защищаемое значение размещает изнутри барьер защиты. Есть два способа использования этого барьера:

* Стационарное значение. Значение никогда не покидает барьер. Чётко определённый набор операций может проходить через барьер и производить вычисления со значением. Результат вычислений остаётся внутри барьера.

* Мобильное значение. Значение может покидать и заново входить в барьер. Когда значение за пределами барьера, то над ним можно выполнять операции. Операции с соответствующим допуском могут извлекать значение из барьера и производить с ним вычисления. Результат помещается обратно в барьер.

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

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

В следующем разделе мы построим безопасный абстрактный тип данных с помощью второго решения. Этот способ наиболее лёгок для понимания в декларативной модели. Для авторизации нам нужно ввести защитный барьер в виде "ключа". Мы добавим его как новую концепцию декларативной модели, под названием name (имя). Раздел 3.7.7 описывает, что ключ - это пример очень общей идеи безопасности, под названием capability (возможность). В Главе 6, Раздел 6.4 завершается история о безопасных типах данных демонстрацией способа реализации первого решения и описанием эффекта, оказываемого явным состоянием на безопасность.

3.7.5 Декларативная модель с безопасными типами

Пустой оператор
Последовательность оператора
Создание переменной
Привязка переменная-переменная
Создание значения
Условие
Сопоставление с образцом
Применение процедуры
Контекст исключения
Порождение исключения
Создание имени
Просмотр без возможности записи

Таблица 3.6: Декларативный язык ядра с безопасными типами

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

Защита значений

Один из способов защитить значения - это добавление операции "обёртки" с "ключом". То есть, внутреннее представление размещено внутри структуры данных, недоступных для всех, кто не знает специального значения, ключа. Знание ключа позволяет создавать новые обёртки и заглянуть внутрь существующих обёрток, сделанных с помощью этого ключа.

Мы реализуем это с помощью нового базового типа под названием имя (name). Имя - это постоянная величина, как и атом, с тем исключением, что имя обладает значительно более ограниченным набором операций. В частности, имена не обладают текстовым представлением: они не могут быть распечатаны или набраны на клавиатуре. В отличие от атомов, невозможно выполнить преобразование между именами и строками. Единственный путь узнать имя - это передать ссылку к нему в программе. Тип имени обладает всего двумя операциями:

Операция
Описание
Возврат нового имени
Сравнение имён N1 и N2

Новое имя - это одно из имён, гарантированно отличающихся от всех других имён системы. Уведомим читателей, что NewName не декларативен, поскольку его повторный вызов вернёт другое значение. На самом деле, создание новых имён - это операция с состоянием. Гарантия уникальности означает что NewName обладает некоторой внутренней памятью. Однако, если мы используем NewName только для того, чтобы защитить декларативный абстрактный тип данных, то никакой проблемы не возникнет. В результате защищённый абстрактный тип данных остаётся декларативным.

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

Это значение - внутреннее состояние типа, ранее определённого нами. Защитить его мы может так:

Вначале создаётся новое имя в Key. Затем создаётся функция, которая может вернуть S, но только при условии корректного переданного аргумента. Мы говорим, что значение S "завёрнуто" внутрь SS. Если известен ключ Key, то можно легко получить доступ к SS:

Мы говорим, что значение S "развёрнуто" из SS. Если не знать ключа Key, то развернуть значение не получится. Нет никакого способа узнать ключ Key кроме как явно передать его в программе. Вызов SS с неправильным аргументом просто породит исключение.

Обёртщик

Мы можем определить абстрактный тип данных для того, чтобы выполнять заворачивание и разворачивание. Тип определяет две операции, Wrap и Unwrap. Wrap получает любое значение и возвращает защищённое значение. Unwrap получает любое защищённое значение и возвращает исходное значение. Операции Wrap и Unwrap идут в парах. Единственный способ развернуть завёрнутое значение - это применить соответствующую операцию развёртки. С помощью имён мы можем определить процедуру NewWrapper, которая будет возвращать пары Wrap/Unwrap:

Для максимальной защиты, каждая абстрактный тип данных может использовать свою собственную пару Wrap/Unwrap. Так они защитятся как друг от друга, так и от главной программы. Зададим значение S как и раньше:

мы защитим его таким образом:

Мы можем получить исходное значение таким образом:

Защищённый стек

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

Защищённое значение

Реализация защищённого стека

Разворачивание с помощью

Заворачивание с помощью

Рисунок 3.31: Выполнение S1={Pop S X} с защищённым стеком

Рисунок 3.31 иллюстрирует операцию Pop. Ящик с замочной скважиной представляет защищённое значение. Ключ представляет имя, предназначенное для внутреннего использования Wrap-ом и Unwrap-ом для запирания и открытия коробки. Лексическая область видимости гарантирует что заворачивание и разворачивание возможно только внутри реализации стека. А именно, идентификаторы Wrap и Unwrap видимы только изнутри локального оператора. За пределами этой области видимости они не видны. Поскольку Unwrap скрыт, то нет абсолютно никакого способа увидеть внутренность значения стека. Поскольку Wrap скрыт, нет абсолютно никакого способа "подделать" значения стека.

Защита несвязанных переменных

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

Переменная X не защищена поскольку все, кто знает S, могут связать X.

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

Операция
Описание

Возвращает доступ для чтения X

Любая попытка связать доступ для чтения будет блокироваться. Любое связывание X будет переноситься на доступ для чтения. Для защиты потока, его хвост должен быть доступен только для чтения.

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

Создание новых имён

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

* Централизованный подход. Где-то в мире есть фабрика имён. Для получения нового имени вам нужно послать сообщение этой фабрике и в ответе будет содержаться новое имя. Фабрика имён не должна физически располагаться в одном месте; она может быть распределена на множестве разных компьютеров. Например, IP протокол допускает уникальные IP адреса для каждого компьютера на свете, подключённого к Интернету. Хотя IP адреса могут меняться с течением времени, например, если использована сетевая трансляция адресов или динамическое выделение IP адресов с использованием протокола DHCP. В этом случае мы дополняем IP адреса временным штампом с высоким разрешением, дающим время создания NewName. Так мы получаем уникальную константу, которая может быть использована для реализации локальной фабрики имён на каждом компьютере.

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

Теперь, когда у нас есть уникальное имя, как нам убедиться что оно не подделываемо? Это потребует криптографических техник, которые лежат за пределами этой книги [166].

3.7.6 Защищённый декларативный словарь

Теперь рассмотрим как защитить декларативный словарь. Это достаточно легко. Мы можем использовать ту же технику, что и для стека, а именно, используем обёртки и развёртки. Вот новое определение:

Поскольку Wrap и Unwrap известны только внутри локальной области видимости, то завёрнутый словарь нельзя развернуть ничем снаружи этой области. Эта техника работает как для спискового словаря, так и для словаря на основе дерева.

3.7.7 Возможности и безопасность

Мы говорим, что вычисление защищено, если оно имеет хорошо определённые и контролируемые свойства, независимые от существования других (возможно злонамеренных) факторов (либо вычислений, либо людей) в системе [4]. Мы называем эти факторы "неприятелями". Безопасность использует защиту и от зловредных вычислений, и от не злоумышленных (но ошибочных) вычислений. Свойство, обозначающее безопасность - глобально; "взлом" системы может возникнуть на любом уровне, начиная от аппаратного обеспечения, и до организации человеком размещения системы. Безопасность компьютерных систем обозначает собой не только информатику, но также и много аспектов человеческого общества [5].

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

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

17 Нахождение внутри языка может быть гарантировано запуском программ только в виртуальной машине, которая принимает только исполняемые файлы авторизованных программ.

Возможности

Введённые нами техники защиты абстрактных типов данных являются особыми случаями концепции безопасности под названием возможность. Возможности - это сердце современных исследований в безопасных языках. Например, безопасный язык E предъявляет такие строгие требования к ссылкам языка, что они ведут себя как свойства [123, 183]. Ранее введённые нами пары Wrap/Unwrap называются в E парами закрываетелей/открывателей. Вместо того, чтобы использовать внешние ссылки для защиты значений, пары закрывателей/открывателей зашифровывают и расшифровывают значения. С этой точки зрения, имя используется как ключ зашифровки и расшифровки.

Концепция возможности была введена в 1960-х годах в контексте архитектуры операционных систем. Операционные системы должны всегда защищать пользователей друг от друга в то же время давая им возможность выполнять свою работу. С этих ранних работ стало ясно что концепция принадлежит языку программирования и в целом она полезна для построения безопасных программ [124]. Возможности могут быть определены многими способами, но последующее определение разумно для языка программирования. Возможность - это не подделываемая сущность языка, которая даёт его хозяину право выполнять заданный набор действий. Набор действий определён внутри возможности и может изменяться со временем. Под выражением "не подделываемая" мы имеем ввиду что ни для какой реализации, даже если она очень сильно связана с такими архитектурными особенностями языка, как язык сборки, невозможно создать возможность. В литературе по E это свойство подытоживается фразой "подключения порождают подключения": единственный способ получить новые возможности - это явно передать их через существующие возможности [125].

В этом смысле все значения типов данных являются возможностями поскольку они дают их хозяевам право выполнять все операции с этим типом, но не более. Хозяин сущности языка - это любой фрагмент программы, ссылающейся на эту сущность. Например, запись R даёт его владельцу право выполнять множество операций, включая выбор поля R.F и чётность {Arity R}. Процедура P даёт её владельцу право на вызов P. Имя даёт его владельцу право сравнивать его значение с другими значениями. Не привязанные переменные дают его владельцу право привязывать его и читать его значение. Переменная доступная только для чтения даёт его владельцу право читать его значение, но не привязывать его.

Новые возможности могут быть определены во время исполнения программы как экземпляры Абстрактных Типов Данных. Для моделей этой книги простейшим способом является использование значений процедур. Ссылка на значение процедуры даёт его владельцу право вызывать процедуру, то есть, выполнять все действия, для которых была спроектирована процедура. Более того, ссылку на процедуру невозможно подделать. В программе, единственный способ которым можно узнать ссылку - только если она передана явно. Процедура может скрывать всю свою важную информацию в её внешних ссылках. Для того, чтобы всё это работало язык должен гарантировать что знание процедуры не означает автоматического получения права изучения внешних ссылок процедуры!

Принцип наименьшей привилегии

Принцип наименьшей привилегии является важным архитектурный принципом систем безопасности: каждая сущность должна быть задана с наименьшей властью (или "привилегией"), необходимой для выполнения её работы. Также этот принцип называется принципом наименьшей власти (principle of least authority - POLA) или принципом "необходимых знаний". Точное определение минимальной власти для всех случаев - это не решаемая задача: не существует алгоритма, для нахождения решений во всех случаях. Происходит это потому, что власть зависит от того, что выполняет сущность в процессе исполнения. Если бы у нас был такой алгоритм, то он был бы достаточно мощным для того, чтобы решить Проблему Останова, было доказано что она не имеет решений.

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

Возможности и явное состояние

Для того, чтобы быть полезными на практике декларативным возможностям, то есть, возможностям, написанным в модели декларативного вычисления, недостаёт одного важного свойства. Набор действий, находящихся в их ведении нельзя изменять с течением времени. В частности, ни один из их действий невозможно аннулировать. Для того, чтобы возможность была отзываемой вычислительной модели нужна дополнительная концепция, а именно, явное состояние. Это объясняется в Разделе 6.4.3.

3.8 Недекларативные нужды

Декларативное программирование, из-за его "чистой функциональной" точки зрения на программирование, несколько оторвано от настоящего мира в котором сущности обладают памятью (состоянием) и могут развиваться независимо и упреждающе (параллелизм). Для подключения декларативных программ к реальному миру, требуются некоторые недекларативные операции. Этот раздел рассказывает о двух классах подобных операций: файловый I/O (ввод/вывод) и графический интерфейс пользователя. Третий класс операций, обособленная компиляция, дан в Разделе 3.9.

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

Новые операции введённые в этом разделе собраны в модули. Модуль - это просто запись, группирующая вместе связанные операции. Например, модуль List группирует множество операций со списками, такими как List.append и List.member (на которые можно сослаться как на Append и Member). Этот раздел вводит три модуля File (для файлового Ввода/Вывода текста), QTk (для графического интерфейса пользователя) и Pickle (для файлового Ввода/Вывода любых значений). Некоторые из этих модулей (таких как Pickle) известны сразу при запуске Mozart. Остальные модули можно загрузить с помощью вызова Module.link. В дальнейшем мы покажем как это выполнить для File и QTk. Больше информации о модулях и о том как их использовать дано позже, в Разделе 3.9.

3.8.1 Файл: текстовый ввод/вывод

Простой способ соединить декларативное программирование с реальным миром - это использовать файлы. Файл - это последовательность значений, которые хранятся снаружи программы на постоянном носителе-хранилище, например, жёсткий диск. Текстовый файл - это последовательность символов. В этом разделе мы покажем как читать и писать текстовые файлы. Этого достаточно для практического использования декларативных программ. Базовый шаблон доступа прост:

Файл с данными -> (чтение) вычисление функции -> (запись) вывод результатов в файл

Мы используем модуль File, который может быть найден на Web сайте книги. Позже мы будем делать более усложнённые файловые операции, но на данный момент нам достаточно этого модуля.

Загрузка модуля File

Первый шаг - это загрузка модуля File в систему как это описано в Приложении A.1.2. Мы полагаем, что вы имеете скомпилированную версию модуля File в файле File.ozf. Затем выполните следующее:

Будет вызван Module.link со списком путей к скомпилированным модулям. Здесь есть только один. Модуль загружается, выполняется линковка с системой, инициализируется и связывается с File.18 Теперь мы готовы выполнять файловые операции.

18 Для точности, модуль загружается лениво: на самом деле он будет загружен при первом его использовании.

Чтение файла

Операция File.readList считывает всё содержимое файла в строку:

Этот пример читает файл foo.txt в L. Также мы можем записать его как:

Помните, что "foo.txt" - это строка (список кодов символов) и 'foo.txt' - атом (константа в напечатанном представлении). Имя файла может быть представлено обоими путями. Есть третий способ представить имена файлов: как виртуальные строки. Виртуальная строка - это кортеж с меткой '#' представляющей строку. Точно также можно было бы ввести следующее:

Кортеж foo#'.'#txt, который также можно записать как '#'(foo '.' txt), представляет строку "foo.txt". Использование виртуальных строк позволяет избежать необходимости выполнять явное сложение строк. Все встроенные в Mozart операции, работающие со строками также работают с виртуальными строками. Все три способа загрузки foo.txt имеют тот же эффект. Они привязывают L к списку кодов из файла foo.txt.

Также файлы можно передавать через URL. URL даёт удобный глобальный адрес для файлов поскольку такой способ широко поддерживается через инфраструктуру World-Wide Web. Прочесть файл через его URL также просто как и через его имя:

Это всё что нужно. URL-ы могут использоваться только для чтения файлов, но не для записи файлов. Происходит это потому, что URL-ы обслуживаются Web серверами, которые обычно настроены так, что позволяют только читать файлы.

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

Запись файла

Обычно запись файла выполняется инкрементально, через последовательное добавление одной строки в файл. Модуль File предоставляет три операции: File.writeOpen - для открытия файла, которое нужно выполнять первым, File.write - для добавления строки в файл и File.writeClose - для закрытия файла, последнее, что нужно сделать. Вот пример:

После этих операций файл 'foo.txt' будет иметь три такие строки текста:

Исполнение примера

В Разделе 3.7.3 мы определили функцию WordFreq, подсчитывающую частоту слов в строке. Мы можем использовать эту функцию для подсчёта частоты слов и записи частот в файл:

В Разделе 3.7.3 даны некоторые временные замеры этого кода при использовании различных реализаций словаря.

3.8.2 Текстовый ввод/вывод с графическим интерфейсом пользователя

Самый короткий путь осуществить взаимодействие программ с пользователем-человеком - это через графический интерфейс пользователя. В этом разделе будет показан простой, но достаточно мощный способ определить графический интерфейс пользователя, а именно, из соображений краткости, в основном в декларативных спецификациях. Это отличный пример описательного декларативного языка, как это описано в Разделе 3.1. Описательный язык определён в модуле QTk системы Mozart. Интерфейс пользователя определён как вложенная запись, дополненная объектами и процедурами. (Объекты вводятся в Главе 7. А сейчас вы можете рассматривать их как процедуры с внутренним состоянием, как примеры Главы 1.)

Этот раздел показывает как строить интерфейсы пользователя для ввода и вывода текстовых данных в окно. Этого достаточно для многих декларативных программ. Мы дадим короткий обзор модуля QTk. Этого будет достаточно для постройки этих интерфейсов пользователя. Позже мы построим более усложнённые графические интерфейсы пользователя. В Главе 10 содержится более полное обсуждение программирования декларативного интерфейса пользователя в целом и его реализация в QTk.

Декларативные спецификации виджетов

Окно на экране состоит из набора виджетов. Виджет - это прямоугольная область окна, которая имеет частичное интерактивное поведение. Например, некоторые виджеты могут отображать текстовую или графическую информацию, и другие виджеты могут принимать действия от пользователя, такие как клавиатурный ввод или щелчки по мыши. Мы определяем каждый виджет декларативно с записью, заголовок и свойства которого описывают тип виджета и начальное состояние. Мы описываем окно декларативно как вложенную запись (то есть, дерево), определяющую логическую структуру виджетов окна. На данный момент мы будем использовать пять виджетов:

* Виджет label может отображать текст. Виджет указывается записью:

где VS - это виртуальная строка.

* Виджет text используется для отображения и ввода большого количества текста. Он может использовать полосы прокрутки для отображения текста не помещающегося на экран. С вертикальной (то есть, вверх-вниз) полосой прокрутки виджет указывается записью:

Когда окно создано, переменная H будет привязана к объекту, использованному для контроля виджета. Мы называем такие объекты обработчиками. В можете рассматривать объект как одно-аргументную процедуру: {H set(VS)} отобразит текст и {H get(VS)} прочитает текст.

* Виджет button указывает кнопку и исполняемое действие при нажатии кнопки. Виджет указывается записью:

где VS - это виртуальная строка и P - это процедура с нулевым количеством аргументов. {P} вызывается всякий раз, когда нажимается кнопка.19 Для каждого окна все действия выполняются последовательно.

19 Если быть точным, каждый раз, после нажатия и отпускания левой кнопки мыши, в то время, когда мышь находится над кнопкой. Это позволяет пользователю исправлять все ошибочные нажатия кнопки мышью.

* Виджеты td (top-down - верх-вниз) и lr (left-right - лево-право) определяют расположение других виджетов в порядке верх-вниз или лево-право:

где W1, W2, ..., Wn - другие описания виджетов.

Декларативное описание поведения изменения размера

При изменении размеров окна внутренние виджеты должны реагировать соответствующе, то есть, либо изменять размер, либо сохранять прежний размер в зависимости от того, что должен выполнять интерфейс. Мы декларативно определяем поведение каждого виджета используя необязательное свойство glue в записи виджета. Свойство glue определяет должны ли быть "приклеенными" границы виджета к окружающему виджету. Аргументы свойства glue - это атомы, состоящие из любых комбинаций четырёх символов n (north - север), s (south - юг), w (west - запад), e (east - восток), обозначающие каждое направление, где нужно или не нужно приклеить границу. Вот некоторые примеры:

* Нет клея. Виджет сохраняет его исходный размер и центрируется в данном ему пространстве по-вертикали и по-горизонтали.

* glue:nswe приклеивает все четыре границы, размещаясь и по-горизонтали и по-вертикали.

* glue:we приклеивает по-горизонтали слева и справа и размещает виджет. Вертикально виджет не размещается, но центрируется в выделенном ему пространстве.

* glue:w приклеивается к левому краю и не растягивается.

* glue:wns приклеивается по вертикали сверху и снизу, растягивается с заполнением по вертикали, и приклеивается к левому краю, не растягивается по горизонтали.

Загрузка модуля QTk

Первый шаг - это загрузка QTk модуля в систему. Поскольку QTk является частью Стандартной Библиотеки Mozart, то достаточно дать правильное имя пути:

Теперь, когда QTk загружена, мы можем использовать её для постройки интерфейса в соответствии со спецификациями из предыдущего раздела.

Постройка интерфейса

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

Запись D всегда начинается с td или tr даже если окно имеет только один виджет. QTk.build возвращает объект W представляющий окно. В начале окно бывает скрытым. Оно может быть отображено или скрыто снова через вызов {W show} или {W hide}. Вот пример побольше, он реализует завершённый интерфейс текстового Ввода/Вывода:

На первый взгляд может показаться сложным, но взгляните снова: есть шесть виджетов (два label, два text, два button) упорядоченных виджетами td и lr. Функция QTk.build получает описание D. Она создаёт окно как на Рисунке 3.32 и создаёт объекты обработки In и Out. Сравните запись D с Рисунком 3.32 для того чтобы посмотреть как они соотносятся.

Есть две процедуры действия A1 и A2 по одной на каждую кнопку. Действие A1 прикреплено к кнопке "Do It". Нажатие кнопки вызывает A1, что трансформирует текст с первого текстового виджета во второй текстовый виджет. Это работает следующим образом. Вызов {In get(X)} получает текст с первого текстового виджета и привязывает его к X. Затем {Out set(X)} устанавливает текст второго текстового виджета в X. Действие A2 прикреплено к кнопке "Quit". Оно вызывает {W close}, которая незамедлительно закрывает окно.

Почти повсеместная вставка клея nswe позволяет реализовать корректное реагирование окна на изменение размера. Виджет lr с двумя кнопками обладает только клеем we, поэтому кнопки не расширяются по вертикали. Виджеты label не имеют клея, поэтому они имеют фиксированные размеры. Виджет td расположенный на высоком уровне не нуждается в клее поскольку мы подразумеваем что он всегда приклеен к его окну.

3.8.3 Файловый ввод/вывод данных без состояния

Ввод/вывод строки выполняется просто поскольку строка состоит из символов, которые можно непосредственно сохранить в файл. Как насчёт других значений? Возможность сохранить любое значение в файл и позже загрузить его из файла была бы большим подспорьем для программиста. Модуль Pickle системы предоставляет именно такую возможность. Он может записать и загрузить любое завершённое значение:

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

F100 - это (скорее большое) целое число; четыре других объекта - функции. Следующая операция сохраняет четыре функции в файл.

Если быть точным, то здесь в файл factfile сохраняется значение списка состоящего из четырёх элементов. В этом примере все элементы являются функциями. Функции были выбраны для того, чтобы показать различные уровни отложенных вычислений. Первые два возвращают результат вычисления 100!. Первая функция, F100Gen1, знает целое число и непосредственно возвращает его, и вторая, F100Gen2, вычисляет значение при каждом вызове. Третья и четвёртая, при вызове с целочисленным аргументом n, возвращает функцию, которая будучи вызванной возвращает n!. Третья, FNGen1, вычисляет n! при вызове, поэтому возвращённая функция только возвращает известное целое число. Четвёртая, FNGen2, не выполняет вычисления но, позволяет возвращённой функции вычислять n! при вызове.

Для того, чтобы использовать содержимое factfile, его вначале нужно загрузить:

Четыре раза будет отображено 100!. Конечно, возможно следующее:

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

Мы подчёркиваем что загруженные значения в точности те же самые, что и сохранённые. Нет никакой разницы между ними всеми. Это истинно для всех возможных значений: чисел, записей, процедур, имён, атомов, списков и так далее включая другие значения, которые мы увидим позже в этой книге. Выполнение это в первом процессе:

... % Первый оператор (определяет X)
{Pickle.save X ´myfile´}

и это во втором процессе:

X={Pickle.load ´myfile´}
... % Второй оператор (использует X)

строго идентично исполнению следующих операций в третьем процессе:

... % Первый оператор (определяет X)
{Pickle.save X ´myfile´}
_={Pickle.load ´myfile´}
... % Второй оператор (использует X)

Если убрать вызовы Pickle, то получаем это:

... % Первый оператор (определяет X)
... % Второй оператор (использует X)

но есть два небольших отличия:

* Первый вариант создаёт и читает файл 'myfile'. Второй вариант не делает этого.

* Первый вариант вызывает исключение если возникла проблема при создании или чтении файла.

3.9 Проектирование малых программ

Теперь, когда мы увидели много программных техник, следующим логическим шагом будет их использование для решения задач. Этот шаг называется проектированием программы. Он начинается с задачи, которую мы хотим решить (обычно описываемую в словах, иногда не очень точно) дающую высокоуровневую структуру программы, то есть, какие программистские техники нам нужно использовать, как они вместе связываются и дают в результате завершённую программу, решающую задачу.

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

3.9.1 Методология проектирования

Допустим у нас есть задача, которую можно решить написав малую программу. Рассмотрим как спроектировать программу. Мы предлагаем следующую методологию проектирования, которая представляет смесь из творчества и строгого мышления:

* Неформальная спецификация. Мы начинаем описывать то, что должна делать программа настолько точно насколько это возможно: что является её входными данными, что является выходными данными и как выходные данные связаны с входными данными. Это описание называется неформальной спецификацией. Даже если она точна, мы называем её "неформальной" поскольку она написана на Английском. "Формальная" спецификация записывается в математической нотации.

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

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

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

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

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

3.9.2 Пример проектирования программы

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

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

Эта спецификация достаточно точна? Как насчёт файла содержащего не корректное английское слово или файла содержащего не-Ascii символы? Наша спецификация недостаточно точна: она не определяет что значит "слово". Для того, чтобы сделать его более точным нам нужно знать назначение программы. Скажем, что нам нужна общая идея частоты слов, не зависящих от любого отдельно взятого языка. Тогда определение слова будет простым:

"Слово" - это максимальная последовательность букв и цифр.

Это означает, что слова разделяются по крайней мере одним символом, не являющимся буквой или цифрой. Сюда подходят слова некорректные в английском языке, но не подходят слова, содержащие не-Ascii символы. Это достаточно хорошо? А как насчёт слов с тире (таких как "true-blue") или идиоматических выражений выступающих как одно целое (таких как "trial and error")? В интересах простоты, на данный момент отбросим их. Но позже мы можем изменить спецификацию для того, чтобы принять их в зависимости от того, как мы будем использовать приложение частоты слов.

Теперь мы составили нашу спецификацию. Заметьте, что ключевая роль была сыграна примерами. Они важные указательные столбы на пути к точной спецификации. Примеры были специально спроектированы для того, чтобы протестировать ограничения спецификации.

Следующий шаг - разработать структуру программы. Подходящая структура, судя по всему, должна иметь вид конвеера: сначала считать файл в список символов, а затем преобразовать список символов в список слов, где каждое слово представлено символьной строкой. Чтобы подсчитать количество слов, нам необходима структура данных, индексируемая словами. Декларативный словарь из Раздела 3.7.2 был бы идеальным выбором, но он индексируется атомами. К счастью, существует операция преобразования символьных строк в атомы: StringToAtom (смотрите Дополнение B). Теперь мы можем писать нашу программу. Рисунок 3.29 ободряет: функция WordFreq, принимающая список символов и возвращающая словарь. Мы можем протестировать этот код на различных примерах, а особенно - на примерах, которые мы использовали, чтобы составить спецификацию. С этой целью, мы добавим код для считывания файла и отображения вывода в окно; для этого мы применим операции для работы с файлами и графическим пользовательским интерфейсом из Раздела 3.8. Важно качественно оформить приложение в виде программного компонента. Как именно это сделать, объясняется в следующих двух разделах.

3.9.3 Программные компоненты

Что такое хороший способ организации программ? Можно было бы писать программу как одно монолитное целое, но это может смущать. Более лучший способ - это разделить программу на логические единицы, каждая из которых реализует набор операций, взаимосвязанных некоторым способом. Каждая логическая единица имеет две части, интерфейс и реализацию. За пределами логической единицы видим только интерфейс. Логическая единица может использовать другие единицы в качестве его реализации.

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

Модули и функторы

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

* Интерфейс модуля - это запись группирующая воедино связанные элементы языка (обычно процедуры, но допустимы и другие части включая классы, объекты и т.д.).

* Реализация модуля - это набор элементов языка доступных для операций интерфейса, но сокрытых снаружи. Такая реализация скрывается через использование лексической области видимости.

Таблица 3.7: Синтаксис функтора

Мы будем рассматривать спецификации модулей как нечто отделённое от модулей. Спецификация модуля - это разновидность шаблона создающего модуль при каждом порождении экземпляра от спецификации модуля. Спецификация модуля иногда называется программным компонентом. К несчастью у выражения "программный компонент" большое количество различных значений [187]. Для того, чтобы избежать неясностей в этой книге мы будем называть спецификации модулей функторами. Функтор - это функция, аргументами которой являются модули, а результатом работы является новый модуль. (Если быть точным, функтор получает в качестве аргументов интерфейсы модулей, создаёт новый модуль и возвращает интерфейс получившегося модуля!) Мы будем предоставлять функтор как лингвистическую абстракцию из-за его роли в структурировании программ. Функтор имеет три части: часть import, которая описывает другие необходимые модули, часть export, которая описывает интерфейс модуля и часть define, которая даёт реализацию модуля включая его инициализирующий код. Синтаксис определения функтора, подобно синтаксису для процедур, позволяет использовать его либо как операторы, либо как выражения. Таблица 3.7 даёт синтаксис определений функтора как операторов.

В терминологии программной инженерии программный компонент - это единица независимой разработки, единица, разработанная третьей стороной, и не имеющая постоянного состояния (следуя определению данному в [187]). Функторы удовлетворяют этому определению и поэтому являются разновидностью программного компонента. По этой терминологии, модуль - это экземпляр компонента; это результат размещения функтора в отдельно взятой среде модуля. Среда модуля состоит из набора модулей, каждый из которых может иметь состояние исполнения.

Функторы в системе Mozart являются единицами компиляции. Это значит что система обладает поддержкой обработки функторов как в виде исходного кода (например, текст доступный для чтения человеком), так и в виде объектного кода (например, скомпилированной формы). Исходный код может быть скомпилирован, или транслирован, в объектный код. Такой подход упрощает применение функторов для обмена программным обеспечением между разработчиками. Например, система Mozart содержит библиотеку, названную MOGUL (от Mozart Global User Library - Глобальная Пользовательская Библиотека Mozart), в которую третьесторонние разработчики могут помещать информацию любого рода.

Приложение является автономным, если его можно запустить без интерактивного интерфейса. Оно состоит из главного функтора, которое вычисляется при запуске программы. Он импортирует модули, необходимые для приложения, что в свою очередь является причиной по которой будут вычислены другие функторы. Главный функтор используется из-за его эффекта запуска приложения, а не из-за его результирующего модуля, которое будет полностью проигнорировано. Вычисление, или "размещение", функтора создаёт новый модуль в три шага. Первое, модули нужно идентифицировать. Второе, запускается код инициализации. Третье, модуль загруженный в начале нужен в течение исполнения. Эта техника называется динамической линковкой, в противоположность статической линковке, в которой модули загружаются при запуске исполнения. В любой момент времени, набор уже размещённых модулей называется модульной средой.

Реализация модулей и функторов

Пошагово рассмотрим как конструировать программные компоненты. Вначале мы дадим демонстрационный модуль. После мы покажем как конвертировать этот модуль в программный компонент. И наконец мы включим его в лингвистическую абстракцию.

Демонстрационный модуль
В целом модуль представляет запись, а доступ к его интерфейсу осуществляется через поля записей. Мы конструируем модуль под названием MyList, реализующий интерфейс для процедур добавления, сортировки и проверки членства списков. Его можно написать так:

Процедура MergeSort недоступна извне оператора local. К другим процедурам нельзя получить доступ напрямую, а только через поля модуля MyList, представляющего запись. Например, Append доступен как MyList.append. Большинство библиотечных модулей Mozart, например, модули Base и System следуют этой структуре.

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

Каждый раз при вызове MyListFunctor создаётся и возвращается другой модуль MyList. Вообще MyListFunctor может иметь аргументы, которые являются другими модулями, необходимыми для MyList.

Из этого определения становится ясным что функторы - это всего лишь значения в языке. Они разделяют следующие свойства с процедурными значениями:

* Определение функтора может быть вычислено во время работы, результатом будет функтор.

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

* Функтор может быть сохранён в файле с помощью модуля Pickle. Этот файл может быть прочитан любым процессом Mozart-а. Это упрощает создание таких библиотек из третьесторонних функторов, как MOGUL.

* Функтор легковесен; он может быть использован для инкапсуляции таких единственных сущностей как объект или класс для явного обозначения модулей требуемых этой сущностью.

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

Лингвистическая поддержка Для организации больших программ разумно использовать такую абстракцию программных компонентов. Для упрощения использования, для того, чтобы быть уверенным в том, что её не применят неверно и с целью прояснения замысла программиста (избежать путаницы с другими высокоуровневыми техниками), мы поместили её в лингвистическую абстракцию. Функция MyListFunctor соответствует следующему синтаксису функтора:

Заметьте, что выражение между define и end выполняет неявное определение переменной также, как и выражение между local и in.

Допустим, что этот функтор был скомпилирован и сохранён в файл MyList.ozf (мы позже увидим как компилировать функтор). Тогда в интерактивном интерфейсе модуль может быть создан следующим образом:

Функция Module.link определена в Системном модуле Module. Она получает список модулей, загружает их из файловой системы, связывает их вместе (то есть, вычисляет их вместе, так каждый модуль видит его импортированные модули), и возвращает соответствующий список модулей. Модуль Module позволяет выполнять множество других операций над функторами и модулями.

Импорт модулей Программные компоненты могут зависеть от других программных компонентов. Если быть точным, то результатом обособления компонента программы является создание модуля. Обособлению могут быть нужны другие модули. В новом синтаксисе мы определяем это с помощью import - импорта определений. Для импорта библиотечного модуля достаточно указать имя его функтора. С другой стороны импорт модуля определённого пользователем требует указания имени файла или URL файла где сохранён функтор. 20 Это разумно, поскольку система знает где хранятся библиотеки модулей, но не знает где вы храните ваши собственные функторы. Рассмотрим следующий функтор:

20 Возможны другие схемы именований в которых функторы имеют некоторые логические имена в системе управления компонентами.

Указание import служит для импортирования Системного модуля Browser и определённого пользователем модуля FO описываемого функтором сохранённым в файле /home/mydir/FileOps.ozf. При связывании функтора выполняется определение между define ... end. Здесь осуществляется вызов функции FO.countLines, которая подсчитывает число строк в указанном файле, после чего вызывается процедура Browser.browse для отображения результата. Этот конкретный функтор определён из-за его эффектов, а не модуля, создаваемого им. Поэтому он не экспортирует никакой интерфейс.

3.9.4 Пример обособленной программы

А теперь упакуем приложение подсчёта частоты слов использующее компоненты и сделаем из него обособленную программу. На Рисунке 3.33 дан скриншот сделанный во время работы программы. Программа состоит из двух компонентов, Dict и WordApp, которые являются функторами, исходный код которых находится в файлах Dict.oz и WordApp.oz. Компоненты реализуют программы декларативного словаря и подсчёт частоты слов. В дополнение к импорту Dict, компонент WordApp также импортирует модули File и QTk. Эти модули используются для чтения из файла и создания окна вывода.

Рисунок 3.33: Скриншот приложения подсчёта частоты слов

Полный исходный код компонент Dict и WordApp дан в Рисунках 3.34 и 3.35. Принципиальное различие между этими компонентами и кодом из Разделов 3.7.3 и 3.7.2 в том, что компоненты заключены в functor ... end с правильными пунктами import и export. Рисунок 3.36 показывает зависимости. Модули Open и Finalize - это модули Системы Mozart. Компонент File может быть найден на Web сайте книги. Компонент QTk входит в стандартную библиотеку системы Mozart. Компонент Dict слегка отличается от декларативного словаря Раздела 3.7.3: он замещает Domain с помощью Entries, которые вместо простого списка ключей дают список пар Key#Value.

Рисунок 3.34: Обособленная библиотека словаря (файл Dict.oz)

Рисунок 3.35: Обособленное приложение подсчёта частоты слов (файл WordApp.oz)

Рисунок 3.36: Зависимости компонентов в приложении подсчёта частоты слов

Это приложение может быть легко расширено многими путями. Например, окно отображения кода в WordApp.oz может быть замещено следующим образом:

Здесь отображаются два фрейма, один в алфавитном порядке, а другой в порядке убывания частоты слов.

Компиляция и исполнение обособленной программы

Рассмотрим компиляцию приложения подсчёта частоты слов как обособленной программы. Функтор может использоваться двумя способами: как скомпилированный функтор (который импортируется другими функторами) или обособленная программа (которая может непосредственно исполняться из командной строки). Любой функтор можно скомпилировать для получения обособленной программы. В этом случае не требуется никаких экспортных частей и инициализационная часть определяет эффект программы. Заданный файл Dict.oz определяет функтор, скомпилированный функтор Dict.ozf создан с помощью команды ozc из интерфейса оболочки:

Файл WordApp.oz определяет функтор, который будет использоваться как обособленная программа, обособленный исполняемый WordApp создаётся с помощью следующей команды:

Возможен следующий запуск:

где book.raw - это файл, содержащий текст. Текст передаётся в стандартный ввод программы, где изнутри программы стандартный ввод виден как файл с именем stdin. Так выполнится динамическая линковка Dict.ozf при первом доступе к словарям. Также возможна статическая линковка Dict.ozf в скомпилированном коде приложения WordApp, так мы обойдёмся без динамической линковки. Эти возможности задокументированы в системе Mozart.

Библиотечные модули

Приложение определения частоты слов использует модуль QTk, являющийся частью системы Mozart. Любой язык программирования, для того, чтобы быть полезным на практике, должен сопровождаться большим набором полезных абстракций. Они организованы в библиотеки. Библиотека - это связная коллекция одной или более связанных абстракций, полезных в некоторой предметной области. В зависимости от языка или библиотеки, библиотека может рассматриваться как часть языка или быть снаружи языка. Разделительная черта может быть весьма нечёткой: почти во всех случаях многие базовые языковые операции на деле оказываются реализованными в библиотеках. Например, более высокие высокие функции над вещественными числами (синус, косинус, логарифм и другие) обычно реализованы в библиотеках. Поскольку число библиотек может быть очень большим, то организация библиотек в модули является хорошей идеей.

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

Библиотечные модули в Mozart Библиотечные модули, доступные в системе Mozart, состоят из Базовых модулей и Системных модулей. Базовые модули доступны сразу при старте. Они часть определения языка, предоставляют базовые операции над типами языковых данных. Продемонстрированные в этом разделе операции над номерами, списком и записями находятся в Базовых модулях. Системные модули недоступны сразу после старта, но могут быть импортированы в функторах. Они обеспечивают такую дополнительную функциональность, как файловый Ввод/Вывод, графический интерфейс пользователя, распределённое программирование, логическое программирование и программирование в ограничениях, доступ к операционной системе и так далее.

Интерактивный интерфейс Mozart может дать полный список библиотечных модулей в Mozart. В интерактивном меню Oz откройте Compiler Panel и нажмите вкладку Environment. В ней будут показаны все определённые переменные в глобальной среде включая модули.

3.10 Упражнения

1. Абсолютное значение вещественного числа. Мы хотим определить функцию Abs которая вычисляет абсолютное значение вещественного числа. Следующее определение не работает:

Почему? Как вы исправите это? Подсказка: проблема тривиальна.

2. Кубические корни. Эта глава использовала метод Ньютона для вычисления квадратных корней. Метод может быть расширен для вычисления корней любых степеней. Например, следующий метод вычисляет кубические корни. Задан предполагаемый корень g для кубического корня x, улучшенное предположение задаётся через (x/g^2 + 2g)/3. Напишите декларативную программу для вычисления кубических корней с помощью метода Ньютона.

3. Метод половинного интервала. Метод половинного интервала - это простая, но мощная техника для нахождения корней уравнений f(x) = 0, где f - непрерывная вещественная функция. Идея заключается в следующем: если нам заданы точки a и b такие, что f(a)<0<f(b), то f должна обладать хотя бы одним корнем между a и b. Для определения корня положим x = (a + b)/2 и вычислим f(x). Если f(x)>0 то f должна обладать корнем между a и x. Если f(x)<0 то f должна обладать корнем между x и b. Повторение этого процесса будет определять всё меньшие и меньшие интервалы сходящиеся к корню. Напишите декларативную программу для решения этой проблемы используя техники итеративного вычисления.

21 Этот пример взят из Абельсона и Сассмана [1].

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

5. Итеративный SumList. Перепишите функцию SumList из Раздела 3.4.2 в итеративном способе используя техники разработанные для Length.

6. Инварианты состояния. Распишите инвариант состояния для функции IterReverse.

7. Проверка чего-либо на списочность. В Разделе 3.4.3 определена функция LengthL вычисляющая число элементов во вложенном списке. Для того, чтобы увидеть является ли X списком или нет, LengthL использует функцию Leaf определённую таким способом:

Что произойдёт если мы заменим это выражение таким определением:

Что пойдёт не так если мы используем эту версию Leaf?

8. Другая функция добавления. В Разделе 3.4.2 определяется функция Append через рекурсию его первого аргумента. Что произойдёт если мы попытаемся выполнить рекурсию его второго аргумента? Вот возможное решение:

Корректна ли эта программа? Завершится ли она? Почему да или почему нет?

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

Мы можем обнаружить это взглянув на расширение:

Здесь возможно выполнение оптимизации последнего вызова поскольку несвязанная переменная Zr может быть вставлена в список Zs и связана позже. Теперь давайте сделаем вычислительную модель строже для того чтобы вычисления выполнялись только со значениями. Как мы можем написать итеративное добавление? Один подход - это определение двух функций: (1) реверс итеративного списка и (2) итеративная функция добавления реверса одного списка к другому. Напишите итеративное добавление с помощью этого подхода.

10. Итеративные вычисления и переменные потока данных. Предыдущий пример показал, что использование переменных потока данных иногда упрощает написание итеративных списковых операций. Возникает следующий вопрос. Возможно ли задать другое итеративное определение той же операции не использующей переменные потока данных для любой итеративной операции определённой с переменными потока данных?

11. Ограничения списков разницы. Что пойдёт не так если попытаться добавить один и тот же список разницы более чем единожды?

12. Сложность уплощения списка. Подсчитайте число операций требуемых для двух версий функции Flatten данной в Разделе 3.4.4. Какой будет наихудшая сложность для каждой версии с n элементами и максимальной глубиной вложения k?

13. Матричные операции. Допустим что мы представили матрицу как список списков целочисленных значений где каждый внутренний список даёт строку матрицы. Определите функции для выполнения таких стандартных матричных операций как матричное транспонирование и матричное перемножение.

14. FIFO (Первый Пришёл - Первый Вышел) очереди. Рассмотрим FIFO очередь определённую в Разделе 3.4.4. Ответьте на следующие два вопроса:

(a) Что произойдёт если вы удалите элемент из пустой очереди?

(b) Почему следующее определение IsEmpty будет неправильным?

15. Быстрая сортировка. Ниже приведён возможный алгоритм сортировки списков. Его изобретатель, Чарльз Энтони Ричард Хоар, назвал его быстрой сортировкой, поскольку это был быстрейший известный сортирующий алгоритм общего назначения на момент изобретения. Он использует стратегию разделяй и властвуй для того, чтобы дать среднюю временную сложность O(n log n).

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

(a) В качестве точки отсчёта выбирается первый элемент X из L.

(b) L разделяется на два списка L1 и L2 так, что все элементы в L1 меньше чем X и все элементы в L2 больше или равны X.

(c) Использование быстрой сортировки на L1 даст S1, а сортировка L2 даст S2.

(d) Сложение списков S1 и S2 даст ответ.

Напишите эту программу со списками различий для того, чтобы избежать линейной сложности сложения.

16. (сложное задание) Свёртка хвостовой рекурсии.22 Для этого упражнения напишите функцию, которая получает два списка [x1 x2 ... xn] и [y1 y2 ... yn] и возвращает их символическую свёртку [x1#yn x2#yn-1 ... xn#y1]. Функция должна быть выражена через хвостовую рекурсию и выполнять не более n рекурсивных вызовов. Подсказка: функция может вычислять реверс второго списка и передавать его как аргумент самой себе. Поскольку унификация не зависит от порядка то этот приём работает отлично.

22 Это упражнение от Оливьера Данви.

17. (сложное упражнение) Каррирование. Цель этого упражнения в определении лингвистической абстракции для добавления каррирования в Oz. Вначале определите схему трансляции определений функций и вызовов. Затем используйте утилиту gump - парсер-генератор для добавления лингвистических абстракций в Mozart.

Переведено на Нотабеноиде
http://notabenoid.org/book/49638/272750

Переводчики: Charlz_Klug, Atronax