Язык и библиотеки Haskell 98

Язык и библиотеки Haskell 98

2-е издание, исправленное

Jones S.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Язык и библиотеки Haskell 98/ S. Jones - М.: Национальный Открытый Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2008-2016
(c) Jones S., 2008-2016

3

Предисловие

Авторы подразумевают, что это “Описание” принадлежит всему сообществу Haskell, и
поэтому дают разрешение копировать и распространять его с любой целью, при
условии, что оно будет воспроизведено полностью, включая это уведомление.
Измененные версии этого “Описания” можно также копировать и распространять с
любой целью, при условии, что измененная версия ясно представлена как таковая и не
претендует на то, чтобы являться определением языка Haskell 98

Авторы: Lennart Augustsson, Dave Barton, Brian Boutel, Warren Burton, Joseph Fasel,
Kevin Hammond, Ralf Hinze, Paul Hudak, John Hughes, Thomas Johnsson, Mark Jones,
John Launchbury, Erik Meijer, John Peterson, Alastair Reid, Colin Runciman, Philip Wadler.

Перевод выполнен М.Ю.Ландиной и В.А.Рогановым

Около полдюжины человек формально написали комбинаторную логику, и
большинство из них, включая нас, допустили ошибки. Поскольку некоторые из наших
приятелей-грешников относятся к наиболее аккуратным и компетентным логикам
современности, мы рассматриваем данный факт как доказательство того, что ошибок
трудно избежать. Таким образом, полнота описания необходима для точности, и
чрезмерная краткость была бы здесь ложной экономией, даже больше, чем обычно. (в
предисловии к Комбинаторной Логике [2], 31 мая 1956)

Хаскелл Б. Карри (Haskell B. Curry) и Роберт Фейс (Robert Feys)

В сентябре 1987 на конференции “Языки функционального программирования и
компьютерная архитектура” (FPCA ‘87) в Портленде, штат Орегон, было организовано
заседание для того, чтобы обсудить плачевную ситуацию, сложившуюся в сообществе
функционального программирования: возникло более дюжины нестрогих чисто
функциональных языков программирования, сходных в выразительной мощности и
семантических основах. Участники встречи пришли к твердому мнению, что более
широкому использованию этого класса функциональных языков препятствовало
отсутствие общего языка. Было решено, что должен быть сформирован комитет для
разработки такого языка, который обеспечил бы более быстрое средство связи новых
идей, устойчивой основы для разработки реальных приложений и механизма
поощрения других людей использовать функциональные языки. Этот документ
описывает результат усилий этого комитета - чисто функциональный язык
программирования, названный Haskell , в честь логика Хаскелла Б. Карри (Haskell B.
Curry), чей труд обеспечивает логическую основу для многих наших работ.

Цели

Основная цель комитета заключалась в разработке языка, который удовлетворял бы
следующим требованиям:

1. Язык должен быть пригоден для обучения, исследований и приложений, включая

построение больших систем.

4

2. Язык должен полностью описываться с помощью формальных синтаксиса и

семантики.

3. Язык должен находиться в свободном доступе. Следует разрешить свободную

реализацию и распространение языка.

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

программирования.

Haskell 98: язык и библиотеки

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

Haskell действительно непрерывно развивался с тех пор, как было опубликовано его
первоначальное описание. К середине 1997 было выполнено четыре итерации в
разработке языка (самая последняя на тот момент - Haskell 1.4). В 1997 на семинаре по
Haskell в Амстердаме было решено, что необходим стабильный вариант Haskell , этот
стабильный вариант языка является темой настоящего описания и называется “Haskell
98”.

Haskell 98 задумывался как относительно незначительная модификация Haskell 1.4,
выполненная за счет некоторых упрощений и удаления некоторых подводных камней.
Он предназначен играть роль “стабильного” языка в том смысле, что разработчики
выполняют поддержку Haskell 98 в точности с его спецификацией, для обеспечения
предсказуемости в будущем.

Первоначальное описание Haskell описывало только язык и стандартную библиотеку,
названную Prelude. К тому времени, когда Haskell 98 был признан стабильной версией,
стало ясно, что многим программам необходим доступ к большому набору
библиотечных функций (особенно это касается ввода - вывода и взаимодействия с
операционной системой). Если эта программа должна быть переносимой, набор
библиотек также должен быть стандартизирован. Поэтому отдельный комитет (в
который входили некоторые из членов комитета по разработке языка) начал вносить
исправления в библиотеки Haskell 98.

Описания языка Haskell 98 и библиотек были опубликованы в феврале 1999.

Внесение исправлений в описание Haskell 98

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

Исправить типографские ошибки.
Разъяснить непонятные переходы.
Разрешить неоднозначности.
С неохотой сделать небольшие изменения, чтобы язык стал более

5

последовательным.

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

Этот документ является результатом описанного процесса усовершенствования. Он
включает и описание языка Haskell 98, и описание библиотек и составляет
официальную спецификацию обоих. Он не является учебным пособием по
программированию на Haskell , как краткий вводный курс “Gentle Introduction” [6], и
предполагает некоторое знакомство читателя с функциональными языками.

Полный текст обоих описаний доступен в режиме онлайн (см. ниже “Ресурсы Haskell
“).

Расширения Haskell 98

Haskell продолжает развиваться и сильно продвинулся дальше Haskell 98. Например, на
момент написания этого документа имеются реализации Haskell , которые
поддерживают:

Синтаксические возможности, включая:

стражи образцов;
рекурсивную do-нотацию;
лексически ограниченные переменные типа;
возможности для метапрограммирования.

Новации в системе типов, включая:

классы типов, использующие множество параметров;
функциональные зависимости;
экзистенциальные типы;
локальный универсальный полиморфизм и типы произвольного ранга.

Расширения управления, включая:

монадическое состояние;
исключения;
параллелизм

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

6

или использовать Haskell для обучения, мог осуществить задуманное, зная, что Haskell
98 продолжит существование.

Ресурсы Haskell

Web-сайт Haskell ссылка: http://haskell.org предоставляет доступ ко многим полезным
ресурсам, включая:

Online-версии определений языка и библиотек, включая полный список всех
различий между Haskell 98, выпущенным в феврале 1999, и этой исправленной
версией.
Обучающий материал по Haskell .
Детали рассылки Haskell .
Реализации Haskell .
Дополнительные средства и библиотеки Haskell .
Приложения Haskell .

Приглашаем Вас комментировать, предлагать усовершенствования и критиковать язык
или его представление в описании посредством рассылки Haskell .

Построение языка

Haskell создан и продолжает поддерживаться активным сообществом исследователей и
прикладных программистов. Те, кто входил в состав комитетов по языку и
библиотекам, в частности, посвятили огромное количество времени и энергии языку.
Их имена, а также присоединившиеся к ним на тот период организации перечислены
ниже: Arvind (MIT), Lennart Augustsson (Chalmers University), Dave Barton (Mitre Corp),
Brian Boutel (Victoria University of Wellington), Warren Burton (Simon Fraser University),
Jon Fairbairn (University of Cambridge), Joseph Fasel (Los Alamos National Laboratory),
Andy Gordon (University of Cambridge), Maria Guzman (Yale University), Kevin Hammond
[редактор] (University of Glasgow), Ralf Hinze (University of Bonn), Paul Hudak
[редактор] (Yale University), John Hughes [редактор] (University of Glasgow; Chalmers
University), Thomas Johnsson (Chalmers University), Mark Jones (Yale University,
University of Nottingham, Oregon Graduate Institute), Dick Kieburtz (Oregon Graduate
Institute), John Launchbury (University of Glasgow; Oregon Graduate Institute), Erik Meijer
(Utrecht University), Rishiyur Nikhil (MIT), John Peterson [редактор] (Yale University),
Simon Peyton Jones [редактор] (University of Glasgow; Microsoft Research Ltd), Mike
Reeve (Imperial College), Alastair Reid (University of Glasgow), Colin Runciman
(University of York), Philip Wadler [редактор] (University of Glasgow), David Wise
(Indiana University), Jonathan Young (Yale University)

Те, кто помечены [редактор], работали в качестве координирующих редакторов одной
или более ревизий языка.

Кроме того, множество других людей внесли свой вклад, некоторые - небольшой, но
многие - существенный. Это следующие люди: Kris Aerts, Hans Aberg, Sten Anderson,

7

Richard Bird, Stephen Blott, Tom Blenko, Duke Briscoe, Paul Callaghan, Magnus Carlsson,
Mark Carroll, Manuel Chakravarty, Franklin Chen, Olaf Chitil, Chris Clack, Guy Cousineau,
Tony Davie, Craig Dickson, Chris Dornan, Laura Dutton, Chris Fasel, Pat Fasel, Sigbjorn
Finne, Michael Fryers, Andy Gill, Mike Gunter, Cordy Hall, Mark Hall, Thomas Hallgren,
Matt Harden, Klemens Hemm, Fergus Henderson, Dean Herington, Ralf Hinze, Bob
Hiromoto, Nic Holt, Ian Holyer, Randy Hudson, Alexander Jacobson, Patrik Jansson, Robert
Jeschofnik, Orjan Johansen, Simon B. Jones, Stef Joosten, Mike Joy, Stefan Kahrs, AnttiJuhani Kaijanaho, Jerzy Karczmarczuk, Wolfram Kahl, Kent Karlsson, Richard Kelsey, SiauCheng Khoo, Amir Kishon, Feliks Kluzniak, Jan Kort, Marcin Kowalczyk, Jose Labra, Jeff
Lewis, Mark Lillibridge, Bjorn Lisper, Sandra Loosemore, Pablo Lopez, Olaf Lubeck, Ian
Lynagh, Christian Maeder, Ketil Malde, Simon Marlow, Michael Marte, Jim Mattson, John
Meacham, Sergey Mechveliani, Gary Memovich, Randy Michelsen, Rick Mohr, Andy
Moran, Graeme Moss, Henrik Nilsson, Arthur Norman, Nick North, Chris Okasaki, Bjarte M.
Ostvold, Paul Otto, Sven Panne, Dave Parrott, Ross Paterson, Larne Pekowsky, Rinus
Plasmeijer, Ian Poole, Stephen Price, John Robson, Andreas Rossberg, George Russell,
Patrick Sansom, Michael Schneider, Felix Schroeter, Julian Seward, Nimish Shah, Christian
Sievers, Libor Skarvada, Jan Skibinski, Lauren Smith, Raman Sundaresh, Josef
Svenningsson, Ken Takusagawa, Satish Thatte, Simon Thompson, Tom Thomson, Tommy
Thorn, Dylan Thurston, Mike Thyer, Mark Tullsen, David Tweed, Pradeep Varma, Malcolm
Wallace, Keith Wansbrough, Tony Warnock, Michael Webber, Carl Witty, Stuart Wray и
Bonnie Yantis.

Наконец, кроме важной основополагающей работы Россера (Rosser), Карри (Curry) и
других, положенной в основу лямбда-исчисления, будет правильным признать влияние
многих заслуживающих внимания языков программирования, разработанных за эти
годы. Хотя трудно точно определить происхождение многих идей, следующие языки
были особенно важны: Lisp (и его современные воплощения Common Lisp и Scheme),
ISWIM Ландина (Landin), APL, FP [1] Бэкуса (Backus), ML и Standard ML, Hope и Hope
+, Clean, Id, Gofer, Sisal и ряд языков Тернера (Turner), завершившиеся созданием
Miranda (Miranda является торговой маркой Research Software Ltd.). Без этих
предшественников Haskell был бы невозможен.

Саймон Пейтон Джонс (Simon Peyton Jones) Кембридж, сентябрь 2002

8

Введение

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

Это описание определяет синтаксис программ на Haskell и неформальную абстрактную
семантику для понимания смысла таких программ.

Мы не рассматриваем способы, которыми программы на Haskell управляются,
интерпретируются, компилируются и т.д., поскольку они зависят от реализации,
включая такие вопросы, как характер сред программирования и сообщения об
ошибках, возвращаемые для неопределенных программ (т.е. программ, формальное
вычисление которых приводит к 
 ).

1.1. Структура программы

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

1. Самый верхний уровень программы на Haskell представляет собой набор модулей,

описанных в лекции 5. Модули предоставляют средство управления
пространствами имен и повторного использования программного обеспечения в
больших программах.

2. Верхний уровень модуля состоит из совокупности объявлений, которых

существует несколько видов, все они описаны в лекции 4. Объявления определяют
такие сущности, как обычные значения, типы данных, классы типов,
ассоциативность и приоритеты операторов.

3. На следующем, более низком, уровне находятся выражения , описанные в лекции

3. Выражение обозначает значение и имеет статический тип; выражения лежат в
основе программирования на Haskell “в малом”.

4. На нижнем уровне находится лексическая структура Haskell , определенная в

лекции 2.Лексическая структура охватывает конкретное представление программ
на Haskell в текстовых файлах.

Данное описание направлено снизу вверх по отношению к синтаксической структуре
Haskell.

Лекции, которые не упомянуты выше, - это лекция 6, которая описывает стандартные

9

встроенные типы данных и классы в Haskell , и лекция 7, в которой рассматривается
средство ввода - вывода в Haskell (т.е. как программы на Haskell связываются со
внешним миром). Также есть несколько лекций, описывающих Prelude, конкретный
синтаксис, грамотное программирование, подробное описание производных
экземпляров и псевдокомментарии, поддерживаемые большинством компиляторов
Haskell.

Примеры фрагментов программ на Haskell в данном тексте даны в машинописном
шрифте:

let x = 1

z = x+y

in z+1

“Дыры” во фрагментах программ, представляющие собой произвольные части кода на
Haskell , написаны в курсиве, как, например, в if e1 then e2 else e3. Вообще
курсивные имена являются мнемоническими, например, e - для выражений
(expressions), d - для объявлений (declarations), t - для типов (types) и т.д.

1.2. Ядро Haskell

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

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

1.3. Значения и типы

Результатом вычисления выражения является значение. Выражение имеет статический
тип. Значения и типы не смешаны в Haskell. Тем не менее, система типов допускает
определяемые пользователем типы данных различных видов и разрешает не только
параметрический полиморфизм (используя традиционную структуру типов ХиндлиМилнера (Hindley-Milner)), но также специальный полиморфизм, или перегрузку
(используя классы типов).

Ошибки в Haskell семантически эквивалентны 
. С формальной точки зрения они не

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

10