А ещё это язык из которого в Lisp сбежали почти все скобки.
Эта заметка о необычном, но очень интересном языке программирования, который я нежно люблю и использую на протяжении десятка лет. Он не самый новый, не самый модный, и даже не самый странный из языков на котором люди сообщают компьютеру и друг другу свои мысли и пожелания, однако репутацию он себе заработал своеобразную. Чего только стоит неофициальный и шуточный девиз языка: "Избегай популярности любой ценой!". Так что иногда Haskell можно встретить в числе эзотерических языков программирования, несмотря на хорошо развитое сообщество, постоянно развивающийся компилятор (последняя версия ghc-9.4.8 вышла в минувшую пятницу), внушительную коллекцию библиотек и промышленное применение (оконный менеджер Xmonad, универсальный конвертер pandoc, подсистема Semantic в GitHub, несколько подсистем в Meta*, а в 2022 году специалистов по Haskell начала набирать компания Tesla).
Три кита, на которых строится концепция языка: чистая функциональность, ленивость, и алгебраическая система типов, с параметрическим полиморфизмом, в свою очередь, опираются на могучих черепах: лямбда-исчисление Чёрча, изоморфизм Карри-Ховарда, вывод типов Хиндли-Милнера. Черепахи плавают где-то в Космосе теории категорий. Поскольку меня попросили написать о Haskell по-человечески, черепах и прочее мы пока трогать не будем, и даже монады не упомянем, вопреки распространённому мнению, программировать можно и без них. Вернее, можно до поры не знать что это такое, вполне продуктивно программируя.
Лаконичность языка позволяет выразить многое в небольшом, так что я буду строить рассказ вокруг примеров кода. Вы можете не разворачивать у себя рабочую среду для разработки на Haskell, а поиграть с приведённым в статье кодом с помощью онлайн-транслятора Replit.
Простая программка, с импортом, выводящая "Hello world" с незамысловатым диалогом выглядит не сильно подозрительно:
Есть точка входа в виде функции main. Есть что-то вроде переменной name. Блоки кода оформляются отступами, как в Python. Разве что, скобок при вызове функций не видно, но ничего сверхъестественного пока не наблюдается. Последовательность команд ввода-вывода, всё вполне адекватно задаче.
Давайте приведём ещё один классический пример — функция, рекурсивно вычисляющая числа Фибоначчи:
Заметно, что синтаксис языка экономит на скобках, используя их только там, где необходимо, но, в целом, здесь тоже всë понятно. Вместо ветвления, как видно, можно использовать сопоставление с образцом, так тоже бывает во многих современных языках.
Если мы запустим интерпретатор с такой программой, то без труда вычислим 10-е или 20-е число, а то и целый кусочек ряда:
Синтаксис из-за отсутствия скобок непривычный, но тоже вполне понятный: функция map применяет функцию fib к списку аргументов. В каком-нибудь JavaScript или Julia этот приëм тоже свёлся бы к вызову метода map. Этот пример показывает, что функции в Haskell могут быть аргументами других функций, что, в общем, тоже неудивительно для функционального языка и встречается в наше время повсеместно.
Однако, попытка вычислить 30-е число Фибоначчи вызовет неожиданные затруднения. Оно вычислится, но это займëт неприлично заметное время. Неужели Haskell настолько медленный? Давайте дословно переведём эту же функцию на шустрый Julia в том же Replit:
Эта программа работает быстрее, но на 40-вом числе и у Julia начинаются проблемы. Дело, конечно же, не в языке, а в алгоритме. Наивный рекурсивный способ требует 1.6ⁿ шагов для вычисления n-ного числа, что для 30-го превышает уже 1.3 миллиона! Разумеется, вместо рекурсии надо использовать простой цикл с двумя переменными:
У этой программы нет никаких ограничений, кроме разрядности целых чисел, которые легко решаются использованием типа BigInt.
При попытке перевода этой программы с Julia на Haskell выяснится, что в Haskell нет циклов. И переменных тоже нет. Вообще нет. Потому что этот язык бескомпромиссно чистый функциональный.
Что значит быть чистым?
Когда говорят, о функциональном программировании, то обычно имеют в виду, что в рамках этой парадигмы функции могут быть входными данными или результатом вычислений. Сейчас так могут делать практически все основные ЯП от Java (начиная с 8 версии) и C++ (с библиотекой boost), до Python и JavaScript от рождения.
Если говорить более строго, то функциональная парадигма предполагает, что функции и процедуры являются объектами первого класса, то есть, они никак не ущемлены в правах по сравнению с прочими данными. Предпочтение при этом отдаётся чистым функциям.
Чистая функция семантически эквивалентна математической функции, то есть отображению одного множества на другое, и не имеет побочных эффектов. Под побочным эффектом понимается изменение состояний переменных, портов, и прочих элементов вычислительной среды. В математике процесс вычисления синуса не влияет на процесс вычисления логарифма. Результат вычисления обеих этих функций определяется исключительно их аргументами.
Чистые функции хороши тем, что их поведение абсолютно предсказуемо, они идеально комбинируются, оптимизируются и распараллеливаются, поскольку порядок вычисления тоже не влияет на результат.
Ещё в FORTRAN 77 появилось ключевое слово pure, подсказывавшее и компилятору и программисту, что функция чистая и её можно каким-то образом оптимизировать. Локальные переменные и политика видимости переменных в процедурных блоках, абстракция и инкапсуляция в большинстве современных языков программирования тоже решают задачу предсказуемости и модульности программ, понижая так называемую адгезию программных блоков, то есть, взаимное влияние во время исполнения.
В чистом функциональном Haskell дела обстоят так, что ничего кроме чистых функций в нём использовать нельзя. Это значит, что в нём вообще не предусмотрено привычных переменных, счётчиков, циклов или объектов, меняющих своё внутреннее состояние. Даже последовательность вычисления выражений не определена и отдаётся на волю компилятора.
В этом языке есть только константы, функции и их композиция. Роль переменных играют аргументы функций, роль переходов в потоке выполнения программы достаётся вызовам функций, роль циклов исполняет рекурсия, а композиция определяет поток вычислений.
Ну как, страшно? На самом деле, ничуть. Вот как выражается итерационный процесс вычисления чисел Фибоначчи на Haskell:
Здесь появилось локальное определение функции, в данном случае, мы завели себе вспомогательную функцию go, принимающую три аргумента: счётчик i и две "переменные" a и b. Хвостовой рекурсивный вызов функции в этом случае транслируется в плотный цикл, которому требуется лишь n шагов для вычисления n-ного числа Фибоначчи, так что теперь ограничением для вычислений становится память для оперирования с тремя числами, а не время вычисления.
Существует теорема, утверждающая, что любой цикл можно выразить рекурсией (обратное не верно), а любую примитивную рекурсию — циклом. Чистота функций приводит к тому, что конкретный вычислительный процесс (рекурсивный или итеративный) никогда не будет сказываться на результате, а повлияет только на эффективность вычислений. Так что программисту на Haskell нужно научиться думать рекурсивно, а транслятор уже превратит рекурсивные программы в циклы.
"Что же так сложно-то!", — воскликнете вы, — "Почему бы не сделать в языке специальные циклические конструкции, минуя рекурсивный этап?" И будете правы. Дело в том, что ещё одна важная особенность Haskell — его ленивость позволяет программисту самому легко написать нужную ему универсальную циклическую конструкцию с нужными свойствами. А точнее, все они уже реализованы в стандартной библиотеке в виде обычных функций, всевозможных рекурсивных схем: свёрток (катаморфизмов) и развёрток (анаморфизмов).
Так что в постоянной работе программисты редко сами пишут рекурсивные определения, а прибегают к различным рекурсивным схемам. Например, итеративную функцию fib' можно записать без явной рекурсии так:
Здесь функция iterate многократно повторяет преобразование для пары значений, оператор (!!) выделяет n-ную итерацию, а функция fst из пары извлекает первый элемент. Это не особый синтаксис, а обычные функции. Например, функция iterate определена так:
Она генерирует ленивый бесконечный список итераций функции f, который потом лениво обрабатывает оператор (!!). Так что пора нам, наконец, поговорить о лени в программировании.
Наша стратегия — лень!
Математики народ своеобразный. Вместо функции F(n), возвращающей n- ное число Фибоначчи, они предпочитают работать со всей последовательностью сразу, как с единым объектом. Например, у последовательности можно выяснить какое по счëту число превысит миллион, или к чему стремится отношение соседних элементов, можно вычислить функцию, сгенерированную рядом Фибоначчи, или узнать на каких местах располагаются числа Фибоначчи, кратные 17, или вычислить цикл Пизано — последовательность Фибоначчи в модулярной арифметики.
Для каждой из этих задачек несложно написать соответствующие циклы, перебирающие последовательность и отвечающие на конкретные вопросы. Но ленивость языка Haskell предлагает иной подход, более универсальный и главное, модульный.
Поскольку результат чистой функции не зависит от способа еë вычисления, то мы вольны выбирать одну из стратегий: строгую и нестрогую. В строгой стратегии сначала вычисляются все аргументы функции, а потом еë тело с аргументами, переданными по значению или по ссылке. Так работает подавляющее большинство языков программирования. Однако возможен и иной вариант: значения аргументов вычисляются по мере необходимости и исходя из логики тела функции. Тогда, если какой-то аргумент в ходе вычисления функции не требуется, то его можно и не вычислять вовсе. И напротив, если какое-то значение функции уже известно (вычислено раньше), то поскольку изменяемых величин или переменных нет, можно сразу подставить известное значение, не тратя время на его повторное вычисление (при этом можно использовать техники редукции дерева вычислений или мемоизации). Такая стратегия называется ленивой.
При вычислении композиции строгих функций f(g(h(x))) поток данных идёт справа налево от аргумента функции h к функции f, Для ленивых функций происходит поток запросов на вычисления, идущий слева направо от функции f к функции h и её аргументу.
Haskell по умолчанию придерживается ленивой стратегии везде, где только можно. В качестве примера, создадим крайне неприятный список, в котором только последний элемент нормальный:
Все остальные либо вызывают исключение, либо приводят к зависанию программы (первый честно суммирует все натуральные числа, а ω представляет собой незамутнëнную бесконечную рекурсию). Однако это не помешает нам кое-что с ним делать. Например, мы можем выяснить, что в списке четыре элемента с помощью стандартной функции length, извлечь безопасный элемент по индексу, или "обезвредить" весь список функцией const, которая для любого аргумента, возвращает указанное значение.
Этим функциям, как и функции map, абсолютно всë равно какие именно элементы списка они обрабатывают, так что взрывоопасные элементы не будут вычислены без необходимости.
Мне нравится последний способ избежать "взрыва" — с помощью оператора (<>) приклеить опасный список к концу бесконечного ряда натуральных чисел, после чего с ним можно будет делать всё, что угодно :)
Этот пример был нарочитым. Давайте создадим что-нибудь более полезное, например, бесконечную последовательность Фибоначчи:
Здесь мы снова определили локальную функцию go, но теперь её результаты не возвращаются сразу, а с помощью оператора ( : ) помещаются в список. Попытка посмотреть чему равно fibs приведёт к выводу на экран простыней чисел, который придётся прекращать насильно. Так что мы сразу будем пользоваться вспомогательными функциями, для выделения конечных частей списка.
Пример 1.
Вот первые 10 элементов последовательности Фибоначчи:
Пример 2.
Элементы последовательности, не превышающие миллиона и их количество:
Пример 3.
Числа Фибоначчи, делящиеся на 17:
В функциональном языке скобок может быть слишком много, поэтому от них стараются избавиться. Оператор $ позволяет не писать скобки в композиции функций:
Примечательно, что это не какой-то особый синтаксис, оператор аппликации $ определяется как рядовая функция:
Пример 4.
Последовательность отношений соседних чисел Фибоначчи:
Здесь мы из целочисленной последовательности сначала сформировали последовательность чисел с плавающей точкой, а потом вычислили отношения. Функция tail отбрасывает у списка первый элемент и тем самым сдвигает его на один шаг влево. Функция zipWith объединяет два списка с помощью указанной операции.
Пример 5.
Выделение циклов Пизано, то есть циклов в последовательности остатков от деления чисел Фибоначчи по указанному модулю:
Здесь мы снова определили локальную функцию, которая определяет, что цикл завершён по идущим подряд числам 1 и 0. Их сумма будет равна 1, что опять начнёт ряд 0,1,1... Конструкция со стрелкой определяет анонимную функцию.
Посмотрим на несколько циклов Пизано:
Здесь точка обозначает не вызов метода, а композицию функций.
Можно исследовать структуру циклов с помощью простецкой вспомогательной функции showStruct, выделяющей положения нулей:
Напоследок получим первые 10 модулей, для которых число нулей в циклах Пизано содержит ровно один ноль:
Фигурные скобки с двоеточием позволяют вводить многострочные выражения в интерпретаторе.
Я думаю, вы уже получили некоторое представление о том, как мыслит программист на Haskell, решая несложные типовые задачи. В чëм же состоят преимущества чистого функционального подхода?
Во-первых, программы становятся невероятно формализуемыми, предсказуемыми и для них работают теория вычислимости, лямбда-исчисление и теория типов. Всё это позволяет производить верификацию кода, а компилятору развязывает руки для оптимизации.
В-вторых, решение задач распадается на композицию небольших универсальных функций, каждая из которых "делает одно дело, но делает его хорошо". Этот же принцип модульности реализован в инструментах для координации работы утилит Unix, таких как bash, zsh и им подобных. Множество относительно небольших утилит работают независимо друг от друга, а связь осуществляется ленивым потоком данных, который генерируется файлами, либо устройствами, либо программами как /dev/random, или yes, генерирующими "бесконечные списки". Все утилиты ленивы и по возможности обрабатывают данные на лету, не занимая памяти больше, чем надо для выполнения работы.
В качестве примера добудем десять случайных однобайтных целых чисел с помощью утилит, написанных разными авторами в разное время, но работающими слаженно
Как видите, в философии Unix много черт чистого функционального подхода, а Haskell — это не язык экстремистов и фриков.
К практической стороне добавляется мощнейшая теоретическая база и строгая типизация, которая не позволяет написать ерунды (а если и позволяет, то только ерунду, имеющую вид некоторого верного утверждения, иначе не пропустит компилятор). Принцип "избегания популярности любой ценой" не позволяет разработчикам в угоду моде отойти от основополагающих ограничений, которые накладывает парадигма языка, но вместе с тем и отказаться от выгод, которые даёт это ограничение.
Можно сравнить это с железной дорогой, которая ограничивает движение составов сетью путей (нельзя вызвать электричку к любому дому, а потом поехать в чисто поле), налагает ряд технических ограничений на то, какими могут быть вагоны, но при этом даёт возможность существенно увеличить объём грузопотока, и использовать автоматику для диспетчеризации, оптимизации и безопасности движения.
Строгое и неукоснительное следование принципам чистого функционального программирования позволило создать, отработать и исследовать огромное число интересных и крайне полезных техник. Именно здесь родились, были изучены и внедрены такие вещи как персистентные контейнеры, мощная система автоматического вывода типов, и доказательства теорем, тестирование, ориентированное на свойствах QuickCheck, линзы, линейные типы, комбинаторный парсинг и другие инструменты, которые сейчас стали фишками модных языков, типа Rust, Python или Closure.
Я ничего не написал в этой заметке ни про каррирование функций, ни про алгебраические типы, ни про пресловутые монады, которые позволили ленивому языку, не изменив себе, дать возможность писать императивные программы, ни про классы типов и мощные инструменты для абстракции данных, вычислительных процессов и времени. Если интересно, могу продолжить.
────────────────────────
Хотите, чтобы в вашей ленте Дзена было больше интересных и глубоких материалов? Подскажите алгоритму Дзена, что там нравятся публикации, подобные этой, подпишитесь, поставьте лайк или прокомментируйте.
Давайте формировать информационную среду вместе!