Haskell (язык программирования)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:25, 8 июня 2016.
Haskell
fraimed
Спроектировано Lennart Augustsson, Dave Barton, Brian Boutel, Warren Burton, Joseph Fasel, Kevin Hammond, Ralf Hinze, Paul Hudak, John Hughes, Thomas Johnsson, Mark Jones, Simon Peyton Jones, John Launchbury, Erik Meijer, John Peterson, Alastair Reid, Colin Runciman, Philip Wadler
Печать дисциплины статическая, сильная, полная, с выводом типов
OS Кроссплатформенное
Портал: https://www.haskell.org
Влияние
Agda, Bluespec, Clojure, C#, Cat, Cayenne, Clean, Curry, Epigram, Escher, F#, Factor, Isabelle, Java Generics, LINQ, Mercury, Ωmega, Perl 6, Python, Qi, Scala, Timber, Visual Basic 9.0

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

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

История

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

Haskell 1.0 - 1.4

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

Haskell 98

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

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

Haskell 2010

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

Изменения по сравнению с Haskell '98:

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

Более того изменения, совершенные в базовой библиотеке, были добавлены в отчет.

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

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

Особенности

Статическая система типов

Каждое выражение в Haskell имеет тип, которые устанавливается во время компиляции. Приложение должно сопоставить все типы. Если они не совпадают, то компилятор забракует программу. Типы являются не только формой гарантии, но и языком выражения конструкции программы.

Все переменные в Haskell имеют тип:

char = 'a'    :: Char
int = 123     :: Int
fun = isDigit :: Char -> Bool

Вы должны передать функции переменные правильных типов, иначе компилятор отвергнет программу:

Type error
isDigit 1

Вы можете декодировать байты в текст:

bytes = Crypto.Hash.SHA1.hash "hello" :: ByteString
text = decodeUtf8 bytes               :: Text

Но вы не можете декодировать текст, которые уже является последовательностью символов Unicode:

Type error
doubleDecode = decodeUtf8 (decodeUtf8 bytes)

Логический вывод типов

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

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

main :: IO ()
main = do line :: String <- getLine
          print (parseDigit line)
  where parseDigit :: String -> Maybe Int
        parseDigit ((c :: Char) : _) =
          if isDigit c
             then Just (ord c - ord '0')
             else Nothing

Но вы можете просто написать следующее:

main = do line <- getLine
          print (parseDigit line)
  where parseDigit (c : _) =
          if isDigit c
             then Just (ord c - ord '0')
             else Nothing

Также можно использовать вывод типов во избежание траты времени, объясняя, чего вы хотите:

do ss <- decode "[\"Hello!\",\"World!\"]"
   is <- decode "[1,2,3]"
   return (zipWith (\s i -> s ++ " " ++ show (i + 5)) ss is)
 => Just ["Hello! 6","World! 7"]

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

do ss <- decode "[1,2,3]"
   is <- decode "[null,null,null]"
   return (zipWith (\s i -> s ++ " " ++ show (i + 5)) ss is)
 => Nothing

Ленивый

Функции не вычисляют свои аргументы. Это значит, что программа может довольно хорошо сформироваться, с возможностью писать проверяющие конструкции (н-р if/else), просто составляя нормальные функции. Чистота кода Haskell облегчает соединение цепочек из функций, предоставляя преимущество в производительности.

Определить проверяющие конструкции легко:

when p m = if p then m else return ()
main = do args <- getArgs
          when (null args)
               (putStrLn "No args specified!")

Если вы заметили повторяющийся паттерн, например такой:

if c then t else False

вы можете дать ему имя

and c t = if c then t else False

и затем использовать его с тем же успехом, что и первоначальное выражение.

Получите повторное использование кода путем составления ленивых функций. Довольно естественно выразить любую функцию, используя функции map или or:

any :: (a -> Bool) -> [a] -> Bool
any p = or . map p

Использование повторно рекурсивные паттерны в map, filter, foldr и других.

Чисто функциональный

Каждая функция в Haskell это функция в математическом смысле (т.е. "чистая"). Даже операции ввода/вывода, влекущие за собой некоторые побочные эффекты и являющиеся только описанием действия, написаны на чистом коде. Здесь нет утверждений и инструкций, только выражения, которые не могут видоизмениться в переменные (локальные или глобальные) и которые не имеют доступ к структурам таким как время или случайные числа.

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

square :: Int -> Int
square x = x * x

Следующее соединение строк будет произведено успешно:

"Hello: " ++ "World!"

Однако следующий пример выдаст ошибку типов:

Type error
"Name: " ++ getLine

так как getLine имеет тип IO String, а не String как "Name: ". Поэтому из-за системы типов вы не можете смешивать и соотносить чистое и нечистое.

Параллельность

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

Легко установите потоки и связывайтесь со стандартной библиотекой:

main = do
  done <- newEmptyMVar
  forkIO (do putStrLn "I'm one thread!"
             putMVar done "Done!")
  second <- forkIO (do delayThread 100000
                       putStrLn "I'm another thread!")
  killThread second
  msg <- takeMVar done
  putStrLn msg

Используйте асинхронный API для потоков:

do a1 <- async (getURL url1)
  a2 <- async (getURL url2)
  page1 <- wait a1
  page2 <- wait a2
  ...

Атомарные потоки с программной транзакционной памятью:

transfer :: Account -> Account -> Int -> IO ()
transfer from to amount =
  atomically (do deposit to amount
                 withdraw from amount)

Атомарные транзакции должны быть повторяющимися, поэтому независимый ввод/вывод запрещен в системе типов:

Type error
main = atomically (putStrLn "Hello!")

Пакеты

Open source содействие Haskell очень активно, доступен широкий ряд пакетов на публичных серверах.

Свободно доступны 6.954 пакетов. Здесь приведен список наиболее используемых:

  • bytestring - Бинарные данные
  • base - Вводная часть программы, ввод/вывод, потоки
  • network - Работа с сетями
  • text - Текс Unicode
  • parsec - Библиотека синтаксического анализатора
  • directory - Файл/директория
  • hspec - Тесты RSpec
  • attoparsec - Быстрый синтаксический анализатор
  • monad-logger - Логгирование
  • persistent - База данных ORM
  • template-haskell - Мета-программирование
  • tar - Архивы Tar
  • snap - Веб
  • time - Дата, время и т.д.
  • happstack - Веб
  • yesod - Веб
  • containers - Отображения, графы, множества
  • fsnotify - Наблюдатель файловой системы
  • hint - Интерпретатор Haskell
  • unix - Связки UNIX
  • SDL - Связки SDL
  • OpenGL - Графическая система OpenGL
  • criterion - Разметка
  • pango - Перевод текста
  • cairo - Графика Cairo
  • statistics - Статистический анализ
  • gtk - Библиотека Gtk+
  • glib - Библиотека GLib
  • test-framework - Тестирование
  • resource-pool - Пулинг ресурсов
  • conduit - поточный ввод/вывод
  • mwc-random - Случайные числа высокой точности
  • QuickCheck - Тестирование свойств
  • stm - Атомарные потоки
  • blaze-html - Создание разметки
  • cereal - Бинарный анализ/печать
  • xml - XML анализ/печать
  • http-client - HTTP клиент
  • zlib - zlib/gzip/raw
  • yaml - YAML анализ/печать
  • pandoc - Изменение разметки
  • binary - Сериализация
  • tls - TLS/SSL
  • zip-archive - Сжатие Zip
  • warp - Веб
  • text-icu - Кодирование текста
  • vector - Векторы
  • async - Асинхронное распараллеливание
  • pipes - Поточный ввод/вывод
  • scientific - Длинные числа
  • process - Запуск процессов
  • aeson - JSON анализ/печать
  • dlist - Difflists
  • syb - Универсальное программирование

Примеры

Ниже представлена программа Hello world, написанная на Haskell (заметим, что все кроме последней строки может быть опущено):

module Main where
main :: IO ()
main = putStrLn "Hello, World!"

Следующий пример - вычисление факториала, определенная несколькими способами:

-- Пояснение типов (не обязательно)
factorial :: (Integral a) => a -> a

-- С использованием рекурсии
factorial n | n < 2 = 1
factorial n = n * factorial (n - 1)

-- С использованием рекурсии с ограничением 
factorial n
  | n < 2     = 1
  | otherwise = n * factorial (n - 1)

-- С использованием рекурсии, но без отождествления
Using recursion but written without pattern matching
factorial n = if n > 0 then n * factorial (n-1) else 1

-- С использованием списков
factorial n = product [1..n]

-- С использованием fold (встроенное)
factorial n = foldl (*) 1 [1..n]

-- Point-free
factorial = foldr (*) 1 . enumFromTo 1

Сортировка Quicksort на Haskell

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

Реализации

Все приведенные реализации находятся в открытом доступе[4]. Все они полностью или почти полностью скомпилированы на стандарте Haskell 98.

  • The Glasgow Haskell Compiler (GHC) компилирует в родной код с использованием нескольких различных архитектур - а также в ANSI C с использованием C-- как промежуточного языка. GHC стал фактическим стандартным диалектом Haskell[5]. Существуют библиотеки (например, привязка к OpenGL), которая будет работать только с GHC. Также он поставляется вместе с платформой Haskell.
  • The Utrecht Haskell Compiler (UHC) - реализация Haskell из Утрехтского Университета. UHC поддерживает практически все особенности Haskell 98, а еще многие экспериментальные расширения. Он реализован с использованием атрибутной грамматики и на данный момент используется для исследований основных систем типов и расширений языка.

Следующие реализации активно уже не поддерживаются:

  • Hugs, the Haskell User's Gofer System - это интерпретатор байткода. Некогда был широко использован вместе с GHC[6], но был заменен GHCi. Также поставляется вместе с графической библиотекой.
  • nhc98 - другой компилятор байткода. Nhc98 фокусируется на минимизации затрат памяти.
  • Yhc, the York Haskell Compiler был разновидности nhc98, имел целью быть проще, более портативным и более эффективным, совмещался с Hat, средство трассировки Haskell. Также содержит в себе JavaScript бэкэнд, позволяя пользователям запускать программы на Haskell на веб браузере.
  • HBC - это ранняя реализация, поддерживающая Haskell 1.4. Ее автором явзяется Леннарт Августсон, взяв за основу Lazy ML. В последнее время он не развивается.

Реализации, приведенные ниже, исполнены не полностью на haskell 98 и используют языки- вариации Haskell:

  • Gofer это обучающий диалект Haskell с характерной чертой, называемой "конструктор классов", разработанной Марком Джонсом. Gofer был вытеснен Hugs.
  • Helium - новейший диалект Haskell. Он сосредоточен на облегчении изучения языка, предоставляя более ясные сообщения об ошибках. В настоящее время ему не достает полной поддержки классов типов, что делает его несовместимым со многими программами на Haskell.

Применение

Darcs это система контроля версий, написанная на Haskell с несколькими инновационными особенностями. Cabal - инструмент для построения и упаковки библиотек и программ на Haskell[7]. Linspire GNU/Linux выбрали Haskell для разработки системных инструментов[8]. Xmonad - оконный менеджер для X Window System, полностью написанный на Haskell[9]. GHC также часто используется как система отладки передовых черт функционального программирования и оптимизаций в других языках программирования.

Индустрия

  1. Facebook использует анти-спам программы, реализованные на Haskell.
  2. Bluespec SystemVerilog (BSV) - это язык для проектирования полупроводников, является расширением для Haskell. Более того инструменты luespec, Inc. также написаны на Haskell.
  3. Cryptol, язык и инструментарий для разработки и верификации криптографических алгоритмов, реализован на Haskell.
  4. Первое формально заверенное микроядро[10], seL4, использовало Haskell как прототипирующий язык для разработчиков операционной системы[10]. В то же время код Haskell определял исполняемую спецификацию для автоматической трансляции, использующая инструмент доказательства теорем. Таким образом, код на Haskell предоставлял прототип до окончательного уточнения C.

Веб

Здесь представлены веб фреймворки Haskell[11], такие как:

  1. Yesod
  2. Happstack
  3. Snap[12]

Почему именно Haskell?

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

(оригинал)
"WOW! I basically wrote this without testing just thinking about my program in terms of transformations between types. I wrote the test/example code and had almost no implementation errors in the code! The compiler/type-system is really really good at preventing you from making coding mistakes! I've never in my life had a block of code this big work on the first try. I am WAY impressed."

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

(оригинал)
"I learned Haskell a couple of years ago, having previously programmed in Python and (many) other languages. Recently, I've been using Python for a project (the choice being determined by both technical and non-technical issues), and find my Python programming style is now heavily influenced (for the better, I hope ;-) by my Haskell programming experience."

Graham Klyne

Haskell предоставляет вам:

  • Существенно увеличивающуюся производительность (Ericsson получили увеличение коэффициента производительности от 9 до 25 при использовании Erlang, функционального языка программирования, схожего с Haskell, в одной из серий экспериментов ПО телефонии).
  • Более короткий, понятный и поддерживаемый код.
  • Меньшее количество ошибок, более высокую надежность.
  • Меньший "семантический разрыв" между программистом и языком.
  • Более короткое время на выполнение задачи.

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

Большая часть времени жизни ПО тратится на ее спецификацию, разработку и поддержку, и не только в программировании. Функциональные языки великолепно подходят для написания спецификации, которая фактически может быть исполнена (и, следовательно, тестирована и отлажена). Такая спецификация является первым прототипом конечной программы.

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

Критика

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

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

Haskell имеет ряд остальные недостатков по сравнению с другими академическими/исследовательскими языками. Например, его модульная система (если это можно так назвать) явно хуже, чем модульные системы в стандартном ML и OCaml. Его статическое средство мета-программирования, Template Haskell, иногда полезно, но на самом деле оно мало используется для современных новейших макросистем. И, конечно, есть еще много вещей, которые некоторые языки могут сделать, а другие не могут. Например, если вы хотите корректно использовать свою программу, система типов в Haskell, даже с последними расширениями в этом направлении, не позволит вам это сделать так, как это может Coq или Agda. Но это требование к языку сделать что-либо, подо что он не был спроектирован, так что это не может быть рассмотрено как здравая критика.

Наконец, Haskell страдает из-за некоторой социальной уязвимости, будучи странным и исследовательским. Нанимать большое число программистом на Haskell становится все сложнее (несмотря на то, что вы скорее всего найдете хороших специалистов). Так как он очень отличается от языков, которые знают большинство, это представляет потенциально резкую кривую обучения. И, конечно, сообщество, будучи полезным и очень большим, очень мало сравнимо с более популярными языками. Разновидности и качество библиотек, доступных на Hackage, предоставленные программистами на Haskell, поразительно, но в среднем не может соревноваться с Java. В заключение, так как Haskell до сих пор ориентирован на исследования, он быстро меняется и временами непредсказуемо[13].

Примечания

  1. 1,0 1,1 1,2 1,3 Peyton Jones, Simon, ed. (2003). Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press. ISBN 0521826144.
  2. Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip (2007). "A History of Haskell: Being Lazy with Class" (PDF). Proceedings of the third ACM SIGPLAN conference on History of programming languages (HOPL III): 12–1–55. doi:10.1145/1238844.1238856. ISBN 978-1-59593-766-7.
  3. "Haskell Wiki: Implementations"
  4. [1]
  5. C. Ryder and S. Thompson (2005). "Porting HaRe to the GHC API"
  6. Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip (2007). "A History of Haskell: Being Lazy with Class" (PDF). Proceedings of the third ACM SIGPLAN conference on History of programming languages (HOPL III): 12–1–55. doi:10.1145/1238844.1238856. ISBN 978-1-59593-766-7.
  7. "the Haskell Cabal"
  8. "Linspire/Freespire Core OS Team and Haskell"
  9. [xmonad.org]
  10. 10,0 10,1 A formal proof of functional correctness was completed in 2009. Klein, Gerwin; Elphinstone, Kevin; Heiser, Gernot; Andronick, June; Cock, David; Derrin, Philip; Elkaduwe, Dhammika; Engelhardt, Kai; Kolanski, Rafal; Norrish, Michael; Sewell, Thomas; Tuch, Harvey; Winwood, Simon (October 2009). "seL4: Formal verification of an OS kernel" (PDF). 22nd ACM Symposium on Operating System Principles. Big Sky, MT, USA.
  11. – Haskell web frameworks
  12. "Snap Framework"
  13. "What are the main weaknesses of Haskell as a programming language?"