MLton

MLton (произносится «ми́ллтон»[1]) — кроссплатформенный полнопрограммно-оптимизирующий компилятор языка программирования Standard ML (SML). Как и большинство остальных реализаций Standard ML, написан на самом Standard ML (за исключением рантайм-системы, написанной на Си) и распространяется с открытыми исходными кодами под лицензией в стиле BSD.

Характеристики

Обеспечивает очень высокую производительность программ на Standard ML: на мелких программах по скорости лишь незначительно отстаёт от Си/C++[2]; на более крупных, за счёт полнопрограммной оптимизации на основе глобального анализа потока управления программы, способен превосходить их. Порождает самостоятельные исполнимые файлы компактного размера. Производительность в MLton обеспечивается даже при интенсивном использовании механизмов абстракции SML (параметрического полиморфизма, функций высшего порядка, функторов), что позволяет использовать язык как для быстрого прототипирования, так и в крупномасштабном программировании, не требуя от программиста искать баланс между абстракцией и эффективностью. Прирост скорости кода в сравнении с другими реализациями SML на разных тестах составляет от нескольких раз до нескольких порядков[3].

Сопровождается очень богатой документацией, в том числе описанием трюков с нетривиальным использованием языка. На сайте проекта можно найти почти полный список ссылок на существующую научную и учебную литературу по Standard ML[4]. Достаточно строго соответствует Определению языка и спецификации Базисной библиотеки. Имеется четыре отклонения от Определения, которые авторы не планируют корректировать, а наоборот, классифицируют как исправление дефектов в самом Определении.

Имеет тонкий и быстрый FFI, обеспечивающий полное двустороннее взаимодействие с языком Си (вплоть до взаимной рекурсии); а также генератор привязок NLFFI (No-Longer-Foreign Function Interface — рус. интерфейс к отныне-более-не-чужеродным функциям), позволяющий встраивать заголовочные файлы Си прямо в проект на SML и использовать прямые вызовы функций Си в программах на SML[5].

Поддерживает множество нативных платформ (x86, IA-64, AMD64, SPARC, ARM, PowerPC/PowerPC64, DEC Alpha, HPPA, S390) и разнообразных операционных систем, в том числе различных Unix-like-систем (Debian, Fedora, *BSD). Под Windows требует Cygwin или MinGW (по состоянию на 2014 год), родной порт входит в планы разработчиков. Имеет дополнительные бэк-энды в Си, C--, LLVM; ранее имел в своём составе бэк-энд в байт-код, но его поддержку прекратили, так как он не снискал популярности.

Реализация

Эффективность и компактность программ MLton обеспечивает за счёт:

Подход к оптимизации, применённый в MLton, разительно отличается от традиционного[2]. Обычные компиляторы языков с поддержкой сущностей высших порядков выполняют оптимизации непосредственно над AST, полученном после разбора грамматики и вывода типов, после чего осуществляют преобразование замыканий и низкоуровневые оптимизации. В MLton же порядок работы упрощённо выглядит так. Сперва выполняется дефункторизация и мономорфизация, в результате чего код представляется на промежуточном языке со значительно упрощённой, по сравнению с SML, системой типов, но с поддержкой функций высшего порядка. Затем следует дефункционализация и код на промежуточном языке первого порядка, состоящем только из определений верхнего уровня (SSA). И лишь затем на полученном плоском коде применяются более традиционные оптимизации (замена хвостовой рекурсии на плоскую итерацию, распространение констант, удаление мёртвого кода, выбор представления и прочее), а также плоское представление замыканий. Такая цепочка даёт выигрыш и для пользователей компилятора, и для его разработчиков:

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

Всего же MLton использует восемь промежуточных языков[8], в том числе нарушающих безопасность ради производительности (в отличие, например, от компилятора TILT[9], не поступающегося безопасностью до самого машинного кода), и несколько десятков проходов.

Расширения

MLton предлагает ряд нестандартных библиотек:

  • порты множества характерных библиотек SML/NJ, в том числе:
    • MLRISC[10] — написанный на SML перенаправляемый фреймворк для разработки оптимизирующих бэк-ендов компиляторов высокоуровневых языков под разные аппаратные платформы. Позволяет инкапсулировать функциональность бэк-энда, облегчая повторное использование остального кода реализации компилятора.
    • реализация продолжений.
    • Модуль Unsafe — небезопасные возможности, в том числе каламбуры типизации (в основном необходимы для FFI).
  • «Тонкие» потоки, предоставляющие платформенно-независимый, но высокопроизводительный интерфейс к потокам операционной системы.
  • Порт встраиваемого языка Concurrent ML (CML). MLton предоставляет базовую функциональность CML, в основном повторяющую поведение имеющейся в SML/NJ, но вместо продолжений использует собственные «тонкие» потоки; однако, не реализует потоко-безопасную обёртку над Базисной библиотекой и реактивные эквиваленты функциональности модулей IO и OS.
  • «World save and restore» — возможность дампа всего состояния программы в файл с последующим восстановлением.
  • MLBasis — собственная система управления модулями SML, более развитая, чем CM из состава SML/NJ. Сопровождается автоматическим преобразователем из формата .cm в формат .mlb.

и многое другое[11].

Существуют экспериментальные расширения самого MLton:

История, философия, разработчики

В апреле 1997 года Стивен Уикс (англ. Stephen Weeks) разработал дефункторизатор для SML/NJ, сразу показавший прирост скорости от 2 до 6 раз. В августе того же года была начата разработка оптимизирующего компилятора, который на тот момент назывался smlc. К октябрю был реализован мономорфизатор. За следующие полтора года smlc стал полностью независимым компилятором и был переименован в MLton, первый релиз которого состоялся в марте 1999 года. К 2005 году MLton показывал превосходные характеристики производительности программ[3].

С самого начала разработка велась с упором на производительность за счёт глобальной оптимизации программ.[13]

Разработчики MLton диктуют прочтение названия своего компилятора как «ми́ллтон», по аналогии со словом «мельница» (англ. mill)[1] — вероятно, шутливо подразумевая «перемалывание программ на ML», что отражает применение агрессивных методик преобразования и рафинирования программ.

Проектом MLton руководят четыре человека:

  • Стивен Уикс (англ. Stephen Weeks)
  • Генри Чейтин (англ. Henry Cejtin)
  • Мэтью Флют (англ. Matthew Fluet)
  • Суреш Джаганнатан (англ. Suresh Jagannathan)

Немалый вклад также внесли многие другие люди[14].

В 2013 году проект MLton входил в программу Google Summer of Code[15][16].

Разработчики MLton являются активными участниками совета по successor ML. В 2014 году двое из них были удостоены премии «NSF CISE Research Infrastructure (CRI)»[17] «за позиционирование MLton для исследований языка нового поколения».

Критика и сравнение с альтернативами

MLton обеспечивает быстродействие программ на уровне Си/C++, вне зависимости от использованного стиля программирования.

Недостатки напрямую вытекают из применения глобального анализа и множества этапов преобразований:

  • значительные затраты времени и памяти для работы. Например, компиляция собственного кода (более 140 тысяч строк на SML) на процессоре уровня 1.6 ГГц занимает от 5 до 10 минут и требует более 500 Мб RAM[18].
  • отсутствие возможности раздельной компиляции.
  • отсутствие режима REPL, характерного для большинства реализаций Standard ML.

Сравнение с OCaml

И OCaml, и MLton порождают программы высокого быстродействия[19], нередко способные соперничать с программами на Си и C++, портированы на множество платформ (хотя список не идентичен) и сопровождаются обширной документацией. Это делает актуальным вопрос об их отличиях[20]:

  • MLton на данный момент не имеет родного порта для Windows. OCaml работает сам и порождает программы, работающие под Windows, но отладчик работает только под Unix-like, так как использует вызов fork().
  • OCaml поставляется с IDE выдающегося уровня развития (например, отладчик позволяет трассировать код не только вперёд, но и назад). MLton не имеет графической среды и работает из командной строки, но некоторый дополнительный инструментарий разработчика предоставляет (например, профилировщик кода по размеру и по скорости). MLton не поддерживает режим REPL, но позволяет выводить в отдельный файл результат вывода типов.
  • OCaml имеет два компилятора с единственным бэк-ендом для каждого — в нативный код и в байт-код — из которых первый компилирует быстро, а второй очень быстро. MLton имеет множество бэк-эндов, и вне зависимости от выбора одного из них компилирует очень медленно.
  • OCaml не раскрывает рамки модулей и не выполняет мономорфизацию. Как следствие, он порождает эффективный код преимущественно для программ, написанных в императивном стиле и без использования полиморфизма. Для программ, интенсивно использующих функциональные идиомы, он может давать существенные потери скорости. Перенос фрагментов кода между модулями может также заметно влиять на эффективность. В отличие от него, MLton за счёт применяемых им стратегий компиляции всегда порождает максимально эффективный код, существенно снижая необходимость ручной оптимизации. Для OCaml существует отдельный дефункторизатор[21].
  • OCaml почти всегда использует обёртнутое представление примитивных и структурных типов и меченое представление целых: старший бит используется для различения целых и указателей, так что максимальное значение целых на 32-разрядной платформе ограничено 31 битом, либо реализуется обёртнутым способом. MLton использует нативное представление всех примитивных и простейших структурных типов и уплощает ссылки до мутабельных переменных.
  • Внешнеязыковой интерфейс в MLton тоньше и эффективнее, чем в OCaml, что в значительной степени связано с предыдущим пунктом. При связывании кода на OCaml с кодом на Си требуется вручную писать обёртку в виде набора прокси-функций и обращаться к этой обёртке, а не непосредственно к библиотеке[22]. MLton предоставляет генератор байндингов NLFFI.

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

  • Оба несут в своём составе реализацию Lex/Yacc (соответственно, ocamllex/ocamlyacc и MLLex/MLYacc). В дополнение OCaml имеет параметрический парсер CamlpX, позволяющий изменять синтаксис языка в очень широком диапазоне и являющийся удобным средством для разработки встраиваемых языков. MLton не предусматривает ничего аналогичного.
  • Экосистема OCaml лучше развита: для OCaml накоплено довольно много библиотек и сообщество OCaml существенно больше, чем сообщество Standard ML. Для Standard ML библиотек существенно меньше, но реализация FFI и NLFFI в MLton позволяет без труда обеспечить двустороннее взаимодействие с библиотеками на Си.
  • В OCaml действует политика «один модуль в одном файле», и знание об этом используется компилятором для поддержки крупномасштабного программирования. Standard ML не диктует такого правила, а MLton предоставляет собственную систему управления модулями SML — MLBasis.

См. также

Примечания
  1. «MLton» Pronounce
  2. Weeks - Whole-Program Compilation in MLton, 2006.
  3. MLton Performance
  4. References
  5. No-Longer-Foreign, 2001.
  6. Inline
  7. Contify
  8. MLton’s Intermediate Languages
  9. TILT (TIL-Two) compiler Архивировано 9 мая 2008 года.
  10. MLRISC
  11. MLton’s Extensions
  12. Multi-MLton
  13. MLton History
  14. MLton Credits
  15. Google Summer of Code 2013 (GSoC/GCI Archive)
  16. MLton in Google Summer of Code 2013 (on MLton page)
  17. MLton compiler page.
  18. MLton Drawbacks
  19. The Breakfast Post. SML and OCaml: So, why was the OCaml faster? (англ.).
  20. Сравнение MLton и OCaml
  21. The Caml Hump: ocamldefun (недоступная ссылка). Calcul Statique des Applications de Modules Parametres. Julien Signoles. JFLA 2003. (2010). Дата обращения: 10 декабря 2014. Архивировано 4 ноября 2015 года. — Defunctorizer for OCaml
  22. Chailloux, Manoury, Pagano, "Developing with OCaml", 2007.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.