Компилятор Глазго Haskell

Компилятор для языка программирования Haskell

Glasgow Haskell Compiler ( GHC ) — это собственный или машинный компилятор кода для функционального языка программирования Haskell . ^[5] Он предоставляет кроссплатформенную программную среду для написания и тестирования кода Haskell и поддерживает множество расширений, библиотек и оптимизаций, которые упрощают процесс генерации и выполнения кода. GHC — наиболее часто используемый компилятор Haskell. ^[6] Это бесплатное программное обеспечение с открытым исходным кодом , выпущенное под лицензией BSD .

История

GHC изначально был начат в 1989 году как прототип, написанный на Lazy ML (LML) Кевином Хаммондом в Университете Глазго . Позже в том же году прототип был полностью переписан на Haskell, за исключением его парсера , Корделией Холл, Уиллом Партейном и Саймоном Пейтоном Джонсом. Его первый бета-релиз состоялся 1 апреля 1991 года. Более поздние выпуски добавили анализатор строгости и расширения языка, такие как монадический ввод-вывод , изменяемые массивы, неупакованные типы данных, параллельные и параллельные модели программирования (такие как программная транзакционная память и параллелизм данных ) и профилировщик . ^[2]

Пейтон Джонс и Марлоу позже перешли в Microsoft Research в Кембридже , где они продолжили нести основную ответственность за разработку GHC. GHC также содержит код более чем трехсот других участников. ^[1] С 2009 по 2014 год сторонние вклады в GHC финансировались Industrial Haskell Group. ^[7]

Имена GHC

С ранних выпусков официальный сайт ^[8] называл GHC The Glasgow Haskell Compiler , тогда как в команде исполняемой версии он идентифицировался как The Glorious Glasgow Haskell Compilation System . ^[9] Это было отражено в документации. ^[10] Первоначально он имел внутреннее название The Glamorous Glasgow Haskell Compiler . ^[11]

Архитектура

GHC написан на языке Haskell , ^[12] но система выполнения для Haskell, необходимая для запуска программ, написана на языках C и C-- .

Интерфейс GHC , включающий лексер , парсер и проверку типов , разработан для сохранения как можно большего количества информации об исходном языке до завершения вывода типов , с целью предоставления пользователям четких сообщений об ошибках. ^[2] После проверки типов код Haskell десахаризируется в типизированный промежуточный язык, известный как «Core» (основанный на System F , расширенный выражениями letи case). Core был расширен для поддержки обобщенных алгебраических типов данных в своей системе типов и теперь основан на расширении System F, известном как System F _C . ^[13]

В традиции компиляции с управлением типами, упроститель GHC, или «средняя часть», где выполняется большинство оптимизаций, реализованных в GHC, структурирован как ряд преобразований исходного кода в исходный. Анализы и преобразования, выполняемые на этом этапе компиляции, включают анализ спроса (обобщение анализа строгости ), применение пользовательских правил перезаписи (включая набор правил, включенных в стандартные библиотеки GHC, которые выполняют слияние foldr/build ), разворачивание (называемое « встраиванием » в более традиционных компиляторах), let-floating, анализ, который определяет, какие аргументы функции могут быть распакованы, анализ результата сконструированного продукта , специализация перегруженных функций и набор более простых локальных преобразований, таких как сворачивание констант и бета-редукция . ^[14]

Бэкэнд компилятора преобразует код Core во внутреннее представление C-- через промежуточный язык STG (сокращение от "Spineless Tagless G-machine"). ^[15] Затем код C-- может пойти одним из трех путей: он либо печатается как код C для компиляции с GCC , либо преобразуется непосредственно в машинный код (традиционная фаза " генерации кода "), либо преобразуется в LLVM IR для компиляции с LLVM. Во всех трех случаях полученный машинный код в конечном итоге связывается с системой выполнения GHC для создания исполняемого файла.

Язык

GHC соответствует стандартам языка, как Haskell 98 ^[16] , так и Haskell 2010. [ ^17] Он также поддерживает множество дополнительных расширений стандарта Haskell: например, библиотеку программной транзакционной памяти (STM), которая позволяет выполнять составные транзакции памяти .

Расширения для Haskell

Было предложено много расширений для Haskell. Они предоставляют возможности, не описанные в спецификации языка, или переопределяют существующие конструкции. Таким образом, каждое расширение может не поддерживаться всеми реализациями Haskell. Продолжаются усилия ^[18] по описанию расширений и выбору тех, которые будут включены в будущие версии спецификации языка.

Расширения ^[19], поддерживаемые компилятором Glasgow Haskell, включают:

• Неупакованные типы и операции. Они представляют примитивные типы данных базового оборудования без косвенного указания указателя на кучу или возможности отложенной оценки. Численно-интенсивный код может быть значительно быстрее при кодировании с использованием этих типов.
• Возможность указать строгую оценку для поля значения, привязки шаблона или типа данных.
• Более удобный синтаксис для работы с модулями, шаблонами, списочными генераторами , операторами, записями и кортежами.
• Синтаксический сахар для вычислений со стрелками и рекурсивно определенными монадическими значениями. Обе эти концепции расширяют монадическую do- нотацию, предоставленную в стандартном Haskell.
• Значительно более мощная система типов и классов типов, описанная ниже.
• Template Haskell , система для метапрограммирования времени компиляции . Выражения могут быть написаны для создания кода Haskell в форме абстрактного синтаксического дерева . Эти выражения проверяются на соответствие типам и оцениваются во время компиляции; сгенерированный код затем включается, как если бы он был частью исходного кода. Вместе с возможностью размышлять над определениями, это обеспечивает мощный инструмент для дальнейших расширений языка.
• Квазикавычки, которые позволяют пользователю определять новый конкретный синтаксис для выражений и шаблонов. Квазикавычки полезны, когда метапрограмма, написанная на Haskell, манипулирует кодом, написанным на языке, отличном от Haskell.
• Универсальные классы типов, которые определяют функции исключительно в терминах алгебраической структуры типов, с которыми они работают.
• Параллельная оценка выражений с использованием нескольких ядер ЦП. Это не требует явного создания потоков. Распределение работы происходит неявно, на основе аннотаций, предоставленных в программе.
• Прагмы компилятора для управления оптимизацией, такой как встроенное расширение и специализированные функции для определенных типов.
• Настраиваемые правила перезаписи — это правила, описывающие, как заменить одно выражение эквивалентным, но более эффективно оцененным выражением. Они используются в библиотеках основных структур данных для обеспечения улучшенной производительности во всем коде уровня приложения. ^[20]
• Синтаксис записи с точкой. Предоставляет синтаксический сахар для доступа к полям (потенциально вложенной) записи, который похож на синтаксис многих других языков программирования. ^[21]

Расширения системы типов

Выразительная статическая система типов является одной из основных определяющих особенностей Haskell. Соответственно, большая часть работы по расширению языка была направлена ​​на типы данных и классы типов .

Компилятор Glasgow Haskell поддерживает расширенную систему типов, основанную на теоретической системе F C. _[ ^13] Основные расширения системы типов включают в себя:

• Произвольный ранг и непредикативный полиморфизм . По сути, полиморфная функция или конструктор типов данных может потребовать, чтобы один из его аргументов также был полиморфным.
• Обобщенные алгебраические типы данных . Каждый конструктор полиморфного типа данных может кодировать информацию в результирующий тип. Функция, которая сопоставляется с образцом для этого типа, может использовать информацию о типе для каждого конструктора для выполнения более конкретных операций с данными.
• Экзистенциальные типы . Их можно использовать для «связывания» некоторых данных с операциями над этими данными таким образом, что операции можно использовать без раскрытия конкретного типа базовых данных. Такое значение очень похоже на объект, который встречается в объектно-ориентированных языках программирования .
• Типы данных, которые на самом деле не содержат никаких значений. Они могут быть полезны для представления данных в метапрограммировании на уровне типов .
• Семейства типов : определяемые пользователем функции из типов в типы. В то время как параметрический полиморфизм обеспечивает одну и ту же структуру для каждого экземпляра типа, семейства типов обеспечивают полиморфизм ad hoc с реализациями, которые могут различаться между экземплярами. Варианты использования включают контейнеры оптимизации с учетом содержимого и метапрограммирование на уровне типа.
• Неявные параметры функции, имеющие динамическую область действия . Они представлены в типах во многом так же, как ограничения класса типа.
• Линейные типы (GHC 9.0)

Расширения, относящиеся к классам типов, включают:

• Класс типов может быть параметризован на более чем одном типе. Таким образом, класс типов может описывать не только набор типов, но и n -арное отношение на типах.
• Функциональные зависимости , которые ограничивают части этого отношения, чтобы они были математической функцией типов. То есть, ограничение указывает, что некоторый параметр класса типа полностью определяется, как только фиксируется некоторый другой набор параметров. Это направляет процесс вывода типа в ситуациях, где в противном случае была бы неоднозначность.
• Значительно смягчены правила относительно допустимой формы экземпляров классов типов. Когда они включены полностью, система классов типов становится полным по Тьюрингу языком для логического программирования во время компиляции.
• Семейства типов, как описано выше, также могут быть связаны с классом типов.
• Автоматическая генерация определенных экземпляров классов типов расширена несколькими способами. Поддерживаются новые классы типов для обобщенного программирования и общие шаблоны рекурсии. Кроме того, когда новый тип объявляется как изоморфный существующему типу, любой экземпляр класса типа, объявленный для базового типа, может быть поднят до нового типа «бесплатно».

Портативность

Версии GHC доступны для нескольких систем или вычислительных платформ , включая Windows и большинство разновидностей Unix (таких как Linux , FreeBSD , OpenBSD и macOS ). ^[22] GHC также был портирован на несколько различных архитектур процессоров . ^[22]

Смотрите также

• Объятия (переводчик)
• Yhc
• Платформа Хаскелл

Ссылки

1. "The GHC Team". Haskell.org . Получено 1 сентября 2016 г. .
2. Hudak, P.; Hughes, J.; Peyton Jones, S .; Wadler, P. (июнь 2007 г.). "История Haskell: ленивые отношения с классами" (PDF) . Процедуры Третьей конференции ACM SIGPLAN по истории языков программирования (HOPL-III) . Получено 1 сентября 2016 г.
3. "Загрузить – Компилятор Glasgow Haskell". Haskell.org .
4. "Устаревание 32-битных платформ Darwin и Windows". Команда GHC.
5. "The Glorious Glasgow Haskell Compilation System User's Guide". Haskell.org . Получено 27 июля 2014 г. .
6. "Результаты опроса о состоянии Haskell за 2017 год". taylor.fausak.me . 15 ноября 2017 г. Получено 11 декабря 2017 г.
7. "Industrial Haskell Group". Haskell.org . 2014 . Получено 1 сентября 2016 .
8. "GHC The Glasgow Haskell Compiler". Haskell.org . Получено 14 января 2022 г. .
9. "Репозиторий: configure.ac". gitlab.haskell.org . 12 января 2022 г. . Получено 14 января 2022 г. .
10. "The Glorious Glasgow Haskell Compilation System User's Guide, Version 7.6.3". downloads.haskell.org . Получено 14 января 2022 г. .
11. "ghc-0.29-src.tar.gz" ( tar gzip ) . downloads.haskell.org . Файл: ghc-0.29/ghc/PATCHLEVEL . Получено 14 января 2022 г. .
12. "GHC Commentary: The Compiler". Haskell.org . 23 марта 2016 г. Архивировано из оригинала 23 марта 2016 г. Получено 26 мая 2016 г.
13. Sulzmann, M.; Chakravarty, MMT; Peyton Jones, S .; Donnelly, K. (январь 2007 г.). "Система F с приведением типов к равенству". Процедуры семинара ACM по типам в разработке и реализации языков (TLDI) .
14. Пейтон Джонс, С. (апрель 1996 г.). «Компиляция Haskell путем преобразования программ: отчет с окопов». Процедуры Европейского симпозиума по программированию (ESOP) .
15. Пейтон Джонс, С. (апрель 1992 г.). «Реализация ленивых функциональных языков на стандартном оборудовании: бесхребетная безтеговая G-машина, версия 2.5». Журнал функционального программирования . 2 (2): 127–202. doi :10.1017/S0956796800000319.
16. "Язык и библиотеки Haskell 98: пересмотренный отчет". Haskell.org . Получено 28 января 2007 г. .
17. "Haskell 2010 Language Report". Haskell.org . Получено 30 августа 2012 .
18. "Welcome to Haskell' (Haskell Prime)". Haskell.org . Архивировано из оригинала 20 февраля 2016 . Получено 26 мая 2016 .
19. "GHC Language Features". Haskell.org . Архивировано из оригинала 29 июня 2016 . Получено 25 мая 2016 .
20. Coutts, D.; Leshchinskiy, R.; Stewart, D. (апрель 2007 г.). "Stream Fusion: From Lists to Streams to Nothing at All". Процедуры Международной конференции ACM SIGPLAN по функциональному программированию (ICFP) . Архивировано из оригинала 23 сентября 2007 г.
21. Митчелл, Нил; Флетчер, Шейн (3 мая 2020 г.). «Record Dot Syntax». ghc-proposals . GitHub . Получено 30 июня 2020 г. .
22. Платформы на gitlab.haskell.org

Внешние ссылки

• Официальный сайт