Функциональное программирование. Стиль программирования функциональный

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

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

Другими словами, функциональное программирование является способом создания программ, в которых единственным действием является вызов функции, единственным способом разбиения программы является создание нового имени функции и задания для этого имени выражения, вычисляет значение функции, а единственным правилом композиции является оператор суперпозиции функций. Никаких ячеек памяти, операторов присваивания, циклов, ни, тем более, блок-схем или передачи управления. [1]

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

Основное внимание функциональным языкам программирования, особенно "чисто функциональным", уделили академические исследователи. Однако, в известных функциональных языков программирования, используемых в промышленности и коммерческом программировании принадлежит Erlang (параллельные программы), R (статистика), Mathematica (символьные вычисления) J и K ( финансовый анализ), и специализированные языки программирования например XSLT. Существенное влияние на функциональное программирование осуществило лямбда-исчисление, язык APL, язык Lisp и новая язык Haskell.

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

1. Языки программирования

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

• XQuery
• Haskell - чистый функциональный. Назван в честь Хаскелл Карри
• LISP (Джон Маккарти, 1958, множество его потомков, современные из которых - Scheme и Common Lisp)
• ML (Робин Милнер, 1979, из ныне используемых диалектов известны Standard ML и Objective CAML)
• Miranda (Дэвид Тернер, 1985, который впоследствии дал развитие речи Haskell)
• Erlang - (Joe Armstrong, 1986) функциональная язык с поддержкой процессов
• Nemerle - гибридная функционально / императивная речь.
• F # - функциональная язык для платформы . NET
• Scala - гибридная ОО / функциональная язык для платформы Java
• Clojure - функциональная язык для платформы Java

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

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

2. История

Лямбда-исчисление стало теоретической базой для описания и вычисления функций. Будучи математической абстракцией, а не языке программирования, оно составило базис многих языков функционального программирования на сегодняшний день. Подобное теоретическое понятие, комбинаторная логика, более абстрактным, чем λ-исчисление и был создан ранее. Эта логика используется в некоторых эзотерических языках, например в Unlambda. И λ-исчисления, и комбинаторная логика были разработаны для более ясного и точного описания принципов и основ математики [3].

Первой функциональной языке был Lisp, созданный Джоном МакКарти в период его работы в МТИ в конце пятидесятых и реализован, прежде всего, для IBM 700/7000 (Англ.) укр. . Lisp ввел множество понятий функционального языка, хотя при этом исповедовал не только парадигму функционального программирования [4]. Дальнейшим развитием Лиспа стали такие языки как Scheme и Dylan.

Язык обработки информации (Information Processing Language}} IPL) иногда определяется как самая машинно-функциональный язык [5]. Это язык ассемблерного типа для работы со списком символов. В нем было понятие "генератора", который использовал функцию как аргумент, а также, поскольку это язык ассемблерного уровня, он может позиционироваться как язык, имеет функции высшего порядка. Однако, в целом IPL акцентировано на использование императивных понятий [6].

Кеннет Е. Айверсон разработал язык APL в начале шестидесятых, продокоментувавшы ее в своей книге A Programming Language (ISBN 9780471430148) [7]. APL оказал значительное влияние на язык FP (Англ.) укр. , Созданную Джоном Бэкуса. В начале девяностых Айверсон и Роджер Хуэй (Англ.) укр. создали преемника APL - язык J. В середине девяностых Артур Уитни (Англ.) укр. , Ранее работавший с Айверсоном, создал язык K, которая впоследствии использовалась в финансовой индустрии на коммерческой основе.

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

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

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

3. Концепции

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

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

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

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

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

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

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

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

3.3. Рекурсия

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

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

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

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

print ( len ( [ 2 + 1 , 3 * 2 , 1 / 0 , 5 - 4 ] ) )

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

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

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

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

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

4. Стили программирования

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

# Императивный стиль target = [ ] # Создать пустой список for item in source_list: # Для каждого элемента исходного списка trans1 = G ( item ) # Применить функцию G () trans2 = F ( trans1 ) # Применить функцию F () target. append ( trans2 ) # Добавить преобразован элемент в список

Функциональная версия выглядит по-другому:

# Функциональный стиль # Языки ФП часто имеют встроенную функцию compose () compose2 = lambda A , B: lambda x: A ( B ( x ) ) target = map ( compose2 ( F , G ) , source_list )

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

5. Особенности

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

5.1. Сильные стороны

5.1.1. Повышение надежности кода

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

5.1.2. Удобство организации модульного тестирования

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

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

5.1.3. Возможности оптимизации при компиляции

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

5.1.4. Возможности параллелизма

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

5.2. Недостатки

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

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

6. Правила

1. Хендерсон 1983, Предисловие редактора перевода
2. Вольфенгаген В. Э.. Конструкции языков программирования. Приемы описания. - М: АО "Центр ЮрИнфоР", 2001. - 276 с ISBN 5-89158-079-9.
3. Роджер Пенроуз Глава 2: Лямбда-исчисление Черча / / Новый ум короля. О компьютерах, мышлении и законах физики = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. - Едиториал УРСС, 2003. - ISBN 5-354-00005-X + Переиздание ISBN 978 - 5-382-01266-7; 2011
4. J. Harrison, 1997, Гл. 3. λ-исчисление как язык программирования
5. В своих мемуарах Герберт Саймон (1991), Models of My Life pp. 189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых "часто называют отцами искусственного интеллекта" за написание программы Logic Theorist (Англ.) укр. автоматически доказывает теоремы из Principia Mathematica. Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.
6. History of Programming Languages: IPL
7. XIV. APL Session / / History of Programming Language / Richard L. Wexelbblat. - Academic Press, 1981. - С. 661-693. - ISBN 0-12-745040-8
8. Пол Хьюдак (Англ.) укр. Conception, evolution, and application of functional programming languages ​​/ / ACM Computing Surveys. - Т. 21. - (September 1989) (3) С. 359 -411.
9. Скачать PDF: "Техники функционального программирования, В.А. Потапенко" с. 8 "Функции высших порядков".
10. GCC, Declaring Attributes of Functions
11. XL Fortran for AIX, V13.1 Language Reference, Pure procedures (Fortran 95)]
12. Tail call optimization
13. Revised5 Report on the Algorithmic Language Scheme, 3.5. Proper tail recursion
14. Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений - М.: ГИНФО, 2002. - 260 с. Стр. 14 п. 3.1. Ленивые и энергичные вычисления
15. Ахмечет В. "Функциональное программирование для всех"

nado.znate.ru

Стили программирования

530	Глава 22. Рецепт программы

окончательного срока. Вынуть, вывалить и дать остыть, перед тем как подавать клиенту.

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

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

Мы писали программы для ZX spectrum не так, как для современного наладонного PDA, и не так, как систему биржевого контроля для мэйнфрейма с высокопроизводительным веб%интерфейсом. В одиноч% ку мы программируем иначе, чем в паре, и иначе, чем в команде из 200 человек. Выбор рецепта определяется различиями в целевой плат% форме и команде разработчиков (и их уровне мастерства). Искусство программирования не ограничивается работой с редактором, компи% ляцией, сборкой и запуском.

Хорошие программисты знают, как программировать – владеют методами и приемами работы.

Каковы же эти рецепты программирования?

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

Разным языкам программирования соответствуют разные стили про% граммирования. Одни стили подогнаны под конкретный язык, другие

Стили программирования

531

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

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

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

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

Структурное программирование

В этом стандартном методе процедурного проектирования применяет% ся алгоритмическая декомпозиция – процесс разбиения системы на части, каждая из которых представляет собой небольшой шаг в более крупном процессе. Проектные решения направлены на поток управле% ния и создают иерархическую функциональную структуру. Как писал Дейкстра: «Иерархические системы обладают тем свойством, что сущ% ность, считающаяся неделимой на одном уровне, рассматривается как составной объект на следующем, более низком уровне детализации; в результате естественные гранулы пространства или времени, приме% нимые на каждом уровне, уменьшаются на порядок, когда мы пере% ключаем свое внимание на очередной более низкий уровень. Мы гово% рим о стенах в терминах кирпичей, о кирпичах – в терминах кристал% лов, о кристаллах – в терминах молекул, и т. д.» Так Дейкстра попу% ляризировал структурное программирование в своей классической статье «Go To Statement Considered Harmful» (Оператор Go To вреден). (Dijkstra 68)

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

532	Глава 22. Рецепт программы

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

•Каждый шаг декомпозиции должен быть в пределах разумного по% нимания программистом. (Дейкстра сказал: «Я предлагаю ограни% читься проектированием и реализацией программ, понимаемых ра% зумом».)

•Поток управления нужно тщательно контролировать: избегайте ужасного оператора goto (неструктурированного перехода в произ% вольное место программы) и пишите функции с одним входом и од% ним выходом (так называемый код SESE).

•Структурность кода обеспечивается циклическими конструкциями и условными операторами внутри функциональных блоков. Отно% шение к досрочным выходам в середине цикла или из вложенного блока такое же негодующее, как к goto.

Распространенные языки структурного программирования – C, Pascal, BASIC и более древние, типа Fortran и COBOL. С помощью большинст% ва процедурных языков легко пишется структурный код, хотя это не их специализация; структурные программисты часто принимают но% вомодные языки, не принимая новых идиом.1

ОбъектноNориентированное программирование

Буч так описывает ОО%программирование: «Метод реализации, при котором программы организованы в виде взаимодействующих между собой объектов, каждый из которых представляет собой экземпляр не% которого класса, а классы образуют иерархическую структуру, осно% ванную на отношениях наследования.» (Booch 94) Это тоже процедур% ный стиль, но он позволяет более естественным способом моделировать реальность; мы направляем свое внимание на моделируемые взаимо% действующие сущности, а не на конкретный поток выполнения.

Эта модель в значительной степени строится вокруг данных (в отличие от структурного программирования, где в центре находятся процес% сы). Мы интересуемся здесь жизнью данных и их перемещением, а не последовательностью действий, которые нужно выполнить, чтобы ре% шить задачу. У объектов (данных) есть поведение (они что%то делают) и состояние (которое изменяется в результате действий). На уровне языка это реализовано в виде методов классов объектов. ОО%програм% мы рассматриваются как наборы взаимодействующих программных компонент, а не монолитные списки команд ЦП. ОО%проектирование позволило нам эффективно моделировать крупные системы.

В объектно%ориентированном программировании применяются сле% дующие понятия компьютерной науки:

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

Стили программирования

533

Абстракция

Абстракция – как искусство избирательно уделять внимание – по% зволяет проектировать код так, что верхние уровни управления мо% гут игнорировать конкретные детали реализации. Не все ли равно, что происходит при обращении к get_next_item – бинарный поиск по дереву, выбор элемента массива или телефонный звонок во Франк% фурт? Важно, что возвращается очередной элемент (чем бы он ни был), и вызывающему коду больше ни о чем беспокоиться не нужно.

Представление Дейкстрой иерархии (вернитесь к нему и прочтите снова) открыло определенный вид абстракции.

Инкапсуляция

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

Наследование

Это механизм для создания объектов, являющихся особой версией родительских. Пусть родительский тип называется Фигура, а насле% дуют ему Квадрат, Круг и Треугольник. Наследники обладают более де% тальным и специализированным поведением (например, они знают, сколько сторон у фигуры). Как и любые идеи в программировании, наследование может служить основой для создания непонятных и странных программ, а может применяться в логически правиль% ном, элегантном коде. Хорошие ОО%программисты умеют создавать эффективные наследственные иерархии.

Полиморфизм

Это свойство позволяет одному и тому же коду действовать с данны% ми разных типов (которые в ОО%языках обычно называются класса% ми), используя контекст, в котором выполняется код. Эта техноло% гия особо выделяет программирование согласно явно заданным ин% терфейсам, а не неявным реализациям – полиморфизм обеспечивает четкое разделение обязанностей при написании кода. Полиморфизм бывает двух видов: динамический истатический.

Динамический полиморфизм в соответствии со своим названием определяет фактическую операцию на этапе исполнения – в зависи% мости от типа операнда или целевого объекта. При этом часто ис% пользуется иерархия наследования: клиент, работающий с типом Фигура, может в конкретном случае работать с объектами типа Квад рат или Треугольник, что определяется во время прогона.

studfiles.net

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

Функциона́льное программи́рование — раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних (в отличие от функций как подпрограмм в процедурном программировании).

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

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

На практике отличие математической функции от понятия «функции» в императивном программировании заключается в том, что императивные функции могут опираться не только на аргументы, но и на состояние внешних по отношению к функции переменных, а также иметь побочные эффекты и менять состояние внешних переменных. Таким образом, в императивном программировании при вызове одной и той же функции с одинаковыми параметрами, но на разных этапах выполнения алгоритма, можно получить разные данные на выходе из-за влияния на функцию состояния переменных. А в функциональном языке при вызове функции с одними и теми же аргументами мы всегда получим одинаковый результат: выходные данные зависят только от входных. Это позволяет средам выполнения программ на функциональных языках кешировать результаты функций и вызывать их в порядке, не определяемом алгоритмом и распараллеливать их без каких-либо дополнительных действий со стороны программиста (что обеспечивают функции без побочных эффектов — чистые функции[⇨]).

Лямбда-исчисление являются основой для функционального программирования, многие функциональные языки можно рассматривать как «надстройку» над ними[1].

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

Наиболее известными языками функционального программирования являются[2]:

Ещё не полностью функциональные изначальные версии и Лиспа, и APL внесли особый вклад в создание и развитие функционального программирования. Более поздние версии Lisp, такие как Scheme, а также различные варианты APL поддерживали все свойства и концепции функционального языка[5].

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

История

Лямбда-исчисление стало теоретической базой для описания и вычисления функций. Являясь математической абстракцией, а не языком программирования, оно составило базис почти всех языков функционального программирования на сегодняшний день. Сходное теоретическое понятие, комбинаторная логика, является более абстрактным, нежели λ-исчисления и было создано раньше. Эта логика используется в некоторых эзотерических языках, например в Unlambda. И λ-исчисление, и комбинаторная логика были разработаны для более ясного и точного описания принципов и основ математики[6].

Первым функциональным языком был Лисп, созданный Джоном Маккарти в период его работы в Массачусетском технологическом институте в конце пятидесятых и реализованный, первоначально, для IBM 700/7000 (англ.)русск.[7]. В Лиспе впервые введено множество понятий функционального языка, хотя при этом в языке применяется не только парадигма функционального программирования[8]. Дальнейшим развитием Лиспа стали такие языки как Scheme и Dylan.

Язык обработки информации (Information Processing Language (англ.)русск., IPL) иногда определяется как самый первый машинный функциональный язык[9]. Это язык ассемблерного типа для работы со списком символов. В нём было понятие «генератора», который использовал функцию в качестве аргумента, а также, поскольку это язык ассемблерного уровня, он может позиционироваться как язык, имеющий функции высшего порядка. Однако, в целом IPL акцентирован на использование императивных понятий[10].

Кеннет Е. Айверсон разработал язык APL в начале шестидесятых, документировав его в своей книге A Programming Language (ISBN 978-0-471-43014-8)[11]. APL оказал значительное влияние на язык FP (англ.)русск., созданный Джоном Бэкусом. В начале девяностых Айверсон и Роджер Хуэй (англ.)русск. создали преемника APL — язык программирования J. В середине девяностых Артур Витни (англ.)русск., ранее работавший с Айверсоном, создал язык K, который впоследствии использовался в финансовой индустрии на коммерческой основе.

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

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

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

Концепции

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

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

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

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

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

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

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

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

Рекурсия

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

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

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

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

print(len([2+1, 3*2, 1/0, 5-4]))

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

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

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

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

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

Стили программирования

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

# императивный стиль target = [] # создать пустой список for item in source_list: # для каждого элемента исходного списка trans1 = G(item) # применить функцию G() trans2 = F(trans1) # применить функцию F() target.append(trans2) # добавить преобразованный элемент в список

Функциональная версия выглядит по-другому:

# функциональный стиль # языки ФП часто имеют встроенную функцию compose() compose2 = lambda A, B: lambda x: A(B(x)) target = map(compose2(F, G), source_list)

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

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

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

Особенности

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

Сильные стороны

Повышение надёжности кода

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

Удобство организации модульного тестирования

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

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

Возможности оптимизации при компиляции

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

Возможности параллелизма

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

Недостатки

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

Для преодоления недостатков функциональных программ уже первые языки функционального программирования включали не только чисто функциональные средства, но и механизмы императивного программирования (присваивание, цикл, «неявный PROGN» были уже в Лиспе). Использование таких средств позволяет решить некоторые практические проблемы, но означает отход от идей (и преимуществ) функционального программирования и написание императивных программ на функциональных языках. В чистых функциональных языках эти проблемы решаются другими средствами, например, в языке Haskell ввод-вывод реализован при помощи монад — нетривиальной концепции, позаимствованной из теории категорий.

См. также

Примечания

1. ↑ А. Филд, П. Харрисон Функциональное программирование: Пер. с англ. — М.: Мир, 1993. — 637 с, ил. ISBN 5-03-001870-0. Стр. 120 [Глава 6: Математические основы: λ-исчисление].
2. ↑ Tiobe Programming Community Index
3. ↑ Николас Чейз. Введение в XSLT. IBM developerWorks (12 января 2009). Проверено 25 июня 2013. Архивировано 2 июля 2013 года.
4. ↑ Дмитрий Сошников. «F# – компромисс между академическим миром и реальной жизнью» // Системный администратор. — 2013. — № 1-2 (122-123).
5. ↑ 1 2 Пол Хьюдак (англ.)русск. (September 1989). «Conception, evolution, and application of functional programming languages» (PDF). ACM Computing Surveys 21 (3): 359—411. DOI:10.1145/72551.72554.
6. ↑ Роджер Пенроуз. Глава 2: Лямбда-исчисление Черча // Новый ум короля. О компьютерах, мышлении и законах физики = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. — Едиториал УРСС, 2003. — ISBN 5-354-00005-X. + переиздание ISBN 978-5-382-01266-7; 2011 г.
7. ↑ McCarthy, John (June 1978). «History of Lisp». In ACM SIGPLAN History of Programming Languages Conference: 217–223. DOI:10.1145/800025.808387.
8. ↑ J. Harrison, 1997, Гл. 3. λ-исчисление как язык программирования.
9. ↑ В своих мемуарах Герберт Саймон (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых «часто называют родителями искусственного интеллекта» за написание программы Logic Theorist (англ.)русск. автоматически доказывающей теоремы из Principia Mathematica. Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.
10. ↑ History of Programming Languages: IPL
11. ↑ XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. — Academic Press, 1981. — С. 661-693. — 749 с. — ISBN 0-12-745040-8.
12. ↑ Евгений Кирпичёв. Элементы функциональных языков // Практика функционального программирования. — 2009. — Декабрь (вып. 3). — ISSN 2075-8456.
13. ↑ Скачать PDF: «Техники функционального программирования, В. А. Потапенко» стр. 8 «Функции высших порядков».
14. ↑ GCC, Declaring Attributes of Functions
15. ↑ XL Fortran for AIX, V13.1 > Language Reference, Pure procedures (Fortran 95)
16. ↑ Tail call optimization
17. ↑ Revised5 Report on the Algorithmic Language Scheme, 3.5. Proper tail recursion
18. ↑ Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений — М.: ГИНФО, 2002. — 260 с. Стр. 14 п. 3.1. Ленивые и энергичные вычисления
19. ↑ Ахмечет В. «Функциональное программирование для всех»

Литература

Ссылки

ru-wiki.org

Функциональное программирование: структура и интерпретация. Часть I

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

Я начал программировать еще в детстве, и годам к двадцати пяти мне казалось, что я все знаю и понимаю. Объектно ориентированное программирование стало частью моего мозга, все мыслимые книги о промышленном программировании были прочитаны. Но у меня оставалось такое ощущение, будто я что-то упустил, что-то очень тонкое и необыкновенно важное. Дело в том, что, как и многих в девяностые годы, в школе меня учили программировать на Pascal (о да, слава Turbo Pascal 5.5! — Прим. ред.), потом был C и C++. В университете Fortran и потом Java, как основной инструмент на работе. Я знал Python и еще несколько языков, но все это было не то. А серьезного образования в области Computer Science у меня не было. Однажды во время перелета через Атлантику я не мог заснуть, и мне захотелось что-то почитать. Каким-то волшебным образом у меня под рукой оказалась книга про язык программирования Haskell. Мне кажется, именно тогда я понял истинный смысл выражения «красота требует жертв».

Теперь, когда меня спрашивают, как я выучил Haskell, я так и говорю: в самолете. Этот эпизод изменил мое отношение к программированию вообще. Конечно, после первого знакомства многие вещи казались мне не вполне понятными. Пришлось напрячься и изучить вопрос более тщательно. И знаешь, прошло десять лет, многие функциональные элементы стали частью промышленных языков, лямбда-функции уже есть даже в Java, вывод типов — в С++, сопоставление с образцом — в Scala. Многие думают, что это какой-то прорыв. И в этой серии статей я расскажу тебе про приемы функционального программирования, используя разные языки и их особенности.

Интернетчики часто на потеху публике составляют всякие списки и топы. Например, «список книг, которые ты должен прочесть до тех пор, пока тебе не исполнилось тридцать». Если бы передо мной стояла задача сделать список книг по программированию, которые ты должен прочесть до тех пор, пока тебе сколько-то там не исполнилось, то первое место, безусловно, досталось бы книге Абельсона и Сассмана «Структура и интерпретация компьютерных программ». Мне даже иногда кажется, что компилятор или интерпретатор любого языка должен останавливать каждого, кто не читал эту книгу.

Поэтому если и есть язык, с которого нужно начинать изучение функционального программирования, так это Lisp. Вообще, это целое семейство языков, куда входит довольно популярный сейчас язык для JVM под названием Clojure. Но в качестве первого функционального языка он не особо подходит. Для этого лучше использовать язык Scheme, который был разработан в MIT и до середины двухтысячных годов служил основным языком для обучения программированию. Хотя сейчас вводный курс с тем же названием, что упомянутая книга, был заменен на курс по Python, она все еще не потеряла своей актуальности.

Обложка знаменитой книги «Структура и интерпретация компьютерных программ»

Постараюсь кратко рассказать о языке Scheme и вообще об идее, стоящей за языками данной группы. Несмотря на то что Lisp очень старый (из всех языков высокого уровня старше только Fortran), именно в нем впервые стали доступны многие методы программирования, применяемые сейчас. Далее я буду использовать название Lisp, имея в виду конкретную реализацию — Scheme.

Синтаксис в языке Lisp, хм, слегка спорный. Дело в том, что идея, лежащая в основе синтаксиса, крайне проста и построена на основе так называемых S-выражений. Это префиксная запись, в которой привычное тебе выражение 2 + 3 записывается как (+ 2 3). Это может показаться странным, но на практике дает некоторые дополнительные возможности. Кстати, (+ 2 10 (* 3.14 2)) тоже работает :). Таким образом, вся программа — это набор списков, в которых используется префиксная нотация. В случае языка Lisp сама программа и абстрактное синтаксическое дерево — «если вы понимаете, о чем я» 😉 — по сути, ничем не отличаются. Такая запись делает синтаксический анализ программ на Lisp очень простым.Раз уж мы говорим о языке программирования, то следует сказать о том, как определять функции в этом языке.

Тут нужно сделать небольшое отступление. Существует одна тонкость, значимость которой в современной литературе недооценена. Нужно все-таки разделять функцию в математическом смысле и функцию, как мы ее понимаем в функциональном программировании. Дело в том, что в математике функции являются декларативными объектами, а в программировании они используются для организации процесса вычислений, то есть в каком-то смысле, скорее, представляют собой императивное знание, знание, отвечающее на вопрос «как?». Именно поэтому Абельсон и Сассман в своей книге это очень тщательно разделяют и называют функции в программировании процедурами. В современной литературе по функциональному программированию это не принято. Но я все же настоятельно рекомендую разделять эти два смысла слова «функция» хотя бы у себя в голове.

Самый простой способ определить функцию — это написать следующий код. Начнем с неприлично простого:

(define (sq-roots a b c) (let ((D (- (* b b) (* 4 a c)))) (if (< D 0) (list) (let ((sqrtD (sqrt D))) (let ((x1 (/ (- (- b) sqrtD) (* 2.0 a))) (x2 (/ (+ (- b) sqrtD) (* 2.0 a)))) (list x1 x2))))))

Да, это именно то, что ты подумал, — решение квадратного уравнения на Scheme. Но этого более чем достаточно, чтобы разглядеть все особенности синтаксиса. Здесь sq-roots — это название функции от трех формальных параметров.

На первый взгляд в конструкции let, которая используется для определения локальных переменных, слишком много скобок. Но это не так, просто сначала мы определяем список переменных, а затем выражение, в котором эти переменные используются. Здесь (list) — это пустой список, который мы возвращаем, когда корней нет, а (list x1 x2) — это список из двух значений.

Теперь о выражениях. В нашей функции sq-roots мы использовали конструкцию if. Вот здесь-то и начинается функциональное программирование.

Дело в том, что в отличие от императивных языков, таких как C, в функциональных языках if — это выражение, а не оператор. На практике это означает, что у него не может отсутствовать ветка else. Потому что выражение всегда должно иметь значение.

Нельзя рассказать про синтаксис, не поговорив о синтаксическом сахаре. В языках программирования синтаксическим сахаром называют конструкции, которые не являются необходимыми, а лишь облегчают чтение и переиспользование кода. Для начала приведем классический пример из языка C. Многие знают, что массивы не обязательное средство выражения, так как есть указатели. Да, действительно, массивы реализованы через указатели, и a[i] для языка C — это то же самое, что и *(a + i). Данный пример вообще довольно необычный, с ним связан забавный эффект: так как операция сложения остается коммутативной в случае указателей, то последнее выражение — это то же самое, что и *(i + a), а это может быть получено при удалении синтаксического сахара из выражения i[a]! Операция удаления синтаксического сахара в английском языке называется специальным словом desugaring.

Возвращаясь к языку Scheme, следует привести важный пример синтаксического сахара. Для определения переменных, как и в случае функций, используется ключевое слово (в Lisp и Scheme это называется специальной формой) define. К примеру, (define pi 3.14159) определяет переменную pi. Вообще говоря, точно так же можно и определять функции:

(define square (lambda (x) (* x x)))

это то же самое, что и

(define (square x) (* x x))

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

Если посмотреть на let с точки зрения лямбда-выражения, то легко заметить следующее соответствие:

(let ((x 5) (y 2)) (* x y)) (apply (lambda (x y) (* x y)) (list 5 2))

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

Функциональные языки бывают чистыми и нечистыми. Чистые функциональные языки сравнительно редки, к ним относятся в первую очередь Haskell и Clean. В чистых языках нет побочных эффектов. На практике это означает отсутствие присваивания и ввода-вывода в том виде, к которому мы привыкли. Это создает ряд трудностей, хотя в уже упомянутых языках это решено довольно хитроумно, и на этих языках пишут код с большим количеством ввода-вывода. Языки типа Lisp, OCaml или Scala допускают функции с побочными эффектами, и в этом смысле данные языки зачастую более практичны.

Наша задача — изучить основные приемы функционального программирования на Scheme. Поэтому мы будем писать чисто функциональный код, без использования генератора случайных чисел, ввода-вывода и функции set!, которая позволят менять значения переменных. Обо всем этом можно прочитать в книге SICP. Сейчас остановимся на самом существенном для нас.

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

Пускай у нас есть две функции — succ и prev. Первая возвращает число, на 1 большее, чем аргумент, а вторая — на 1 меньшее. Теперь попробуем определить операцию сложения, причем двумя способами:

(define (add x y) (if (eq? y 0) x (add (succ x) (prev y)))) (define (add-1 x y) (if (eq? y 0) x (succ (add-1 x (prev y)))))

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

(add 3 4) => (add 4 3) => (add 5 2) => (add 6 1) => (add 7 0) => 7

Во втором случае мы будем иметь примерно следующее:

(add-1 3 4) => (succ (add-1 3 3)) => (succ (succ (add-1 3 2))) => (succ (succ (succ (add-1 3 1)))) => (succ (succ (succ (succ (add-1 3 0))))) => (succ (succ (succ (succ 3)))) => (succ (succ (succ 4))) => (succ (succ 5)) => (succ 6) => 7

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

Один из важнейших элементов функционального программирования, наряду с рекурсией, — списки. Они обеспечивают основу для сложных структур данных. Как и в других функциональных языках, списки являются односвязными по принципу голова — хвост. Для создания списка используется функция cons, а для доступа к голове и хвосту списка — функции car и cdr соответственно. Так, список (list 1 2 3) — это не что иное, как (cons 1 (cons 2 (cons 3 '()))). Здесь '() — пустой список. Таким образом, типичная функция обработки списка выглядит так:

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))

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

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

(define (map f lst) (if (null? lst) lst (cons (f (car lst)) (map f (cdr lst)))))

Функция map применяет функцию f к каждому элементу списка. Как бы это странно ни выглядело, но теперь мы можем выразить функцию вычисления длины списка length через sum и map:

(define (length lst) (sum (map (lambda (x) 1) lst)))

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

То есть нужно реализовать функции cons, car и cdr так, чтобы они удовлетворяли следующему соотношению: для любого списка lst верно, что значение (cons (car lst) (cdr lst)) совпадает с lst. Это можно сделать следующим образом:

(define (cons x xs) (lambda (pick) (if (eq? pick 1) x xs))) (define (car f) (f 1)) (define (cdr f) (f 2))

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

Одна приятная особенность языка Lisp делает его необыкновенно удобным для написания программ, которые занимаются преобразованием других программ. Дело в том, что программа состоит из списков, а список — это основная структура данных в языке. Существует способ просто «закавычить» текст программы, чтобы она воспринималась как список атомов.

Атомы — это просто символьные выражения, к примеру ('hello 'world), что то же самое, что и '(hello world), или в полной форме (quote (hello world)). Несмотря на то что в большинстве диалектов Lisp есть строки, иногда можно обходиться quote. Что более важно, с помощью такого подхода можно упростить кодогенерацию и обработку программ.

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

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

Так что я лишь приведу пример кода, который бы показывал суть дела, детали оставлю читателю (который, как я надеюсь, тщательно изучит книгу «Структура и интерпретация компьютерных программ»).

(define (deriv exp var) (cond ((number? exp) 0) ((variable? exp) (if (same-variable? exp var) 1 0)) ((sum? exp) (make-sum (deriv (addend exp) var) (deriv (augend exp) var))) ((product? exp) (make-sum (make-product (multiplier exp) (deriv (multiplicand exp) var)) (make-product (deriv (multiplier exp) var) (multiplicand exp)))) (else (error "unknown expression type - DERIV" exp))))

Здесь функция deriv представляет собой реализацию алгоритма дифференцирования так, как его проходят в школе. Данная функция требует реализации функций number?, variable? и так далее, которые позволяют понять, какую природу имеет тот или иной элемент выражения. Также нужно реализовать дополнительные функции make-product и make-sum. Здесь используется пока неизвестная нам конструкция cond — это аналог оператора switch в таких языках программирования, как C и Java.

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

(define (variable? x) (symbol? x)) (define (same-variable? v1 v2) (and (variable? v1) (variable? v2) (eq? v1 v2))) (define (make-sum a1 a2) (list '+ a1 a2)) (define (make-product m1 m2) (list '* m1 m2)) (define (sum? x) (and (pair? x) (eq? (car x) '+))) (define (addend s) (cadr s)) (define (augend s) (caddr s)) (define (product? x) (and (pair? x) (eq? (car x) '*))) (define (multiplier p) (cadr p)) (define (multiplicand p) (caddr p))

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

Если воспользоваться интерактивным интерпретатором Scheme, то легко убедиться, что полученный код работает правильно, но без упрощения выражений:

(deriv '(+ x 3) 'x) => (+ 1 0) (deriv '(* (* x y) (+ x 3)) 'x) => (+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+ x 3)))

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

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

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

(define (desugar-define def) (let ((fn-args (cadr def)) (body (caddr def))) (let ((name (car fn-args)) (args (cdr fn-args))) (list 'define name (list 'lambda args body)))))

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

(desugar-define '(define (succ x) (+ x 1))) => (define succ (lambda (x) (+ x 1)))

Однако это не работает для обычных определений, таких как (define x 5).Если мы хотим удалить синтаксический сахар в большой программе, содержащей множество различных определений, то мы должны реализовать дополнительную проверку:

(define (sugared? def) (and (eq? (car def) 'define) (list? (cadr def))))

Такую проверку можно встроить прямо в функцию desugar-define, сделав так, чтобы в случае, если определение не нуждается в удалении синтаксического сахара, оно просто бы не менялось (данное тривиальное упражнение остается читателю). После чего можно обернуть всю программу в список и использовать map:

(map desugar-define prog)

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

xakep.ru

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

Функциона́льное программи́рование — раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних (в отличие от функций как подпрограмм в процедурном программировании).

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

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

На практике отличие математической функции от понятия «функции» в императивном программировании заключается в том, что императивные функции могут опираться не только на аргументы, но и на состояние внешних по отношению к функции переменных, а также иметь побочные эффекты и менять состояние внешних переменных. Таким образом, в императивном программировании при вызове одной и той же функции с одинаковыми параметрами, но на разных этапах выполнения алгоритма, можно получить разные данные на выходе из-за влияния на функцию состояния переменных. А в функциональном языке при вызове функции с одними и теми же аргументами мы всегда получим одинаковый результат: выходные данные зависят только от входных. Это позволяет средам выполнения программ на функциональных языках кешировать результаты функций и вызывать их в порядке, не определяемом алгоритмом и распараллеливать их без каких-либо дополнительных действий со стороны программиста (что обеспечивают функции без побочных эффектов — чистые функции[⇨]).

Лямбда-исчисление являются основой для функционального программирования, многие функциональные языки можно рассматривать как «надстройку» над ними[1].

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

Наиболее известными языками функционального программирования являются[2]:

Ещё не полностью функциональные изначальные версии и Лиспа, и APL внесли особый вклад в создание и развитие функционального программирования. Более поздние версии Lisp, такие как Scheme, а также различные варианты APL поддерживали все свойства и концепции функционального языка[5].

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

Видео по теме

История

Лямбда-исчисление стало теоретической базой для описания и вычисления функций. Являясь математической абстракцией, а не языком программирования, оно составило базис почти всех языков функционального программирования на сегодняшний день. Сходное теоретическое понятие, комбинаторная логика, является более абстрактным, нежели λ-исчисления и было создано раньше. Эта логика используется в некоторых эзотерических языках, например в Unlambda. И λ-исчисление, и комбинаторная логика были разработаны для более ясного и точного описания принципов и основ математики[6].

Первым функциональным языком был Лисп, созданный Джоном Маккарти в период его работы в Массачусетском технологическом институте в конце пятидесятых и реализованный, первоначально, для IBM 700/7000 (англ.)русск.[7]. В Лиспе впервые введено множество понятий функционального языка, хотя при этом в языке применяется не только парадигма функционального программирования[8]. Дальнейшим развитием Лиспа стали такие языки как Scheme и Dylan.

Язык обработки информации (Information Processing Language (англ.)русск., IPL) иногда определяется как самый первый машинный функциональный язык[9]. Это язык ассемблерного типа для работы со списком символов. В нём было понятие «генератора», который использовал функцию в качестве аргумента, а также, поскольку это язык ассемблерного уровня, он может позиционироваться как язык, имеющий функции высшего порядка. Однако, в целом IPL акцентирован на использование императивных понятий[10].

Кеннет Е. Айверсон разработал язык APL в начале шестидесятых, документировав его в своей книге A Programming Language (ISBN 978-0-471-43014-8)[11]. APL оказал значительное влияние на язык FP (англ.)русск., созданный Джоном Бэкусом. В начале девяностых Айверсон и Роджер Хуэй (англ.)русск. создали преемника APL — язык программирования J. В середине девяностых Артур Витни (англ.)русск., ранее работавший с Айверсоном, создал язык K, который впоследствии использовался в финансовой индустрии на коммерческой основе.

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

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

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

Концепции

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

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

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

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

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

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

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

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

Рекурсия

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

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

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

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

print(len([2+1, 3*2, 1/0, 5-4]))

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

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

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

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

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

Стили программирования

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

# императивный стиль target = [] # создать пустой список for item in source_list: # для каждого элемента исходного списка trans1 = G(item) # применить функцию G() trans2 = F(trans1) # применить функцию F() target.append(trans2) # добавить преобразованный элемент в список

Функциональная версия выглядит по-другому:

# функциональный стиль # языки ФП часто имеют встроенную функцию compose() compose2 = lambda A, B: lambda x: A(B(x)) target = map(compose2(F, G), source_list)

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

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

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

Особенности

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

Сильные стороны

Повышение надёжности кода

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

Удобство организации модульного тестирования

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

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

Возможности оптимизации при компиляции

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

Возможности параллелизма

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

Недостатки

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

Для преодоления недостатков функциональных программ уже первые языки функционального программирования включали не только чисто функциональные средства, но и механизмы императивного программирования (присваивание, цикл, «неявный PROGN» были уже в Лиспе). Использование таких средств позволяет решить некоторые практические проблемы, но означает отход от идей (и преимуществ) функционального программирования и написание императивных программ на функциональных языках. В чистых функциональных языках эти проблемы решаются другими средствами, например, в языке Haskell ввод-вывод реализован при помощи монад — нетривиальной концепции, позаимствованной из теории категорий.

См. также

Примечания

1. ↑ А. Филд, П. Харрисон Функциональное программирование: Пер. с англ. — М.: Мир, 1993. — 637 с, ил. ISBN 5-03-001870-0. Стр. 120 [Глава 6: Математические основы: λ-исчисление].
2. ↑ Tiobe Programming Community Index
3. ↑ Николас Чейз. Введение в XSLT. IBM developerWorks (12 января 2009). Проверено 25 июня 2013. Архивировано 2 июля 2013 года.
4. ↑ Дмитрий Сошников. «F# – компромисс между академическим миром и реальной жизнью» // Системный администратор. — 2013. — № 1-2 (122-123).
5. ↑ 1 2 Пол Хьюдак (англ.)русск. (September 1989). «Conception, evolution, and application of functional programming languages» (PDF). ACM Computing Surveys 21 (3): 359—411. DOI:10.1145/72551.72554.
6. ↑ Роджер Пенроуз. Глава 2: Лямбда-исчисление Черча // Новый ум короля. О компьютерах, мышлении и законах физики = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. — Едиториал УРСС, 2003. — ISBN 5-354-00005-X. + переиздание ISBN 978-5-382-01266-7; 2011 г.
7. ↑ McCarthy, John (June 1978). «History of Lisp». In ACM SIGPLAN History of Programming Languages Conference: 217–223. DOI:10.1145/800025.808387.
8. ↑ J. Harrison, 1997, Гл. 3. λ-исчисление как язык программирования.
9. ↑ В своих мемуарах Герберт Саймон (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых «часто называют родителями искусственного интеллекта» за написание программы Logic Theorist (англ.)русск. автоматически доказывающей теоремы из Principia Mathematica. Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.
10. ↑ History of Programming Languages: IPL
11. ↑ XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. — Academic Press, 1981. — С. 661-693. — 749 с. — ISBN 0-12-745040-8.
12. ↑ Евгений Кирпичёв. Элементы функциональных языков // Практика функционального программирования. — 2009. — Декабрь (вып. 3). — ISSN 2075-8456.
13. ↑ Скачать PDF: «Техники функционального программирования, В. А. Потапенко» стр. 8 «Функции высших порядков».
14. ↑ GCC, Declaring Attributes of Functions
15. ↑ XL Fortran for AIX, V13.1 > Language Reference, Pure procedures (Fortran 95)
16. ↑ Tail call optimization
17. ↑ Revised5 Report on the Algorithmic Language Scheme, 3.5. Proper tail recursion
18. ↑ Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений — М.: ГИНФО, 2002. — 260 с. Стр. 14 п. 3.1. Ленивые и энергичные вычисления
19. ↑ Ахмечет В. «Функциональное программирование для всех»

Литература

Ссылки

wikipedia.green

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

Функциона́льное программи́рование — раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних (в отличие от функций как подпрограмм в процедурном программировании).

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

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

На практике отличие математической функции от понятия «функции» в императивном программировании заключается в том, что императивные функции могут опираться не только на аргументы, но и на состояние внешних по отношению к функции переменных, а также иметь побочные эффекты и менять состояние внешних переменных. Таким образом, в императивном программировании при вызове одной и той же функции с одинаковыми параметрами, но на разных этапах выполнения алгоритма, можно получить разные данные на выходе из-за влияния на функцию состояния переменных. А в функциональном языке при вызове функции с одними и теми же аргументами мы всегда получим одинаковый результат: выходные данные зависят только от входных. Это позволяет средам выполнения программ на функциональных языках кешировать результаты функций и вызывать их в порядке, не определяемом алгоритмом и распараллеливать их без каких-либо дополнительных действий со стороны программиста (что обеспечивают функции без побочных эффектов — чистые функции[⇨]).

Лямбда-исчисление являются основой для функционального программирования, многие функциональные языки можно рассматривать как «надстройку» над ними[1].

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

Наиболее известными языками функционального программирования являются[2]:

Ещё не полностью функциональные изначальные версии и Лиспа, и APL внесли особый вклад в создание и развитие функционального программирования. Более поздние версии Lisp, такие как Scheme, а также различные варианты APL поддерживали все свойства и концепции функционального языка[5].

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

История

Лямбда-исчисление стало теоретической базой для описания и вычисления функций. Являясь математической абстракцией, а не языком программирования, оно составило базис почти всех языков функционального программирования на сегодняшний день. Сходное теоретическое понятие, комбинаторная логика, является более абстрактным, нежели λ-исчисления и было создано раньше. Эта логика используется в некоторых эзотерических языках, например в Unlambda. И λ-исчисление, и комбинаторная логика были разработаны для более ясного и точного описания принципов и основ математики[6].

Первым функциональным языком был Лисп, созданный Джоном Маккарти в период его работы в Массачусетском технологическом институте в конце пятидесятых и реализованный, первоначально, для IBM 700/7000 (англ.)русск.[7]. В Лиспе впервые введено множество понятий функционального языка, хотя при этом в языке применяется не только парадигма функционального программирования[8]. Дальнейшим развитием Лиспа стали такие языки как Scheme и Dylan.

Язык обработки информации (Information Processing Language (англ.)русск., IPL) иногда определяется как самый первый машинный функциональный язык[9]. Это язык ассемблерного типа для работы со списком символов. В нём было понятие «генератора», который использовал функцию в качестве аргумента, а также, поскольку это язык ассемблерного уровня, он может позиционироваться как язык, имеющий функции высшего порядка. Однако, в целом IPL акцентирован на использование императивных понятий[10].

Кеннет Е. Айверсон разработал язык APL в начале шестидесятых, документировав его в своей книге A Programming Language (ISBN 978-0-471-43014-8)[11]. APL оказал значительное влияние на язык FP (англ.)русск., созданный Джоном Бэкусом. В начале девяностых Айверсон и Роджер Хуэй (англ.)русск. создали преемника APL — язык программирования J. В середине девяностых Артур Витни (англ.)русск., ранее работавший с Айверсоном, создал язык K, который впоследствии использовался в финансовой индустрии на коммерческой основе.

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

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

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

Концепции

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

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

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

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

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

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

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

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

Рекурсия

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

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

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

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

print(len([2+1, 3*2, 1/0, 5-4]))

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

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

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

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

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

Стили программирования

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

# императивный стиль target = [] # создать пустой список for item in source_list: # для каждого элемента исходного списка trans1 = G(item) # применить функцию G() trans2 = F(trans1) # применить функцию F() target.append(trans2) # добавить преобразованный элемент в список

Функциональная версия выглядит по-другому:

# функциональный стиль # языки ФП часто имеют встроенную функцию compose() compose2 = lambda A, B: lambda x: A(B(x)) target = map(compose2(F, G), source_list)

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

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

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

Особенности

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

Сильные стороны

Повышение надёжности кода

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

Удобство организации модульного тестирования

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

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

Возможности оптимизации при компиляции

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

Возможности параллелизма

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

Недостатки

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

Для преодоления недостатков функциональных программ уже первые языки функционального программирования включали не только чисто функциональные средства, но и механизмы императивного программирования (присваивание, цикл, «неявный PROGN» были уже в Лиспе). Использование таких средств позволяет решить некоторые практические проблемы, но означает отход от идей (и преимуществ) функционального программирования и написание императивных программ на функциональных языках. В чистых функциональных языках эти проблемы решаются другими средствами, например, в языке Haskell ввод-вывод реализован при помощи монад — нетривиальной концепции, позаимствованной из теории категорий.

См. также

Примечания

1. ↑ А. Филд, П. Харрисон Функциональное программирование: Пер. с англ. — М.: Мир, 1993. — 637 с, ил. ISBN 5-03-001870-0. Стр. 120 [Глава 6: Математические основы: λ-исчисление].
2. ↑ Tiobe Programming Community Index
3. ↑ Николас Чейз. Введение в XSLT. IBM developerWorks (12 января 2009). Проверено 25 июня 2013. Архивировано 2 июля 2013 года.
4. ↑ Дмитрий Сошников. «F# – компромисс между академическим миром и реальной жизнью» // Системный администратор. — 2013. — № 1-2 (122-123).
5. ↑ 1 2 Пол Хьюдак (англ.)русск. (September 1989). «Conception, evolution, and application of functional programming languages» (PDF). ACM Computing Surveys 21 (3): 359—411. DOI:10.1145/72551.72554.
6. ↑ Роджер Пенроуз. Глава 2: Лямбда-исчисление Черча // Новый ум короля. О компьютерах, мышлении и законах физики = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. — Едиториал УРСС, 2003. — ISBN 5-354-00005-X. + переиздание ISBN 978-5-382-01266-7; 2011 г.
7. ↑ McCarthy, John (June 1978). «History of Lisp». In ACM SIGPLAN History of Programming Languages Conference: 217–223. DOI:10.1145/800025.808387.
8. ↑ J. Harrison, 1997, Гл. 3. λ-исчисление как язык программирования.
9. ↑ В своих мемуарах Герберт Саймон (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых «часто называют родителями искусственного интеллекта» за написание программы Logic Theorist (англ.)русск. автоматически доказывающей теоремы из Principia Mathematica. Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.
10. ↑ History of Programming Languages: IPL
11. ↑ XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. — Academic Press, 1981. — С. 661-693. — 749 с. — ISBN 0-12-745040-8.
12. ↑ Евгений Кирпичёв. Элементы функциональных языков // Практика функционального программирования. — 2009. — Декабрь (вып. 3). — ISSN 2075-8456.
13. ↑ Скачать PDF: «Техники функционального программирования, В. А. Потапенко» стр. 8 «Функции высших порядков».
14. ↑ GCC, Declaring Attributes of Functions
15. ↑ XL Fortran for AIX, V13.1 > Language Reference, Pure procedures (Fortran 95)
16. ↑ Tail call optimization
17. ↑ Revised5 Report on the Algorithmic Language Scheme, 3.5. Proper tail recursion
18. ↑ Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений — М.: ГИНФО, 2002. — 260 с. Стр. 14 п. 3.1. Ленивые и энергичные вычисления
19. ↑ Ахмечет В. «Функциональное программирование для всех»

Литература

Ссылки

wikiredia.ru

Функциональное программирование - Gpedia, Your Encyclopedia

Функциона́льное программи́рование — раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних (в отличие от функций как подпрограмм в процедурном программировании).

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

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

На практике отличие математической функции от понятия «функции» в императивном программировании заключается в том, что императивные функции могут опираться не только на аргументы, но и на состояние внешних по отношению к функции переменных, а также иметь побочные эффекты и менять состояние внешних переменных. Таким образом, в императивном программировании при вызове одной и той же функции с одинаковыми параметрами, но на разных этапах выполнения алгоритма, можно получить разные данные на выходе из-за влияния на функцию состояния переменных. А в функциональном языке при вызове функции с одними и теми же аргументами мы всегда получим одинаковый результат: выходные данные зависят только от входных. Это позволяет средам выполнения программ на функциональных языках кешировать результаты функций и вызывать их в порядке, не определяемом алгоритмом и распараллеливать их без каких-либо дополнительных действий со стороны программиста (что обеспечивают функции без побочных эффектов — чистые функции[⇨]).

Лямбда-исчисление являются основой для функционального программирования, многие функциональные языки можно рассматривать как «надстройку» над ними[1].

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

Наиболее известными языками функционального программирования являются[2]:

Ещё не полностью функциональные изначальные версии и Лиспа, и APL внесли особый вклад в создание и развитие функционального программирования. Более поздние версии Lisp, такие как Scheme, а также различные варианты APL поддерживали все свойства и концепции функционального языка[5].

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

История

Лямбда-исчисление стало теоретической базой для описания и вычисления функций. Являясь математической абстракцией, а не языком программирования, оно составило базис почти всех языков функционального программирования на сегодняшний день. Сходное теоретическое понятие, комбинаторная логика, является более абстрактным, нежели λ-исчисления и было создано раньше. Эта логика используется в некоторых эзотерических языках, например в Unlambda. И λ-исчисление, и комбинаторная логика были разработаны для более ясного и точного описания принципов и основ математики[6].

Первым функциональным языком был Лисп, созданный Джоном Маккарти в период его работы в Массачусетском технологическом институте в конце пятидесятых и реализованный, первоначально, для IBM 700/7000 (англ.)русск.[7]. В Лиспе впервые введено множество понятий функционального языка, хотя при этом в языке применяется не только парадигма функционального программирования[8]. Дальнейшим развитием Лиспа стали такие языки как Scheme и Dylan.

Язык обработки информации (Information Processing Language (англ.)русск., IPL) иногда определяется как самый первый машинный функциональный язык[9]. Это язык ассемблерного типа для работы со списком символов. В нём было понятие «генератора», который использовал функцию в качестве аргумента, а также, поскольку это язык ассемблерного уровня, он может позиционироваться как язык, имеющий функции высшего порядка. Однако, в целом IPL акцентирован на использование императивных понятий[10].

Кеннет Е. Айверсон разработал язык APL в начале шестидесятых, документировав его в своей книге A Programming Language (ISBN 978-0-471-43014-8)[11]. APL оказал значительное влияние на язык FP (англ.)русск., созданный Джоном Бэкусом. В начале девяностых Айверсон и Роджер Хуэй (англ.)русск. создали преемника APL — язык программирования J. В середине девяностых Артур Витни (англ.)русск., ранее работавший с Айверсоном, создал язык K, который впоследствии использовался в финансовой индустрии на коммерческой основе.

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

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

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

Концепции

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

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

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

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

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

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

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

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

Рекурсия

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

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

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

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

print(len([2+1, 3*2, 1/0, 5-4]))

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

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

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

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

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

Стили программирования

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

# императивный стиль target = [] # создать пустой список for item in source_list: # для каждого элемента исходного списка trans1 = G(item) # применить функцию G() trans2 = F(trans1) # применить функцию F() target.append(trans2) # добавить преобразованный элемент в список

Функциональная версия выглядит по-другому:

# функциональный стиль # языки ФП часто имеют встроенную функцию compose() compose2 = lambda A, B: lambda x: A(B(x)) target = map(compose2(F, G), source_list)

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

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

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

Особенности

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

Сильные стороны

Повышение надёжности кода

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

Удобство организации модульного тестирования

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

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

Возможности оптимизации при компиляции

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

Возможности параллелизма

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

Недостатки

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

Для преодоления недостатков функциональных программ уже первые языки функционального программирования включали не только чисто функциональные средства, но и механизмы императивного программирования (присваивание, цикл, «неявный PROGN» были уже в Лиспе). Использование таких средств позволяет решить некоторые практические проблемы, но означает отход от идей (и преимуществ) функционального программирования и написание императивных программ на функциональных языках. В чистых функциональных языках эти проблемы решаются другими средствами, например, в языке Haskell ввод-вывод реализован при помощи монад — нетривиальной концепции, позаимствованной из теории категорий.

См. также

Примечания

1. ↑ А. Филд, П. Харрисон Функциональное программирование: Пер. с англ. — М.: Мир, 1993. — 637 с, ил. ISBN 5-03-001870-0. Стр. 120 [Глава 6: Математические основы: λ-исчисление].
2. ↑ Tiobe Programming Community Index
3. ↑ Николас Чейз. Введение в XSLT. IBM developerWorks (12 января 2009). Проверено 25 июня 2013. Архивировано 2 июля 2013 года.
4. ↑ Дмитрий Сошников. «F# – компромисс между академическим миром и реальной жизнью» // Системный администратор. — 2013. — № 1-2 (122-123).
5. ↑ 1 2 Пол Хьюдак (англ.)русск. (September 1989). «Conception, evolution, and application of functional programming languages» (PDF). ACM Computing Surveys 21 (3): 359—411. DOI:10.1145/72551.72554.
6. ↑ Роджер Пенроуз. Глава 2: Лямбда-исчисление Черча // Новый ум короля. О компьютерах, мышлении и законах физики = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. — Едиториал УРСС, 2003. — ISBN 5-354-00005-X. + переиздание ISBN 978-5-382-01266-7; 2011 г.
7. ↑ McCarthy, John (June 1978). «History of Lisp». In ACM SIGPLAN History of Programming Languages Conference: 217–223. DOI:10.1145/800025.808387.
8. ↑ J. Harrison, 1997, Гл. 3. λ-исчисление как язык программирования.
9. ↑ В своих мемуарах Герберт Саймон (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых «часто называют родителями искусственного интеллекта» за написание программы Logic Theorist (англ.)русск. автоматически доказывающей теоремы из Principia Mathematica. Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.
10. ↑ History of Programming Languages: IPL
11. ↑ XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. — Academic Press, 1981. — С. 661-693. — 749 с. — ISBN 0-12-745040-8.
12. ↑ Евгений Кирпичёв. Элементы функциональных языков // Практика функционального программирования. — 2009. — Декабрь (вып. 3). — ISSN 2075-8456.
13. ↑ Скачать PDF: «Техники функционального программирования, В. А. Потапенко» стр. 8 «Функции высших порядков».
14. ↑ GCC, Declaring Attributes of Functions
15. ↑ XL Fortran for AIX, V13.1 > Language Reference, Pure procedures (Fortran 95)
16. ↑ Tail call optimization
17. ↑ Revised5 Report on the Algorithmic Language Scheme, 3.5. Proper tail recursion
18. ↑ Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений — М.: ГИНФО, 2002. — 260 с. Стр. 14 п. 3.1. Ленивые и энергичные вычисления
19. ↑ Ахмечет В. «Функциональное программирование для всех»

Литература

• Городняя Л. В. Основы функционального программирования. Курс лекций — М.: Интернет-университет информационных технологий, 2004. С. 280. ISBN 5-9556-0008-6
• Душкин Р. В. Функциональное программирование на языке Haskell. — М.: ДМК Пресс, 2006. С. 608. ISBN 5-94074-335-8
• Филд А., Харрисон П. Функциональное программирование = Functional Programming. — М.: Мир, 1993. — 637 с. — ISBN 5-03-001870-0.
• Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений — М.: ГИНФО, 2002. — 260 с.
• John Harrison. Функциональное программирован&

www.gpedia.com

---

• 
  Трекер что такое
• 
  Проблема при возврате пк в исходное состояние windows 10 как исправить
• 
  Windows server 2018 отличие от server 2018 r2
• 
  Основные устройства пк
• 
  Википедия аида 64
• 
  Восстановить удаленные данные с компьютера
• 
  Это 360 total security
• 
  Убрать вирус
• 
  Очистка памяти компьютера windows 7
• 
  Svchost файл
• 
  Кнопка пуск где находится