Языки функционального и императивного программирования различаются контролем выполнения программы и управлением памятью.
Императивные языки предоставляют больший контроль над выполнением программы и памятью. Находясь ближе к реальной машине, такой код может быть эффективнее, но при этом код теряет в устойчивости выполнения. Функциональное программирование предоставляет более высокий уровень абстракции и таким образом лучший уровень устойчивости выполнения: типизация (динамическая или статическая) помогает избежать некорректных значений, автоматическая сборка мусора, хотя и замедляет скорость выполнения, обеспечивает правильное манипулирование областями памяти.
Исторически обе эти парадигмы программирования существовали в разных сферах: символьные программы для первого случая и числовые для второго. Однако, с тех времен кое–что изменилось, в частности появилась техника компиляции функциональных языков и выросла эффективность GC. С другой стороны, устойчивость выполнения стала важным критерием, иногда даже важнейшим критерием качества программного обеспечения. В подтверждение этому “коммерческий аргумент” языка Java: эффективность не должна преобладать над правильностью, оставаясь при этом благоразумно хорошей. Эта идея приобретает с каждым днем новых сторонников в мире производителей программного обеспечения.
Objective CAML придерживается этой позиции: он объединяет обе парадигмы, расширяя таким образом область своего применения и облегчая написание алгоритмов в том или ином стиле. Он сохраняет, однако, хорошие свойства правильности выполнения благодаря статической типизации, GC и механизму исключений. Исключения — это первая структура контроля выполнения позволяющая приостановить/продолжить расчет при возникновении определенных условий. Эта особенность находится на границе двух стилей программирования, хоть она и не изменяет результат, но может изменить порядок вычислений. Введение физически изменяемых значений может повлиять на чисто функциональную часть языка. Порядок вычисления аргументов функции становится определимым если это вычисление производит побочный эффект. По этим причинам подобные языки называются “не чистые функциональные языки”. Мы теряем часть абстракции, так как программист должен учитывать модель памяти и выполнение программы. Это не всегда плохо, в частности для читаемости кода. Однако, императивные особенности изменяют систему типов языка: некоторые функциональные программы, с теоретически правильными типами, не являются правильными на практике из-за введения ссылок (reference). Хотя такие программы могут быть легко переписаны.
В этой главе мы сравним функциональную и императивную модель Objective CAML по критерию контроля выполнения программы и представления значений в памяти. Смесь обоих стилей позволяет конструировать новые структуры данных. Это будет рассмотрено в первом разделе. Во втором разделе мы обсудим выбор между композицией функций (composition of functions) или последовательности (sequencing) с одной стороны и разделение (sharing) или копирование значений с другой. Третий раздел выявляет интерес к смешиванию двух стилей для создания функциональных изменяемых данных (mutable functional data), что позволит создавать не полностью вычисленные (evaluated) данные. В четвертом разделе рассмотрены streams, потенциально бесконечные потоки данных и их интеграция, посредством сопоставления с образцом.
Воспользуемся строками (string) и списками ('a list) для иллюстрации разницы между двумя стилями.
map это одна из классических функций в среде функциональных языков. В чистом функциональном стиле она пишется так:
Конечный список состоит из результатов применения функции f к элементам списка переданного в аргументе. Он рекурсивно создается указывая начальный элемент (заголовок) (f t) и последующую часть (хвост) (map f q). В частности, программа не указывает какой из них будет вычислен первым.
При этом, для написания такой функции программисту не нужно знать физическое представление данных. Проблемы выделения памяти и разделения данных решаются Objective CAML без внешнего вмешательства программиста. Следующий пример иллюстрирует это:
Оба списка example и result содержат одинаковые значения:
Оба значения имеют одинаковую структуру, хоть они и представлены в памяти по разному. Убедимся в этом при помощи проверки на физическое равенство:
Вернемся к предыдущему примеру и изменим строку списка result.
Определено, изменив список result, мы изменили список example. То есть знание физической структуры необходимо как только мы пользуемся императивными особенностями.
Рассмотрим теперь как порядок вычисления аргументов функции может стать ловушкой в императивном программировании. Определим структуру изменяемого списка, а так же функции создания, добавления и доступа:
Несмотря на то что мы переняли общую структуру функции map предыдущего параграфа, с imap мы получим другой результат:
В чем тут дело? Вычисление (itl l) произошло раньше чем (ihd l) и в последней итерации imap, список l пустой в момент обращения к его заголовку. Список example теперь пуст, хоть мы и не получили никакого результата:
Проблема функции imap в недостаточном контроле смеси стилей программирования: мы предоставили системе выбор порядка вычисления. Переформулируем функцию imap явно указав порядок при помощи конструкции let .. in ..
Однако, начальный список опять утерян:
Использование оператора последовательности (sequencing operator) и цикла есть другой способ явного указания порядка.
Присутствие ignore — это факт того что нас интересует побочный эффект функций над ее аргументами, а не их (функций) результат. Так же было необходимо выстроить в правильном порядке элементы результата (функцией List.rev).
Часто ошибочно ассоциируют рекурсию с функциональным стилем и императивный с итерацией. Чисто функциональная программа не может быть итеративной, так как значение условия цикла не меняется никогда. Тогда как императивная программа может быть рекурсивной: функция imap тому пример.
Значения аргументов функции хранятся во время ее выполнения. Если она (функция) вызовет другую функцию, то эта последняя сохранит и свои аргументы. Эти значения хранятся в стеке выполнения. При возврате из функции эти значения извлечены из стека. Зная что пространство памяти ограничено, мы можем дойти до ее предела, используя функцию с очень большой глубиной рекурсии. В подобных случаях Objective CAML возбуждает исключение Stack_overflow.
В итеративной версии место занимаемое функцией succ_iter в стеке не зависит от величины аргумента.
У следующей версии функции a priori аналогичная глубина рекурсии, однако она успешно выполняется с тем же аргументом.
Данная функция имеет специальную форму рекурсивного вызова, так называемую хвостовую рекурсию при которой результат вызова функции будет результатом функции без дополнительных вычислений. Таким образом отпадает необходимость хранить аргументы функции во время вычисления рекурсивного вызова. Если Objective CAML распознал конечную рекурсивную функцию, то перед ее вызовом аргументы извлекаются из стека.
Распознание конечной рекурсии существует во многих языках, однако это свойство просто необходимо функциональным языкам, где она естественно много используется.
Естественно, речь не идет о “священных” либо эстетических для каждого понятиях, a priori не существует стиля красивее или лучше чем другой. Однако, в зависимости от решаемой проблемы, один стиль может быть более подходящим или более адаптированным чем другой.
Первое правило — простота. Желаемый алгоритм (будь то в книге или лишь в голове программиста) уже определен в каком-то стиле, вполне естественно его и использовать при реализации.
Второй критерий — эффективность программы. Можно сказать что императивная программа (хорошо написанная) более эффективна чем ее функциональный аналог, но в очень многих случаях разница между ними не достаточно существенна для оправдания сложности кода императивного стиля, там где функциональный был бы естественен. Функция map есть хороший пример натурально выраженной в функциональном стиле проблемы и мы ни в чем не выиграем написав ее в императивном стиле.
Мы уже видели, что как только в программе появляются побочные эффекты, необходимо явно указывать порядок выполнения элементов программы. Это может быть сделано двумя способами:
Давайте рассмотрим данную проблему выбора стиля на следующем примере. Рекурсивный алгоритм быстрой сортировки вектора описывается следующим образом:
Сортировка вектора — означает изменение его состояния, поэтому мы должны использовать императивный стиль, как минимум для манипуляции данными.
Начнем с определения функции переставляющей элементы вектора.
Выбор правильной точки опоры важен для эффективности алгоритма, но мы ограничимся самым простым способом: вернем индекс первого элемента вектора.
Напишем теперь желаемый алгоритм переставляющий элементы вектора вокруг выбранной точки.
При реализации алгоритма мы естественно воспользуемся императивными управляющими структурами.
Кроме эффекта над вектором, функция возвращает индекс опорной точки.
Нам остается лишь собрать воедино различные этапы и написать рекурсивный вызов для подвекторов.
Здесь мы воспользовались двумя стилями. Выбранная опорная точка служит аргументом при перестановке вокруг нее и ее порядок в векторе после этой процедуры служит аргументом рекурсивного вызова. Зато, полученный после перестановки вектор мы получаем в результате побочного эффекта, а не как возвращенное значение функции permute_pivot. Тогда как функция quick возвращает вектор и сортировка подвекторов реализуется композицией рекурсивных вызовов.
Теперь главная функция:
Это полиморфная функция, так как отношение порядка < полиморфное.
До тех пор пока наши данные не изменяемые, нет необходимости знать используются они совместно или нет.
Является ли b копией a или же это один и тот же список не имеет значения, так как по любому это “неосязаемые” значения. Однако, если на место целых чисел, мы поместим изменяемые значения, необходимо будет знать скажется ли изменение одного значения на другое.
Реализация полиморфизма Objective CAML вызывает (causes) копирование непосредственных значений (immediate values) и разделение (sharing) структурных значений. Хоть передача аргументов осуществляется копированием, в случае структурных значений передается лишь указатель. Как в случае с функцией id.
Здесь мы действительно имеем случай выбора стиля программирования, от которого зависит эффективность представления данных. С одной стороны, использование изменяемых значений позволяет немедленное манипулирование данными (без дополнительного выделения памяти). Однако это вынуждает, в некоторых случаях, делать копии там, где использование неизменяемого значения позволило бы разделение. Проиллюстрируем это двумя способами реализации списков.
Фиксированные списки строго эквивалентны спискам Objective CAML, тогда как изменяемые больше в стиле C, где ячейка состоит из значения и ссылки на следующую ячейку.
С фиксированными списками существует единственный способ реализовать конкатенацию и он вынуждает копирование структуры первого списка, тогда как второй список может быть разделен с конечным списком.
В этом примере мы видим что первые ячейки li1 и li3 различны, тогда как вторая часть li3 есть именно li2.
С изменяемыми списками можно изменить аргументы (функция concat_share) или создать новое значение (функция concat_copy)
Это решение, concat_copy, аналогично предыдущей функции concat. Вот второе вариант, с общим использованием.
Конкатенация с общим использованием не нуждается в выделении памяти (мы не используем конструктор LMcons), мы лишь ограничиваемся тем что последняя ячейка первого списка теперь указывает на второй список. При этом, конкатенация способна изменить аргументы переданные функции.
Мы получили ожидаемый результат для lm3, однако значение lm1 изменено.
Таким образом это может повлиять на оставшуюся часть программы.
В чисто функциональной программе побочных эффектов не существует, это свойство лишает нас операций ввода/вывода, исключений и изменяемых структур данных. Наше определение функционального стиля является менее ограниченным, то есть функция не изменяющая свое глобальное окружение может быть использована в функциональном стиле. Подобная функция может иметь локальные изменяемые значения (и значит следовать императивному стилю), но не должна изменять ни глобальные переменные ни свои аргументы. С внешней стороны, такие функции можно рассматривать как “черный ящик”, чье поведение сравнимо с поведением функции в чисто функциональном стиле, с разницей что выполнение первой может быть приостановлен возбуждением исключения. В том же духе, изменяемое значение, которое больше не изменяется после инициализации, может быть использовано в функциональном стиле.
С другой стороны, программа написанная в императивном стиле, унаследует следующие достоинства Objective CAML: правильность статической типизации, автоматическое управление памятью, механизм исключений, параметризованный полиморфизм и вывод типов.
Выбор между стилем функциональным и императивным зависит от программного обеспечения которое вы хотите реализовать. Выбор может быть сделан в соответствии со следующими характеристиками:
Эти несколько замечаний подтверждают тот факт, что часто смешанное использование обоих стилей является рациональным выбором. Функциональный стиль быстрее в разработке и обеспечивает более простую организацию программы, однако части кода где необходимо повысить скорость выполнения лучше написать в императивном стиле.
Как мы уже заметили, язык программирования имеющий функциональные и императивные особенности дает свободу выбора наиболее подходящего стиля для реализации того или иного алгоритма. Конечно, мы можем использовать оба аспекта Objective CAML совместно в одной и той же функции. Именно этим мы сейчас и займемся.
Обычно функция с побочным эффектом рассматривается как процедура и она возвращает значение () типа unit. Однако, иногда бывает полезно произвести побочный эффект внутри функции и вернуть определенное значение. Мы уже использовали подобный коктейль стилей в функции permute_pivot в быстрой сортировке.
В следующем примере реализуем генератор символов, который создает новый символ при каждом вызове функции. Мы используем счетчик, значение которого увеличивается с каждым вызовом.
А теперь спрячем ссылку на c от всей программы следующим образом:
Таким образом мы объявили пару функций, разделяющие локальную (для декларации) переменную c. Использование обеих функций производит тот же результат что и раньше.
Этот пример иллюстрирует способ представления замыкания. Замыкание можно рассматривать как пару, состоящую из кода (то есть часть function) и локальное окружение, содержащее значения свободных переменных замыкания с другой стороны. На диаграмме 3.1 мы можем увидеть представление в памяти замыканий reset_s и new_s.
Оба эти замыкания разделяют одно и тоже окружение (значение c). Когда одно из них меняет ссылку c, то оно меняет содержимое памяти разделяемое с другим окружением.
Исключения позволяет отслеживать ситуацию, при которой дальнейшее продолжение программы невозможно. В подобном случае сборщик исключений позволит продолжить вычисление, зная что произошла ошибка. В момент возбуждения исключения может возникнуть проблема побочного эффекта с состоянием модифицируемых данных. Это состояние не может быть гарантированно если произошли физические изменения в ответвлении неудавшегося вычисления.
Определим функцию увеличения (++), с аналогичным результатом что и в C:
Следующий пример, иллюстрирует небольшой расчет в котором деление на ноль совпадает с побочным эффектом:
Переменная x не изменяется во время вычисления выражения (*1*), тогда как она изменяется во время (*2*). Если заранее не сохранить начальные значения, конструкция try .. with .. не должна (в части with ..) зависеть от изменяемых переменных, которые участвуют в вычислении возбудившем исключение.
В функциональном программирование программа, как функциональное выражение, является в то же время данными — чтобы уяснить этот момент напишем список ассоциированных значений в виде функционального выражения. Этот список ассоциаций ('a * 'b) list можно рассматривать как частичную функцию из 'a (множество ключей) в 'b (множество соответствующих значений). Другими словами, функция 'a -> 'b.
Пустой список это неопределенная функция, которую мы будем моделировать возбуждением исключения:
Теперь напишем функцию add_assoc добавляющую элемент в список или другими словами расширим функцию новыми значениями.
Перепишем функцию mem_assoc:
Однако, написание функции удаляющей элементы из списка, не совсем простое дело. У нас больше нет доступа к значениям входящим в замыкание. Для этого мы спрячем старое значение возбудив исключения Not_found.
Естественно, можно воспользоваться ссылками и побочным эффектом для использования таких значений, однако существует несколько предостережений.
Мы получили функцию l которая указывает сама на саму себя и значит будет зацикливаться. Этот досадный побочных эффект есть результат того что разыменование !l находится внутри замыкания function x ->. Значение !l вычислено при выполнении, а не компиляции. В этот момент, l указывает на значение измененное add_assoc. Необходимо исправить наше определение используя замыкание полученное определением add_assoc:
Смесь императивных особенностей с функциональным языком образует хорошие средства реализации языков программирования. В данном параграфе мы проиллюстрируем эту особенность в реализации структур данных с отсроченным вычислением. Такая структура данных не вычисляется полностью, вычисление продвигается в зависимости от использования структуры.
Отложенное вычисление, часто используемое в чистых функциональных языках, можно моделировать использованием функциональных значений (возможно, изменяемых). Выгода от использования данных с отложенным выполнением двойная; во первых вычисляется лишь то что необходимо для расчета, во вторых использование потенциально бесконечных данных.
Определим тип vm элементы которого либо уже вычисленное значение (конструктор Imm) либо значение которое будет вычислено (конструктор Deferred).
Откладывание вычислений может быть получено инкапсуляцией в замыкание. Функция вычисляющая такое значение должна или вернуть значение если оно уже вычислено или, в противном случае, вычислить и сохранить результат.
Операции задержки и активации вычисления также называют замораживанием и размораживанием значения.
Напишем условный контроль в виде функции:
А теперь воспользуемся этим в рекурсивной функции подсчета факториала.
Заметим, что классический if не может быть записан в виде функции. Действительно, определим функцию if_function следующим образом:
Дело в том что все три аргумента вычисляются, это приводит к зацикливанию, так как рекурсивный вызов fact(n-1) всегда вычисляется, даже в случае когда n=0.
Трудности во внедрении замороженных значений происходят от конструкции выражений с отложенным вычислением в контексте немедленного вычисления Objective CAML. Мы это увидели при попытке переопределить условное выражение. Нельзя написать функцию замораживающую значение при конструкции объекта типа vm.
Эта функция следует стратегии вычисления Objective CAML, то есть выражение e вычисляется перед тем как создать замыкание fun () ->e. Проиллюстрируем это в следующем примере:
По этой причине была введена следующая синтаксическая форма:
Синтаксис
Warning
Это особенность является расширением языка и может
измениться в следующих версиях.
Когда к выражению применяется ключевое слово lazy то создается значение особого типа, который определен в модуле Lazy:
Выражение (print_string “Hello”) не вычислено, так как не было никакого вывода на экран. При помощи функции Lazy.force мы можем вынудить вычисление выражения.
Тут мы замечаем, что значение x изменилось:
Теперь это значение замороженного выражения, в данном случае 12.
Новый вызов функции force просто возвращает вычисленное значение:
Строка “Hello” больше не выводится на экран.
Другой интерес использования отложенного вычисления состоит в возможности построения потенциально бесконечных структур данных, как на пример множество натуральных чисел. Вместо того чтобы конструировать каждое число, мы определим лишь первый элемент и способ получения следующего.
Определим настраиваемую (generic) структуру 'a enum с помощью которой мы будем определять элементы множества.
Для того, чтобы получить множество натуральных достаточно конкретизировать (instanciating) поля этой структуры.
Другой пример — ряд чисел Фибоначчи, который определен как:
| ⎧ ⎪ ⎨ ⎪ ⎩ |
|
Функция, вычисляющая текущее значение, должна использовать значения un−1 и un−2. Для этого воспользуемся состоянием c в следующем замыкании.
Потоки это потенциально бесконечная последовательность данных определенного рода. Вычисление части потока выполняется по необходимости для текущего вычисления — пассивные структуры данных.
stream абстрактный тип данных, реализация которого неизвестна. Мы манипулируем объектами этого типа при помощи функций конструкции и деструкции. Для удобства пользователя, Objective CAML предоставляет пользователю простые синтаксические конструкции для создания и доступа к элементам потока.
Warning
Это особенность является расширением языка и может
измениться в следующих версиях.
Упрощенный синтаксис конструкции потоков похож на синтаксис конструкции списков или векторов. Пустой поток создается следующим способом:
Другой способ конструкции потока состоит в перечислении элементов этого потока, где перед каждым из них ставится апостроф.
Выражения, перед которыми не стоит апостроф, рассматриваются как под–потоки.
Остальные функции сгруппированы в модуле Stream. На пример, функции of_channel и of_string возвращают поток состоящий из символов полученных из входного потока или строки символов.
Отложенное вычисление потоков позволяет использовать бесконечные структуры данных, как это было в случае с типом 'a enum на стр. ??. Определим поток натуральных чисел при помощи первого элемента и функции вычисляющей поток из следующих элементов.
Элементарная операция next одновременно вычисляет, возвращает и извлекает первый элемент потока.
Когда данные в потоке закончились возбуждается исключение.
Для использования потоков Objective CAML предоставляет специальное сопоставление для потоков — уничтожающее сопоставление (destructive matching). Сопоставляемое значение вычисляется и удаляется из потока. Понятие исчерпываемости сопоставления (exhaustive match) не существует для потоков, так как мы используем пассивные и потенциально бесконечные структуры данных. Синтаксис сопоставления следующий:
Синтаксис
Функция next может быть переписана в следующей форме:
Заметьте, что перечисление чисел началось с того места где мы остановились.
Существует другая форма синтаксиса для фильтрации функционального параметра типа Stream.t.
Синтаксис
Перепишем функцию next используя новый синтаксис.
Мы можем сопоставлять пустой поток, но необходимо помнить о следующем: образец потока [<>] сопоставляется с каким угодно потоком. То есть, поток s всегда равен потоку [< [<>]; s >]. Поэтому нужно поменять обычный порядок сопоставления.
Используя тот факт что сопоставление уничтожающее, перепишем предыдущую функцию.
Несмотря на то что потоки пассивные, они добровольно и с “восторгом” отдают свой первый элемент, который после этого будет утерян для потока. Эта особенность отображается на сопоставлении. Следующая функция есть попытка (обреченная на неудачу) вывода на экран двух чисел из потока, в конце потока может остаться один элемент.
Два первых элемента потока были выведены на экран без проблем, однако во время вычисления рекурсивного вызова (print_stream [< 3 >]) образец обнаружил x, который был “употреблен”, но для y в потоке ничего нет. Это и привело к ошибке. Дело в том что второй образец абсолютно бесполезный, если поток не пустой то первый образец всегда совпадет.
Для того, чтобы получить ожидаемый результат необходимо упорядочить сопоставление.
Если сопоставление не срабатывает на первом элементе образца, то фильтр работает как обычно.
Из–за своего свойства уничтожения сопоставление потоков отличается от сопоставления типов сумма. Давайте рассмотрим на сколько глубоко они отличаются.
Вот простейшая функция складывающая два элемента потока.
Однако, мы можем поглотить поток “изнутри” придав имя полученному результату.
В главе 10, посвященной лексическому и синтаксическому анализу, мы рассмотрим другие примеры использования потоков. В частности, мы увидим как “поглощение” потока изнутри можно с выгодой использовать.
В этой главе мы сравнили функциональный и императивный стили программирования. Основные различия состоят в контроле выполнения (неявный в функциональном и явный в императивном стиле) и представлении в памяти данных (явное разделение или копирования в императивном стиле, не имеющее такой важности в функциональном). Реализация алгоритмов в функциональном и императивном стилях подразумевает эти различия. Выбор между обоими стилями на самом деле приводит к их одновременному использованию. Это позволяет явно выразить представление замыкания, оптимизировать критические части программы и создать изменяемые функциональные данные. Физическое изменение значений в окружении замыкания помогает нам лучше понять что такое функциональное значение. Одновременное использование обоих стилей предоставляет мощные средства для реализации. Мы воспользовались этим при создании потенциально бесконечных данных.
