История языков программирования: как Haskell стал стандартом функционального программирования



    Теоретические основы императивного программирования были заложены ещё в 30-х годах XX века Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, формировалась в 20-х и 30-х годах. В числе разработчиков математических основ функционального программирования — Мозес Шёнфинкель (Германия и Россия) и Хаскелл Карри (Англия), а также Алонзо Чёрч (США). Шёнфинкель и Карри заложили основы комбинаторной логики, а Чёрч является создателем лямбда-исчисления.

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

    Но теория так и оставалась теорией, пока в начале 50-х прошлого века Джон МакКарти не разработал язык Lisp (1958), который стал первым почти функциональным языком программирования. На протяжении многих лет у Lisp не было конкурентов. Позднее появились функциональные языки программирования APL (1964), ISWIM (1966) и FP (1977), которые не получили столь широкого распространения.

    Со временем Lisp перестал удовлетворять некоторым требованиям разработчиков программ, особенно с ростом объема и сложности программного кода. В связи с этим обстоятельством всё большую роль стала играть типизация. В конце 70-х — начале 80-х годов XX века интенсивно разрабатывались модели типизации, подходящие для функциональных языков.

    Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм. Появилось множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивалось число диалектов.
    ML (1973) – первый язык с типизацией Хиндли–Милнера;
    Scheme (1975) — это один из двух самых популярных диалектов языка Lisp;
    SASL, KRC, Miranda (1972–1985) – одни из первых ленивых языков;
    Hope (1980) – один из первых языков с алгебраическими типами данных.


    Хаскелл Карри

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

    История языка Haskell начинается в 1987 году. Один за другим появлялись новые функциональные языки программирования. После выхода Miranda (Research Software Ltd, 1985 год) возрос интерес к ленивым вычислениям: к 1987 году возникло более дюжины нестрогих чисто функциональных языков программирования.

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

    Так появился Haskell. Он был назван в честь одного из основателей комбинаторной логики Хаскела Кaрри (Haskell Curry).

    К концу 1980-х годов было создано много функциональных языков. Часть из них оказали значительное влияние на Haskell:



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

    Haskell 1.0 — 1.4


    Первая версия Haskell (Haskell 1.0) была выпущена в 1990г. Попытки комитета вылились в серию реализаций языка (1.0, 1.1, 1.2, 1.3, 1.4).



    Haskell 98


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

    В феврале 1999 года стандарт языка Haskell 98 впервые был опубликован, как «The Haskell 98 Report». В январе 2003 года измененная версия была опубликована как «Haskell 98 Language and Libraries: The Revised Report». Язык продолжил стремительно развиваться, реализация компилятора Glasgow Haskell Compiler (GHC) представляет фактический стандарт языка.

    Haskell 2010


    Современный стандарт Haskell — Haskell 2010 — был анонсирован 24 ноября 2009 года; GHC поддерживает его с версии 7.0.1.

    По сравнению с Haskell '98 он содержал следующие изменения:

    • Do и If Then Else
    • Иерархические модули
    • Объявления пустых переменных
    • Решение устойчивости
    • Интерфейс сторонних функций
    • Линейный синтаксис комментариев
    • Охраняющие паттерны
    • Облегченных анализ зависимостей
    • Указания для языка (pragma)
    • Отсутствие паттернов n+k



    Дополнительные изменения были опубликованы 7 января 2011 года:

    • Отсутствие контекста типов данных
    • Маркированные списки переменных

    Haskell продолжает развиваться и сегодня. Но стабильные версии опираются на стандарты 1998 и 2010 года соответственно. Но кроме них в Haskell включается множество расширений, постоянно вносятся новые идеи. Над языком работают нескольких странах мира — это Англия, Нидерланды, Америка и Австралия. Интерес к Haskell вызван популярностью многопроцессорных технологий. Модель Haskell хорошо подходит для параллельных вычислений.

    От создателя Haskell


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

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

    Популярность


    На сайте Github сейчас занимает 23-ю строчку по популярности среди языков программирования.

    В индексе TIOBE он находится на 38 месте:



    В рейтинге RedMonk Haskell стоит достаточно высоко — на 16-й позиции. В данном случае рейтинг строится на основе оценки сочетания популярности на GitHub, плюс активность обсуждений на Stack Overflow.

    Проекты


    На Haskell реализовано много сложных проектов:

    • Компиляторы и другие средства разработки.

    • Распределенная система управления версиями Darcs.

    • Оконный менеджер xmonad.

    • Сервер Web-приложений HAppS.

    • Интерпретатор/компилятор Pugs для языка Perl 6.

    • Операционная система House.

    • Язык описания аппаратных средств Lava.

    • Система обработки натурального языка LOLITA.

    • Системы доказательства теорем Equinox / Paradox и Agda.

    Facebook


    Фильтрация спама — одна из самых главных задач, которую решают инженеры Facebook. Крупнейшая социальная сеть обрабатывает сообщения от более 1,5 миллиарда человек, так что можно оценить масштаб проблемы. В 2015 году компания внедрила новые антиспамерские фильтры, для разработки которых использовала язык программирования Haskell.



    Несмотря на молодость, экспериментальный статус и относительно низкую популярность, Facebook выбрал именно Haskell для создания важного модуля. Один из инженеров Луис Брэнди (Louis Brandy), который входит в группу разработчиков нового антиспамерского фильтра, провел два года за этим проектом вместе с коллегами. В интервью Wired он объяснил, чем они руководствовались.

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

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

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

    Евгений Козлов в своем блоге рассказал о впечатлениях от работы с Haskell:



    Недостатки

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

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

    Положительные стороны

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

    Если написан код, то его сложно интерпретировать двумя способами. Например, нельзя перепутать применение функции и ссылку на функцию, как в Scala, так как в Haskell функции являются объектами первого класса. Или, например, нельзя перепутать функцию с типом или классом, так как все функции должны начинаться с маленькой буквы, а типы/классы – с большой.

    Свойство языка, без которого разговор о Haskell был бы бессмысленным – это полиморфизм. Вряд ли будет преувеличением, если я скажу, что Haskell является языком с максимальным количеством переиспользованного кода. Любая хоть сколько-нибудь повторяющаяся функциональность выносится в абстракцию.
    Поделиться публикацией
    Комментарии 47
      +1
      Не увидел источников: http://www.ibm.com/developerworks/ru/library/l-haskell/index.html
        +2
        В русской транскрипции Шейнфинкеля все таки именуют Моисеем.
        • НЛО прилетело и опубликовало эту надпись здесь
            +1
            Автор придерживается точки зрения:
            Положительные стороны
            В первую очередь, конечно же чистота языка. Чистота в обоих смыслах: чистота функций и полное отсутствие ООП-парадигмы. Это очень здорово...
            то есть считает и Erlang и LISP — «зашкваренными».
              –6
              Э-э-э-э-э…

              Что может быть чище AST? То есть, если мы говорим о семантической чистоте — то Haskell рядом не валялся с LISPом. А если о полном отсутствии ООП-парадигмы (не уверен, что я понимаю, что кроется за этими очень нынче модными словами, но в любом случае) — то Haskell рядом не валялся с Erlang’ом.
                +3
                Речь идет о той чистоте, которая означает отсутствие состояния. Т. е. когда результат функции зависит только от её аргументов.
                  0
                  Я правильно понимаю, что на хаскеле в принципе невозможно реализовать функцию, которая дописывает 1 байт в файл, а потом возвращает его размер?
                    0
                    Возможно. Но есть четкая граница между чистыми функциями и функциями с побочными эффектами, использующими монаду IO например.
                      0
                      У этого, насколько я понимаю, есть один значительный эффект: возможность на уровне компилятора собрать всё чистое и приготовить для отложенного, легко распараллеливаемого вычисления. Так? Кроме этого — все остальное уже религиозный спор.

                      Или я ошибаюсь?

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

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

                          Стало быть, остается «чистое — отдельно» ну и «lazyness», конечно.

                          Вот теперь у меня есть вопрос, который я всегда задавал и всегда мне отвечали конструктивными минусами вместо слов. Задам еще раз :)

                          Вот берем, скажем, эрланг и программиста уровня «умнее стиральной машины „Bosch“». И он нам пишет вотсап. Потому что виртуальная машина и «умри, если споткнулся» — распараллеливается ничуть не хуже. Да, компилятор по рукам не надает, но люди еще со времен ассемблера как-то более-менее научились с этим справляться. Я обычно понимаю, где у меня чистая функция, а где — не очень. Более того, я все нечистое запущу сбоку и оно мне мое чистое не испортит.

                          Что именно я упускаю из того, что делает вот эту «абсолютную чистоту» такой киллер фичей? Только, если это возможно, очень прошу — без примеров из вычислительной математики (здесь никто и не спорит) и абстрактных тезисов (типа «чистый лучше, чем нечистый»).
                            0
                            Да нет никакой киллер — фичи.
                            Все это абстрактный спор, далекий от практики программирования.

                            А фильтры спама в Фейсбуке с таким-же успехом реализуются на любом другом языке.
                              0
                              Гарантии? А так, звучит как «что делает вот эту статическую типизацию такой киллер фичей», при том, что каждый первый может привести пачку доводов и за, и против.
                                0

                                Про статическую типизацию я умею спорить аргументированно. Здесь я в предмете плаваю, потому и спрашиваю. Вот случайный комментарий рядом: «Haskell в этом смысле чистый, Erlang и Lisp — нет». Внимание, вопрос: и чё? Не то, чтобы даже «почему это зорошо?», нет. «Почему на этом имеет смысл заострять внимание?».


                                Тем более, что мы выше разобрались с IO монадой, это уже как бы не совсем так.

                                  0
                                  А почему бы и не обратить на это внимание при описании преимуществ? Ведь в нем действительно на чистоту (на самом деле на типы, но ладно) обращается особое внимание.

                                  В том же эрланге ничего не мешает запихать функцию, рассылающую сообщения, в lists:map/2 вместо lists:foreach/2. Оно конечно будет работать, но порядок вычислений однажды может начать давать какие-нибудь интересные побочные эффекты. А в хаскелле компилятор сразу ткнет носом в то, что похоже написано не то, что хотелось написать. Оно может и непрактично порой, но как идеализированная концепция привлекательно.
                                    0

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


                                    Я бы даже сказал, «чистая, типа „идеализированная“ концепция» :)

                                0
                                На самом деле не такой простой вопрос как кажется. Можно много холиварить на «прикладном» уровне, чем в основном и занимаются, но это скучно да и бессмысленно.

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

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

                                  Это вы сейчас прямо как из рекламной брошюры по OTP кусками скопипастили :)


                                  Я понимаю же, какие плюсы у stateless вообще (там, где stateless уместен, но «уместность» — это опять на похоливарить, так что замнем, тут это ни при чем вовсе).


                                  Я не понимал, чем эрланг хуже. У меня просто складывалось такое ощущение, что haskell — про «а давайте все запретим, чтобы дебил-программист не отстрелил себе ногу», как golang. С появлением в дискуссии слова «академический» все встало на свои места. Это действительно идеальный язык для академического моделирования (whatever it means); тут очень заметно, что эрланг разрабатывался бизнесом, а хаскел — наукой.


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

                                    0
                                    А что такое OTP? :) Понятия не имею, написал исходя из своего опыта разработки.

                                    Я вообще не понимаю разговоров вида X лучше/хуже Y. Больше всего воплей обычно от людей, которые ни того ни другого обычно и в глаза не видели, но зато «точно знают» что лучше.

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

                                    Лично я и изучал и эрланг и хаскель, но не собираюсь делать никаких однозначных выводов в пользу того или другого. Все зависит от задачи.
                                    +1
                                    У меня просто складывалось такое ощущение, что haskell — про «а давайте все запретим, чтобы дебил-программист не отстрелил себе ногу»

                                    Вот вы хитрите. Как будто Эрланг не про это :) Покажите Эрланг тому же лисперу. Он тоже пожалуется на ограничения — иммутабельность данных, единичные присваивания и падение процесса при сфейлившимся паттерн-матчинге.
                                    Хаскель развивает идею «мощь в ограничениях» дальше, предлагая статическую типизацию и элегантное отделение чистого кода от кода с побочными эффектами. Но он никак не запрещает все, иначе невозможно было бы взаимодействие с нашим императивным миром.
                                    Ограничения в Эрланге и Хаскеле нужны для помощи программисту. Это не значит, что их используют инвалиды ума. Просто человек существо такое — совсем не косячить он не может.
                                    Кстати, а чего мы все про Эрланг? Да это крутой нишевый инструмент, но не более. Телеком, работа с сетью его конек. Написание же на нем вещей типа Wings 3D будет малоинтересным занятием.
                                      0

                                      Wings 3D — наверное. Но вот Riak на нем же написали, а это как бы не совсем телеком.

                                      0

                                      Я бы сказал бы, что Erlang разрабатывался инженерами для решения своих задач. На эту тему очень интересна дискуссия: Joe Armstrong and Simon Peyton Jones discuss Erlang and Haskell

                                        0

                                        Спасибо! Дискуссия и правда очень интересная, как-то до этого прошла мимо меня.

                                    +2
                                    Позволяет проще, как говорится, reason about the code.
                                    +1
                                    Мемоизируются только CAFs и санки в конкретных выражениях.

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

                                      Я вроде видел хаки на эту тему, не могу отыскать ссылку, к сожалению. Типа, как доползли до N гигов памяти — щелкаем по доминошке. Но история про «все мемоизовал, сожрал всю память и закуклился» очень смешная, конечно. В хорошем смысле: это же еще одно явное указание на академическую природу языка.

                                        +1
                                        Почему ж указание? Автомемоизации в хаскеле нет.
                            0
                            Чистота функций — в смысле отсутствие побочных эффектов. Haskell в этом смысле чистый, Erlang и Lisp — нет.
                            0
                            А где в Эрланге и в Лиспе ООП?

                            Хотя… Для правоверных функциональщиков, '!' может являться признаком ООП ереси.
                              +3
                              Ну, как минимум в Common Lisp есть Common Lisp Object System.
                                +1
                                В Common Lisp ООП оопестее всех ООпов в других языках. Гуглите CLOS и MOP.
                                Erlang наиболее близок к оригинальным идеям Алана Кея, в которых ООП был не в наследовании, а в сообщениях.
                                +3
                                полное отсутствие ООП-парадигмы

                                Есть мнение, что автор «ниасилил» ООП.
                                  0
                                  Оно вообще очень сложное. На самом деле его мало кто действительно осилил.
                              –2
                              Что-то звучит как реквием…
                                0

                                Караван идёт

                                  –1
                                  В индексе TIOBE Haskell находится на 38 месте (появился в 1990г), тогда как:
                                  Lisp — на 31, 1958г
                                  Scheme — 34, 1975г
                                  Scala — 32, 2003г.
                                  Видим, что два языка, появившиеся раньше, являются и более популярными. Как-то это не очень согласуется с термином «общепринятый стандарт». Вот было бы просто «История и перспективы....» и вопросов бы не было. В других двух упомянутых рейтингах относительные позиции у Haskell лучше, но всё же пафос так мешает…

                                  ps: и вообще перспективы так описаны, что действительно пессимизм в отношении Haskell возникают…
                                    0
                                    Потому что когда говорят, что всё будет прекрасно, но приводят слабые доводы, то мнение само собой склоняется в другую сторону. А караван пусть идет ))
                                      0
                                      Видим, что два языка, появившиеся раньше, являются и более популярными.

                                      Ну так Haskell — "чисто функциональный", а другие два языка — нет.


                                      Опять же, некая часть популярности Scala берётся от JVM платформы. В языке намешано всё что угодно и нередко предполагается (поначалу) "писать как на джаве". Не пытаюсь доказать, что Scala "недостаточно функциональна", но не уверен, что (очень) мультипарадигменные языки могут быть "стандартом" в чём-то одном.


                                      Собственно, не удивлюсь, если Clojure популярнее чем Common Lisp. А в рейтинге TIOBE вообще некий "обобщённый" лисп присутствует: вполне возможно, что туда всё лиспо-подобное попало.

                                        0
                                        Вот в таком свете, смысл статьи стал понятен — не лучше, а просто «чище».
                                  +1
                                  1. Ну так как он стал-то стандартом функционального программирования?

                                  2. А точно стал? Как это определяется?

                                  3. И в конце концов, что такое стандарт функционального программирования? «Язык считается стандартом функционального программирования если находится на 38 позиции в индексе TIOBE»?

                                    0

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

                                      +2
                                      Ох. Не путайте тёплое с мягким. То что Хаскель проедставляет собой эталонный академический язык функционального программирования не имеет никакого отношения ни к его популярности, ни к его применимости в продакшене ни даже к количеству основанных на нём университетских курсов функционального программирования. Это означает только то, что «чистое функциональное программирование — это хаскель».
                                      +2
                                      Лисп изначально основан на теории рекурсивных функций, а не на лямбда исчислении.
                                        +1
                                        От создателя Haskell
                                        Curry — встраиваемый язык программирования общего назначения, реализованный поверх языка Haskell


                                        Чем докажете? Вроде бы Curry делали совсем другие люди, нежели Haskell.

                                        Вообще, статья донельзя обзорная и короткая. Писали чисто ради денюжки?
                                          0
                                          APL все-таки имеет живых потомков — J и K.
                                          А Scheme — динамически типизированный язык, как и большинство Lisp-ов.
                                            +1

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


                                            Нет ООП поэтому нет проблем с приведениями

                                            ничего не мешает сделать ООП-язык и запретить в нём downcasting на уровне компилятора. Сила типов хаскеля не в «отсутствии ООП».


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

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

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

                                            Самое читаемое