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

Языки программирования, о которых не каждый знает

Я начал программировать еще в детстве, и годам к двадцати пяти мне казалось, что я все знаю и понимаю. Объектно ориентированное программирование стало частью моего мозга, все мыслимые книги о промышленном программировании были прочитаны. Но у меня оставалось такое ощущение, будто я что-то упустил, что-то очень тонкое и необыкновенно важное. Дело в том, что, как и многих в девяностые годы, в школе меня учили программировать на 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))

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

Функциональные языки бывают чистыми и нечистыми . Чистые функциональные языки сравнительно редки, к ним относятся в первую очередь 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 возвращает другую функцию, которая имеет один параметр и в зависимости от этого возвращает либо первый, либо второй аргументы. Легко проверить, что необходимое соотношение выполняется для этих функций.

Использование quote и метапрограммирование

Одна приятная особенность языка 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.

• Перевод

- ООП не сможет больше спасать нас от «Облачных монстров».

Примечание переводчика: Есть два понятия - параллельность (выполнение одновременно, независимо) и конкурентность (выполнение по шагам, поочерёдно, но одновременно несколько задач) и как всегда, мне пришлось поломать голову подобрая правильные термины.

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

Возможно вы уже слышали такое выражение, вроде: “Clojure”, “Scala”, “Erlang” или даже “Java теперь имеет лямбды”. И вы имеете хоть и отдалённое представление о «Функциональном программировании». Если вы участник какого-либа программисткого сообщества, тогда эта тема могла уже вами обсуждаться.

Если вы поищите в Google по словосочетанию «Функциональное программирование», вы не увидите что-то нового. Второй язык из созданных ранее уже охватывает эту тему, он был создан в 50-ых и называется Lisp. Тогда, какого чёрта, эта тема стала популярна только сейчас? Всего то 60 лет спустя?

В начале, компьютеры были очень медленными

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

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

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

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

• краткость и простота;
• строгая типизация;
• модульность;
• функции - объекты вычисления;
• отложенные (ленивые) вычисления.

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

Miranda (какое семейство?)

Ссылки

• http://roman-dushkin.narod.ru/fp.html - Курс лекций по функциональному программированию , читаемый в МИФИ с 2001 года.

Wikimedia Foundation . 2010 .

Смотреть что такое "Функциональный язык программирования" в других словарях:

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

функциональный язык - Язык программирования, в котором действия над данными выражаются в виде обращений к функциональным процедурам. [ГОСТ 19781 90] Тематики обеспеч. систем обраб. информ. программное EN functional language … Справочник технического переводчика

Ruby Семантика: мультипарадигмальный Тип исполнения: интерпретатор Появился в: 1995 г. Автор(ы): Юкихиро Мацумото Последняя версия: 1.9.1 … Википедия

Функциональный язык - 37. Функциональный язык Functional language Язык программирования, в котором действия над данными выражаются в виде обращений к функциональным процедурам Источник: ГОСТ 19781 90: Обеспечение систем обработки информации программное. Термины и… … Словарь-справочник терминов нормативно-технической документации

Erlang Файл:Erlang logo.png Семантика: мультипарадигмальный: конкурентное, функциональное программирование Появился в: 1987 г. Автор(ы): Типизация данных: строгая, динамическая Основные реализации: E … Википедия

Scheme Семантика: функциональный Тип исполнения: интерпретатор или компилятор Появился в: 1970 г. Автор(ы): Гай Стил и Джеральд Сассмен Типизация данных … Википедия

У этого термина существуют и другие значения, см. Миранда. Miranda функциональный язык программирования, созданный в 1985 году Дэвидом Тёрнером в качестве стандартного функционального языка. Имеет строгую полиморфную систему типов,… … Википедия

Hope функциональный язык программирования, разработанный в начале 1980 х годов; является предшественником языков Miranda и Haskell. В журнале Byte за август 1985 впервые опубликовано руководство по языку Hope. Пример программы вычисления… … Википедия

У этого термина существуют и другие значения, см. SASL. SASL полностью функциональный язык программирования, разработанный Дэвидом Тёрнером в Сент Эндрюсском университете в 1972 году, на базе аппликативного подмножества ISWIM. В 1976 году… … Википедия

У этого термина существуют и другие значения, см. Scala. Scala Класс языка: Мультипарадигмальный: функ … Википедия

Книги

• Программирование в Clojure. Практика применения Lisp в мире Java , Эмерик Ч., Карпер Б., Гранд К.. Почему многие выбирают Clojure? Это - функциональный язык программирования, не только позволяющий пользоваться Java-библиотеками, службами и другими ресурсами JVM, но и соперничающий с…

Если вы такой же разработчик, как и я, то наверняка сперва изучали парадигму ООП. Первым вашим яыком были Java или C++ - или, если вам повезло, Ruby, Python или C# - поэтому вы наверняка знаете, что такое классы, объекты, экземпляры и т.д. В чём вы точно не особо разбираетесь, так это в основах той странной парадигмы, называющейся функциональным программированием, которая существенно отличается не только от ООП, но и от процедурного, прототипно-ориентированного и других видов программирования.

Функциональное программирование становится популярным - и на то есть причины. Сама парадигма не нова: Haskell , пожалуй, является самым функциональным языком, а возник он в 90-ых. Такие языки, как Erlang, Scala, Clojure также попадают под определение функциональных. Одним из основных преимуществ функционального программирования является возможность написания программ, работающих конкурентно (если вы уже забыли, что это - освежите память прочтением ), причём без ошибок - то есть взаимные блокировки и потокобезопасность вас не побеспокоят.

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

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

1. Все функции - чистые

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

1. Функция, вызываемая от одних и тех же аргументов, всегда возвращает одинаковое значение.
2. Во время выполнения функции не возникают побочные эффекты .

Первое правило понятно - если я вызываю функцию sum(2, 3) , то ожидаю, что результат всегда будет равен 5. Как только вы вызываете функцию rand() , или обращаетесь к переменной, не определённой в функции, чистота функции нарушается, а это в функциональном программировании недопустимо.

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

2. Все функции - первого класса и высшего порядка

Эта концепция - не особенность ФП (она используется в Javascript, PHP и других языках) - но его обязательное требование. На самом деле, на Википедии есть целая статья, посвящённая функциям первого класса . Для того, чтобы функция была первоклассной, у неё должна быть возможность быть объявленной в виде переменной. Это позволяет управлять функцией как обычным типом данных и в то же время исполнять её.

3. Переменные неизменяемы

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

4. Относительная прозрачность функций

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

Пусть у нас есть Java-функция, которая складывает 3 и 5:

Public int addNumbers(){ return 3 + 5; } addNumbers() // 8 8 // 8

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

Public void printText(){ System.out.println("Hello World"); } printText() // Returns nothing, but prints "Hello World"

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

5. Функциональное программирование основано на лямбда-исчислении

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

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

Как я уже говорил, лямбда-исчисление на этом не заканчивается - но мы рассмотрели лишь ключевые аспекты, связанные с ФП. Теперь, в разговоре о функциональном программировании вы сможете блеснуть словечком «лямбда-исчисление», и все подумают, что вы шарите 🙂

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

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

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

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

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

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

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

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

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

• функции - объекты вычисления;

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

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

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

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

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

Gofel

Harlequin"s MLWorks

Классификация функциональных языков

В качестве примера чистого функционального языка можно привести Haskell . Однако большинство функциональных языков являются гибридными и содержат свойства как функциональных, так и императивных языков. Яркие примеры - языки Scala и Nemerle. В них органично сочетаются характеристики как объектно-ориентированных языков, так и функциональных. Реализована хвостовая рекурсия и её оптимизация, функция является полноправным объектом, то есть может быть сохранена в переменной, передана в качестве аргумента в другую функцию или возвращена из функции.

Также функциональные языки делят на строгие и нестрогие . К нестрогим языкам относят те, которые поддерживают отложенные вычисления (F#), то есть аргументы функции вычисляются только тогда, когда они действительно понадобятся при вычислении функции. Ярким примером нестрогого языка является Haskell. В качестве примера строгого языка можно привести Standard ML .

Некоторые функциональные языки реализованы поверх платформообразующих виртуальных машин (JVM, .NET), то есть приложения на этих языках могут работать в среде времени исполнения (JRE, CLR) и использовать встроенные классы. К ним относятся Scala, Clojure (JVM), F#, Nemerle, SML.NET (.NET).

Ссылки

• http://fprog.ru/ - Журнал «Практика функционального программирования»
• http://www.intuit.ru/department/pl/funcpl/1/ - Основы функционального программирования. Л. В. Городняя
• http://roman-dushkin.narod.ru/fp.html - Курс лекций по функциональному программированию , читаемый в МИФИ с 2001 года;
• http://alexott.net/ru/fp/books/ - Обзор литературы о функциональном программировании . Рассматриваются книги как на русском, так и на английском языке.

Wikimedia Foundation . 2010 .

Смотреть что такое "Язык функционального программирования" в других словарях:

язык прграммирования Лисп - Язык функционального программирования. Тематики информационные технологии в целом EN Lisp … Справочник технического переводчика

Универсальный язык программирования высокого уровня. Язык Лисп: относится к декларативным языкам функционального типа; предназначен для обработки символьных данных, представленных в виде списков. Основой языка являются функции и рекурсивные… … Финансовый словарь

У этого термина существуют и другие значения, см. Alice. Alice Семантика: функциональный Тип исполнения: компиляция в байткод для виртуальной машины Появился в: 2002 … Википедия

У этого термина существуют и другие значения, см. Scala. Scala Класс языка: Мультипарадигмальный: функ … Википедия

Oz Семантика: функциональный, процедурный, декларативный, объектно ориентированный, вычисления с ограничениями, Н модели, параллельные вычисления Тип исполнения: компилируемый Появился в: 1991 Автор(ы): Gert Smolka his students Релиз … Википедия

AWL (Alternative Web Language) Класс языка: мультипарадигмальный: функциональный, процедурный, объектно ориентированный Тип исполнения: интерпретируемый Появился в: 2005 г. Типизация данных: динамическая … Википедия

У этого термина существуют и другие значения, см. Леда (значения). Леда (Leda) мультипарадигмальный язык программирования, спроектированный Тимоти Баддом. Язык Leda исходно создавался с целью совмещения императивного программирования, объектно… … Википедия

Erlang Файл:Erlang logo.png Семантика: мультипарадигмальный: конкурентное, функциональное программирование Появился в: 1987 г. Автор(ы): Типизация данных: строгая, динамическая Основные реализации: E … Википедия

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

Python был задуман в 1980 х годах, а его создание началось в декабре 1989 года Гвидо ван Россумом в составе центра математики и информатики в Нидерландах. Язык Python был задуман как потомок языка программирования ABC, способный к обработке… … Википедия