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Перейти к разделу «#MLBasis».

См. также

Примечания

  1. ↑ 1 2 «MLton» Pronounce. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  2. ↑ 1 2 3 4 5 Weeks - Whole-Program Compilation in MLton, 2006.
  3. ↑ 1 2 MLton Performance. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  4. ↑ References. Дата обращения: 10 декабря 2014. Архивировано 14 декабря 2014 года.
  5. ↑ No-Longer-Foreign, 2001.
  6. ↑ Inline. Дата обращения: 21 ноября 2014. Архивировано 29 ноября 2014 года.
  7. ↑ Contify. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  8. ↑ MLton’s Intermediate Languages. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  9. ↑ TILT (TIL-Two) compiler Архивировано 9 мая 2008 года.
  10. ↑ MLRISC. Дата обращения: 18 ноября 2014. Архивировано 23 сентября 2015 года.
  11. ↑ MLton’s Extensions. Дата обращения: 13 ноября 2014. Архивировано 2 января 2015 года.
  12. ↑ Multi-MLton. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  13. ↑ MLton History. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  14. ↑ MLton Credits. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  15. ↑ Google Summer of Code 2013 (GSoC/GCI Archive). Дата обращения: 14 сентября 2016. Архивировано 23 июня 2016 года.
  16. ↑ MLton in Google Summer of Code 2013 (on MLton page). Дата обращения: 14 сентября 2016. Архивировано 23 сентября 2016 года.
  17. ↑ MLton compiler page.
  18. ↑ MLton Drawbacks. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  19. ↑ The Breakfast Post. SML and OCaml: So, why was the OCaml faster? (англ.). Дата обращения: 16 сентября 2016. Архивировано 21 сентября 2016 года.
  20. ↑ Сравнение MLton и OCaml. Дата обращения: 13 ноября 2014. Архивировано 13 ноября 2014 года.
  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.

Ссылки

  • MLton compiler page (англ.).
  • Сравнение MLton и OCaml
  • Stephen Weeks. Whole-Program Compilation in MLton ( (англ.)). — 2006. Архивировано 29 июня 2007 года.
  • Jens Olsson, Andreas Rossberg. Сравнение Standard ML и OCaml (англ.) (2009).
  • Matthias Blume. No-Longer-Foreign: Teaching an ML compiler to speak C “natively” ( (англ.)). — Elsevier Science B. V., 2001. Архивировано 4 апреля 2005 года.
  • Matthew Fluet, Riccardo Pucella. Phantom Types and Subtyping ( (англ.)). — IFIP International Conference on Theoretical Computer Science, 2002.
  • Zhong Shao, Andrew W. Appel. Space-Efficient Closure Representations ( (англ.)). — Lisp and Functional Programming, 2006.
  • Chailloux, Manoury, Pagano. Developing Applications With Objective Caml (неопр.). — 2007. — С. 349-370, Глава 11. Взаимодействие с языком Си.