Хаскелл, детище британских учёных

Есть языки программирования, которые просто блестящи. Но есть и такие, которые с матовым покрытием.
       Из заметок наблюдательного программиста

Язык Haskell занимает заметное место среди языков функционального программирования. Вот что о нём пишет Миран Липовача:

Язык Haskell был придуман несколькими по-настоящему умными ребятами (с диссертациями). Работа по его созданию началась в 1987 году, когда комитет исследователей задался целью изобрести язык, который станет настоящей сенсацией. В 1999 году было опубликовано описание языка (Haskell Report), ознаменовавшее появление первой официальной его версии.

Оказывается, бритаские учёные (из университета Глазго) хотели прославиться! Впрочем, они не первые и не последние. Похожее мнение было высказано мне сотрудником РАН, автором монографии о функциональном программировании:

• «Этот язык создавался с целью защиты диссертаций»,
• «Концепцию монад считаю несколько спекулятивной»,
• «Для русского уха "монада" звучит как иностранное слово, что повышает его статус в речи наших программистов»,
• «Слабая понятность понятия "монада" позволяет употреблять его в любых правдоподобных контекстах без особых размышлений о смысле фраз».

Мнение: «Один разработчик на Haskell заменяет пять программистов на JavaScript»

... новый техдиректор решил переписать всё на Haskell. Сначала он написал небольшой сервер — и за два года в нём ничего не сломалось. После этого он нанял двух разработчиков (одним из них был я). Вместе мы за полгода переписали весь JS-код на Haskell.

Когда новый сервер запустили, он работал без багов и ни разу не упал в продакшене. А благодаря статическим типам, компилятору и другим преимуществам Haskell мы очень быстро пилили и выпускали новые фичи.

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

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

Мнение: «Это как чинить движок через выхлопную трубу»

Витринный случай — кусок кода сишного и кода хаскельного, который якобы реализует qsort. Проблема в том, что там сравниваются реализации разных алгоритмов. Хаскельный код сортирует списки, а не массивы, и использует голову списка для разбиения его на два — плохое (O(N^2)) поведение на упорядоченных данных, часто встречающееся в реальной жизни, гарантировано. Во-вторых, правильно написанная qsort использует лишь O(log N)[1] дополнительной памяти, сколько использует хаскельный код — одному Богу известно, а алгоритмы с разными O() — это разные алгоритмы и есть. Поэтому приведенный хаскельный код гарантированно не попадет в продакшн и является лишь игрушкой. На самом деле на хаскеле можно написать настоящую in-place quicksort, но с использованием монад и выглядит это уродливее, чем код сишный. Все это хаскеллофаги отлично знают, но троллинга ради и чтобы не отпугивать новичков, приводят короткий и бесполезный код.

Синтаксис Хаскелл

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

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

f(x)

my_fun :: Int -> Int -> Int

int my_fun (int, int);

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

my_fun x y = x + y

f a b

Это опять не соответствует традициям в математике. В математике и на Фортране и Алголе, которые были созданы математиками и для математиков, пишут так:

f(a, b)

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

f a b

Или вот такой вводящий в заблуждение синтаксис:

prepare_length :: Double -> Double
prepare_length line =
    line * coefficient
    where coefficient = 0.4959

line *= coefficient;

-- функция с тремя аргументами целого типа
some_summ :: Integer -> Integer -> Integer -> Integer
some_summ a b c = a + b + c

-- одноимённая функция с двумя аргументами целого типа
some_summ :: Integer -> Integer -> Integer
some_summ a b = a + b

f $ g x

f (g (x))

Похоже, эту фишку придумали последней, когда на клавиатуре закончились клавиши, осталась только «$». Иначе объяснить странный выбор не получается. А теперь попробуйте угадать: для чего в Хаскелле используются квадратные скобки? Думаете, для массивов? Нет, для списков! А как же тогда обращаются к элементу массива по индексу? Не поверите, с помощью восклицательного знака!

А вот ещё одна «особенность». Наверное, понятно, почему нечистые функции нельзя использовать внутри чистых. Но Хаскелл запрещает использование чистых функций внутри монадических. Почему?! Ведь чище чистых функций нет ничего, они гарантируют ссылочную прозрачность! Хаскелл же принуждает «оборачивать» чистый тип в монаду. Знаете, какое имя носит функция, которое это делает? Она называется «return»! А почему бы её не назвать «почесать левое ухо правой пяткой»? И то, и другое — не пришей к звезде манжет. К вызову чистой фунции они имеют одинаковое отношение. «Return» означает «возвратить, вернуть». В Хаскеллу у этой функции совершенно обратная роль — вызов функции и получение значенения, которое потом «оборачивается» монадой.

«Непонятность» Хаскелл

Пишущие о Haskell почему-то забывают, что «физик должен уметь объяснить простой уборщице, чем он тут занимается». «Непонятность» Haskell, связана, не в последнюю очередь, с почти полным отсутствием хороших книг по нему. А хороших книг нет потому, что нет хороших авторов. Отсутствие последних можно объяснить законами Дарвина: чем ниже численность какой-то популяции, тем меньше шансов на появление особи с выдающимися качествами. В императивном программировании, в силу его распространённости и большей численности популяции программистов, конкуренция вынесла на вершину хороших писателей. Возможно, со временем изменится в функциональном программировании ситуация придёт к тому же. Но улучшению положения, скорее всего, мешает проблема курицы и яйца: функциональных программистов мало, потому что мало хороших книг, а последних мало, потому что мало первых.

Нескалярные (агрегатные) типы данных. Массивы

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

Вдохновлённые такой перспективой мы берём учебники по Haskell — языку, ярко раскрывающим достоинства функционального программирования. Берём книги «О Haskell по-человечески» Дениса Шевченко и «Изучай Haskell во имя добра» Мирана Липовачи. Наиболее доходчивые книги. И ищем, как в Haskell работают с массивами, о которых написал Спольски. «Ctrl-F», затем «массив» и ... Ничего не находим! В Haskell нет массивов?! Десятки учебников по программированию было прочитано. И везде были массивы!

Потом, конечно, ложечки массивы нашлись. Но вот осадочек остался. Массивы, оказывается есть, но(!) они не простые, которые имееют самую эффективную машинную реализацию, а ассоциативные :(

Вот это да! Я хочу, чтобы Спольски вернул мне то время, которое я на него потратил! Почему нет самых простых обычных массивов?! Ведь доступ к элементу массива — это очень просто! Обращение к нему на машинном уровне производится так: в одном регистре хранится адрес начала массива, а в другом смещение. Автоматически вычисляемая сумма этих регистров даёт адрес необходимого элемента, поэтому доступ к нему выполняется единственной машинной операцией. Такая аппаратная поддержка делает использование массивов очень выгодным. Да и поиск в массиве достаточно быстр: уменьшаемый в два раза диапазон индексов массива даёт скорость поиска в логарифмической закономерности. Выбор из двух элементов делается за одно сравнение, из четырёх — за два и т.д. Для поиска в 1024 элементах достаточно 10 сравнений, а в 1024x1024 — 20 (двадцати!) сравнений. В миллионе элементов гарантирован поиск максимум за двадцать сравнений! Спискам в этом плане трудно тягаться с массивами. Отказ от поддержки традиционных массивов — это большой минус для производительности.

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

Попробуем представить, что может дать на практике использование массивов для распараллеливания. 1) Представим себе, что у нас есть массив на миллион элементов и полмиллиона процессоров. Надо посчитать сумму всех элементов. Первый процессор сложит значения первого и второго элементов массива, второй — третьего и четвёртого и т.д. Это будет сделано очень быстро — за один такт. Вот она, сила параллелизма! Но результат ещё не достигнут.

Нескалярные (агрегатные) типы данных. Списки

Списки традиционно являются одним из столпов функционального языка программирования. Название LISP (первого языка функционального программирования) означает LISt Processor. Списки — достаточно гибкая структура данных. Её серьёзное преимущество состоит в том, что в эту структуру легко добавлять новые элементы и удалять ненужные. Но опрадано ли ставить списки во главу угла? Обратимся к фактам:

• Список — это структура с последовательным доступом к данным. Чтобы обратиться к какому-либо элементу списка, нужно либо шаг за шагом (то есть императивно) пройти к нему от начала списка, либо хранить адрес (то есть состояние, которого в функциональном программировании стараются избегать) предыдущего элемента. Это тот самый случай, когда 9 даже самых здоровых женщин не могут родить 1 ребёнка за 1 месяц.
• Функциональные языки программирования отдают предпочтение программированию без состояний. Одна из целей функционального программирования — распараллеливание процессов (особенно актуально в эпоху многоядерных процессоров), но последовательный доступ исключает параллелизм.

Но Александр Коновалов опровергает вышесказанное:

Вызов map f xs, где f — функция, а xs — список, прекрасно распараллеливается. Все вычисления чистые и могут выполняться независимо.

Но, позвольте спросить, как? В списках невозможен прямой доступ к произвольному элементу за один шаг.

Непредсказуемость, непрозрачность модели затрат

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

Опубликовано: 2022.03.16, последняя правка: 2023.03.04    00:04

     2022/05/13 21:15, MihalNik          # 

Чтобы обратиться к элементу n, необходимо последовательно пройти от элемента 1 до элемента n.

     2022/05/14 19:02, Автор сайта          # 

в программировании нет строгих общих межязыковых понятий

     2022/05/14 19:31, Gudleifr          # 

Связный список... коллекцией или контейнером? Эти термины общеприняты, нет ничего стыдного в их использовании

     2022/05/15 08:30, MihalNik          # 

общепринятая «классика» в информатике

Какие-то иные толкования надо ещё постараться найти.

Но даже если в каком-то языке списки реализованы посредством динамических массивов или деревьев, то почему бы это прямо не назвать массивами или деревьями?

     2022/05/15 10:46, Gudleifr          # 

любая абстракция скрывает некоторые детали

Потому что пользователю могут быть предоставлены только свойства списков?

Можно, например, сделать ЯП, в котором стек реализовать через список

     2022/05/15 13:48, MihalNik          # 

Потребность в этом кончается одновременно с учебными примерами Вирта.

идея аппаратных списков

     2022/05/15 13:59, Gudleifr          # 

Это, видимо, Ваша потребность?

В языках Вирта встроенных или библиотечных списков как раз таки нет, всё делается обычно с массивами

Списки решают проблему фрагментации памяти

     2022/05/15 15:21, Автор сайта          # 

Списков не бывает!!!

Жена: А почему ты домой так поздно пришёл? Или ты другую нашёл?
Муж: Других… не бывает!

     2022/05/15 15:27, Gudleifr          # 

Но их легко сделать!

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su