Гарантированная оптимизация хвостовой рекурсии, то есть хвостовая рекурсия всегда заменяется циклом при компиляции.
Выведение типов. В частности, возможно выведение типов локальных переменных и выведение сигнатуры локальных функций.
Отсутствие четкой границы между инструкцией (statement) и выражением (expression). «Everything is expression». Например, условный оператор может находиться внутри арифметического выражения. Нет необходимости в инструкциях return, break, continue.
Алгебраические типы данных, кортежи и сопоставление с образцом.
Упрощенный синтаксис работы со списками. Списочные литералы.
Частичное применение операторов и функций - простая генерация обёртки некоторой функции, в которой часть параметров подставлена заранее, а часть передаётся непосредственно при вызове функции.
Основные недостатки - сложность синтаксиса, непривычность принятых соглашений и ограничений, практическая невозможность макротрансформаций., Miranda, Haskell
Язык Hope появился в 70х годах в Эдинбургском Университете. Hope является первым языком, в котором появились отложенные вычисления и алгебраические типы, но в нем отсутствует возможность неявного объявления типов. В последующих версиях языка добавилась поддержка отложенных вычислений[7]. Язык является важным этапом в жизни функционального программирования, он послужил основой для таких языков как Miranda и Haskell, но сам распространения не получил.
Язык Miranda был разработан в 1985 году, он стал первым коммерчески поддерживаемым чисто функциональным языком программирования. Его чистая функциональность обеспечивает отсутствие побочных эффектов, так как в языке нет состояния, нет переменных. Выделим также другие особенности языка:поддерживает функции в качестве данных.является «ленивым» (нестрогим) языком, поддерживаются нестрогие функции и бесконечные размерности.
Реализованы генераторы списков (list comprehensions), т.е. создание списков при помощи математических выражений.
В основе языка лежит полиморфная строгая типизация.
Абстрактные типы данных и модули.
Программа на языке Miranda является набором уравнений, которые описывают разнообразные математические функции и алгебраические типы данных. Важным здесь является слово «набор» - порядок вычисления уравнений, в общем, не определен, и до их вычисления не нужно объявлять каких либо сущностей.
Так как при синтаксическом анализе программы используется интеллектуальный разбор, редко появляется необходимость использовать скобки или другие ограничители при ее написании. Также в Miranda не нужно описывать типы при объявлении переменных так как в языке присутствует система вывода типов. В языке существует лишь несколько встроенных типов:
числа (целые неограниченной размерности и числа с плавающей точкой двойной точности)
символы
списки
кортежи
функции[8]была относительно популярна в 1980-х годах, но оставалась проприетарным программным обеспечением. Это затрудняло развитие и исследования возможностей ленивого функционального программирования, поэтому буквально за пару лет появилось более десятка схожих языков. Чтобы объединить усилия разных разработчиков, в 1987 г. на конференции по функциональным языкам программирования и компьютерной архитектуре в Орегоне (FPCA’87) было решено создать комитет для разработки открытого стандарта.
В 1990 г. была предложена первая версия языка Haskell 1.0. В дальнейшем работа комитета продолжилась, и в 1999 г. был опубликован «The Haskell 98 Report», который стал стабильным стандартом языка на много лет. Язык, однако, продолжал бурно развиваться, компилятор GHC (Glasgow Haskell Compiler) был фактическим стандартом в отношении новых возможностей. Последняя версия языка - Haskell 2010 - была объявлена в конце 2009 г, но последней «значительной» версией (стандартом) остаётся Haskell 98 [9].является чисто функциональным языком программирования общего назначения, который включает много последних инноваций в разработке языков программирования. Haskell обеспечивает функции высокого порядка, нестрогую семантику, статическую полиморфную типизацию, определяемые пользователем алгебраические типы данных, сопоставление с образцом, описание списков, модульную систему, монадическую систему ввода - вывода и богатый набор примитивных типов данных, включая списки, массивы, целые числа произвольной и фиксированной точности и числа с плавающей точкой. Haskell является и кульминацией, и кристаллизацией многих лет исследования нестрогих функциональных языков [10].
В качестве основных характеристик языка Haskell можно выделить следующие:
возможность использования лямбда-абстракции;
функции высшего порядка;
частичное применение;
недопустимость побочных эффектов (чистота языка);
ленивые вычисления (lazy evaluation);
сопоставление с образцом, функциональные образцы (pattern matching);
параметрический полиморфизм (в т.ч. абстрагирование от конструктора типа) и полиморфизм классов типов;
статическая типизация;
автоматическое выведение типов (основано на модели типизации Хиндли - Милнера);
алгебраические типы данных;
параметризуемые типы данных;
рекурсивные типы данных;
абстрактные типы данных (инкапсуляция);
генераторы списков (list comprehensions);
охраняющие выражения (guards) - выражения, которые предназначены для ограничения вычислительных процессов и направления их по определённому направлению в зависимости от условия охраны[11];
возможность писать программы с побочными эффектами без нарушения парадигмы функционального программирования с помощью монад;
возможность интеграции с программами, реализованными на императивных языках программирования посредством открытых интерфейсов (стандартное расширение языка Foreign Function Interface);
Среди возможностей компилятора GHC нужно отметить три варианта компиляции: непосредственно в машинные коды целевой архитектуры, компиляция через промежуточный код на языке C или C--, компиляция в язык LLVM (Low Level Virtual Machine).
Со времени принятия последнего стандарта языка (Haskell98) прошло много времени, и с тех пор ведущие реализации языка (ghc и hugs) были расширены множеством дополнительных возможностей:
Полиморфизм 2-го и высших рангов (rank-2 and rank-N polymorphism)
Функциональные зависимости (FD, functional dependencies)
В 2009 году сформировалась концепция Haskell Platform - стандартного дистрибутива языка, включающего кроме компилятора (GHC), также дополнительный инструментарий (систему сборки и развёртывания пакетов Cabal) и набор популярных библиотек. Сейчас Haskell Platform - это рекомендованный базовый дистрибутив для разработчиков. Готовые сборки Haskell Platform доступны для Windows, MacOS X и ряда дистрибутивов Linux.
Развитием ранних языков программирования стали языки функционального программирования с сильной типизацией, характерным примером которых является классический ML, и далее, его прямой потомок, SML. В языках с сильной типизацией каждая конструкция (или выражение) должно иметь тип. При этом в более поздних языках функционального программирования, однако, нет необходимости явного приписывания типа, и типы изначально неопределенных выражений могут выводиться (до запуска программы), исходя из типов связанных с ними выражений.
Следующим шагом в развитии языков функционального программирования стала поддержка полиморфных функций, т.е. функций с параметрическими аргументами (аналогами математической функции с параметрами). В частности, полиморфизм поддерживается в языках SML, Miranda и Haskell.
На современном этапе развития возникли языки
функционального программирования «нового поколения» со следующими расширенными
возможностями: сопоставление с образцом (Scheme, F#, Nemerle), параметрический
полиморфизм (SML) и так называемые «ленивые» (по мере необходимости) вычисления
(Haskell, Miranda, F#,)[12].
1.3 Преимущества функционального
программирования
Важным преимуществом реализации языков функционального программирования является автоматизированное динамическое распределение памяти компьютера для хранения данных. При этом программист избавляется от рутинной необходимости контролировать данные, а при необходимости может запустить функцию «сборки мусора» - очистки памяти от тех данных, которые больше не потребуются программе.
Сложные программы при функциональном подходе строятся посредством агрегирования функций. При этом текст программы представляет собой функцию, некоторые аргументы которой можно также рассматривать как функции. Таким образом, повторное использование кода сводится к вызову ранее описанной функции, структура которой, в отличие от процедуры императивного языка, прозрачна математически.
Типы отдельных функций, используемых в функциональных языках, могут быть переменными. При таком подходе обеспечивается возможность обработки разнородных данных (например, упорядочение элементов списка по возрастанию для целых чисел, отдельных символов и строк) или полиморфизм. Таким образом, при создании программ на функциональных языках программист сосредотачивается на предметной области и в меньшей степени заботится о рутинных операциях (обеспечении правильного с точки зрения компьютера представления данных и т.д.).
Поскольку функция является естественным формализмом для языков функционального программирования, реализация различных аспектов программирования, связанных с функциями, существенно упрощается. Интуитивно прозрачным становится написание рекурсивных функций, т.е. функций, вызывающих самих себя в качестве аргумента. Естественной становится и реализация обработки рекурсивных структур данных.
Благодаря реализации механизма сопоставления с образцом, такие языки функционального программирования как ML и Haskell весьма хорошо применимы для символьной обработки.
Близость к математической формализации и изначальная функциональная ориентированность являются причиной следующих преимуществ функционального подхода:
простота тестирования и верификации программного кода на основе возможности построения строгого математического доказательства корректности программ;
унификация представления программы и данных (данные могут быть инкапсулированы в программу как аргументы функций, означивание или вычисление значения функции может производиться по мере необходимости);
безопасная типизация: недопустимые операции над данными исключены;
динамическая типизация: возможно обнаружение ошибок типизации во время выполнения;
независимость программной реализации от машинного представления данных и системной архитектуры программы (программист концентрирует внимание на деталях реализации, а не особенностях машинного представления данных).
Основной особенностью функционального программирования, определяющей как преимущества, так и недостатки данной парадигмы, является то, что в ней реализуется модель вычислений без состояний. Если императивная программа на любом этапе исполнения имеет состояние, то есть совокупность значений всех переменных, и производит побочные эффекты, то чисто функциональная программа ни целиком, ни частями состояния не имеет и побочных эффектов не производит. То, что в императивных языках делается путём присваивания значений переменным, в функциональных достигается путём передачи выражений в параметры функций. Непосредственным следствием становится то, что чисто функциональная программа не может изменять уже имеющиеся у неё данные, а может лишь порождать новые путём копирования и/или расширения старых. Следствием того же является отказ от циклов в пользу рекурсии.
Привлекательная сторона вычислений без состояний - повышение надёжности кода за счёт чёткой структуризации и отсутствия необходимости отслеживания побочных эффектов. Любая функция работает только с локальными данными и работает с ними всегда одинаково, независимо от того, где, как и при каких обстоятельствах она вызывается. Невозможность мутации данных при пользовании ими в разных местах программы исключает появление труднообнаруживаемых ошибок (таких, например, как случайное присваивание неверного значения глобальной переменной в императивной программе).
Поскольку функция в функциональном программировании не может порождать побочные эффекты, менять объекты нельзя как внутри области видимости, так и снаружи (в отличие от императивных программ, где одна функция может установить какую-нибудь внешнюю переменную, считываемую второй функцией). Единственным эффектом от вычисления функции является возвращаемый ей результат, и единственный фактор, оказывающий влияние на результат - это значения аргументов.
Таким образом имеется возможность протестировать каждую функцию в программе, просто вычислив её от различных наборов значений аргументов. При этом можно не беспокоиться ни о вызове функций в правильном порядке, ни о правильном формировании внешнего состояния. Если любая функция в программе проходит модульные тесты, то можно быть уверенным в качестве всей программы. В императивных программах проверка возвращаемого значения функции недостаточна: функция может модифицировать внешнее состояние, которое тоже нужно проверять, чего не нужно делать в функциональных программах[13].
Традиционно упоминаемой положительной особенностью функционального программирования является то, что оно позволяет описывать программу в так называемом «декларативном» виде, когда жесткая последовательность выполнения многих операций, необходимых для вычисления результата, в явном виде не задаётся, а формируется автоматически в процессе вычисления функций. Это обстоятельство, а также отсутствие состояний даёт возможность применять к функциональным программам достаточно сложные методы автоматической оптимизации.
Ещё одним преимуществом функциональных программ является то, что они предоставляют широчайшие возможности для автоматического распараллеливания вычислений. Поскольку отсутствие побочных эффектов гарантировано, в любом вызове функции всегда допустимо параллельное вычисление двух различных параметров - порядок их вычисления не может оказать влияния на результат вызова.
Естественно, языки функционального программирования не лишены и некоторых недостатков.
Часто к ним относят нелинейную структуру программы и относительно невысокую эффективность реализации. Второй недостаток постепенно исправляется с новыми версиями компиляторов. Тем не менее, программирование с использованием математического понятия функции вызывает некоторые трудности, поэтому функциональные языки, в той или иной степени предоставляют и императивные возможности [2].
Отсутствие присваиваний и замена их на порождение новых данных приводят к необходимости постоянного выделения и автоматического освобождения памяти, поэтому в системе исполнения функциональной программы обязательным компонентом становится высокоэффективный сборщик мусора.
Для преодоления недостатков функциональных программ уже первые языки функционального программирования включали не только чисто функциональные средства, но и механизмы императивного программирования (присваивание, цикл)[14].
В качестве обобщения сравним функциональный и императивный подходы к программированию.
Нужно понимать, что принципы функционального программирования формулировались специально для поддержки функционального, декларативного подхода к решению проблем. Напротив, при императивном подходе разработчик пишет код, подробно определяющий шаги, которые должен выполнить компьютер для достижения цели.
Основные усилия программиста при императивном подходе направлены на способы выполнения (алгоритмы) задач и отслеживания изменений в их состоянии, при функциональном - на требуемые данные и их преобразования. В императивном подходе важное значение имеют состояние и порядок вычисления, в функциональном состояния не существует, а порядок маловажен. Императивный подходи использует циклы, условия и вызовы методов, а функциональный - лишь вызовы функций, в том числе рекурсивный.
Основными единицами обработки в императивном программировании являются экземпляры структур или классов, в функциональном - функции как полноценные объекты и коллекции данных.