Содержание
-
Переводы, 23 января 2017 в 13:43
Если вы такой же разработчик, как и я, то наверняка сперва изучали парадигму ООП. Первым вашим яыком были Java или C++ — или, если вам повезло, Ruby, Python или C# — поэтому вы наверняка знаете, что такое классы, объекты, экземпляры и т.д. В чём вы точно не особо разбираетесь, так это в основах той странной парадигмы, называющейся функциональным программированием, которая существенно отличается не только от ООП, но и от процедурного, прототипно-ориентированного и других видов программирования.
Функциональное программирование становится популярным — и на то есть причины. Сама парадигма не нова: Haskell, пожалуй, является самым функциональным языком, а возник он в 90-ых. Такие языки, как Erlang, Scala, Clojure также попадают под определение функциональных. Одним из основных преимуществ функционального программирования является возможность написания программ, работающих конкурентно (если вы уже забыли, что это — освежите память прочтением статьи о конкурентности), причём без ошибок — то есть взаимные блокировки и потокобезопасность вас не побеспокоят.
У функционального программирования есть много преимуществ, но возможного максимального использования ресурсов процессора благодаря конкурентному поведению — это его главный плюс. Ниже мы рассмотрим основные принципы функционального программирования.
Вступление: Все эти принципы не обязательны (многие языки следуют им не полностью). Все они теоретические и нужны для наиболее точного определения функциональной парадигмы.
1. Все функции — чистые
Это правило безусловно является основным в функциональном программировании. Все функции являются чистыми, если они удовлетворяют двум условиям:
- Функция, вызываемая от одних и тех же аргументов, всегда возвращает одинаковое значение.
- Во время выполнения функции не возникают побочные эффекты.
Первое правило понятно — если я вызываю функцию sum(2, 3) , то ожидаю, что результат всегда будет равен 5. Как только вы вызываете функцию rand() , или обращаетесь к переменной, не определённой в функции, чистота функции нарушается, а это в функциональном программировании недопустимо.
Второе правило — никаких побочных эффектов — является более широким по своей природе. Побочный эффект — это изменение чего-то отличного от функции, которая исполняется в текущий момент. Изменение переменной вне функции, вывод в консоль, вызов исключения, чтение данных из файла — всё это примеры побочных эффектов, которые лишают функцию чистоты. Может показаться, что это серьёзное ограничение, но подумайте ещё раз. Если вы уверены, что вызов функции не изменит ничего “снаружи”, то вы можете использовать эту функцию в любом сценарии. Это открывает дорогу конкурентному программированию и многопоточным приложениям.
2. Все функции — первого класса и высшего порядка
Эта концепция — не особенность ФП (она используется в Javascript, PHP и других языках) — но его обязательное требование. На самом деле, на Википедии есть целая статья, посвящённая функциям первого класса. Для того, чтобы функция была первоклассной, у неё должна быть возможность быть объявленной в виде переменной. Это позволяет управлять функцией как обычным типом данных и в то же время исполнять её.
Функции высшего порядка же определяются как функции, принимающие другую функцию как аргумент или возвращающие функцию. Типичными примерами таких функций являются map и filter.
3. Переменные неизменяемы
Тут всё просто. В функциональном программировании вы не можете изменить переменную после её инициализации. Вы можете создавать новые, но не можете изменять существующие — и благодаря этому вы можете быть уверены, что никакая переменная не изменится.
4. Относительная прозрачность функций
Сложно дать корректное определение относительной прозрачности. Самым точным я считаю такое: если вы можете заменить вызов функции на возвращаемое значение, и состояние при этом не изменится, то функция относительно прозрачна. Это, быть может, очевидно, но я приведу пример.
В данном параграфе изучены вопросы, относящиеся к истории развития, идеологии, математическому обоснованию и обзору возможностей программных систем на основе функционального подхода к проектированию и реализации программного обеспечения. Рассмотрены важнейшие научные исследования, относящиеся к математическому обоснованию функционального подхода к программированию, а также исследовано своеобразие функционального подхода по сравнению с другими направлениями проектирования и реализации программного обеспечения, известными сегодня.
Представлен вариант классификации языков функционального программирования на основе реализованных в них теоретически важных свойств и практически полезных механизмов (в частности, полиморфизма и сопоставления с образцом). На основе классификации сделаны выводы о преимуществах и недостатках рассмотренных языков и подхода в целом для реализации тех или иных классов практических задач.
Существенное внимание уделено языку функционального программирования F#, который изучается на протяжении всей книги, его истории развития, особенностям, а также его практической реализации на технологической платформе .NET.
Сосредоточимся на функциональном подходе к программированию. Прежде всего, обратимся к истории фундаментальных математических исследований, которые привели к появлению функционального подхода к программированию.
Время появления теоретических работ, которые обосновывают функциональный подход, относится к 1920—1930-м гг. Как мы увидим впоследствии, теория часто значительно опережает практику программирования, и важнейшие работы, которые сформировали математическую основу подхода, были созданы задолго до появления компьютеров и языков программирования, которые потенциально могли бы реализовать эту теорию. Что касается первой реализации, то она появилась в 1950-х гг. в форме языка LISP, о котором речь пойдет далее.
Напомним, что важнейшей характеристикой функционального подхода является то обстоятельство, что всякая программа, разработанная на языке функционального программирования, может рассматриваться как функция, аргументы которой, возможно, также являются функциями.
Функциональный подход породил целое семейство языков, родоначальником которых, как уже отмечалось, стал язык программирования LISP. Позднее, в 1970-х гг., был разработан первоначальный вариант языка ML, который впоследствии развился в ряд других языков (SML, Haskell), из которых самым «молодым» является созданный недавно, в 2005 г., язык F#.
Истоки математических основ функционального подхода к программированию следует искать в ранних работах М. Шейнфинкеля (Moses Schonfinkel), которые малоизвестны, так как довольно далеки по времени от работ, непосредственно связанных с функциональным подходом.
Не вызывает сомнений тот факт, что разработанная Л. Черчем (Alonso Church) теория конечных последовательностей в форме исчисления лямбда-конверсий (или короче лямбда-исчислений), которая будет рассмотрена подробнее в следующем параграфе, положила начало математическому исчислению, формализующему понятие функции.
Дальнейшее развитие функциональный подход получает в работах, посвященных типизированному лямбда-исчислению, согласно которым аргументам функций и самим функциям можно назначать (или, иначе, приписывать) тот или иной тип. Типизация существенно увеличивает вычислительную стройность и значимость любой математической формализации, и, естественно, без нее немыслимы современные языки программирования. Проблемы и особенности типизации будут подробно рассмотрены ниже.
Теорию и практику программирования существенно обогатило моделирование среды вычислений в форме абстрактной машины, построенной на основе категориальной комбинаторной логики, созданной X. Карри (Haskell В. Curry), в честь которого назван язык Haskell. Заметим, что абстрактные (или, иначе, виртуальные) машины являются основой для реализации платформы .NET.
Наконец, теория решеток Д. Скотта (Dana S. Scott) стала основой для моделирования вычисления значения функции (или семантики) языка программирования.
Важным преимуществом реализации языков функционального программирования является автоматизированное динамическое распределение памяти компьютера для хранения данных. При этом программист избавляется от рутинной необходимости контролировать данные, а при необходимости может запустить функцию «сборки мусора» — очистки памяти от тех данных, которые больше не потребуются программе.
Сложные программы при функциональном подходе строятся посредством агрегирования функций. При этом текст программы представляет собой функцию, некоторые аргументы которой можно также рассматривать как функции. Таким образом, повторное использование кода сводится к вызову ранее описанной функции, структура которой, в отличие от процедуры императивного языка, прозрачна математически.
Типы отдельных переменных функций, используемых в функциональных языках, могут быть переменными. При этом подходе обеспечивается возможность обработки разнородных данных (например, упорядочение элементов списка но возрастанию для целых чисел, отдельных символов и строк), или полиморфизм. Таким образом, при создании программ на функциональных языках программист сосредотачивается на предметной области и в меньшей степени заботится о рутинных операциях (обеспечении правильного с точки зрения компьютера представления данных, «сборке мусора» и т.д.).
Для профессиональной разработки программного обеспечения на языках функционального программирования необходимо глубоко понимать природу функции. Исследованию закономерностей и особенностей природы функции, в основном, и посвящен первый раздел этой книги.
Прежде всего, заметим, что под термином «функция» в математической формализации и программной реализации имеются в виду различные понятия. Так, математической функцией / с областью определения А и областью значений В называется множество упорядоченных пар
В свою очередь, функцией в языке программирования называется конструкция этого языка, описывающая правила преобразования аргумента (так называемого фактического параметра) в результат.
Для формализации понятия «функция» была построена математическая теория, известная сегодня под названием лямбда-исчисления (лямбда-конверсии).
Под конверсией понимается преобразование объектов исчисления (а в программировании — функций и данных) из одной формы в другую. Исходной задачей в математике было стремление к упрощению формы выражений. В программировании именно эта задача не является столь существенной, хотя, как мы увидим в дальнейшем, использование лямбда- исчисления как исходной формализации может способствовать упрощению вида программы, т.е. вести к оптимизации программного кода.
Кроме того, конверсии обеспечивают переход к вновь введенным обозначениям и, таким образом, позволяют представлять предметную область в более компактном либо более детальном виде, или, говоря математическим языком, изменять уровень абстракции по отношению к предметной области. Эту возможность широко используют также языки объектно-ориентированного и структурно-модульного программирования в иерархии объектов, фрагментов программ и структур данных. На этом же принципе основано взаимодействие компонентов приложения в .NET. Именно в этом смысле переход к новым обозначениям является одним из важнейших элементов программирования в целом, и именно лямбда-исчисление (в отличие от многих других разделов математики, в том числе булевой логики) является адекватным способом формализации переобозначений.
Систематизируем эволюцию теорий, лежащих в основе современного подхода к лямбда-исчислению.
Еще в 1924 г. М. Шенфинкель разработал простую (simple) теорию функций, которая фактически являлась исчислением объектов-функций и предвосхитила появление лямбда-исчисления. Затем, в 1934 г., А. Черч предложил собственно исчисление лямбда-конверсий и применил его для исследования теории множеств. Вклад ученого был настолько фундаментальным, что теория до сих пор называется лямбда-исчислением и часто именуется в литературе лямбда-исчислением Черча.
Позднее, в 1940 г., X. Карри (Haskell Curry) предложил теорию функций без переменных (иначе называемых комбинаторами), известную в настоящее время как комбинаторная логика. Эта теория является развитием лямбда-исчисления и представляет собой формальный язык, аналогичный языку функционального программирования и позволяющий более наглядно моделировать вычисления в среде абстрактных машин, в значительной мере схожих с виртуальной машиной .NET.
Позднее, уже в 1960-х гг., Р. Хиндли (Roger Hindley) разработал выводимость типов (type inference), т.е. возможность неявно определить тип выражения, исходя из типов выражений, которые его окружают. Именно эта возможность широко используется в современных языках программирования, таких как SML, Haskell и F#.
Также в 1960-х гг. П. Лендин (Peter Landin) создал первую абстрактную машину на основе расширенного лямбда-исчисления. Машина получила название SECD и формализовала вычисления на языке программирования ISWIM (If you See What I Mean), который впоследствии стал прообразом языка функционального программирования ML.
Наконец, в 1970-х гг. Р. Милнер (Robin Milner) создал полиморфную систему типизации для языка функционального программирования ML, которая вместе с развернутым описанием того же автора положила начало стандартизации этого языка программирования. Язык ML впоследствии эволюционировал по нескольким направлениям (мы будем изучать F#).
Рассмотрим эволюцию языков программирования, развивающихся в рамках функционального подхода.
Ранние языки функционального программирования, которые берут свое начало от классического языка LISP (LISt Processing), были предназначены, как следует из названия, для обработки списков, т.е. символьной информации. При этом основными типами были атомарный элемент и список из атомарных элементов, а основной акцент делался на анализ содержимого списка.
Развитием ранних языков программирования стали языки функционального программирования с сильной типизацией, характерным примером которых являются классический ML и далее, его прямой потомок, F#. В языках с сильной типизацией каждая конструкция (или выражение) должна иметь тип. При этом в более поздних языках функционального программирования, однако, нет необходимости явного приписывания типа, и типы изначально неопределенных выражений, как в F#, могут выводиться (до запуска программы) исходя из типов связанных с ними выражений.
Следующим шагом в развитии языков функционального программирования стала поддержка полиморфных функций, т.е. функций с параметрическими аргументами (аналогами математической функции с параметрами). В частности, полиморфизм поддерживается в языках F#, SML, Miranda и Haskell.
На современном этапе развития возникли языки функционального программирования «нового поколения» со следующими расширенными возможностями: сопоставление с образцом (Scheme, SML, Miranda, Haskell, F#), параметрический полиморфизм (SML, F#) и так называемые «ленивые» (по мере необходимости) вычисления (Haskell, Miranda, SML, F#).
Семейство языков функционального программирования достаточно многочисленно. Это очевидно не столько из значительного списка языков, сколько из того факта, что многие языки дали начало целым направлениям в программировании. Напомним, что LISP дал начало целому семейству языков: Scheme, InterLisp, COMMON Lisp и др.
Развитием «классического» ML стали сразу несколько современных языков с практически одинаковыми возможностями (параметрический полиморфизм, сопоставление с образцом, «ленивые» вычисления). Это язык SML, разработанный в Великобритании и США, CaML, созданный группой французских ученых института INRIA, SML/NJ, — диалект SML из Ныо-Джерси, российская разработка — mosml («московский» диалект ML). На основе CaML для реализации функциональной парадигмы на платформе .NET в 2005 г. командой разработчиков из Microsoft Research под руководством Д. Сайма (Don Syme) был создан язык F#.
Близость к математической формализации и изначальная функциональная ориентированность являются причиной следующих преимуществ функционального подхода:
- 1) простота тестирования и верификации программного кода на основе возможности построения строгого математического доказательства корректности программ;
- 2) унификация представления программы и данных (данные могут быть инкапсулированы в программу как аргументы функций, означивание или вычисление значения функции может производиться по мере необходимости);
- 3) безопасная типизация: недопустимые операции над данными исключены;
- 4) динамическая типизация: возможно обнаружение ошибок типизации во время выполнения (это свойство ранних языков функционального программирования может приводить к переполнению оперативной памяти компьютера);
- 5) независимость программной реализации от машинного представления данных и системной архитектуры программы (программист концентрирует внимание на деталях реализации, а не особенностях машинного представления данных).
По сравнению с другими языками программирования, в том числе с ранними функциональными языками, F# обладает рядом несомненных достоинств. К ним, в первую очередь, относятся:
- 1) безопасность программного кода, т.е. гарантия отсутствия переполнения памяти (в случае корректно написанной программы) и, соответственно, защиты от потенциальной неустойчивости работы системы посредством искусственного создания этого переполнения (такие языки программирования, как «классический» С и C++, потенциально небезопасны);
- 2) статическая типизация — все ошибки несоответствия типов выявляются уже на стадии контроля соответствия типов в ходе трансляции (а не во время выполнения программы, как в LISP и Scheme);
- 3) выводимость типов (нет необходимости явно указывать тип каждого выражения, при этом результирующий программный код становится более удобочитаемым, его легче хранить и повторно использовать).
К числу других преимуществ языка функционального программирования F# следует отнести параметрический полиморфизм (возможность обрабатывать аргументы абстрактного типа). При этом трудозатраты на разработку программного обеспечения сокращаются за счет универсальности разрабатываемых функций (скажем, становится возможным написать унифицированную функцию для упорядочения по возрастанию элементов списка, которая сможет упорядочивать и список из целочисленных элементов, и список из символьных строк).
Еще одним мощным средством, облегчающих символьную обработку (в частности, декомпозицию и верификацию программ), является механизм сопоставления с образцом.
Построение программ из модулей способствует разделению интерфейсной части (описательной части) и реализации (содержательной части) функций, что обеспечивает унификацию и сокращает время создания сложных программных проектов, облегчая тестирование на соответствие спецификациям заказчика.
Обработка исключительных ситуаций, которые описывают ход выполнения программы в случае возникновения тех или иных относительно редких событий, а также теоретически интересного механизма продолжений, создают возможность реализации программных систем, взаимодействующих с пользователем в реальном времени.
Заметим, что реализация преимуществ, которые предоставляют языки функционального программирования, существенно зависит от выбора программно-аппаратной платформы. В случае выбора в качестве программной платформы технологии .NET, практически вне зависимости от аппаратной реализации, программист или руководитель программного проекта дополнительно получает следующие преимущества:
- 1) интеграция различных языков функционального программирования (при этом максимально используются преимущества каждого из языков, в частности Scheme предоставляет механизм сопоставления с образцом, a F# — «ленивость» или вычисления по мере необходимости);
- 2) интеграция различных подходов к программированию на основе межъязыковой инфраструктуры CLI (в частности, использование C# для обеспечения преимуществ объектно-ориентированного подхода и F# — функционального, как в этой книге);
- 3) общая система типизации Common Type System, CTS (единообразное и безопасное управление типами данных в программе);
- 4) многоступенчатая, гибкая система обеспечения безопасности программного кода (в частности, на основе механизма сборок).
Вариант 1: какие из перечисленных языков программирования основаны на функциональном подходе?
- а) SML и Pro Log;
- б) LISP и Pro Log;
- в) SML и LISP (+).
Вариант 2 в чем состоит преимущество функционального подхода к программированию перед другими подходами?
- а) близость к предметной области;
- б) прозрачность реализации рекурсии (+);
- в) высокая вычислительная эффективность.
Вариант 3: в чем состоит недостаток языков функционального программирования?
- а) высокая степень машинной независимости;
- б) нелинейная структура программы (+);
- в) узкая проблемная ориентированность.
Вариант 1: каково соотношение понятий функции в математике и программировании?
- а) это несопоставимые понятия;
- б) это эквивалентные понятия;
- в) математические функции моделируют функции в программировании (+).
Вариант 2: что отличает лямбда-исчисление от булевой логики?
- а) лямбда-исчисление адекватно формализует процесс программирования (+);
- б) булева логика более наглядно формализует процесс программирования;
- в) существенных различий нет.
Вариант 3: в чем состоит особенность языка функционального программирования SML?
- а) это бестиповый язык программирования;
- б) это язык программирования с полиморфной типизацией (+);
- в) это язык программирования с параметрическим полиморфизмом.
Вариант 1: какие из перечисленных языков программирования являются диалектами языка SML?
- а) CaML и Haskell;
- б) Mosml и Haskell;
- в) CaML и Mosml (+).
Вариант 2: что объединяет классический ML и более поздние аналоги?
- а) механизм сопоставления с образцом;
- б) полиморфная типизация;
- в) поддержка рекурсии (+).
Вариант У. в чем состоит особенность языков функционального программирования?
- а) этот класс языков основан на сценариях;
- б) концептуально близок к любой предметной области;
- в) легко формализуем математически (+).
Классификация подходов к программированию была построена нами в ходе лекции 1.
Сосредоточимся на важнейшем для данного курса функциональном подходе к программированию.
Прежде всего, обратимся к истории фундаментальных математических исследований, которые привели к появлению функционального подхода к программированию.
Время появления теоретических работ , обосновывающих функциональный подход , относится к 20-м – 30-м годам XX столетия. Как мы убедимся впоследствии, теория часто значительно опережает практику программирования, и важнейшие работы, которые сформировали математическую основу подхода, были написаны задолго до появления компьютеров и языков программирования, которые потенциально могли бы реализовать эту теорию.
Что касается первой реализации, то она появилась в 50-х годах XX столетия в форме языка LISP , о котором речь пойдет далее.
Напомним, что важнейшей характеристикой функционального подхода является то обстоятельство, что всякая программа , разработанная на языке функционального программирования, может рассматриваться как функция , аргументы которой, возможно, также являются функциями .
Функциональный подход породил целое семейство языков, родоначальником которых, как уже отмечалось, стал язык программирования LISP . Позднее, в 70-х годах, был разработан первоначальный вариант языка ML, который впоследствии развился, в частности, в SML , а также ряд других языков. Из них, пожалуй, самым "молодым" является созданный уже совсем недавно, в 90-х годах, язык Haskell.
Важным преимуществом реализации языков функционального программирования является автоматизированное динамическое распределение памяти компьютера для хранения данных. При этом программист избавляется от необходимости контролировать данные, а если потребуется, может запустить функцию "сборки мусора" – очистки памяти от тех данных, которые больше не понадобятся программе.
Сложные программы при функциональном подходе строятся посредством агрегирования функций . При этом текст программы представляет собой функцию , некоторые аргументы которой можно также рассматривать как функции . Таким образом, повторное использование кода сводится к вызову ранее описанной функции , структура которой, в отличие от процедуры императивного языка , математически прозрачна.
Поскольку функция является естественным формализмом для языков функционального программирования, реализация различных аспектов программирования, связанных с функциями , существенно упрощается. Интуитивно прозрачным становится написание рекурсивных функций , т.е. функций , вызывающих самих себя в качестве аргумента. Естественной становится и реализация обработки рекурсивных структур данных .
Благодаря реализации механизма сопоставления с образцом , такие языки функционального программирования как ML и Haskell хорошо использовать для символьной обработки.
Естественно, языки функционального программирования не лишены и некоторых недостатков.
Часто к ним относят нелинейную структуру программы и относительно невысокую эффективность реализации . Однако первый недостаток достаточно субъективен, а второй успешно преодолен современными реализациями, в частности, рядом последних трансляторов языка SML , включая и компилятор для среды Microsoft . NET .
Для профессиональной разработки программного обеспечения на языках функционального программирования необходимо глубоко понимать природу функции . Исследованию закономерностей и особенностей природы функции в основном и посвящены лекции 2 – 12 данного курса.
Заметим, что под термином " функция " в математической формализации и программной реализации имеются в виду различные понятия.
Так, математической функцией f с областью определения A и областью значений B называется множество упорядоченных пар
,
,
В свою очередь , функцией в языке программирования называется конструкция этого языка, описывающая правила преобразования аргумента (так называемого фактического параметра) в результат.
Для формализации понятия " функция " была построена математическая теория, известная под названием ламбда-исчисления . Более точно это исчисление следует именовать исчислением ламбда-конверсий .
Под конверсией понимается преобразование объектов исчисления (а в программировании – функций и данных) из одной формы в другую. Исходной задачей в математике было стремление к упрощению формы выражений. В программировании именно эта задача не является столь существенной, хотя, как мы увидим в дальнейшем, использование ламбда-исчисления как исходной формализации может способствовать упрощению вида программы, т.е. вести к оптимизации программного кода .
Кроме того, конверсии обеспечивают переход к вновь введенным обозначениям и, таким образом, позволяют представлять предметную область в более компактном либо более детальном виде, или, говоря математическим языком, изменять уровень абстракции по отношению к предметной области . Эту возможность широко используют также языки объектно-ориентированного и структурно- модульного программирования в иерархии объектов, фрагментов программ и структур данных. На этом же принципе основано взаимодействие компонентов приложения в . NET . Именно в этом смысле переход к новым обозначениям является одним из важнейших элементов программирования в целом, и именно ламбда-исчисление (в отличие от многих других разделов математики) представляет собой адекватный способ формализации переобозначений.