MLton

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

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

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

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

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

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

Реализация

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

• дефункторизации, то есть раскрутки модулей SML до определений верхнего уровня. Дефункторизатор был первым шагом разработки MLton.
• мономорфизации, делающей параметрический полиморфизм «бесплатным». В отличие от шаблонов C++, за счёт сочетания с другими методиками оптимизации в MLton это не приводит к лавинообразному раздуванию кода: по данным разработчиков, увеличение машинного кода за счёт мономорфизации в MLton не превышает 30 %.
• агрессивного удаления мёртвого кода (типов, функций, конструкторов типов, конструкторов, значений, аргументов функций, ветвлений и др.).
• глобального анализа потока управления программ и применения частных оптимизаций на основе собранной специфичной информации, в том числе:
  • подстановки функций при условии определённого соотношения между размером её тела и количеством её вызовов, в том числе при наличии в ней циклов.
  • дефункциализации, что не только непосредственно повышает быстродействие соответствующих участков кода, но и высвобождает дополнительную информацию об управляющей логике, которая затем используется последующими проходами оптимизации.
• использования нативного (необёрнутого и бестегового, в отличие от большинства компиляторов функциональных языков) представления примитивных типов и массивов из них, а также плоского (не структурного) представления замыканий (ML-функций).
• реализации длинной арифметики (стандартная структура IntInf, сопоставимая с сигнатурой INTEGER) посредством GNU Multi-Precision Library.
• уплощения ссылочных типов до мутабельных переменных соответствующих независимых типов, то есть устранения косвенной адресации и экономии памяти.
• нескольких стратегий сборки мусора.

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

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

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

Расширения

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

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

и многое другое.

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

• Multi-MLton — компилятор для масштабируемых многоядерных платформ. Позволяет сочетать возможности MLton с распределёнными вычислениями (безопасные преднамеченности, предсказания, транзакции и др.). Отлаженные элементы Multi-MLton планируется объединять с MLton.

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

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

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

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

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

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

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

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

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

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

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

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

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

Сравнение с OCaml

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

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

См. также

• Standard ML и другие его реализации (в т.ч. SML/NJ)*
• Язык модулей ML
• Concurrent ML
• Оптимизирующий компилятор
• Преобразование замыканий
• OCaml

Ссылки

• 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. Взаимодействие с языком Си.