Haskell

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

Háskell (русск. Ха́скель, Ха́скелл) — стандартизованный чистый функциональный язык программирования общего назначения. Является одним из самых распространённых языков программирования с поддержкой отложенных вычислений. Типизация в Хаскеле строгая, статическая, с автоматическим выводом типов. Поскольку язык функциональный, основная управляющая структура — это функция. Серьёзное отношение к типизации — другая отличительная черта Хаскеля. Концепция языка отражает идею математика Хаскелла Карри, писавшему, что «доказательство — это программа, а доказываемая формула — это тип программы»[1][2]. Именно в честь Х. Карри язык и получил своё название.

Сегодня Хаскель стал языком быстрой разработки надёжных, кратких и корректных программ. Имеются средства взаимодействия с кодом на других языках программирования, встроенная поддержка многозадачного и параллельного программирования, развитый инструментарий (средства автоматического тестирования, отладки и профилирования, в том числе для параллельных программ), существует много библиотек с открытым исходным кодом (более 1800 пакетов в одном только архиве Hackage)[3].

Содержание

История

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

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

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

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

Характеристики языка

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

Со времени принятия последнего стандарта языка (Haskell98) прошло много времени и с тех пор ведущие реализации языка (ghc и hugs) были расширены множеством дополнительных возможностей:

  • Полиморфизм 2-го и высших рангов (rank-2 and rank-N polymorphism)
  • Функциональные зависимости (FD, functional dependencies)

Использование

Имеет интерпретаторы (один из самых известных — HUGS) и компиляторы (один из самых известных — Glasgow Haskell Compiler (GHC)).

Популярен в академических кругах, но малоизвестен среди прикладных программистов. В последнее время расширяется набор прикладных библиотек, язык интегрируется в распространённые программные системы (.Net [1], COM/ActiveX HaskellScript, Java jaskell), что делает язык всё более и более привлекательным для прикладных программистов.

Расширения языка:

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

Примеры

Простейшие примеры

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

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

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

fac n = product [1..n]

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

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

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

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


Калькулятор

Простейший калькулятор для вычисления выражений в обратной польской записи может быть определён на языке Haskell при помощи одной функции:

 calc :: String -> [Float]
 calc = foldl f [] . words
   where 
     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 xs y         = read y : xs

В данном определении функция левосторонней свёртки (foldl) вызывается с фактическими параметрами [] (пустой список — начальное значение для свёртки), f (функция для интерпретации одного слова во входном выражении) и списка, полученного разбивкой исходной строки с выражением на слова, то есть строки, отделённые друг от друга пробельными символами. В результате работы получается список, который содержит промежуточные и окончательное значения, получаемые при вычислении входного выражения.

Числа Фибоначчи

Другой пример показывает способ вычисления бесконечного списка чисел Фибоначчи за линейное время:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

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

fibs         = 0 : 1 : 1 : 2 : 3 : 5 : ...
               +   +   +   +   +   +
tail fibs    = 1 : 1 : 2 : 3 : 5 : ...
               =   =   =   =   =   =
zipWith ...  = 1 : 2 : 3 : 5 : 8 : ...
fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 : ...

Та же самая функция может быть записана короче и более понятно при использовании расширения языка Haskell, которое реализовано в компиляторе GHC (параллелизация определителей списков, Parallel List Comprehensions):

 fibs = 0 : 1 : [a + b | a <- fibs
                       | b <- tail fibs]


Простые числа

Реализация нахождения всех простых чисел обычным путём (проверка каждого числа на простоту)

 -- общее определение (все натуральные числа, которые являются простыми :-)
 primes = [n | n <- [2..], isPrime n]
 
 -- список остатков от деления n на все числа
 -- из диапазона [2..n/2]
 listOfRemainders n =[n `mod` x | x <- [2..(n `div` 2)]] 
 
 -- Число простое, если приведённый выше список не содержит нулей
 isPrime n = null (filter (==0) (listOfRemainders n))

а также с помощью решета Эратосфена:

 ero = eroPrimes [2..]
 eroPrimes (x : xs) = x : eroPrimes [y | y <- xs , y `mod` x /= 0]

И получение, вообще говоря, бесконечного списка простых чисел:

 listOfPrimes = [n | n <- [2..], and [n `mod` (n-x) /= 0 | x <- [1..n-2] ] ]


Численное интегрирование

Численное интегрирование <math>\int\limits_0^{2\pi}x\sin x\,{\rm d}x = -2\pi</math> методом трапеций:
trapezeIntegrate f a b n =
    ((sum (map f [a + h, a + 2*h .. b - h])) + t) * h
    where
        t = (f a + f b)/2
        h = (b - a) / n
 
main = do
    print $ trapezeIntegrate (\x -> x*sin x) 0 (2*pi) 100
 
-- Вывод: -6.281118086046067


Проверка палиндромов

Как видно, Хаскель прекрасно работает с Юникодом.

import Char -- функции toLower и isAlpha
 
palindrom :: [Char] -> Bool
palindrom s =
    norm == reverse norm
    where norm = map toLower . filter (isAlpha) $ s
 
test :: [Char] -> IO ()
test s =
    putStrLn $ s ++ ": " ++ show (palindrom s)
 
main = do
    test "А в Енисее — синева"
    test "А роза упала не на лапу Азора"
    test "Не роза упала на лапу Азора"
    test "Мир как Рим"
    test "Мир не Рим"
    test "Dogma: I am God"
    test "I prefer Pi"
    test "حوت فمه مفتوح"
    test "Ne mateno, bone tamen"
 
-- Вывод:
-- А в Енисее — синева: True
-- А роза упала не на лапу Азора: True
-- Не роза упала на лапу Азора: False
-- Мир как Рим: True
-- Мир не Рим: False
-- Умер — и хрен с ним: False
-- Dogma: I am God: True
-- I prefer Pi: True
-- حوت فمه مفتوح: True
-- Ne mateno, bone tamen: True

Приложения, написанные на языке Haskell

Мозаичный оконный менеджер Xmonad для X Window System целиком написан на Хаскеле. Darcs — распределённая система управления версиями с рядом уникальных возможностей — написана на Хаскеле. Одри Танг (Audrey Tang) написал Pugs, интерпретатор и компилятор будущего языка Perl 6, который оказался полезен уже спустя несколько месяцев, после начала работы над ним. Аналогично, компилятор GHC часто выступает экспериментальной площадкой для проверки новых продвинутых возможностей функционального программирования и оптимизации.

Проприетарные приложения

Хаскель всё чаще используется в коммерческой среде[7]. Этому способствует и принятая в сообществе традиция выпускать библиотеки под либеральными лицензиями (более 70% свободно распространяемых библиотек распространяются на условиях лицензий BSD, MIT или являются общественным достоянием).

Вот примеры некоторых коммерческих приложений, написанных на Хаскеле: Bluespec SystemVerilog, язык проектирования и верификации полупроводниковых схем, является расширением Хаскеля[8]. Cryptol, коммерческий язык для разработки и проверки криптографических алгоритмов, реализован на Хаскеле. Примечательно, что первое формально верифицированное микроядро seL4 было тоже написано на Хаскеле.

Приложения с открытым исходным кодом

Также на Хаскеле написано много приложений c открытым исходным кодом. Большинство из них доступны в архиве Hackage. Вот некоторые из них:

Разработка

Более полный список см. в Hackage:Development

Базы данных

Более полный список см. в Hackage:Databases

  • haskelldb — строго типизированный интерфейс доступа к SQL-базам данных
  • HDBC — универсальный интерфейс доступа к реляционным базам данных
  • Takusen — библиотека доступа к базам данных, использующая интерфейс левой свёртки

Игры

Более полный список см. в Hackage:Games.

Графика и графические интерфейсы

Более полный список см. в Hackage:Graphics.

  • gtk2hs — библиотека для создания графических интерфейсов на основе GTK+
  • wxHaskell — библиотека для создания графических интерфейсов на основе wxWidgets
  • qtHaskell — библиотека для создания графических интерфейсов на основе Qt
  • SDL — интерфейс для использования libSDL из Хаскеля

Языки и компиляторы

Более полный список см. в Hackage:Language

  • Pugs — компилятор и интерпретатор языка Perl 6
  • Lava — язык аппаратных схем
  • Curry — функциональный логический язык Curry
  • cpphs – реализация препроцессора языка Си
  • Agda – язык программирования с зависимыми типами и доказатель теорем
  • Epigram — язык программирования с зависимыми типами
  • Flapjax — язык для реактивного программирования веб-приложений
  • Language.Python — библиотека лексического и синтаксического анализа кода на языке Python
  • Language.C — библиотека анализа и генерации кода на языке Си
  • WebBits — библиотека для работы с кодом на языке Javascript

Системные программы

Более полный список см. в Hackage:System

  • Darcs — продвинутая распределённая система контроля версий
  • Xmonad — популярный мозаичный менеджер окон
  • House – операционная система, написанная на Хаскеле

Обработка текста

Более полный список см. в Hackage:Text

  • Pandoc – универсальный конвертер текста между различными языками разметки
  • Yi – подобный Emacs-у текстовый редактор, с Хаскель в качестве скриптового языка
  • Leksah [2] – интегрированная среда разработки (IDE), написанная на Хаскеле и, в основном, для разработки на Хаскеле; поддерживает навигацию по исходным текстом, «умное» автодополнение, отладку и сборку пакетов.
  • HaXml — многофункциональная библиотека для работы с XML
  • HXT — комбинаторная библиотека для работы с XML, использующая выразительный предметно-ориентированный язык, основанный на стрелках
  • Parsec — комбинаторная библиотека для синтаксического анализа
  • The Grammatical Framework — библиотека работы с естественными языками

Интернет

Более полный список см. в Hackage:Network

См. также

Примечания

  1. Curry, Haskell (1934), "Functionality in Combinatory Logic", Proceedings of the National Academy of Sciences, vol. 20, pp. 584–590 
  2. <cite id="CITEREFCurryFeys1958">Curry, Haskell B. & Feys, Robert (1958), Combinatory Logic Vol. I, Amsterdam: North-Holland , with 2 sections by William Craig, see paragraph 9E</cite>
  3. HaskellWiki — по состоянию на 05.02.2010.
  4. The Haskell 98 Language Report — получено 05.02.2010
  5. Haskell Prime
  6. Simon Marlow, Announcing Haskell 2010
  7. (англ.)Коммерческие применения языка Хаскель
  8. Bluespec

Литература

  • Bryan O’Sullivan, John Goerzen, Don Stewart. Real World Haskell — O’Reilly, 2008—710 C. ISBN 0-596-51498-0. ISBN 978-0-596-51498-3
  • Душкин Роман Викторович Функциональное программирование на языке Haskell / Гл. ред. Д. А. Мовчан;. — М.: ДМК Пресс,, 2008. — 544 с., ил. с. — 1500 экз. — ISBN 5-94074-335-8

Ссылки


Источник — «http://www.sbup.com/wiki/Haskell»
Личные инструменты

Served in 0.656 secs.