Размещено на http://www.allbest.ru/

Реферат

Основные свойства функциональных языков программирования

Санкт-Петербург

2014 год

Содержание

• Введение
• 1. Общие сведения о функциональном программировании
• 1.1 История функционального программирования
• 1.2 Основы функционального программирования
• 1.2.1 Краткость и простота
• 1.2.2 Строгая типизация
• 1.2.3 Модульность
• 1.2.4 Функции - это значения
• 1.2.5 Чистота (отсутствие побочных эффектов)
• 1.2.6 Отложенные (ленивые) вычисления
• Заключение

Список литературы



Введение

Созданная в 1998 году спецификация языка Haskell (названного так в честь учёного Хаскелла Карри, одного из основоположников функционального программирования) нашла необычайно широкую поддержку в научных кругах, в первую очередь, Европы и Японии. В связи с этим буквально за несколько месяцев различными исследовательскими группами и коммерческими компаниями было создано несколько реализаций языка Haskell как в виде интерпретаторов, так и в виде компиляторов - бесплатных и коммерческих.

Наиболее интересным инструментальным средством (ИС), которое используется во многих университетах мира при изучении основ функционального программирования, является ИС HUGS 98, включающее в себя собственно интерпретатор языка Haskell стандарта 1998 года (далее Haskell-98), а также интегрированную среду программирования.

Кроме того, ИС HUGS 98 является абсолютно бесплатным программным средством и может быть свободно получено через Интернет по адресу www.haskell.org. Это дополнительно способствует распространению рассматриваемого ИС в качестве средства для обучения, хотя оно и обладает некоторыми недостатками по сравнению с коммерческими реализациями языка Haskell_98.



1. Общие сведения о функциональном программировании

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

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

Например:

MOV 5, AX

MOV 4, BX

ADD BX

Однако даже ассемблеры не могли стать инструментом, удобным для пользования, так как мнемокоды всё ещё оставались слишком сложными, тем более что всякий ассемблер был жёстко связан с архитектурой компьютера, на котором он исполнялся. Таким образом, следующим шагом после ассемблера стали так называемые императивные языки высокого уровня (BASIC, Pascal, C, Modula и прочие, включая объектно-ориентированные). Императивными такие языки были названы по причине того, что главным их свойством является ориентированность, в первую очередь, на последовательное исполнение инструкций, оперирующих с памятью (т.е. присваиваний), и итеративные циклы. Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности (предписания).

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

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

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

1.1 История функционального программирования

Широко известно, что теоретические основы императивного программирования были заложены еще в 30-х годах XX века учёными Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, также родилась в 20-х-30-х годах XX столетия. В числе разработчиков математических основ функционального программирования можно назвать Мозеса Шёнфинкеля (Германия и Россия) и Хаскелла Карри (Англия), разработавших комбинаторную логику, а также Алонзо Чёрча (США), создателя -исчисления.

Теория так и оставалась теорией, пока в начале 50-х годах XX века Джон МакКарти не разработал язык Lisp, который стал первым почти функциональным языком программирования и на протяжении многих лет оставался единственным. Хотя Lisp все еще используется (как, например, и FORTRAN), он уже не удовлетворяет некоторым современным запросам, которые заставляют разработчиков программ взваливать как можно большую ношу на компилятор, облегчив тем самым свой непосильный труд. Необходимость в этом, конечно же, возникла из-за всё более возрастающей сложности программного обеспечения.

В связи с этим всё большую роль начинает играть типизация. В конце 70-х-начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов, как абстракция данных и полиморфизм. Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число их диалектов, применяемых для решения конкретных задач.

В результате вышло так, что практически каждая группа исследователей, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многочисленные более мелкие проблемы. Чтобы исправить ситуацию, объединенная группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов. В настоящее время действителен стандарт Haskell-98.

В первую очередь, большинство функциональных языков программирования реализуются как интерпретаторы, следуя традициям языка Lisp. Интерпретаторы удобны для быстрой отладки программ, исключая длительную фазу компиляции, тем самым укорачивая обычный цикл разработки. Однако с другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения в несколько раз. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, Objective Caml) или код на C/C++ (например, Glasgow Haskell Compiler). Практически каждый компилятор с функционального языка реализован на этом же языке.

Концепции

Некоторые концепции и парадигмы специфичны для функционального программирования и в основном чужды императивному программированию (включая объектно-ориентированное программирование). Тем не менее, языки программирования обычно представляют собой гибрид нескольких парадигм программирования, поэтому "большей частью императивные" языки программирования могут использовать какие-либо из этих концепций.

Функции высших порядков

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

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

Чистые функции

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

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

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

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

§ Если нет никакой зависимости по данным между двумя чистыми функциями, то порядок их вычисления можно поменять или распараллелить (говоря иначе вычисление чистых функций удовлетворяет принципам thread-safe)

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

Хотя большинство компиляторов императивных языков программирования распознают чистые функции и удаляют общие подвыражения для вызовов чистых функций, они не могут делать это всегда для предварительно скомпилированных библиотек, которые, как правило, не предоставляют эту информацию. Некоторые компиляторы, такие как gcc, в целях оптимизации предоставляют программисту ключевые слова для обозначения чистых функций. Fortran 95 позволяет обозначать функции как "pure" (чистые).

Рекурсия

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

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

Подход к вычислению аргументов

Функциональные языки можно классифицировать по тому, как обрабатываются аргументы функции в процессе её вычисления. Технически различие заключается в денотационной семантике выражения. К примеру, при строгом подходе к вычислению выражения <source lang="python"> print(len([2+1, 3*2, 1/0, 5-4])) </source> на выходе будет ошибка, так как в третьем элементе списка присутствует деление на ноль. При нестрогом подходе значением выражения будет 4, поскольку для вычисления длины списка значения его элементов, строго говоря, не важны и могут вообще не вычисляться. При строгом (аппликативном) порядке вычисления заранее подсчитываются значения всех аргументов перед вычислением самой функции. При нестрогом подходе (нормальный порядок вычисления) значения аргументов не вычисляются до тех пор, пока их значение не понадобится при вычислении функции.

Как правило, нестрогий подход реализуется в виде редукции графа. Нестрогое вычисление используется по умолчанию в нескольких чисто функциональных языках, в том числе Miranda, Clean и Haskell.

ФП в нефункциональных языках

Принципиально нет препятствий для написания программ в функциональном стиле на языках, которые традиционно не считаются функциональными, точно так же, как программы в объектно-ориентированном стиле можно писать на структурных языках. Некоторые императивные языки поддерживают типичные для функциональных языков конструкции, такие как функции высшего порядка и списковые включения (list comprehensions), что облегчает использование функционального стиля в этих языках. Примером может быть функциональное программирование на языке Python.

В языке C указатели на функцию в качестве типов аргументов могут быть использованы для создания функций высшего порядка. Функции высшего порядка и отложенная списковая структура реализованы в библиотеках С++.

В языке C# версии 3.0 и выше можно использовать ?-функции для написания программы в функциональном стиле.

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

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

Простой пример двух решений одной задачи (используется один и тот же язык Python) иллюстрирует это. <source lang="python">

1. императивный стиль

target = [] # создать пустой список for item in source_list: # для каждого элемента исходного списка

</source> Функциональная версия выглядит по-другому: <source lang="python">

1. функциональный стиль

2. языки ФП часто имеют встроенную функцию compose()

compose2 = lambda A, B: lambda x: A(B(x)) target = map(compose2(F, G), source_list) </source>

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

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

Функции высших порядков

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

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

Чистые функции

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

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

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

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

· Если нет никакой зависимости по данным между двумя чистыми функциями, то порядок их вычисления можно поменять или распараллелить (говоря иначе вычисление чистых функций удовлетворяет принципам thread-safe)

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

Хотя большинство компиляторов императивных языков программирования распознают чистые функции и удаляют общие подвыражения для вызовов чистых функций, они не могут делать это всегда для предварительно скомпилированных библиотек, которые, как правило, не предоставляют эту информацию. Некоторые компиляторы, такие как gcc, в целях оптимизации предоставляют программисту ключевые слова для обозначения чистых функций. Fortran 95 позволяет обозначать функции как "pure" (чистые).

Рекурсия

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

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

Функциональные языки можно классифицировать по тому, как обрабатываются аргументы функции в процессе её вычисления. Технически различие заключается в денотационной семантике выражения. К примеру, при строгом подходе к вычислению выражения <source lang="python"> print(len([2+1, 3*2, 1/0, 5-4])) </source> на выходе будет ошибка, так как в третьем элементе списка присутствует деление на ноль. При нестрогом подходе значением выражения будет 4, поскольку для вычисления длины списка значения его элементов, строго говоря, не важны и могут вообще не вычисляться. При строгом (аппликативном) порядке вычисления заранее подсчитываются значения всех аргументов перед вычислением самой функции. При нестрогом подходе (нормальный порядок вычисления) значения аргументов не вычисляются до тех пор, пока их значение не понадобится при вычислении функции.

Как правило, нестрогий подход реализуется в виде редукции графа. Нестрогое вычисление используется по умолчанию в нескольких чисто функциональных языках, в том числе Miranda, Clean и Haskell.

Принципиально нет препятствий для написания программ в функциональном стиле на языках, которые традиционно не считаются функциональными, точно так же, как программы в объектно-ориентированном стиле можно писать на структурных языках. Некоторые императивные языки поддерживают типичные для функциональных языков конструкции, такие как функции высшего порядка и списковые включения (list comprehensions), что облегчает использование функционального стиля в этих языках. Примером может быть функциональное программирование на языке Python.

В языке C указатели на функцию в качестве типов аргументов могут быть использованы для создания функций высшего порядка. Функции высшего порядка и отложенная списковая структура реализованы в библиотеках С++. В языке C# версии 3.0 и выше можно использовать ?-функции для написания программы в функциональном стиле. В сложных языках, типа Алгол-68, имеющиеся средства метапрограммирования (фактически, дополнения языка новыми конструкциями) позволяют создать специфичные для функционального стиля объекты данных и программные конструкции, после чего можно писать функциональные программы с их использованием.

1.2 Основы функционального программирования

Функциональное программирование - раздел дискретной математики и парадигма программирования (совокупность идей и понятий, определяющая стиль написания программ), в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании. Функциональное программирование объединяет разные подходы к определению процессов вычисления на основе достаточно строгих абстрактных понятий и методов символьной обработки данных. Сформулированная Джоном Маккарти (1958) концепция символьной обработки информации компьютером восходит к идеям Черча и других математиков, известным как лямбда-исчисление с конца 20-х годов прошлого века. ?-исчисления являются основой для функционального программирования, многие функциональные языки можно рассматривать как "надстройку" над ними.

Лямбда-исчисление (?-исчисление, лямбда-исчисление) - формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости. ?-исчисление может рассматриваться как семейство прототипных языков программирования. Их основная особенность состоит в том, что они являются языками высших порядков. Тем самым обеспечивается систематический подход к исследованию операторов, аргументами которых могут быть другие операторы, а значением также может быть оператор. Языки в этом семействе являются функциональными, поскольку они основаны на представлении о функции или операторе, включая функциональную аппликацию и функциональную абстракцию.

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

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

Язык обработки информации (ИПЛ) иногда определяется как самый первый машинный функциональный язык. Это язык ассемблерного типа для работы со списком символов. У него было понятие "генератор", использующий функцию в качестве аргумента, а так же он может позиционироваться как язык имеющих функции высшего порядка.

Кеннет Е. Айверсон разработал язык APL в начале 60-х, документировав его в своей книге A Programming Language. APL оказал значительное влияние на FR-язык, созданный Джоном Бэкусом. В начале 90-х Айверсон и Роджер Хьюи создали преемника APL - язык программирования J. В середине 90-х Артур Витни, ранее работавший с Айверсоном, создал язык K, который впоследствии использовался в финансовой индустрии на коммерческой основе.

В 70-х г. в университете Эдинбурга Робин Милнер создал язык ML, а Дэвид Тернер начинал разработку языка SASL в университете Сент-Эндрюса и, впоследствии, язык Miranda в университете города Кент. В конечном итоге на основе ML были созданы несколько языков, среди которых наиболее известные Objective Caml и Standard ML. Так же осуществлялась разработка языка программирования по принципу Scheme, получившего описание в известной работе "Lambda Papers", а так же в книге "Structure and Interpretation of Computer Programs", в которой принципы функционального программирования были донесены до более широкой аудитории.

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

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

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

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

· краткость и простота;

· строгая типизация;

· модульность;

· функции - это значения;

· чистота (отсутствие побочных эффектов);

· отложенные (ленивые) вычисления.

1.2.1 Краткость и простота

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

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

Пример 1. Быстрая сортировка Хоара на языке C:

void quickSort (int a[], int l, int r)

{

int i = l;

int j = r;

int x = a[(l + r) / 2];

do

{

while (a[i] < x) i++;

while (x < a[j]) j--;

if (i <= j)

{

int temp = a[i];

a[i++] = a[j];

a[j--] = temp;

}

}

while (i <= j);

if (l < j) quickSort (a, l, j);

if (i < r) quickSort (a, i, r);

}

Пример 2. Быстрая сортировка Хоара на абстрактном функциональном языке:

quickSort ([]) = []

quickSort ([h : t]) = quickSort (n | n t, n <= h) + [h] + quickSort (n | n t, n > h)



Пример 2 следует читать так:

1. Если список пуст, то результатом также будет пустой список.

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

Пример 3. Быстрая сортировка Хоара на языке Haskell:

quickSort [] = []

quickSort (h : t) = quickSort [y | y <- xs, y < x] ++ [h] ++ quickSort [y | y <- xs, y >= x]

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

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

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

Пример 4. Определение N-го числа Фибоначчи:

fibb (0) = 1

fibb (1) = 1

fibb (N) = fibb (N - 2) + fibb (N - 1)

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

1.2.2 Строгая типизация

Практически все современные языки программирования являются строго типизированными языками (возможно, за исключением языка JavaScript и его диалектов, не существует императивных языков без понятия "тип"). Строгая типизация обеспечивает безопасность. Программа, прошедшая проверку типов, просто не может выпасть в операционную систему с сообщением подобным "access violation", особенно это касается таких языков, как C/C++ и Object Pascal, где применение указателей является типичным способом использования языка. В функциональных языках большая часть ошибок может быть исправлена на стадии компиляции (первого шага интерпретации - кодогенерации), поэтому стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерировать более эффективный код и тем самым ускорять выполнение программ.

Рассматривая пример с быстрой сортировкой Хоара, можно увидеть, что помимо уже упомянутых отличий между вариантом на языке C и вариантами на абстрактном функциональном языке и на языке Haskell есть ещё одно важное отличие: функция на языке C сортирует список значений типа int (целых чисел), а функции на абстрактном функциональном языке и на языке Haskell - список значений любого типа, который принадлежит к классу упорядоченных величин. Поэтому последние две функции могут сортировать и список целых чисел, и список чисел с плавающей точкой, и список строк. Можно описать какой-нибудь новый пользовательский тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функции quickSort и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным полиморфизмом и поддерживается большинством функциональных языков.

Ещё одной разновидностью полиморфизма является перегрузка функций, позволяющая давать различным, но в чём-то схожим функциям одинаковые имена. Типичным примером перегруженной операции является обычная операция сложения. Функции сложения для целых чисел и чисел с плавающей запятой различны, однако для удобства они носят одно и то же имя (инфиксный знак "+"). Некоторые функциональные языки помимо параметрического полиморфизма поддерживают и перегрузку операций.

В языке C++ имеется такое понятие, как шаблон, ко

торое позволяет программисту определять полиморфные функции, подобные quickSort. В стандартную библиотеку C++ STL входит такая функция и множество других полиморфных функций. Но шаблоны языка C++, как и родовые функции языка Ada, на самом деле порождают множество перегруженных функций, которые компилятор должен каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция quickSort - это одна единственная функция.

В некоторых языках, например в языке Ada, строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Чтобы избежать этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста. Этот механизм называется механизмом вывода типов. Известно несколько таких механизмов, однако большинство из них являются разновидностями модели типизации Хиндли-Милнера, разработанной в начале 80-х годов XX века. Таким образом, в функциональных языках в большинстве случаев можно не указывать типы функций.

1.2.3 Модульность

Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с чётко определёнными связями между ними. Тем самым облегчается процесс проектирования и последующей поддержки больших программных систем. Поддержка модульности не является свойством именно функциональных языков программирования, однако поддерживается большинством таких языков. Существуют очень развитые модульные императивные языки. В качестве примеров подобных языков можно привести языки Modula-2 и Ada-95.

1.2.4 Функции - это значения

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

Например, определив функцию возведения целого числа в квадрат как

square (N) = N * N,

можно воспользоваться функцией map для возведения в квадрат всех элементов некоторого списка:

squareList = map (square, [1, 2, 3, 4])

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



1.2.5 Чистота (отсутствие побочных эффектов)

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

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

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

Каковы же преимущества чистых функциональных языков? Помимо упрощения анализа программ есть еще одно весомое преимущество - параллелизм.

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

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

В качестве примера можно привести Lisp-машину.

1.2.6 Отложенные (ленивые) вычисления

В традиционных языках программирования (например, C++) вызов функции приводит к вычислению всех аргументов. Этот метод вызова функции называется вызов-по-значению. Если какой-либо аргумент не использовался в функции, то результат вычислений пропадает, следовательно, вычисления были произведены впустую. В каком-то смысле противоположностью вызова-по-значению является вызов-по-необходимости. В этом случае аргумент вычисляется, только если он нужен для вычисления результата. Примером такого поведения можно взять оператор конъюнкции все из того же C++ (&&), который не вычисляет значение второго аргумента, если первый аргумент имеет ложное значение.

Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим. На самом деле, в таких языках порядок вычисления строго определен. В качестве примера строгих языков можно привести языки Scheme, Standard ML и Caml.

Языки, использующие отложенные вычисления, называются нестрогими. Haskell - нестрогий язык, так же как, например, языки Gofer и Miranda. Нестрогие языки зачастую являются чистыми.

Строгие языки часто включают в себя средства некоторых полезных возможностей, присущих нестрогим языкам, например бесконечных списков. В поставке языка Standard ML присутствует специальный модуль для поддержки отложенных вычислений. А язык Objective Caml, помимо этого, поддерживает дополнительное зарезервированное слово lazy и конструкцию для списков значений, вычисляемых по необходимости.

Языки функционального программирования

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

Лисп (List processor). Считается первым функциональным языком программирования. Поддерживает динамическую и факультативно статическую типизацию. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. В стандарт Common Lisp входит Common Lisp Object System (CLOS) - объектная система Common Lisp, которая по многим параметрам превосходит объектные системы в других языках (поддерживает метаобъектный протокол, мультиметоды и т.д.).

ISWIM (If you See What I Mean). Функциональный язык-прототип. Разработан Питером Ландиным в 60-х годах XX вемка для демонстрации того, каким может быть язык функционального программирования. Вместе с языком П. Ландин разработал и специальную виртуальную машину для исполнения программ на ISWIM'е. Эта виртуальная машина, основанная на вызове-по-значению, получила название SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.

Scheme. Диалект Lisp'а, предназначенный для научных исследований в области computer science. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем Common Lisp.

ML (Meta Language). Семейство строгих языков с развитой полиморфной системой типов и параметризуемыми модулями. ML преподаётся во многих западных университетах (в некоторых даже как первый язык программирования).

Standard ML. Один из первых типизированных языков функционального программирования. Содержит некоторые императивные свойства, такие как ссылки на изменяемые значения и поэтому не является чистым. При вычислениях использует вызов-по-значению. Очень интересная реализация модульности. Мощная полиморфная система типов. Последний стандарт языка - Standard ML-97, для которого существует формальные математические определения синтаксиса, а также статической и динамической семантик языка.

Caml Light и Objective Caml. Как и Standard ML принадлежит к семейству ML. Objective Caml отличается от Caml Light в основном поддержкой классического объектно-ориентированного программирования. Также как и Standard ML строгий, но имеет некоторую встроенную поддержку отложенных вычислений.

Miranda. Разработан Дэвидом Тёрнером, в качестве стандартного функционального языка, использовавшего отложенные вычисления. Имеет строгую полиморфную систему типов. Как и ML преподаётся во многих университетах. Оказал большое влияние на разработчиков языка Haskell.

Haskell. Один из самых распространённых не строгих языков. Имеет очень развитую систему типизации. Несколько хуже разработана система модулей. Последний стандарт языка - Haskell-98.

Gofer (GOod For Equational Reasoning). Упрощённый диалект Haskell'а. Предназначен для обучения функциональному программированию.

Clean. Специально предназначен для параллельного и распределённого программирования. По синтаксису напоминает Haskell. Чистый. Использует отложенные вычисления. С компилятором поставляется набор библиотек (I/O libraries), позволяющих программировать графический пользовательский интерфейс под Win32 или Mac OS.

Как правило, интерес к функциональным языкам программирования, особенно чисто функциональным, был скорее научный, нежели коммерческий. Однако, такие примечательные языки как Erlang, OCaml,Haskell, Scheme (после 1986) а также специфические R (статистика), Mathematica (символьная математика), J и K (финансовый анализ), и XSLT (XML) находили применение в индустрии коммерческого программирования. Такие широко распространенные декларативные языки как SQL и Lex/Yacc содержат некоторые элементы функционального программирования, например, они остерегаются использовать переменные. Языки работы с электронными таблицами также можно рассматривать как функциональные, потому что в ячейках электронных таблиц задаётся массив функций, как правило, зависящих лишь от других ячеек, а при желании смоделировать переменные приходится прибегать к возможностям императивного языка макросов.



Заключение

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

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

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

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

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

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

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



Список литературы

1. Могилёв А.В., Пак Н.И., Хеннер Е.К. Информатика: Учеб. пособие для студ. пед. ву-зов / Под ред. Е.К. Хеннера. - М., Academia, 2004.

2. Сборник задач по программированию. / Авт. - сост. А.П. Шестаков; Перм. ун-т. - Пермь, 2001. (Ч. I - 76 с.; Ч. II (Олимпиадные задачи) - 112 с.).

3. Семакин И.Г., Шестаков А.П. Основы программирования: Учебник. - М.: Мастерство, НМЦ СПО; Высшая школа, 2004. - 432 с.

4. Касперски К.; Рокко Е. Искусство дизассемблирования; BHV - Москва, 2008. - 896 c.

5. Касьянов В.Н. Оптимизирующие преобразования программ; Наука - 1988. - 336 c.

6. Кнут Д. Искусство программирования для ЭВМ; М.: Мир - Москва, 1976. - 569 c.

7. Кувыкин В.А.; Коваль И.Г.; Кувыкина М.И. и др. Прикладное программирование в системе КАМА; М.: Финансы и статистика - 1983. - 271c.

8. Культин Никита Основы программирования в Delphi 7; СПб: БХВ - Москва, 2003. - 608 c.

9. Кьоу Дж.; Джеанини М. Объектно-ориентированное программирование. Просто и понятно; СПб: Питер - Москва, 2005. - 238 c.

10. Намиот Д.Е. Практическое использование MS Windows; Унитех - Москва, 1992. - 124 c.

11. Интернет ресурс dic.academic.ru (http://dic.academic.ru/dic.nsf/bse/124059/)

12. Интернет ресурс wikibooks.org (http://ru.wikibooks.org/wiki/)

Размещено на Allbest.ru