Haskell

Haskell (МФА: ) — стандартизированный чистый функциональный язык программирования общего назначения. Является одним из самых распространённых языков программирования с поддержкой отложенных вычислений. Система типов — полная, сильная, статическая, с автоматическим выводом типов, основанная на системе типов Хиндли — Милнера. Поскольку язык функциональный, то основная управляющая структура — это функция.

Отличительная черта языка — серьёзное отношение к типизации; во многом в связи с этим язык назван в честь исследователя теории типов и изобретателя комбинаторной логики Хаскелла Карри.

Имеются средства взаимодействия с кодом на других языках программирования. Есть встроенная поддержка многозадачного и параллельного программирования, развитый инструментарий (средства автоматического тестирования, отладки и профилирования, в том числе для параллельных программ), существует несколько тысяч библиотек с открытым исходным кодом.

История Haskell принадлежит к семейству языков ML. Непосредственно на него оказал большое влияние язык Миранда, разработанный в 1985 году Дэвидом Тёрнером. Миранда был первым чистым функциональным языком, имевшим коммерческую поддержку, и был относительно популярен в 1980-х годах, но оставался собственническим программным обеспечением. Это затрудняло развитие и исследования возможностей ленивого функционального программирования, поэтому буквально за пару лет появилось более десятка схожих языков. Чтобы объединить усилия разных разработчиков в 1987 году на конференции по функциональным языкам программирования и компьютерной архитектуре в Орегоне (FPCA’87) было решено создать комитет для разработки открытого стандарта.

В 1990 году была предложена первая версия языка, Haskell 1.0. В дальнейшем работа комитета продолжилась, и в 1999 году был опубликован «The Haskell 98 Report»The Haskell 98 Language Report  — получено 05.02.2010, который стал стабильным стандартом языка на много лет. Язык, однако, продолжал бурно развиваться, компилятор GHC был фактическим стандартом в отношении новых возможностей.

Разработка новых версий языка идёт открыто, этот процесс получил название Haskell’ (Haskell Prime [ˈhæskəl praɪm], «Хаскелл-штрих»). Все желающие могут выдвигать свои предложения к обсуждению, предложения обсуждаются в течение года, комитет отбирает и объявляет предложения, которые готов принять, формируется новый комитет и к концу года готовится новая версия языка. Таким образом, новые версии языка теперь могут появляться каждый год. Планируется объявлять некоторые ревизии «значительными» и поддерживать такие ревизии на протяжении длительного времени.

Версия языка Haskell 2010 — была объявлена в конце 2009 года, но последней «значительной» версией (стандартом) остаётся Haskell 98.

Характеристики языка В качестве основных характеристик языка Haskell можно выделить следующие:

недопустимость побочных эффектов (чистота языка); возможность писать программы с побочными эффектами без нарушения парадигмы функционального программирования с помощью монад; статическая сильная полная типизация с автоматическим выведением типов, основанная на типизации Хиндли — Милнера; функции высшего порядка, в том числе лямбда-абстракции; частичное применение; ленивые вычисления; сопоставление с образцом (), функциональные образцы, охраняющие выражения (guards); параметрический полиморфизм и его объединение с ad-hoc-полиморфизмом в единую модель посредством классов типов; алгебраические типы данных, в том числе псевдобесконечные (за счёт ленивости); списковое включение; возможность интеграции с программами, реализованными на императивных языках программирования посредством интерфейса внешних функций.

С момента принятия последнего стандарта языка (Haskell’98) ведущие реализации языка (ghc и hugs) были расширены множеством дополнительных возможностей: параметрический полиморфизм высших рангов за счёт квантификации переменных типа (вплоть до импредикативного) — естественно, исключающая выведение типов; функциональные зависимости.

Реализации языка Есть несколько реализаций языка Haskell. Некоторые реализации ориентированы на практическое применение, в то время как другие — представляют прежде всего академический интерес.

Компиляторы и интерпретаторы Наиболее популярен на практике оптимизирующий компилятор GHC, который создаёт быстрый код и позволяет использовать многие расширения языка. GHC может оптимизировать как скорость, так и компактность программ, способен создавать многозадачный и параллелизованный код. В комплекте с компилятором GHC поставляется также интерактивная среда программирования GHCi со встроенным отладчиком. GHC работает в Windows, MacOS X и на нескольких юникс-подобных платформах (Linux, *BSD, Solaris). Именно GHC является стандартным компилятором в Haskell Platform, и именно на нём в первую очередь тестируются все новые библиотекиThe Glasgow Haskell Compiler. The Architecture of Open Source Applications, Volume 2 , 2012.

Другая популярная реализация языка — интерпретатор HUGS. Он написан на Си, имеет малый размер дистрибутива и работает практически на всех платформах. HUGS предоставляет интерактивную среду программирования, но может также запускать программы на Haskell в стиле скриптовых языков. Пользователи Windows могут использовать графическую интерактивную среду WinHugs. Поскольку HUGS — это интерпретатор, то программы, запущенные в нём, выполняются медленнее, чем код, созданный большинством компиляторов языка Haskell. HUGS часто рекомендуют в качестве среды для изучения языка. HUGS полностью поддерживает стандарт языка Haskell 98, а также некоторые наиболее популярные расширения языка.

Другие известные реализации:

nhc98 — быстрый компилятор, поддерживающий стандарт Haskell 98, написанный на Haskell 98; доступен для всех юникс-подобных платформ, включая MacOS X и Windows/cygwin; YHC (York Haskell Compiler) — форк nhc98, ставящий целью быть более переносимым и эффективным, поддерживает отладчик Hat; генерирует промежуточный байт-код, который можно использовать для генерации кода на других языках программирования; UHC (Utrecht Haskell Compiler) — компилятор, поддерживающий Haskell 98 почти полностью, а также некоторые расширения; поддерживает глобальный анализ программ; имеет несколько кодогенераторов, в том числе почти полностью функциональный генератор JVM-кода, кодогенераторы для LLVM и CLR в состоянии разработки; работает на юникс-подобных системах (включая MacOS X и Windows/cygwin); HBI и HBC — интерпретатор и компилятор, поддерживающие стандарт Haskell 98 с некоторыми расширениями; точно работает в Linux, поддерживается слабо; LHC (The Luxurious LHC Haskell Optimization System) — альтернативный кодогенератор для GHC, поддерживающий глобальную низкоуровневую оптимизацию программы в целом; jhc — экспериментальный компилятор для исследования возможностей глобальной оптимизации программ; Yale Haskell — ранняя реализация языка Haskell на Лиспе.

Haskell Platform В 2009 году сформировалась концепция Haskell Platform — стандартного дистрибутива языка, включающего кроме компилятора (GHC), также дополнительный инструментарий (систему сборки и развёртывания пакетов Cabal) и набор популярных библиотек.

С 2022 года Haskell Platform считается устаревшим способом установки Haskell.

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

LLVM: патч для GHC, добавляющий генератор кода для LLVM, в настоящее время включён в компилятор GHC; использование LLVM позволяет достичь большей производительности на ряде задач. альтернативный кодогенератор в UHT (работоспособен частично)

виртуальная машина Java (JVM): LambdaVM — патч для GHC, добавляющий генератор байт-кода JVM jvm-bridge — мост между Haskell и JVM (для GHC) jaskell — генератор байт-кода JVM (вероятно заброшен) альтернативный кодогенератор в UHC (работоспособен почти полностью)

Common Language Runtime (.Net): прототип генератора MSIL-кода для компилятора EHT/UHT некоторые проекты по поддержке CLR упоминаются в GHC FAQ, на начало 2010 года их состояние не ясно

JavaScript: кодогенератор JavaScript для GHC — патч для GHC, позволяющий компилировать программы в JavaScript-код Ycr2Js — конвертер байт-кода компилятора YHC в JavaScript Fay — компилятор подмножества Haskell в JavaScript

Языки описания архитектуры (Verilog/VHDL): Clash — альтернативный способ разработки ASIC и программирования FPGA

Несколько интересных целевых платформ доступны при использовании компилятора YHC, в частности существуют интерпретатор байт-кода YHC на Python и конвертер байт-кода YHC в Erlang Core, но эти разработки пока ещё экспериментальны. Также существуют реализации подмножеств языка на разных целевых платформах.

Расширения языка макрорасширение с контролем типов (); объектно-ориентированное программирование (O’Haskell, Haskell++ и Mondrian).

Расширения реализаций языка (относится к GHC):

развитие системы типизации; многопоточность; параллельные вычисления; распределённые вычисления; транзакционная память.

Примеры

Вычисление факториала Следующий пример показывает синтаксис языка Haskell при реализации функции для вычисления факториала:

fac :: Integer -> Integer fac 0 = 1 fac n | n > 0 = n * fac (n - 1)

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

fac n = product [1..n]

что соответствует математическому определению факториала.

Первая строка в приведённом выше коде необязательна и является объявлением функционального типа, то есть задаёт типы аргументов (указаны до последней «->») и тип возвращаемого значения (указан после последней «->»). Эта строка может быть прочитана как: функция fac имеет тип (::) из целого в целое (). Это значит, что она получает на вход один целочисленный аргумент (записан слева от «->») и возвращает результат также целого типа (записан справа от «->»). Если программист не указал типы явно, компилятор или интерпретатор может определить их автоматически.

Вторая и третья строки формируют определение тела функции. Определение состоит из предложений, или «клауз» (). Каждое предложение представляет собой пару «образец — выражение». Компилятор или интерпретатор использует механизм сопоставления с образцом для выбора одного из выражений. В данном случае вторая строка определения будет выбрана тогда, когда фактический параметр при вызове функции fac будет равен нулю.

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

Калькулятор Простейший калькулятор для вычисления выражений в обратной польской записи может быть определён на языке Haskell при помощи одной функции: calc :: String -> Float calc = head . foldl f [] . words where f :: [Float] -> String -> [Float] f (x:y:zs) "+" = (y + x):zs f (x:y:zs) "-" = (y - x):zs f (x:y:zs) "*" = (y * x):zs f (x:y:zs) "/" = (y / x):zs f (x:y:zs) "FLIP" = y:x:zs f (x:zs) "ABS" = (abs x):zs f xs y = read y : xs