Главная › Настройки › Основные принципы программирования: функциональное программирование. Элементы функционального программирования

Основные принципы программирования: функциональное программирование. Элементы функционального программирования

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

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

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

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

В первом случае основные принципы понятны: вы оперируете математической логикой для вывода новых фактов и состояний из уже известных. Ярким примером такого языка является Prolog.

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

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

Что это

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

Функциональное программирование, несмотря на кажущуюся сложность, несёт в себе ряд преимуществ:

Код становится короче;
Понятнее;
Включает в себя признаки хороших императивных языков: модульность, типизация, чистота кода.

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

Конкретнее

Логично, что по функциональному программированию, существующему уже почти 50 лет, написано множество книг и статей. Поэтому какой смысл представлять собственную версию «ФП для чайников», если всё уже в прекрасном и удобочитаемом виде давно есть в сети? Поэтому просто поделимся ссылками:

, имеющая исторический экскурс, яркие образы, но главное хорошие примеры. Имеется перевод .
Книга , которую необходимо прочитать каждому функциональщику, если можно так выразиться. Тоже есть на русском .
Онлайн-курс , который можно прослушать на английском языке. Будем надеяться, что-то похожее скоро появится и у нас на GeekBrains.
Забавное и познавательное слад-шоу на тему функционального программирования.
Прекрасная книга про Haskell, написанная доступным языком (русским), для тех, кто созрел для полноценного изучения первого функционального языка. Справочник прилагается.
Для тех, кто предпочитает начать изучение не с простого, а с хронологического начала – перевод книги Кристиана Кеннека «Les Langages Lisp». Она же «Lisp in Small Pieces».

Куда с этими знаниями идти

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функциональный подход породил целое семейство языков, родоначальником которых, как уже отмечалось, стал язык программирования LISP. Позднее, в 70-х годах, был разработан первоначальный вариант языка ML, который впоследствии развился, в частности, в SML, а также ряд других языков. Из них, пожалуй, самым "молодым" является созданный уже совсем недавно, в 90-х годах, язык Haskell.

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

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

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

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

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

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

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

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

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

таких, что если

(a,b 1) f и (a,b 2) f,

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

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

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

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

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

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

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

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

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

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

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

Семейство языков функционального программирования довольно многочисленно. Об этом свидетельствует не столько значительный список языков, сколько тот факт, что многие языки дали начало целым направлениям в программировании. Напомним, что LISP дал начало целому семейству языков: Scheme, InterLisp, COMMON Lisp и др.

Не стал исключением и язык программирования SML, который был создан в форме языка ML Р. Милнером (Robin Milner) в MIT (Massachusetts Institute of Technology) и первоначально предназначен для логических выводов, в частности, доказательства теорем. Язык отличается строгой типизацией, в нем отсутствует параметрический полиморфизм.

Развитием "классического" ML стали сразу три современных языка с практически одинаковыми возможностями (параметрический полиморфизм, сопоставление с образцом, "ленивые" вычисления). Это язык SML, разработанный в Великобритании и США, CaML, созданный группой французских ученых института INRIA, SML/NJ – диалект SML из New Jersey, а также российская разработка – mosml ("московский" диалект ML).

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

1. простота тестирования и верификации программного кода на основе возможности построения строгого математического доказательства корректности программ;

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

3. безопасная типизация: недопустимые операции с данными исключены;

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

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

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

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

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

2. интеграция различных подходов к программированию на основе межъязыковой инфраструктуры Common Language Infrastructure, или CLI (в частности, возможно использование C# для обеспечения преимуществ объектно-ориентированного подхода и SML – функционального, как в настоящем курсе);

3. общая унифицированная система типизации Common Type System, CTS (единообразное и безопасное управление типами данных в программе);

4. многоступенчатая, гибкая система обеспечения безопасности программного кода (в частности, на основе механизма сборок).

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

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

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

Следующим критерием, по которому можно провести классификацию функциональных языков программирования, может стать наличие императивных механизмов. При этом принято называть функциональные языки программирования, лишенные императивных механизмов, «чистыми», а имеющие их – «нечистыми». В обзоре функциональных языков программирования, приведенном ниже, языки программирования будут называться «практическими» и «академическими». Под «практическими» языками понимаются языки, имеющие коммерческое приложение (на них разрабатывались реальные приложения или были коммерческие системы программирования). Академические языки программирования имеют популярность в исследовательских кругах и в области компьютерного образования, но коммерческих приложений, написанных на таких языках, практически нет. Они остаются всего лишь инструментом при проведении теоретических исследований в области информатики и широко используются в образовательном процессе.

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

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

Scheme. Диалект Лиспа, предназначенный для научных исследований в области компьютерной науки и обучения функциональному программированию. Благодаря отсутствию императивных включений язык получился намного меньше, чем Common Lisp. Восходит к языку, разработанному Дж. Маккарти в 1962 г. Академический, безтиповый, энергичный, чистый.

Refal. Семейство языков, разработанных В. Ф. Турчиным. Старейший член этого семейства впервые реализован в 1968 году в России. Широко используется и поныне в академических кругах. Содержит элементы логического программирования (сопоставление с образцом). Поэтому язык Refal предлагается в данном учебном пособии в качестве языка для самостоятельного изучения.

Miranda. Строго типизированный, поддерживает типы данных пользователя и полиморфизм. Разработан Тернером на основе более ранних языков SALS и KRC. Имеет ленивую семантику. Без императивных включений.

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

Clean. Диалект Haskell, приспособленный к нуждам практического программирования. Как и Haskell, является ленивым чисто функциональным языком, содержит классы типов. Но Clean также содержит интересные особенности, которые не имеют эквивалента в Haskell. Например, императивные возможности в Clean основаны на уникальных типах, идея которых заимствована из линейной логики (linear logic). Clean содержит механизмы, которые позволяют значительно улучшить эффективность программ. Сред этих механизмов явное подавление отложенных вычислений. Реализация Clean является коммерческим продуктом, но свободная версия доступна для исследовательских и образовательных целей.

ML(Meta Language). Разработан группой программистов во главе с Робертом Милиером в середине 70-х гг. в Эдинбурге (Edinburgh Logic for Computable Functions). Идея языка состояла в создании механизма для построения формальных доказательств в системе логики для вычислимых функций. В 1983 язык был пересмотрен дополнен такими концепциями, как модули. Стал называться стандартный ML. ML – это сильно типизированный язык со статическим контролем типов и аппликативным выполнением программ. Он завоевал большую популярность в исследовательских кругах и в области компьютерного образования.

String reverse(String arg) { if(arg.length == 0) { return arg; } else { return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1); } }
Эта функция довольно медленная, потому что она повторно вызывает сама себя . Здесь возможна утечка памяти, так как множество раз создаются временные объекты. Но это функциональный стиль. Вам может показать странным, как люди могут так программировать. Ну, я как раз собирался вам рассказать.

Преимущества функционального программирования

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

Unit тестирование

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

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

Отладка

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

Как только вы воспроизведёте ошибку, найти её источник - тривиальная задача. Это даже приятно. Как только вы остановите выполнение программы, перед вами будет весь стек вызовов. Вы можете просмотреть аргументы вызова каждой функции, прямо как в императивном языке. С тем отличием, что в императивной программе этого не достаточно, ведь функции зависят от значений полей, глобальных переменных и состояний других классов. Функция в ФП зависит только от своих аргументов, и эта информация оказывается прямо у вас перед глазами! Даже больше, в императивной программе проверки возвращаемого значения не достаточно для того, чтобы сказать, правильно ли ведёт себя кусок кода. Вам придётся выследить десятки объектов за пределами функции, чтобы удостовериться, что всё работает правильно. В функциональном программировании всё, что нужно сделать - это взглянуть на возвращаемое значение!

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

Многопоточность

Функциональная программа сразу готова к распараллеливанию без каких-либо изменений. Вам не придётся задумываться о deadlock-ах или состояниях гонки (race conditions) потому что вам не нужны блокировки! Ни один кусочек данных в функциональной программе не меняется дважды одним и тем же потоком или разными. Это означает, что вы можете легко добавить потоков к вашей программе даже не задумываясь при этом о проблемах, присущих императивным языкам.

Если дела обстоят подобным образом, то почему так редко функциональные языки программирования используются в многопоточных приложениях? На самом деле чаще, чем вы думаете. Компания Ericsson разработала функциональный язык под названием Erlang для использования на отказоустойчивых и масштабируемых телекоммуникационных коммутаторах. Многие отметили преимущества Erlang-а и стали его использовать . Мы говорим о телекоммуникациях и системах контроля трафика, которые далеко не так просто масштабируются, как типичные системы, разработанные на Wall Street. Вообще-то, системы написанные на Erlang, не такие масштабируемые и надёжные, как Java системы. Erlang системы просто сверхнадёжные.

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

Компилятор функционального языка может проанализировать код, классифицировать функции, которые создают строки s1 и s2 , как функции потребляющие много времени, и запустить их параллельно. Это невозможно сделать в императивном языке, потому что каждая функция может изменять внешнее состояние и код, идущий непосредственно после вызова, может зависеть от неё. В ФП автоматический анализ функций и поиск подходящих кандидатов для распараллеливания - это тривиальнейшая задача, как автоматический inline ! В этом смысле функциональный стиль программирования соответствует требованиям завтрашнего дня. Разработчики железа уже не могут заставить CPU работать быстрее. Вместо этого они наращивают количество ядер и заявляют о четырёхкратном увеличении скорости многопоточных вычислений. Конечно они очень вовремя забывают сказать, что ваш новый процессор покажет прирост только в программах, разработанных с учётом распараллеливания. Среди императивного ПО таких очень мало. Зато 100% функциональных программ готовы к многопоточности из коробки.

Развёртывание по горячему

В старые времена для установки обновлений Windows приходилось перезагружать компьютер. Много раз. После установки новой версии медиа проигрывателя. В Windows XP произошли значительные изменения, но ситуация всё ещё далека от идеальной (сегодня я запустил Windows Update на работе и теперь надоедливое напоминание не оставит меня в покое, пока не перезагружусь). В Unix системах модель обновления была получше. Для установки обновлений приходилось останавливать некоторые компоненты, но не всю ОС. Хотя ситуация выглядит лучше, но для большого класса серверных приложений это всё ещё не приемлемо. Телекоммуникационные системы должны быть включены 100% времени, ведь если из-за обновления человек не сможет вызвать скорую, то жизни могут быть потеряны. Фирмы с Wall Streets тоже не желают останавливать сервера на выходных, чтобы установить обновления.

В идеале нужно обновить все нужные участки кода не останавливая систему в принципе. В императивном мире это невозможно [пер. в Smalltalk-е очень даже возможно]. Представьте себе выгрузку Java класса на лету и перезагрузка новой версии. Если бы мы так сделали, то все экземпляры класса стали бы нерабочими, потому что потерялось бы состояние, которое они хранили. Нам пришлось бы писать хитрый код, для контроля версий. Пришлось бы серриализовать все созданные экземпляры класса, потом уничтожить их, создать экземпляры нового класса, попытаться загрузить серриализованные данные в надежде, что миграция пройдёт нормально и новые экземпляры будут валидными. И кроме того, миграционный код необходимо писать каждый раз вручную. И ещё миграционный код должен сохранять ссылки между объектами. В теории ещё куда ни шло, но на практике это никогда не заработает.

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

Доказательные вычисления и оптимизация (Machine Assisted Proofs and Optimizations)

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

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

Функции высшего порядка

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

В ФП функция - это не тоже самое, что функция в Java или C. Это надмножество - они могут тоже самое, что Java функции и даже больше. Пусть у нас есть функция на C:

Int add(int i, int j) { return i + j; }
В ФП это не тоже самое, что обычная C функция. Давайте расширим наш Java компилятор, чтобы он поддерживал такую запись. Компилятор должен превратить объявление функции в следующий Java код (не забывайте, что везде присутствует неявный final):

Class add_function_t { int add(int i, int j) { return i + j; } } add_function_t add = new add_function_t();
Символ add не совсем функция. Это маленький класс с одним методом. Теперь мы можем передавать add в качестве аргумента в другие функции. Мы можем записать его в другой символ. Мы можем создавать экземпляры add_function_t в runtime и они будут уничтожены сборщиком мусора, если станут ненужными. Функции становятся базовыми объектами, как числа и строки. Функции, которые оперируют функциями (принимают их в качестве аргументов) называются функциями высшего порядка. Пусть это вас не пугает. Понятие функций высшего порядка почти не отличается от понятия Java классов, которые оперируют друг другом (мы можем передавать классы в другие классы). Мы можем называть их «классы высшего порядка», но никто этим не заморачивается, потому что за Java не стоит строгое академическое сообщество.

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

Предположим, что у нас есть участок Java кода, который получает сообщение, преобразует его различными способами и передаёт на другой сервер.

Void handleMessage(Message msg) { // ... msg.setClientCode("ABCD_123"); // ... sendMessage(msg); } // ... }
Теперь представьте себе, что система поменялась, и теперь нужно распределять сообщения между двумя серверами вместо одного. Всё остаётся неизменным, кроме кода клиента - второй сервер хочет получать этот код в другом формате. Как нам справиться с этой ситуацией? Мы можем проверять, куда должно попасть сообщение, и в зависимости от этого устанавливать правильный код клиента. Например так:

Class MessageHandler { void handleMessage(Message msg) { // ... if(msg.getDestination().equals("server1") { msg.setClientCode("ABCD_123"); } else { msg.setClientCode("123_ABC"); } // ... sendMessage(msg); } // ... }
Но такой подход плохо масштабируется. При добавлении новых серверов функция будет расти линейно, и внесение изменений превратится в кошмар. Объектно ориентированный подход заключается в выделении общего суперкласса MessageHandler и вынесение логики определения кода клиента в подклассы:

Abstract class MessageHandler { void handleMessage(Message msg) { // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); } abstract String getClientCode(); // ... } class MessageHandlerOne extends MessageHandler { String getClientCode() { return "ABCD_123"; } } class MessageHandlerTwo extends MessageHandler { String getClientCode() { return "123_ABCD"; } }
Теперь для каждого сервера мы можем создать экземпляр соответствующего класса. Добавление новых сервером становится более удобным. Но для такого небольшого изменения многовато текста. Пришлось создать два новых типа чтобы просто добавить поддержку различного кода клиента! Теперь сделаем тоже самое в нашем языке с поддержкой функций высшего порядка:

Class MessageHandler { void handleMessage(Message msg, Function getClientCode) { // ... Message msg1 = msg.setClientCode(getClientCode()); // ... sendMessage(msg1); } // ... } String getClientCodeOne() { return "ABCD_123"; } String getClientCodeTwo() { return "123_ABCD"; } MessageHandler handler = new MessageHandler(); handler.handleMessage(someMsg, getClientCodeOne);
Мы не создавали новых типов и не усложняли иерархию классов. Мы просто передали функцию в качестве параметра. Мы достигли того же эффекта, как и в объектно-ориентированном аналоге, только с некоторыми преимуществами. Мы не привязывали себя к какой-либо иерархии классов: мы можем передавать любые другие функции в runtime и менять их в любой момент, сохраняя при этом высокий уровень модульности меньшим количеством кода. По сути компилятор создал объектно-ориентированный «клей» вместо нас! При этом сохраняются все остальные преимущества ФП. Конечно абстракции, предлагаемые функциональными языками на этом не заканчиваются. Функции высшего порядка это только начало

Каррирование

Большинство людей, с которыми я встречаюсь, прочли книгу «Паттерны проектирования» Банды Четырёх. Любой уважающий себя программист будет говорить, что книга не привязана к какому-либо конкретному языку программирования, а паттерны применимы к разработке ПО в целом. Это благородное заявление. Но к сожалению оно далеко от истины.

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

Паттерн Адаптер наиболее часто применяется к «стандартной» единице абстракции в Java - классу. В функциональных языках паттерн применяется к функциям. Паттерн берёт интерфейс и преобразует его в другой интерфейс, согласно определённым требованиям. Вот пример паттерна Адаптер:

Int pow(int i, int j); int square(int i) { return pow(i, 2); }
Этот код адаптирует интерфейс функции, возводящей число в произвольную степень, к интерфейсу функции, которая возводит число в квадрат. В аккадемических кругах этот простейший приём называется каррирование (в честь специалиста по логике Хаскелла Карри (Haskell Curry), который провёл ряд математических трюков, чтобы всё это формализовать). Так как в ФП функции используются повсеместно в качестве аргументов, каррирование используется очень часто, чтобы привести функции к интерфейсу, необходимому в том или ином месте. Так как интерфейс функции - это её аргументы, то каррирование используется для уменьшения количества аргументов (как в примере выше).

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

Square = int pow(int i, 2);
Этой строкой мы автоматически создаём функцию возведения в квадрат с одним аргументом. Новая функция будет вызывать функцию pow , подставляя 2 в качестве второго аргумента. С точки зрения Java, это будет выглядеть следующим образом:

Class square_function_t { int square(int i) { return pow(i, 2); } } square_function_t square = new square_function_t();
Как видите, мы просто написали обёртку над оригинальной функцией. В ФП каррирование как раз и представляет из себя простой и удобный способ создания обёрток. Вы сосредотачиваетесь на задаче, а компилятор пишет необходимый код за вас! Всё очень просто, и происходит каждый раз, когда вы хотите использовать паттерн Адаптер (обёртку).

Ленивые вычисления

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

String s1 = somewhatLongOperation1(); String s2 = somewhatLongOperation2(); String s3 = concatenate(s1, s2);
В императивных языках программирования очерёдность вычисления не вызывает никаких вопросов. Поскольку каждая функция может повлиять или зависеть от внешнего состояния, то необходимо соблюдать чёткую очерёдность вызовов: сначала somewhatLongOperation1 , затем somewhatLongOperation2 , и concatenate в конце. Но не всё так просто в функциональных языках.

Как мы уже видели ранее somewhatLongOperation1 и somewhatLongOperation2 могут быть запущены одновременно, потому что функции гарантированно не влияют и не зависят от глобального состояния. Но что, если мы не хотим выполнять их одновременно, нужно ли вызывать их последовательно? Ответ - нет. Эти вычисления должны быть запущены, только если какая-либо другая функция зависит от s1 и s2 . Нам даже не нужно выполнять их до тех пор, пока они понадобятся внутри concatenate . Если вместо concatenate мы подставим функцию, которая в зависимости от условия использует один аргумент из двух, то второй аргумент можно даже не вычислять! Haskell - это пример языка с отложенными вычислениями. В Haskell отсутствует гарантия какой-либо очередности вызовов (вообще!), потому что Haskell выполняет код по мере необходимости.

Ленивые вычисления обладают рядом достоинств как и некоторыми недостатками. В следующем разделе мы обсудим достоинства и я объясню как уживаться с недостатками.

Оптимизация

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

Абстрагирование структур управления

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

Unless(stock.isEuropean()) { sendToSEC(stock); }
Мы хотим, чтобы функция sendToSEC выполнялась только если фонд (stock) не европейский. Как можно реализовать unless ? Без ленивый вычислений нам бы понадобилась система макросов, но в языках, подобных Haskell, это не обязательно. Мы можем объявить unless в виде функции!

Void unless(boolean condition, List code) { if(!condition) code; }
Заметьте, что code не будет выполняться, если condition == true . В строгих языках такое поведение невозможно повторить, так как аргументы будут вычислены прежде, чем unless будет вызвана.

Бесконечные структуры данных

Ленивые языки позволяют создавать бесконечные структуры данных, создание которых в строгих языках гораздо сложнее [пер. - только не в Python]. Например представьте себе последовательность Фибоначи. Очевидно, что мы не можем вычислить бесконечный список за конечное время и при этом сохранить его в памяти. В строгих языках, таких как Java, мы просто написали бы функцию, которая возвращает произвольный член последовательности. В языках подобных Haskell мы можем абстрагироваться и просто объявить бесконечный список чисел Фибоначи. Так как язык ленивый, то будут вычислены лишь необходимые части списка, которые реально используются в программе. Это позволяет абстрагироваться от большого числа проблем и посмотреть на них с более высокого уровня (например можно использовать функции обработки списков на бесконечных последовательностях).

Недостатки

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

В ленивом языке никто не гарантирует, что первая строка выполнится раньше второй! Это означает, что мы не можем делать ввод-вывод, не можем нормально использовать нативные функции (ведь их нужно вызывать в определённом порядке, чтобы учитывать их побочные эффекты), и не можем взаимодействовать с внешним миром! Если мы введём механизм для упорядочивания выполнения кода, то потеряем преимущество математической строгости кода (а следом потеряем все плюшки функционального программирования). К счастью ещё не всё потеряно. Математики взялись за работу и придумали несколько приёмов для того, чтобы убедится в правильном порядке выполняемых инструкций не потеряв функционального духа. Мы получили лучшее от двух миров! Такие приёмы включают в себя продолжения (continuation), монады (monads) и однозначная типизация (uniqueness typing). В данной статье мы поработаем с продолжениями, а монады и однозначную типизацию отложим до следующего раза. Занятно, что продолжения очень полезная штука, которая используется не только для задания строгого порядка вычислений. Об этом мы тоже поговорим.

Продолжения

Продолжения в программировании играют такую же роль, как «Код да Винчи» в человеческой истории: удивительное разоблачение величайшей тайны человечества. Ну, может не совсем так, но они точно срывают покровы, как в своё время вы научились брать корень из -1.

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

Int i = add(5, 10); int j = square(i);
Функция add возвращает число 15, которое записывается в i , в том месте, где функция и была вызвана. Затем значение i используется при вызове square . Заметьте, что ленивый компилятор не может поменять очередность вычислений, ведь вторая строка зависит от результата первой. Мы можем переписать этот код с использованием Стиль Передачи Продолжения (Continuation Passing Style или CPS), когда add возвращает значение в функцию square .

Int j = add(5, 10, square);
В таком случае add получает дополнительный аргумент - функцию, которая будет вызвана после того, как add закончит работать. В обоих примерах j будет равен 225.

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

System.out.println("Please enter your name: "); System.in.readLine();
Эти две строки не зависят друг от друга, и компилятор волен поменять их порядок по своему хотению. Но если мы перепишем в CPS, то тем самым добавим нужную зависимость, и компилятору придётся проводить вычисления одно за другим!

System.out.println("Please enter your name: ", System.in.readLine);
В таком случае println должен будет вызвать readLine , передав ему свой результат, и вернуть результат readLine в конце. В таком виде мы можем быть уверены, что эти функции будут вызваны по очереди, и что readLine вообще вызовется (ведь компилятор ожидает получить результат последней операции). В случае Java println возвращает void . Но если бы возвращалось какое-либо абстрактное значение (которое может служить аргументом readLine), то это решило бы нашу проблему! Конечно выстраивание таких цепочек функций сильно ухудшает читаемость кода, но с этим можно бороться. Мы можем добавить в наш язык синтаксических плюшек, которые позволят нам писать выражения как обычно, а компилятор автоматически выстраивал бы вычисления в цепочки. Теперь мы можем проводить вычисления в любом порядке, не потеряв при этом достоинств ФП (включая возможность исследовать программу математическими методами)! Если вас это сбивает с толку, то помните, что функции - это всего лишь экземпляры класса с единственным членом. Перепишите наш пример так, чтобы println и readLine были экземплярами классов, так вам станет понятней.

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

Как только мы переведём программу к CPS виду, становится ясно, что у каждой инструкции есть продолжение, функция в которую будет передаваться результат, что в обычной программе было бы точкой вызова. Возьмём любую инструкцию из последнего примера, например add(5,10) . В программе, написанной в CPS виде, понятно что будет являться продолжением - это функция, которую add вызовет по окончанию работы. Но что будет продолжением в случае не-CPS программы? Мы, конечно, можем конвертировать программу в CPS, но нужно ли это?

Оказывается, что в этом нет необходимости. Посмотрите внимательно на наше CPS преобразование. Если вы начнёте писать компилятор для него, то обнаружите, что для CPS версии не нужен стек! Функции никогда ничего не возвращают, в традиционном понимании слова «return», они просто вызывают другую функцию, подставляя результат вычислений. Отпадает необходимость проталкивать (push) аргументы в стек перед каждым вызовом, а потом извлекать (pop) их обратно. Мы можем просто хранить аргументы в каком-либо фиксированном участке памяти и использовать jump вместо обычного вызова. Нам нет нужны хранить первоначальные аргументы, ведь они больше никогда не понадобятся, ведь функции ничего не возвращают!

Таким образом, программы в CPS стиле не нуждаются в стеке, но содержат дополнительный аргумент, в виде функции, которую нужно вызвать. Программы в не-CPS стиле лишены дополнительного аргумента, но используют стек. Что же хранится в стеке? Просто аргументы и указатель на участок памяти, куда должна вернуться функция. Ну как, вы уже догадались? В стеке храниться информация о продолжениях! Указатель на точку возврата в стеке - это то же самое, что и функция, которую нужно вызвать, в CPS программах! Чтобы выяснить, какое продолжение у add(5,10) , достаточно взять из стека точку возврата.

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

Хорошо, теперь мы уяснили, что же такое текущее продолжение. Что это значит? Если мы возьмём текущее продолжение и сохраним его где-нибудь, мы тем самым сохраним текущее состояние программы - заморозим её. Это похоже на режим гибернации ОС. В объекте продолжения хранится информация, необходимая для возобновления выполнения программы с той точки, когда был запрошен объект продолжения. Операционная система постоянно так делает с вашими программами, когда переключает контекст между потоками. Разница лишь в том, что всё находится под контролем ОС. Если вы запросите объект продолжения (в Scheme это делается вызовом функции call-with-current-continuation), то вы получите объект с текущим продолжением - стеком (или в случае CPS - функцией следующего вызова). Вы можете сохранить этот объект в переменную (или даже на диск). Если вы решите «перезапустить» программу с этим продолжением, то состояние вашей программы «преобразуется» к состоянию на момент взятия объекта продолжения. Это то же самое, как переключение к приостановленному потоку, или пробуждение ОС после гибернации. С тем исключением, что вы можете проделывать это много раз подряд. После пробуждения ОС информация о гибернации уничтожается. Если этого не делать, то можно было бы восстанавливать состояние ОС с одной и той же точки. Это почти как путешествие по времени. С продолжениями вы можете себе такое позволить!

В каких ситуациях продолжения будут полезны? Обычно если вы пытаетесь эмулировать состояние в системах лишенных такового по сути. Отличное применение продолжения нашли в Web-приложениях (например во фреймворке Seaside для языка Smalltalk). ASP.NET от Microsoft прикладывает огромные усилия, чтобы сохранять состояние между запросами, и облегчить вам жизнь. Если бы C# поддерживал продолжения, то сложность ASP.NET можно было бы уменьшить в два раза - достаточно было бы сохранять продолжение и восстанавливать его при следующем запросе. С точки зрения Web-программиста не было бы ни единого разрыва - программа продолжала бы свою работу со следующей строки! Продолжения - невероятно полезная абстракция для решения некоторых проблем. Учитывая то, что всё больше и больше традиционных толстых клиентов перемещаются в Web, важность продолжений будет со временем только расти.

Сопоставление с образцом (Pattern matching)

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

Давайте начнём наше знакомство с Pattern matching следующим примером. Вот функция вычисления чисел Фибоначи на Java:

Int fib(int n) { if(n == 0) return 1; if(n == 1) return 1; return fib(n - 2) + fib(n - 1); }
А вот пример на Java-подобном языке с поддержкой Pattern matching-а

Int fib(0) { return 1; } int fib(1) { return 1; } int fib(int n) { return fib(n - 2) + fib(n - 1); }
В чём разница? Компилятор реализует ветвление за нас.

Подумаешь, велика важность! Действительно важность не велика. Было подмечено, что большое количество функций содержат сложные switch конструкции (это отчасти верно для функциональных программ), и было принято решение выделить этот момент. Определение функции разбивается на несколько вариантов, и устанавливается паттерн на месте аргументов функции (это напоминает перегрузку методов). Когда происходит вызов функции, компилятор на лету сравнивает аргументы со всеми определениями и выбирает наиболее подходящий. Обычно выбор падает на самое специализированное определение функции. Например int fib(int n) может быть вызвана при n равном 1, но не будет, ведь int fib(1) - более специализированное определение.

Сопоставление с образцом обычно выглядит сложнее, чем в нашем примере. Например сложная система Pattern matching позволяет писать следующий код:

Int f(int n < 10) { ... } int f(int n) { ... }
Когда сопоставление с образцом может быть полезно? Список таких случаев на удивление очень большой! Каждый раз, когда вы используете сложные конструкции вложенных if , pattern matching может справиться лучше с меньшим количеством кода. В голову приходит хороший пример с функцией WndProc , которая реализуется в каждой Win32 программе (даже если она спрятана от программиста за высоким забором абстракций). Обычно сопоставление с образцом может даже проверять содержимое коллекций. Например, если вы передаёте массив в функцию, то вы можете отбирать все массивы, у которых первый элемент равен 1, а третий элемент больше 3.

Ещё одним преимуществом Pattern matching является то, что в случае внесения изменений вам не придётся копаться в одной огромной функции. Вам достаточно будет добавить (или изменить) некоторые определения функций. Тем самым мы избавляется от целого пласта паттернов из знаменитой книги Банды Четырёх. Чем сложнее и ветвистее условия, тем полезнее будет использовать Pattern matching. Как только вы начнёте их использовать, то удивитесь, как вы могли раньше без них обходится.

Замыкания

До сих пор мы обсуждали особенности ФП в контексте «чисто» функциональных языков - языков, которые являются реализацией лямбда исчисления и не содержат особенностей, противоречащих формальной системе Чёрча. Тем не менее, многие черты функциональных языков используются за пределами лямбда исчисления. Хотя реализация аксиоматической системы интересна с точки зрения программирования в терминах математических выражений, это не всегда может быть применимо на практике. Многие языки предпочитают использовать элементы функциональных языков не придерживаясь строгой функциональной доктрины. Некоторые такие языки (например Common Lisp) не требуют от переменных быть final - их значения можно менять. Они даже не требуют, чтобы функции зависели только от своих аргументов - функциям дозволенно обращаться к состоянию за пределом своей области видимости. Но при этом они включают в себя такие особенности, как функции высшего порядка. Передача функции в не-чистом языке немного отличается от аналогичной операции в пределах лямбда исчисления и требует наличия интересной особенности под названием: лексическое замыкание. Давайте взглянем на следующий пример. Помните, что в данном случае переменные не final и функция может обращаться к переменным за пределом своей области видимости:

Function makePowerFn(int power) { int powerFn(int base) { return pow(base, power); } return powerFn; } Function square = makePowerFn(2); square(3); // returns 9
Функция make-power-fn возвращает функцию, которая принимает один аргумент и возводит его в определённую степень. Что произойдёт, когда мы попробуем вычислить square(3) ? Переменная power находится вне области видимости powerFn , потому что makePowerFn уже завершилась, и её стек уничтожен. Как же тогда работает square ? Язык должен каким-либо образом сохранить значение power , чтобы функция square могла работать. А что если мы создадим ещё одну функцию cube , которая возводит число в третью степень? Язык должен будет сохранять два значения power для каждой созданной в make-power-fn функции. Феномен хранения этих значений и называется замыканием. Замыкание не только сохраняет аргументы верхней функции. Например замыкание может выглядеть следующим образом:

Function makeIncrementer() { int n = 0; int increment() { return ++n; } } Function inc1 = makeIncrementer(); Function inc2 = makeIncrementer(); inc1(); // returns 1; inc1(); // returns 2; inc1(); // returns 3; inc2(); // returns 1; inc2(); // returns 2; inc2(); // returns 3;
В процессе выполнения значения n сохраняются, и счётчики имеют доступ к ним. Более того у каждого счётчика своя копия n , не смотря на то, что они должны были исчезнуть после того, как функция makeIncrementer отработает. Как же компилятор умудряется это скомпилировать? Что происходит за кулисами замыканий? К счастью у нас есть волшебный пропуск.

Всё сделано достаточно логично. С первого взгляда ясно, что локальные переменные больше не подчиняются правилам области видимости и их время жизни не определено. Очевидно, что они больше не хранятся в стеке - их нужно держать в куче (heap) . Замыкание, следовательно, сделано как обычная функция, которую мы обсуждали ранее, за исключением того, что в нём есть дополнительная ссылка на окружающие переменные:

Class some_function_t { SymbolTable parentScope; // ... }
Если замыкание обращается к переменной, которой нет в локальной области видимости, тогда оно принимает во внимание родительскую область. Вот и всё! Замыкание связывает функциональный мир с миром ООП. Каждый раз, когда вы создаёте класс, который хранит некоторое состояние, и передаёте его куда-то, вспомните про замыкания. Замыкание - это всего лишь объект, который создаёт «атрибуты» на лету, забирая их из области видимости, чтобы вам не пришлось делать это самим.

Что теперь?

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