Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

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

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

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

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

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

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

Монада


Мнение: «Один разработчик на 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
Для C++ одноимённые функции с разным количеством аргументов не является проблемой. Хаскел «не дотягивает» до C++? А ещё в языке есть оператор «$»:

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 — список, прекрасно распараллеливается. Все вычисления чистые и могут выполняться независимо.

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

Доступ к элементам списка
Чтобы обратиться к элементу n, необходимо последовательно пройти от элемента 1 до элемента n. Допустим, мы должны распараллелить доступ n ядер или процессоров к n элементам массива. Если первое ядро получает доступ к первому элементу за один шаг, то n-ое — за n шагов. Одновременный, параллельный доступ всех процессоров ко всем элементам массива невозможен. Да, существует возражение, что «параллельно» — это отнюдь не «одновременно». Приводятся аргументы в пользу того, что ядра процессора могут работать по принципу конвейера. Конечно, это тоже может внести лепту в ускорение вычислений. Однако, когда мы говорим о параллельности, мы ждём, прежде всего, одновременности вычислений.

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

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

Опубликовано: 2022.03.16, последняя правка: 2024.05.08    23:18

ОценитеОценки посетителей
   ██████████████████████████████████████████ 2 (100%)
   ▌ 0
   ▌ 0
   ▌ 0

Отзывы

     2022/05/13 21:15, MihalNik          # 

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

А кто сказал автору, что списки устроены именно так как он себе их представляет в каком-то другом ЯП? Надо понимать, что в программировании нет строгих общих межязыковых понятий. В PHP, например, массивы тоже ассоциативные и это один из самых популярнейших языков. В Лиспе списки вполне позволяют делать деревья, которые вполне могут давать хорошее распараллеливание.

Список вполне может реализовываться как дерево или массив (динамический аки vector в С++), поскольку соответствующую возможность доступа к пред/след членам они позволяют.

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

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

Отчего же нет? Связный список — это общепринятая «классика» в информатике. Какие-то иные толкования надо ещё постараться найти. Но даже если в каком-то языке списки реализованы посредством динамических массивов или деревьев, то почему бы это прямо не назвать массивами или деревьями? Если хотели скрыть детали реализации, сделав понятие списка неким обобщающим термином, то почему бы прямо не назвать это коллекцией или контейнером? Эти термины общеприняты, нет ничего стыдного в их использовании. Тем более, что в точных науках, к которым относит себя информатика, отношение к терминам достаточно щепетильное. Недоговорённость и двусмысленность противопоказаны программированию.

Детали реализации списков в Хаскелле остаются, к сожалению, за кадром: компилятор Хаскелла написан на нём самом. А исследование машинных кодов компилятора, судя по отзывам, — та ещё головоломка.

Впрочем, попробую задать вопрос о списках одному знакомому автору книг о Лиспе и функциональном программировании. О списках в Лиспе ему, как минимум, есть что сказать.

     2022/05/14 19:31, Gudleifr          # 

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

Если речь идет не о машинах 5-го поколения, то это, действительно, стыдно. Потребность в структурировании данных есть следствие оптимизации доступа к ним. Оптимизация доступа невозможна без знания внутреннего устройства. "Высокоуровневые слова" здесь — следствие дремучей веры в способность компилятора делать то, что программист не умеет.

     2022/05/15 08:30, MihalNik          # 

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

Скорее "общепринятая" классика в местной образовательной системе.

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

Дело не в толкованиях, а в том, что любая абстракция скрывает некоторые детали.

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

Потому что пользователю могут быть предоставлены только свойства списков? Можно, например, сделать ЯП, в котором стек реализовать через список — тогда его "переполнение" равносильно нехватки памяти, т.е. утрачивает смысл как самостоятельное понятие.

     2022/05/15 10:46, Gudleifr          # 

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

Именно. А для структур данных это — смерть.

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

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

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

... который будет реализован через массив. Когда Вы уясните, что идея аппаратных списков умерла вместе с машинами пятого поколения? Списков не бывает!!!

     2022/05/15 13:48, MihalNik          # 

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

Это, видимо, Ваша потребность? В языках Вирта встроенных или библиотечных списков как раз таки нет, всё делается обычно с массивами, а вот в STL C++, в Java и многих других современных языках библиотечные или даже встроенные списки есть.

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

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

     2022/05/15 13:59, Gudleifr          # 

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

Разумеется, ведь я вынужден программировать.

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

Вас обманули.

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

Вас опять обманули. Они её не решают, а создают.

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

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

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

Не первый раз от Вас такое утверждение. Ну допустим это так, списков не бывает. Но их легко сделать! Берём какой-нибудь учебник K&R 1978 года, читаем соответствующие разделы и легко реализуем! С этого момента у вас есть списки!

     2022/05/15 15:27, Gudleifr          # 

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

Именно!!! Как и таблицы расстановки, деревья поиска, конечные автоматы и пр. Ровно там, где это надо, и с потребной оптимизацией. В пределах конкретной задачи. Со сборкой мусора или без. Поэтому "универсальные списки" не нужны. Они будут тормозить во ВСЕХ применениях, кроме ровно того единственного случая, под который оптимизированы.

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

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

Авторизация

Регистрация

Выслать пароль

Карта сайта


Содержание

Каким должен быть язык программирования?

Анализ и критика

●  Устарел ли текст как форма представления программы

●  Русский язык и программирование

●  Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

●  Некоторые «вкусности» Алгол-68

●  «Двухмерный» синтаксис Python

●  Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

●  Должна ли программа быть удобочитаемой?

●  Стиль языка программирования

●  Тексто-графическое представление программы

●●  Разделители

●●  Строки программы

●●  Слева направо или справа налево?

●  Комментарии

●●  Длинные комментарии

●●  Короткие комментарии

●●  Комментарии автоматической генерации документации

●●  Нерабочий код

●●  Помеченные комментарии

●  Нужны ли беззнаковые целые?

●  Шестнадцатиричные и двоичные константы

●  Условные операторы

●  Переключатель

●  Циклы

●●  Продолжение цикла и выход из него

●  Некошерный «goto»

●  Изменение приоритетов операций

●  Операции присвоения и проверки на равенство. Возможно ли одинаковое обозначение?

●  Так ли нужны операции «&&», «||» и «^^»?

●  Постфиксные инкремент и декремент

●  Почему в PHP для конкатенации строк используется «.»?

●  Указатели и ссылки в C++

●●  О неправомерном доступе к памяти через указатели

●  Обработка ошибок

●  Функциональное программирование

●●  Нечистые действия в чистых функциях

●●  О чистоте и нечистоте функций и языков

●●  Макросы — это чистые функции, исполняемые во время компиляции

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

●●  Измеряем замедление при вызове функций высших порядков

●●  C vs Haskell: сравнение скорости на простом примере

●●  Уникальность имён функций: за и против

●●  Каррирование: для чего и как

●●  О тестах, доказывающих отсутствие ошибок

●  Надёжные программы из ненадёжных компонентов

●●  О многократном резервировании функций

●  Использование памяти

●  Почему динамическое распределение памяти — это плохо

●  Как обеспечить возврат функциями объектов переменной длины?

●●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●●  Массивы переменной длины в C/C++

●●  Размещение объектов в стеке, традиционный подход

●●  Размещение объектов переменной длины с использованием множества стеков

●●  Размещение объектов переменной длины с использованием двух стеков

●●  Реализация двухстековой модели размещения данных

●●  Двухстековая модель: тесты на скорость

●●  Изменение длины объекта в стеке во время исполнения

●●  Размещение объектов переменной длины с использованием одного стека

●  Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

●  Безопасность и размещение объектов переменной длины в стеке

●  Массивы, структуры, типы, классы переменной длины

●  О хранении данных в стеке, вместо заключения

●  Реализация параметрического полиморфизма

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Новости и прочее




Последние отзывы

2024/05/12 22:14 ••• Сисадмин со стажем
О превращении кибернетики в шаманство

2024/05/11 16:33 ••• Автор сайта
Энтузиасты-разработчики компиляторов и их проекты

2024/04/28 15:58 ••• Автор сайта
Обработка ошибок

2024/04/23 00:00 ••• alextretyak
Признаки устаревшего языка

2024/04/21 00:00 ••• alextretyak
Постфиксные инкремент и декремент

2024/04/20 21:28 ••• Бурановский дедушка
Русский язык и программирование

2024/04/07 15:33 ••• MihalNik
Все языки эквивалентны. Но некоторые из них эквивалентнее других

2024/04/01 23:39 ••• Бурановский дедушка
Новости и прочее

2024/04/01 23:32 ••• Бурановский дедушка
Русской операционной системой должна стать ReactOS

2024/03/22 20:41 ••• void
Раскрутка компилятора

2024/03/20 19:54 ••• kt
О многократном резервировании функций

2024/03/20 13:13 ••• Неслучайный читатель
Надёжные программы из ненадёжных компонентов

2024/03/07 14:16 ••• Неслучайный читатель
«Двухмерный» синтаксис Python