MLton (произносится «») — кроссплатформенный полнопрограммно-оптимизирующий компилятор языка программирования (SML). Как и большинство остальных реализаций , написан на самом (за исключением рантайм-системы, написанной на Си) и распространяется с открытыми исходными кодами под лицензией в стиле BSD.
Характеристики Обеспечивает очень высокую производительность программ на : на мелких программах по скорости лишь незначительно отстаёт от Си/C++; на более крупных, за счёт полнопрограммной оптимизации на основе глобального анализа потока управления программы, способен превосходить их. Порождает самостоятельные исполнимые файлы компактного размера. Производительность в MLton обеспечивается даже при интенсивном использовании механизмов абстракции SML (параметрического полиморфизма, функций высшего порядка, функторов), что позволяет использовать язык как для быстрого прототипирования, так и в , не требуя от программиста искать баланс между абстракцией и эффективностью. Прирост скорости кода в сравнении с другими реализациями SML на разных тестах составляет от нескольких раз до нескольких порядков.
Сопровождается очень богатой документацией, в том числе описанием трюков с нетривиальным использованием языка. На сайте проекта можно найти почти полный список ссылок на существующую научную и учебную литературу по . Достаточно строго соответствует Определению языка и спецификации Базисной библиотеки. Имеется четыре отклонения от Определения, которые авторы не планируют корректировать, а наоборот, классифицируют как исправление дефектов в самом Определении.
Имеет тонкий и быстрый FFI, обеспечивающий полное двустороннее взаимодействие с языком Си (вплоть до взаимной рекурсии); а также генератор NLFFI ( — ), позволяющий встраивать заголовочные файлы Си прямо в проект на 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 . агрессивного удаления мёртвого кода (типов, функций, конструкторов типов, конструкторов, значений, аргументов функций, ветвлений и др.). глобального анализа потока управления программ и применения частных оптимизаций на основе собранной специфичной информации, в том числе: подстановки функций при условии определённого соотношения между размером её тела и количеством её вызовов, в том числе при наличии в ней циклов. дефункциализации, что не только непосредственно повышает быстродействие соответствующих участков кода, но и высвобождает дополнительную информацию об управляющей логике, которая затем используется последующими проходами оптимизации. использования нативного ( и бестегового, в отличие от большинства компиляторов функциональных языков) представления примитивных типов и массивов из них, а также плоского (не структурного) представления замыканий (ML-функций). реализации длинной арифметики (стандартная структура IntInf, сопоставимая с сигнатурой INTEGER) посредством GNU Multi-Precision Library. уплощения ссылочных типов до мутабельных переменных соответствующих независимых типов, то есть устранения косвенной адресации и экономии памяти. нескольких стратегий сборки мусора.
Подход к оптимизации, применённый в MLton, разительно отличается от традиционного. Обычные компиляторы языков с поддержкой сущностей высших порядков выполняют оптимизации непосредственно над AST, полученном после разбора грамматики и вывода типов, после чего осуществляют и низкоуровневые оптимизации. В MLton же порядок работы упрощённо выглядит так. Сперва выполняется дефункторизация и мономорфизация, в результате чего код представляется на промежуточном языке со значительно упрощённой, по сравнению с SML, системой типов, но с поддержкой функций высшего порядка. Затем следует дефункционализация и код на промежуточном языке первого порядка, состоящем только из определений верхнего уровня (SSA). И лишь затем на полученном плоском коде применяются более традиционные оптимизации (замена хвостовой рекурсии на плоскую итерацию, распространение констант, удаление мёртвого кода, выбор представления и прочее), а также плоское представление замыканий. Такая цепочка даёт выигрыш и для пользователей компилятора, и для его разработчиков: полностью устраняются потери производительности от использования механизмов абстракции ML, что позволяет использовать язык на полную мощь. глобальный анализ потока управления выделяется из прочих алгоритмов оптимизации, что делает первый продуктивнее, а последние — намного проще в реализации. Всего же MLton использует восемь промежуточных языков, в том числе нарушающих безопасность ради производительности (в отличие, например, от компилятора TILTTILT (TIL-Two) compiler , не поступающегося безопасностью до самого машинного кода), и несколько десятков проходов.
Расширения MLton предлагает ряд нестандартных библиотек: порты множества характерных библиотек , в том числе: MLRISC — написанный на SML перенаправляемый фреймворк для разработки оптимизирующих бэк-ендов компиляторов высокоуровневых языков под разные аппаратные платформы. Позволяет инкапсулировать функциональность бэк-энда, облегчая повторное использование остального кода реализации компилятора. реализация продолжений. Модуль Unsafe — небезопасные возможности, в том числе каламбуры типизации (в основном необходимы для FFI). «Тонкие» потоки, предоставляющие платформенно-независимый, но высокопроизводительный интерфейс к потокам операционной системы. Порт встраиваемого языка (CML). MLton предоставляет базовую функциональность CML, в основном повторяющую поведение имеющейся в SML/NJ, но вместо продолжений использует собственные «тонкие» потоки; однако, не реализует потоко-безопасную обёртку над Базисной библиотекой и реактивные эквиваленты функциональности модулей IO и OS. «World save and restore» — возможность дампа всего состояния программы в файл с последующим восстановлением. MLBasis — собственная система управления модулями SML, более развитая, чем CM из состава . Сопровождается автоматическим преобразователем из формата .cm в формат .mlb. и многое другое.
Существуют экспериментальные расширения самого MLton: Multi-MLton — компилятор для масштабируемых многоядерных платформ. Позволяет сочетать возможности MLton с распределёнными вычислениями (безопасные преднамеченности, предсказания, транзакции и др.). Отлаженные элементы Multi-MLton планируется объединять с MLton.
История, философия, разработчики
В апреле 1997 года Стивен Уикс () разработал дефункторизатор для , сразу показавший прирост скорости . В августе того же года была начата разработка оптимизирующего компилятора, который на тот момент назывался smlc. К октябрю был реализован мономорфизатор. За следующие полтора года smlc стал полностью независимым компилятором и был переименован в MLton, первый релиз которого состоялся в марте 1999 года. К 2005 году MLton показывал превосходные характеристики производительности программ.
С самого начала разработка велась с упором на производительность за счёт глобальной оптимизации программ.
Разработчики MLton диктуют прочтение названия своего компилятора как «», по аналогии со словом «мельница» () — вероятно, шутливо подразумевая «перемалывание программ на ML», что отражает применение агрессивных методик и программ.
Проектом MLton руководят четыре человека: Стивен Уикс () Генри Чейтин () Мэтью Флют () Суреш Джаганнатан () Немалый вклад также внесли многие другие люди.
В 2013 году проект MLton входил в программу Google Summer of Code.
Разработчики MLton являются активными участниками совета по . В 2014 году двое из них были удостоены премии «NSF CISE Research Infrastructure (CRI)» «за позиционирование MLton для исследований языка нового поколения».
Критика и сравнение с альтернативами MLton обеспечивает быстродействие программ на уровне Си/C++, вне зависимости от использованного стиля программирования.
Недостатки напрямую вытекают из применения глобального анализа и множества этапов преобразований: значительные затраты времени и памяти для работы. Например, компиляция собственного кода (более на SML) на процессоре уровня занимает и требует . отсутствие возможности раздельной компиляции. отсутствие режима REPL, характерного для большинства реализаций .
Сравнение с OCaml И OCaml, и MLton порождают программы высокого быстродействия, нередко способные соперничать с программами на Си и C++, портированы на множество платформ (хотя список не идентичен) и сопровождаются обширной документацией. Это делает актуальным вопрос об их отличиях: MLton на данный момент не имеет родного порта для Windows. OCaml работает сам и порождает программы, работающие под Windows, но отладчик работает только под Unix-like, так как использует вызов fork(). OCaml поставляется с IDE выдающегося уровня развития (например, отладчик позволяет трассировать код не только вперёд, но и назад). MLton не имеет графической среды и работает из командной строки, но некоторый дополнительный инструментарий разработчика предоставляет (например, профилировщик кода по размеру и по скорости). MLton не поддерживает режим REPL, но позволяет выводить в отдельный файл результат вывода типов. OCaml имеет два компилятора с единственным бэк-ендом для каждого — в нативный код и в байт-код — из которых первый компилирует быстро, а второй очень быстро. MLton имеет множество бэк-эндов, и вне зависимости от выбора одного из них компилирует очень медленно. OCaml не раскрывает рамки модулей и не выполняет мономорфизацию. Как следствие, он порождает эффективный код преимущественно для программ, написанных в императивном стиле и без использования полиморфизма. Для программ, интенсивно использующих функциональные идиомы, он может давать существенные потери скорости. Перенос фрагментов кода между модулями может также заметно влиять на эффективность. В отличие от него, MLton за счёт применяемых им стратегий компиляции всегда порождает максимально эффективный код, существенно снижая необходимость ручной оптимизации. Для OCaml существует отдельный дефункторизатор — Defunctorizer for OCaml. OCaml почти всегда использует представление примитивных и структурных типов и меченое представление целых: старший бит используется для различения целых и указателей, так что максимальное значение целых на платформе ограничено , либо реализуется способом. MLton использует нативное представление всех примитивных и простейших структурных типов и уплощает ссылки до мутабельных переменных. Внешнеязыковой интерфейс в MLton тоньше и эффективнее, чем в OCaml, что в значительной степени связано с предыдущим пунктом. При связывании кода на OCaml с кодом на Си требуется вручную писать обёртку в виде набора прокси-функций и обращаться к этой обёртке, а не непосредственно к библиотеке. MLton предоставляет генератор байндингов NLFFI.
Также здесь следует отметить некоторые различия между компиляторами, тесно связанные с различиями между самими языками: