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

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

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

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

Имеет тонкий и быстрый , обеспечивающий полное двустороннее взаимодействие с языком Си (вплоть до взаимной рекурсии ); а также генератор 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 предлагает ряд нестандартных библиотек:

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

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

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

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

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

В апреле 1997 года Стивен Уикс ( англ. Stephen Weeks ) разработал дефункторизатор для , сразу показавший прирост скорости от 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 предоставляет генератор байндингов .

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

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

См. также

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

Примечания

Ссылки

• (англ.) .
• Stephen Weeks. ( (англ.) ). — 2006. 29 июня 2007 года.
• Jens Olsson, Andreas Rossberg. (англ.) (2009).
• Matthias Blume. ( (англ.) ). — Elsevier Science B. V., 2001. 4 апреля 2005 года.
• Matthew Fluet, Riccardo Pucella. ( (англ.) ). — IFIP International Conference on Theoretical Computer Science, 2002.
• Zhong Shao, Andrew W. Appel. ( (англ.) ). — Lisp and Functional Programming, 2006.
• Chailloux, Manoury, Pagano. Developing Applications With Objective Caml (неопр.) . — 2007. — С. 349-370, Глава 11. Взаимодействие с языком Си.