Функциональный стиль — часть 1

Введение.

Функциональное программирование является очень горячей темой в наше время. Люди все больше интересуются функциональными и гибридно-функциональными языками, такими как Haskell, Scala, F # и Clojure, а функциональное программирование является одной из самых популярных запрашиваемых тем для обсуждения на конференциях и в сообществах программистов. Поскольку вы читаете это, может быть, вам интересно узнать больше об этом; Если это так, эта серия статей предназначена для вас. Я был мотивирован, чтобы написать их, потому что я чувствую потребность в большем количестве литературы, объясняющей, как программировать в функциональном стиле. Я хочу проиллюстрировать это примерами обильного кода и подчеркнуть преимущества, которые вы должны увидеть, когда попытаетесь это сделать.

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

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

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

Должен ли я выучить функциональный язык?

Не обязательно, действительно моя главная цель в этой серии — продемонстрировать функциональный стиль , показать, как он может быть принят в определенной степени на многих языках, и какие преимущества вы должны реализовать, если вы это делаете. Я буду использовать Java и, в меньшей степени, C #, чтобы проиллюстрировать многие моменты этой серии. Тем не менее, языки, которые не предназначены для функционального программирования — я буду впредь называть их императивными языками — все в некотором смысле несовершенны для выражения функционального кода. У каждого языка есть своя «сладость» для функционального программирования, и вы по опыту узнаете, где он находится на вашем языке.

Функциональный код может быть выражен наиболее естественно, очевидно, в языках, которые были созданы специально для функционального программирования. Хаскель, как правило, считается самым чистым функциональным языком. Он родился в академической среде, и его сообщество любит думать и обсуждать программирование в очень математических терминах. Другой популярный функциональный язык — Clojure. Это диалект Lisp, который работает на виртуальной машине Java. Не все Лиспы являются должным образом функциональными языками, но Clojure явно разработан для функционального программирования, а также имеет отличную поддержку параллелизма.

Haskell и Clojure существуют, в некотором роде, на противоположных концах спектра FP: Clojure типизируется динамически, в то время как Haskell типизирован статически и очень сильно так. Возможно, вы знаете, что религиозная война бушевала десятилетиями в объектно-ориентированном мире программирования между статической и динамической типизацией. С этим борются и в ФП. Я не буду упоминать это снова, потому что это не то, о чем я хочу, чтобы эта серия была.

Два языка, которые часто рассматриваются как функциональные, Scala и F #, на самом деле являются гибридами: они поддерживают как функциональные, так и императивные стили программирования. Выбор остается за программистом. F # является частью семейства .NET и компилируется для работы в среде Common Language Runtime. Scala, как и Clojure, работает на JVM.

Так что же такое функциональное программирование?

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

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

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

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

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

Побочные эффекты и императивные языки.

Я хочу, чтобы эта серия была легкой на жаргоне, но я уже упомянул пару терминов: побочный эффект и императивные языки . Под императивными языками я подразумеваю все языки, специально не предназначенные для функционального программирования, так что сюда входят все процедурные и объектно-ориентированные языки, такие как Fortran, Algol, C, Smalltalk, C ++, Java, C # и т. Д. это . Целью этих приказов является побочные эффекты. Побочный эффект означает, что какое-то состояние где-то было изменено.

Элементы в большинстве императивных языков программирования можно разбить на три класса:

• Управляющие структуры: if-then-else, циклы и т. Д.
• Операторы: назначить переменную, переназначить переменную, вызвать процедуру и т. Д.
• Выражения: код, который возвращает значение.

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

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

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

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

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

Практическое определение.

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

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

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

Первоначально символ x был связан со значением 0 . Это задание. Тогда это связано с новым значением, которое оказывается старым значением плюс единица. Это переназначение, и акт переназначения изменил состояние:

х был ноль, теперь он один .

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

Это смутило меня. Я уже был знаком с уравнениями, познакомившись с алгеброй в средней школе, но это утверждение не имело смысла. Как может X быть равным X плюс один? Руководство, четко написанное для аудитории, имеющей практические знания по математике, но не имеющей опыта работы с компьютерами, признало странность. Он объяснил, что это вовсе не уравнение, это обязательное утверждение с двумя последовательными шагами:

1. Оцените выражение в правой части знака равенства X + 1 .
2. Присвойте результат символу слева X

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

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

Почему бы нам не запрограммировать это уже так?

Эти два различных подхода к программированию, чтобы изменить состояние или нет, можно проследить до самой зари современных вычислений. В 1936 году Алонзо Черч опубликовал формальную систему математической логики для выражения вычислений, которую он назвал Лямбда-исчисление. Примерно в то же время и независимо Алан Тьюринг создал теоретическую модель для устройств, называемых машинами Тьюринга, которые могли выполнять вычисления, манипулируя символами на ленте. Впоследствии эти две идеи были объединены в формальную теорию вычислений, известную как тезис Черча-Тьюринга, и она заложила основу для современных вычислений.

Машина Тьюринга имеет состояние: она содержит один символ внутри машины, который можно изменить, а также может записывать и перезаписывать символы на ленте. В отличие от этого, лямбда-исчисление является чисто математическим подходом и не имеет понятия состояния. Лямбда-исчисление оказало влияние на один из самых ранних языков программирования, Lisp, но в целом доминировал императивный стиль программирования, основанный на FORTRAN. Причины легко различимы: в основном, скорость обработки и память. У ранних компьютеров было мало чего либо. Кроме того, основные инструкции по программированию всех компьютеров вплоть до сегодняшнего дня являются обязательными: добавьте эти два числа , сохраните результат здесь , сравните эти два числа , установите флаг состояния и т. Д. Самые первые программы были написаны с использованием этого набора команд из-за отсутствия какого-либо другого языка, на котором они могли бы быть написаны. Первые языки высокого уровня, чтобы быть практичными, все еще находились под сильным влиянием их дизайна на машинах, на которых они работали. Только позже стиль функционального программирования начал завоевывать популярность.

Что делает язык функциональным?

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

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

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

Повелительные языки.

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

То же самое относится и к Java и C #. Благодаря этому показателю Ruby становится еще менее функциональным: в Ruby «константы» идентифицируются по имени, начинающемуся с заглавной буквы, но вы все равно можете изменить его значение. Это просто производит предупреждение.

Гибридно-функциональные языки.

Scala, Kotlin и F # все сидят на заборе: эти языки заставляют вас выбирать, должен ли символ быть переменным или его значение никогда не изменится. В Скала:

в то время как в Kotlin, который имеет более Java-подобный синтаксис:

F # склоняется немного больше к функциональной стороне, потому что все «переменные» неизменны, если вы не скажете иначе:

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

Функциональные языки.

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

но если вы используете символ foo любом месте вашей программы, значение всегда будет «bar», а не «foo». Второе определение заменяет первое, и ваш инструмент анализа кода может пометить первое определение как неиспользуемое. Ближайшая вещь, которую Clojure имеет к присваиванию переменной — это let :

Когда вы оцениваете эту форму, она печатает:

так что мы можем видеть, что let фактически не изменяет значение foo вообще; он создал новую область видимости, в которой символ foo связан со значением «bar», но вне этой области он все еще связан с исходным значением «foo».

Аналогично, список типов коллекций, набор, вектор и карта Clojure являются неизменяемыми: после создания они никогда не могут быть изменены. Если у меня есть список:

тогда (cons 0 my-list) выдаст новый список (0 1 2 3) но my-list все еще содержит только (1 2 3) . Карты, наборы и векторы ведут себя одинаково. Если вы действительно хотите изменить значение чего-либо в Clojure, вы должны определить его как atom :

и затем используйте reset! изменить свою стоимость. В Clojure функции, изменяющие состояние, обозначаются знаком! характер:

который печатает:

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

В Haskell переменные являются только «переменными» в математическом смысле, что x является переменной в уравнении, которое определяет прямую линию, y = mx + c . Вы можете изменить x чтобы вычислить соответствующие значения для y но это просто обозначение для описания чего-то неизменного: прямой линии. Вы не можете изменить состояние в чистом Haskell, когда вам нужно сделать это, вы должны использовать монады (я объясню это намного позже). Если вы сравните реализации сортировки пузырьков в Ruby и Haskell в этом посте для примера того, как изменить состояние, я думаю, вы согласитесь, что на императивном языке это выглядит проще. Я сомневаюсь, что программисты на Haskell написали бы императивные программы на Haskell. Но это говорит:

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

и если кто-нибудь узнает о Хаскеле, то это он.

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

В следующий раз:

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