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

1 Введение

Программы на традиционных языках программирования, таких как Си, Паскаль, Java и т.п. состоят их последовательности модификаций значений некоторого набора переменных, который называется состоянием . Если не рассматривать операции ввода-вывода, а также не учитывать того факта, что программа может работать непрерывно (т.е. без остановок, как в случае серверных программ), можно сделать следующую абстракцию. До начала выполнения программы состояние имеет некоторое начальное значение σ0 , в котором представлены входные значения программы. После завершения программы состояние имеет новое значение σ0 , включающее в себя то, что можно рассматривать как «результат» работы программы. Во время исполнения каждая команда изменяет состояние; следовательно, состояние проходит через некоторую конечную последовательность значений:

σ = σ0 → σ1 → σ2 → · · · → σn = σ0

Состояние модифицируется с помощью команд присваивания , записываемых в виде v=E или v:=E, где v - переменная, а E - некоторое выражение. Эти команды следуют одна за другой; операторы, такие как if и while, позволяют изменить порядок выполнения этих команд в зависимости от текущего значения состояния. Такой стиль программирования называютимперативным илипроцедурным .

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

1 Употребление термина «вычисление» не означает, что программа может оперировать только с числами; результатом вычисления могут оказаться строки, списки и вообще, любые допустимые в языке структуры данных.

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

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

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

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

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

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

Вместо циклов функциональные программы широко используют рекурсивные функции.

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

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

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

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

Например, рассмотрим следующую программу на языке Haskell:

factorial n = if n == 0 then 1 else n * factorial (n - 1)

Практически сразу видно, что эта программа соответствует следующей частичной функции:

f(n) = n! n ≥ 0

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

int x = 1; while (n > 0)

x = x * n; n = n - 1;

Следует также сделать замечание относительно употребления термина «функция» в таких языках как Си, Java и т.п. В математическом смысле «функции» языка Си не являются функциями, поскольку:

Их значение может зависеть не только от аргументов;

Результатом их выполнения могут быть разнообразные побочные эффекты (например, изменение значений глобальных переменных)

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

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

2 Основы лямбда-исчисления

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

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

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

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

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

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

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

100% соответствие своей семантики с семантикой подразумеваемых конструкций лямбда-исчисления.

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

Пусть f: R → R определяется следующим выражением:

	(x2 sin(1/x2 ),

Тогда f0 (x) не интегрируема на интервале .

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

Пусть x = 2 и y = 4. Тогда xx = y.

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

где E - некоторое выражение, возможно, использующее переменную x.

Пример. λx.x2 представляет собой функцию, возводящую свой аргумент в квадрат.

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

Применение функции f к аргументу x мы будем обозначать как f x, т.е., в отличие от того, как это принято в математике, не будем использовать скобки2 . По причинам, которые станут ясны позднее, будем считать, что применение функции к аргументу ассоциативно влево, т.е. f x y

2 Заметим, что и в математике такие выражения, как sin x записываются без скобок.

означает (f(x))(y). В качестве сокращения для выражений вида λx.λy.E будем использовать запись λx y.E (аналогично для большего числа аргументов). Также будем считать, что «область действия» лямбда-выра- жения простирается вправо насколько возможно, т.е., например, λx.x y означает λx.(x y), а не (λx.x)y.

На первый взгляд кажется, что нам необходимо ввести специальное обозначение для функций нескольких аргументов. Однако существует операция каррирования 3 , позволяющая записать такие функции в обычной лямбда-нотации. Идея заключается в том, чтобы использовать выражения вида λx y.x + y. Такое выражение можно рассматривать как функцию R → (R → R), т.е. если его применить к одному аргументу, результатом будет функция, которая затем принимает другой аргумент. Таким образом:

(λx y.x + y) 1 2 = (λy.1 + y) 2 = 1 + 2.

Переменные в лямбда-выражениях могут бытьсвободными исвязанными . В выражении вида x2 + x переменная x является свободной; его значение зависит от значения переменной x и в общем случае ее нельзя

вать обозначение j, значение выражения не изменится.

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

В лямбда исчислении выражения λx.E[x] и λy.E[y] считаются эквивалентными (это называется α-эквивалентностью, и процесс преобразования между такими парами называют α-преобразованием). Разумеется, необходимо наложить условие, что y не является свободной переменной в E[x].

3 от фамилии известного логика Хаскелла Карри, в честь которого назван язык программирования Haskell

3 Лямбда-исчисление как формальная система

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

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

2. Константы: также обозначаются строками; отличие от переменных будем определять из контекста.

3. Комбинации: , т.е. применения функции S к аргументу T ; и S и T могут быть произвольными лямбда-термами. Комбинация записывается как S T .

4. Абстракции произвольного лямбда-терма S по переменной x, обозначаемые как λx.S.

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

Exp = Var| Const| Exp Exp| λ Var . Exp

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

3.1 Свободные и связанные переменные

В данном разделе мы формализуем данное ранее интуитивное представление о свободных и связанных переменных. Множество свободных

переменных F V (S) лямбда-терма S можно определить рекурсивно следующим образом:

Аналогично множество связанных переменных BV (S) определяется следующими формулами:

BV (x) =

BV (c) =

BV (S T) = BV (S) BV (T)

BV (λx.S) = BV (S) {x}

Здесь предполагается, что c - некоторая константа.

Пример. Для терма S = (λx y.x) (λx.z x) можно показать, что F V (S) = {z} и

BV (S) = {x, y}.

3.2 Подстановки

Интуитивно ясно, что применение терма λx.S как функции к аргументу T дает в результате терм S, в котором все свободные вхождения переменной x заменены на T . Как ни странно, формализовать это интуитивное представление оказывается нелегко.

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

3.3 Конверсия

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

α-конверсия: λx.S −→ λy.S при условии, что y / F V (S).

Например, λu.u v −→ λw.w u.

β-конверсия: (λx.S) T −→ S.

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

3.4 Равенство лямбда-термов

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

под ней»:

Следует отличать понятие равенства, определяемое этими формулами, от понятия синтаксической эквивалентности, которую мы будем обозначать специальным символом ≡. Например, λx.x 6≡λy.y, но λx.x = λy.y. Часто можно рассматривать синтаксическую эквивалентность термов с точностью до α-конверсий. Такую эквивалентность будем обозначать символом ≡α . Это отношение определяется так же, как равенство лямбда-термов, за тем исключением, что из всех конверсий допустимы только α-конверсии. Таким образом, λx.x ≡α λy.y.

3.5 Экстенсиональность

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

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

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

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

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

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

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

• LISP - (Джон МакКарти , ) и множество его диалектов, наиболее современные из которых:
• Erlang - (Joe Armstrong, ) функциональный язык с поддержкой процессов.
• APL - предшественник современных научных вычислительных сред, таких как MATLAB .
• (Робин Милнер , , из ныне используемых диалектов известны Standard ML и Objective CAML).
• - функциональный язык семейства ML для платформы .NET
• Miranda (Дэвид Тёрнер , , который впоследствии дал развитие языку Haskell).
• Nemerle - гибридный функционально/императивный язык.
• Haskell - чистый функциональный. Назван в честь Хаскелла Карри .

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

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

История

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

Концепции

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

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

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

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

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

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

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

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

Рекурсия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особенности

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

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

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

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

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

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

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

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

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

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

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

Недостатки

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

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

См. также

• Анаморфизм
• Катаморфизм

Примечания

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

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

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

К функциональным языкам программирования относят: Lisp, Miranda, Gofel, ML, Standard ML, Objective CAML, F#, Scala, Пифагор и др.

Процедурные языки программирования

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

Процедурные языки программирования: Ada, Basic, Си, КОБОЛ, Pascal, ПЛ/1, Рапира и др.

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

Стековый язык программирования − это язык программирования, в котором для передачи параметров используется машинная модель стека. Стековые языки программирования: Forth, PostScript, Java, C# и др. При использовании стека, в качестве основного канала передачи параметров между словами, элементы языка, естественным образом, образуют фразы (последовательное сцепление). Это свойство сближает данные языки с естественными языками.

Аспектно-ориентированные языки программирования 5) Декларативные языки программирования 6) Динамические языки программирования 7) Учебные языки программирования 8) Языки описания интерфейсов 9) Языки прототипного программирования 10) Объектно-ориентированные языки программирования 11) Логические языки программирования 12) Сценарные языки программирования 13) Эзотерические языки программирования

Стандартизация языков программирования. Парадигма программирования

Концепция языка программирования неотрывно связана с его реализацией. Для того чтобы компиляция одной и той же программы различными компиляторами всегда давала одинаковый результат, разрабатываются стандарты языков программирования. Организации, занимающиеся вопросами стандартизации: Американский национальный институт стандартов ANSI, Институт инженеров по электротехнике и электронике IEEE, Организация международных стандартов ISO.

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

Парадигмы программирования

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

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

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

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

Программирование – процесс создания компьютерных программ. В более широком смысле: спектр деят-сти, связ-ый с созданием и поддержанием в раб. состоянии программ - ПО ЭВМ.

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

Технология программир-я представляет собой набор технологических инструкций, включающих:

· указание последоват-сти выполнения технологич-х операций;

· перечисление условий, при кот-х выполняется та или иная операция;

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

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

Важным этапом создания прогр-го продукта явл. тестирование и отладка.

Отладка − это деятельность, направленная на обнаружение и исправление ошибок в программном продукте с использованием процессов выполнения его программ.

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

Существуют следующие методы тестирования ПС:

1) Статическое тестирование – ручная проверка программы за столом.

2) Детерминированное тестир-е – при разл-х комбинациях исх-х данных.

3) Стохастическое – исх. данные выбир-ся произвольно, на выходе определяется качеств-е совпадение результатов или примерная оценка.

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

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

Существует несколько стилей программирования:

1. Процедурное программирование – это программирование, при котором программа представляет собой последовательность операторов. Используется в языках высокого уровня Basic, Fortran и др.
2. Функциональное программирование – это программирование, при котором программа представляет собой последовательность вызовов функций. Используется в языках Lisp и др.
3. Логическоепрограммирование – это программирование, при котором программа представляет собой совокупность определения соотношений между объектами. Используется в языках Prolog и др.

Объектно-ориентированноепрограммирование – это программирование, при котором основой программы является объект представляющий собой совокупность данных и правил их преобразования. Используется в языках Turbo-Pascal, C++ и др.

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

Основные концепции

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

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

Чистая функция максимально проста. Она должна всегда возвращать один и тот же результат. Посмотрите на эту JavaScript-функцию:

var z = 10; function add(x, y) { return x + y; }

var z = 10 ; function add (x , y ) { return x + y ;

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

Изменяемые данные и побочные эффекты

Вернемся к примеру кода. Если мы добавим в качестве аргумента функции add() , переменную z , которая объявлена выше, наша функция перестанет быть чистой и предсказуемой. Почему? Потому что z объявлена как обычная переменная: она доступна для изменения из любого места программы.

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

Корректный код чистой функции с z должен выглядеть так:

const x = 10; const z = 10; add (x, z); // вернет 20

const x = 10 ; const z = 10 ; add (x , z ) ; // вернет 20

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

Еще один пример не функционального кода – классические циклы. Вспомним, как выглядит типичный цикл for в JavaScript:

var acc = 0; for (var i = 1; i <= 10; ++i) { acc += i; } console.log(acc); // выведет 55

var acc = 0 ; for (var i = 1 ; i <= 10 ; ++ i ) { acc += i ; console . log (acc ) ; // выведет 55

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

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

function sumRange(start, end, acc) { if (start > end) { return acc; } else { return sumRange(start + 1, end, acc + start); } } console.log(sumRange(1, 10, 0)); // выведет 55

function sumRange (start , end , acc ) { if (start > end ) { return acc ; } else { return sumRange (start + 1 , end , acc + start ) ; console . log (sumRange (1 , 10 , 0 ) ) ; // выведет 55

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

Композиция функций

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

function addOne(x) { return x + 1; } function timesTwo(x) { return x * 2; } console.log(addOne(timesTwo(3))); // выведет 7 console.log(timesTwo(addOne(3))); // выведет 8

function addOne (x ) { return x + 1 ; function timesTwo (x ) {

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

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

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

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

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

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

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

Так как функциональное программирование – это прежде всего подход к написанию кода, использовать его принципы можно в любом языке. Однако существуют языки, специально заточенные под функциональный подход. Первый и самый известный из них – Lisp. Он появился еще в 1958 году. Его автор – Джон Маккарти, информатик и автор термина «искусственный интеллект». Lisp по сей день популярен в среде проектировщиков ИИ.

Более современные функциональные языки, такие как Elm и Elixir, по данным GitHub и Stack Overflow постепенно и уверенно набирают популярность. Рост популярности JavaScript также привел к повышенному интересу к концепциям функционального программирования для применения в этом языке.