Доброго времени суток. Это статья — перевод заинтересовавшего меня поста
в блоге аспиранта Университета штата Нью-Йорк в Стоуни-Брук. Статья в
доступной форме описывает основные концепции функционального
программирования, их преимущества и недостатки. Думаю она будет полезна
широкому кругу читателей, которые сомневаются, нужно ли им углубляться в
мир функционального программирования или нет. Пожелания, предложения и
замечания по переводу и терминологии принимаются по личной почте.
Мнение переводчика может иногда не совпадать с мнением автора, но переводить статью было крайне занимательно.
UPD: альтернативный вариант перевода вы можете найти на rsdn (спасибо flamingo за ссылку).
Понедельник, 19 июня, 2006
Введение
Программисты — прокрастинаторы (то есть лентяи). Прийти, сделать кофе,
проверить почту, почитать RSS летну, почитать новости, проверить свежие
статьи на техническом сайте, полистать политические дискуссии на
программистском форуме. Смыть, повторить, чтобы ничего не пропустить.
Пойти на обед. Вернуться, уткнутся в IDE на несколько минут. Проверить
почту. Приготовить кофе. И вот неожиданно день подходит к концу.
Но время от времени в поле зрения оказываются занятные (затруднительные,
многообещающие) статьи и посты в блогах. Если вы ищете в правильном
месте, то как минимум одна такая статья будет встречаться вам каждые
несколько дней. В этих постах сложно разобраться, на это требуется
время, поэтому они накапливаются в папке «Прочитать». Прежде, чем вы
успеете понять что к чему, окажется что уже накопилась куча ссылок и
папка, полная PDF файлов. Вам, и понадобится целый год и хижина посреди
леса, где на мили вокруг нет ни души, чтобы во всём этом разобраться. И
желательно, чтобы кто-нибудь каждое утро приносил еду и забирал мусор,
пока вы прогуливаетесь к реке.
Я не знаю, какой у вас список, но большая часть моего списка касается
функционального программирования. Такие статьи обычно самые сложные.
Часто они написаны сухим академическим языком, и даже «ветераны Wall
Street с десятилетним стажем» не понимают о чем говорится в статьях по
функциональному программированию (ФП). Если вы зададите вопрос менеджеру
проекта в Citi Group или в Deutsche Bank [1]
почему они выбрали JMS вместо Erlang, то услышите в ответ, что они не
могут использовать академический язык для промышленных разработок.
Проблема в том, что большинство комплексных систем с самыми жесткими
требованиями были написаны с использованием элементов функционального
программирования. Что-то не сходится.
Действительно статьи о ФП трудны для понимания, но их можно написать
проще. Причина возникшей пропасти знаний чисто историческая. По сути в
концепции ФП нет ничего сложного. Взгляните на эту статью, как на
«доступное руководство по ФП», как на мостик между нашими императивными
умами и миром ФП. Заварите себе кофе и продолжим. Надеюсь, что уже очень
скоро коллеги начнут шутить по поводу ваших ФП комментариев.
Так что же такое ФП? Откуда оно пошло? На что оно годно? Если оно
действительно так полезно, как об этом твердят защитники ФП, то почему
его не используют чаще в промышленных масштабах? Почему только люди с
PhD склоняются к функциональным языкам? Но что ещё важнее, почему так
чертовски трудно освоить функциональные языки? Что скрывается за всеми
этими замыканиями, продолжениями, каррированием, ленивые вычисления и
отсутствие побочных эффектов? Как это всё можно использовать в проекте,
который не охватывает целую вселенную? Почему это всё так далеко от того
хорошего, что свято и дорого нашим императивным сердцам? Скоро мы во
всём разберёмся. Для начала давайте поймём в чём причина огромной
пропасти между академическими статьями и реальным миром. Чтобы ответить
на этот вопрос достаточно прогуляться в парке.
Прогулка в парке
Садитесь в машину времени. Наша прогулка в парке произошла более 2 тысяч
лет назад в один из тех солнечных дней давно забытой весны 380 года до
н.э. За городскими стенами Афин под ласковыми тенями оливковых деревьев
Платон прогуливался в направлении Академии с красивым мальчиком рабом.
Стояла чудесная погода, обед приятной тяжестью отдавался в животе, и
разговор плавно перешёл на философские темы.
«Посмотри на тех двух студентов», сказал Платон, аккуратно подбирая
слова, чтобы придать вопросу образовательного смысла. «Кто из них,
по-твоему, выше?» Мальчик раб посмотрел в сторону бассейна, возле
которого стояли два человека. «Они приблизительно одного роста», ответил
мальчик. «Что ты имеешь в виду под словами 'приблизительно одного
роста'?», спросил Платон. «Ну, отсюда они выглядят одинаково, но я
уверен, что если мы подойдём поближе, то я смогу увидеть разницу в
росте.»
Платон улыбнулся. Он вёл мальчика в правильном направлении. «То есть ты
хочешь сказать, что в мире нет идеально совпадающих вещей?» Мальчик
призадумался и ответил: «Да, я так думаю. Всегда существует маленькая
разница, даже если мы не можем её увидеть.» Он дошёл до самой сути!
«Тогда если нет идеально совпадающих вещей в этом мире, то как ты
понимаешь концепцию 'идеального' равенства?» Это ввело мальчика в
ступор. Он ответил: «Я не знаю».
Так родилась первая попытка понять природу математики. Платон
предположил, что в нашем мире всё лишь приближение идеала. Он также
осознал, что люди способны понять концепцию идеала, хотя никогда с ним
не сталкивались. Он пришёл к выводу, что идеальные математические формы
должны существовать в другом мире, и что мы каким-то образом знаем о них
из связей с этой «альтернативной» вселенной. Очевидно, что мы не можем
увидеть идеальный круг. Но при этом мы понимаем, что из себя
представляет идеальный круг, и как он может быть описан математически.
Что же тогда математика? Почему вселенная описывается математическими
законами? Всё ли может описать математика? [2]
Философия математики
очень сложный предмет. Как и большинство философских дисциплин, она
скорее задаёт вопросы, чем отвечает на них. Учёные в большинстве своём
согласны с тем фактом, что математика — это настоящая головоломка: в
основе лежит набор базовых непротиворечивых принципов и набор правил,
как этими принципами оперировать. Затем мы можем комбинировать правила,
получая всё более и более сложные законы. Математики называют такой
метод «формальной системой» или «исчислением». Например, можно построить
формальную систему для Тетриса. По сути работающий Тетрис и есть сам по
себе формальная система, просто она записана в необычном виде.
Цивилизация пушистых существ с Альфы Центавра не сможет прочесть нашу
формальную систему Тетриса или круга, потому что их единственный орган
чувств может воспринимать только запахи. Возможно они никогда не
построят Тетрис, но наверняка у них будет формальная система для круга.
Скорее всего у нас не получится с ней ознакомиться, так как наше
обоняние не настолько развито. Но как только будет расшифрован язык
представления (путём различных сенсорных инструментов и стандартной
техники обратного инженеринга), базовые концепции станут понятны любой
интеллектуально развитой цивилизации.
Даже если бы не существовало ни одной разумной цивилизации во вселенной,
формальная система для Тетриса и круга всё равно были бы логически
верными. Просто не нашлось бы существ, способных эти системы найти и
формализовать. Если внезапно появится разумная расса пришельцев, то они,
скорее всего, разработают свою формальную систему для описания
вселенной. Конечно, маловероятно, что они изобретут Тетрис, потому что
во вселенной нет аналогов этой игре. Тетрис — это один пример из
огромного числа формальных систем, загадок, которые не имеют отношения к
окружающей действительности. Даже такое понятие как натуральные числа
не всегда можно отнести к реальному миру, ведь можно представить себе
настолько большое число, что его нельзя применить к чему-либо во
вселенной, но при этом оно будет конечным.
Немного истории [3]
Давайте повернём колёса нашей машины времени и переместимся немного
ближе, в 1930-е. Великая депрессия опустошила Новый и Старый свет. Почти
все семьи из всех социальных слоев почувствовали на себе громадный
экономический спад. Осталось совсем мало убежищ, в которых люди могли не
боятся бедности. Некоторым людям повезло оказаться в таких убежищах.
Нас интересуют математики в Принстонском университете.
Новые корпуса, построенные в готическом стиле, придавали университету
ауру безопасности. Специалисты по логике со всей страны приглашались в
Принстон для основания нового подразделения. В то время, как большинство
американцев с трудом добывали себе пропитание, высокие потолки, стены с
узорами из дерева, ежедневные дискуссии за чашечкой чая, и прогулки в
лесу, составляли условия проживания в Принстоне.
Одним из математиков, проживавших в таком расточительном образе жизни,
был молодой человек по имени Алонзо Чёрч (Alonzo Church). Алонзо получил
степень бакалавра в Принстоне и его уговорили остаться в аспирантуре.
Алонзо чувствовал, что окружающая обстановка была чересчур роскошной. Он
редко появлялся на обсуждении математических проблем за чашечкой чая и
не любил гулять в лесу. Алонзо был одиночкой: он был более плодовит,
когда работал один. Тем не менее он регулярно встречался с другими
обитателями Принстона. Среди которых были Алан Тьюринг (Alan Turing),
Джон фон Нейман (John von Neumann) и Курт Гёдель (Kurt Gödel).
Эти четверо интересовались формальными системами. Они не уделяли особого
внимания физическому миру, их интересовала работа с абстрактными
математическими головоломками. В их головоломках было нечто общее:
математики изучали вопросы вычислений. Если у нас есть машина с
бесконечными вычислительными возможностями, то какие задачи можно на ней
решать? Можно ли решать задачи автоматически? Существуют ли
неразрешимые задачи и почему? Будут ли машины с разной архитектурой
одинаковыми по мощности?
Совместно с другими учёными Алонзо разработал формальную систему
названную Лямбда-исчислением. Система по сути была языком
программирования для одной из воображаемых машин. Она была основана на
функциях, которые принимают в качестве аргументов функции, и возвращают
функцию. Такая функция была обозначена греческой буквой Лямбда, что дало
название всей системе [4]. Используя эту систему Алонзо удалось построить рассуждения касательно вышеописанных вопросов и вывести ответы на них.
Независимо от Алонзо, Алан Тьюринг проводил подобное исследование. Он
разработал другую формальную систему (которую сейчас называют Машиной
Тьюринга), и используя её пришёл к выводам, подобным Алонзо. Позже было
доказано, что машина Тьюринга и лябда-исчисление имеют одинаковую
мощность.
В этот момент наша история останавливается. Я бы подытожил статью, и вы
переключились бы на другую страницу, если бы не началась Вторая мировая
война. Мир пылал. Войска США очень интенсивно использовали артиллерию.
Чтобы повысить точность армия наняла большую группу математиков, которые
постоянно решали дифференциальные уравнения, необходимые для
баллистических таблиц стрельбы. Быстро стало понятно, что такая задача
слишком сложна для ручного решения, для преодоления этой проблемы было
разработано специальное оборудование. Первой машиной для решения
баллистических таблиц был Mark I построенный IBM — она весила 5 тонн,
состояла из 750'000 деталей и могла совершать 3 операции в секунду.
Гонка, конечно, на этом не закончилась. В 1949 общественности был
показан Электронный Дискретный Переменный Автоматический Компьютер
(Electronic Discrete Variable Automatic Computer, EDVAC). Это был первый
пример реализации архитектуры фон Неймана, и был первой действительно
работающей машиной Тьюринга. На некоторое время работы Алонзо Чёрча были
отложены в сторонку.
В конце 50-ых профессор Массачусетского технологического института (MIT)
Джон Маккарти (John McCarthy ), тоже выпускник Принстона, начал
проявлять интерес к работе Алонзо Чёрча. В 1958 году он представил язык
обработки списков, List Processing language (Lisp). Lisp
задумывался как имплементация Лямбда-исчисления Алонзо, которая работает
на компьютерах фон Неймана. Многие компьютерные учёные отметили
выразительную мощь Lisp-а. В 1973 году группа программистов в
лаборатории искусственного интеллекта в Массачусетском технологическом
институте разработали железо, которое они назвали Lisp-машиной. Это была
аппаратная реализация лямбда-исчислений Алонзо.
Функциональное программирование
Функциональное программирование — это практическая реализация идей
Алонзо Чёрча. Не все идеи Лямбда-исчисления переросли в практическую
сферу, так как лямбда-исчисления не учитывали физических ограничений.
Тем не менее, как и ОО программирование, функциональное программирование
— это набор идей, а не набор четких указаний. Существует много
функциональных языков, и большинство из них делают одни схожие вещи по
разному. В данной статье я объясню наиболее широко используемые идеи из
функциональных языков используя примеры на Java (да, вы можете писать
функциональные программы на Java если у вас есть склонности к
мазохизму). В следующих нескольких разделах мы возьмём язык Java и
внесём в него изменения, чтобы он превратился в пригодный к
использованию функциональный язык. Начнём наше путешествие.
Лямбда исчисление было придумано для изучения проблем, связанным с
вычислениями. Функциональное программирование, стало быть, в первую
очередь имеет дело с вычислениями, и, на удивление, использует для этого
функции. Функция — это базовый элемент функционального
программирования. Функции используются почти для всего, даже для
простейших расчётов. Даже переменные заменяются функциями. В
функциональном программировании переменные — это просто синонимы (alias)
для выражений (чтобы нам не пришлось писать всё в одну строку). Их
нельзя изменять. В каждую переменную можно записать только один раз. В
терминах Java это означает, что все переменные объявляются как final (или const если имеем дело с C++). В ФП нет не-final переменных
final int i = 5;
final int j = i + 3;
Так как все переменные финальные, то можно сформулировать два утверждения. Нет смысла постоянно писать ключевое слово final,
и нет смысла называть переменные … переменными. Теперь мы внесём два
изменения в Java: каждое объявление переменной будет финальным, мы будем
обращаться к переменным как к символам.
Теперь вы, наверное, удивляетесь, как вообще можно написать что-либо
достаточно сложное на таком языке. Если все символы неизменяемые, то мы в
принципе не можем поменять состояние программы! Это не совсем верно.
Когда Алонзо работал над лямбда-исчислением, у него не было нужды
сохранять состояние, чтобы изменить его позже. Его интересовало
проведение операций над данными. Тем не менее, было доказано, что лямбда
исчисление эквивалентно машине Тьюринга. В нём можно делать всё то же,
что возможно в императивных языках. Как же нам достичь тех же
результатов?
Оказывается, что функциональные программы могут хранить состояние,
только они не используют для этого переменные. Они используют функции.
Состояние хранится в параметрах функции, в стеке. Если хотите сохранить
состояние, чтобы потом изменить его через время, то нужно написать
рекурсивную функцию. Например, давайте напишем программу, которая
переворачивает Java строку. Не забудьте, что все переменные объявляются
как final [5].
String reverse(String arg) {
if(arg.length == 0) {
return arg;
}
else {
return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1);
}
}
Эта функция довольно медленная, потому что она повторно вызывает сама себя [6].
Здесь возможна утечка памяти, так как множество раз создаются временные
объекты. Но это функциональный стиль. Вам может показать странным, как
люди могут так программировать. Ну, я как раз собирался вам рассказать.
Преимущества функционального программирования
Вы, наверное, думаете, что я не смогу привести доводы в оправдание
монструозной функции выше. Когда я только начинал изучать функциональное
программирование, я тоже так думал. Я ошибался. Есть очень хорошие
аргументы в пользу такого стиля. Некоторые из них субъективные.
Например, программисты заявляют, что функциональные программы проще
понять. Я не буду приводить таких аргументов, потому что всем известно,
что лёгкость понимания — это очень субъективная вещь. К счастью для
меня, есть ещё куча объективных аргументов.
Unit тестирование
Так как в ФП каждый символ является неизменяемым, то функции не имеют
побочных действий. Вы не можете менять значения переменных, к тому же
функция не может поменять значение вне своей области видимости, и тем
самым повлиять на другие функции (как это может случится с полями класса
или глобальными переменными). Это означает, что единственный результат
выполнения функции — это возвращаемое значение. А единственное, что
может повлиять на возвращаемое значение — это аргументы, передаваемые в
функцию.
Вот она, голубая мечта unit-тестеров. Можно протестировать каждую
функцию в программе используя только нужные аргументы. Нет необходимости
вызывать функции в правильном порядке или воссоздавать правильное
внешнее состояние. Всё что вам нужно, это передать аргументы, которые
соответствуют граничным случаям. Если все функции в вашей программе
проходят Unit-тесты, то вы можете быть намного более уверены в качестве
вашего ПО, чем в случае императивных языков программирования. В Java или
C++ проверки возвращаемого значения не достаточно — функция может
поменять внешнее состояние, которое тоже подлежит проверке. В ФП такой
проблемы нет.
Отладка
Если функциональная программа ведёт себя не так, как вы ожидаете, то
отладка — это пара пустяков. Вы всегда можете воспроизвести проблему,
потому что ошибка в функции не зависит от постороннего кода, который
выполнялся ранее. В императивной программе ошибка проявляется только на
некоторое время. Вам придется пройти через ряд шагов, не относящихся к
багу, из-за того, что работа функции зависит от внешнего состояния и
побочных эффектов других функций. В ФП ситуация намного проще — если
возвращаемое значение неправильное, то оно всегда будет неправильным, не
зависимо от того, какие куски кода выполнялись прежде.
Как только вы воспроизведёте ошибку, найти её источник — тривиальная
задача. Это даже приятно. Как только вы остановите выполнение программы,
перед вами будет весь стек вызовов. Вы можете просмотреть аргументы
вызова каждой функции, прямо как в императивном языке. С тем отличием,
что в императивной программе этого не достаточно, ведь функции зависят
от значений полей, глобальных переменных и состояний других классов.
Функция в ФП зависит только от своих аргументов, и эта информация
оказывается прямо у вас перед глазами! Даже больше, в императивной
программе проверки возвращаемого значения не достаточно для того, чтобы
сказать, правильно ли ведёт себя кусок кода. Вам придётся выследить
десятки объектов за пределами функции, чтобы удостовериться, что всё
работает правильно. В функциональном программировании всё, что нужно
сделать — это взглянуть на возвращаемое значение!
Проходясь по стеку, вы обращаете внимание на передаваемые аргументы и
возвращаемые значения. Как только возвращаемое значение отклоняется от
нормы, вы углубляетесь в функцию и двигаетесь дальше. Так повторяется
несколько раз пока вы не найдёте источник ошибки!
|
