Standard ML

Материал из Википедии — свободной энциклопедии
(перенаправлено с «SML»)
Перейти к: навигация, поиск
Standard ML
Семантика:

Формальная, ориентированная на интерпретацию

Класс языка:

аппликативный,
функциональный,
императивный

Тип исполнения:

общего назначения

Появился в:

1984[1], 1990[2], 1997[3]

Автор:

Робин Милнер и другие>>>

Расширение файлов:

.sml

Выпуск:

SML/NJ 110.76,
MLton 20130715

Система типов:

Хиндли — Милнера

Основные реализации:

SML/NJ[en], MLton и другие>>>

Диалекты:

Alice>>>, SML#>>>, Manticore>>> и другие

Испытал влияние:

Lisp, ISWIM, ML, POP-2[en], Hope, Clear[en][4]

Повлиял на:

Erlang, OCaml, Haskell,
successor ML (sML)

Лицензия:

открытое ПО

Сайт:

sml-family.org

Платформа:

x86, AMD64, PowerPC, ARM, SPARC, S390, DEC Alpha, MIPS, HPPA, PDP-11,
JVM, .Net, LLVM, C--,
TAL[en], Си>>>, Ada>>>

ОС:

Standard ML — компилируемый язык программирования общего назначения высшего порядка[en], основанный на системе типов Хиндли — Милнера.

Отличается точным (rigorous) определением (гарантирующим идентичность смысла программ вне зависимости от компилятора и аппаратного обеспечения), имеющим математически доказанную надёжность статической и динамической семантики. Является «в основном функциональным» языком[5][6], то есть поддерживает большинство технических свойств функциональных языков, но также предоставляет развитые возможности императивного программирования при необходимости. Сочетает устойчивость программ, гибкость на уровне динамически типизируемых языков и быстродействие>>> на уровне языка Си, обеспечивает превосходную поддержку как быстрого прототипирования, так и модульности и крупномасштабного программирования[en][7][8].

SML был первым самостоятельным компилируемым языком в семействе ML и до сих пор служит опорным языком в сообществе по развитию ML (successor ML)[9]. В SML впервые была реализована уникальная аппликативная система модулей — см. язык модулей ML.

Содержание

Общие сведения[править | править вики-текст]

Язык изначально ориентирован на крупномасштабное программирование[en] программных систем и предоставляя эффективные средства абстракции и модульности, обеспечивая высокий коэффициент повторного использования кода, что делает его подходящим также для быстрого прототипирования программ, в том числе крупномасштабных[en]. Например, в процессе разработки (тогда ещё экспериментального) компилятора SML/NJ[en]>>> (60 тысяч строк на SML), на котором отрабатывались многие стандартизированные впоследствии идеи языка, а также стандартная библиотека и ряд расширений,— радикальные изменения в реализации ключевых структур данных, влияющих на десятки модулей, вносились в течение дня.[7] (см. также ICFP Programming Contest за 2008, 2009.)

SML известен своим относительно низким порогом вхождения и служит языком обучения программированию во многих университетах мира[10]. Обширно документирован в рабочем виде, активно используется учёными в качестве базы для исследования новых элементов языков программирования и идиом (см., например, полиморфизм структурных типов). К настоящему времени все реализации языка (включая устаревшие) стали открытыми и свободными.

Отличительные особенности[править | править вики-текст]

Язык имеет математически точное формальное определение, называемое «Определением»>>> (англ. The Definition). Для Определения построено доказательство полной типобезопасности, так что устойчивость программ и предсказуемое поведение даже при некорректных входных данных и возможных ошибках программистов при использовании только SML гарантировано. Даже содержащая ошибку программа на SML всегда продолжает вести себя как ML-программа: она может навечно уйти в расчёты или породить исключение, но она не может обрушиться[en][11].

SML является в основном функциональным (mostly functional или primarily functional) языком[5][6], то есть поддерживает большинство технических свойств функциональных языков, но также предоставляет возможности императивного программирования. Его чаще называют «языком высшего порядка[en]», чтобы подчеркнуть поддержку первоклассных функций и при этом отличить его от ссылочно-прозрачных языков.

SML реализует выдающиеся средства поддержки крупномасштабного программирования[en] за счёт наиболее мощной и выразительной системы модулей среди известных — см. язык модулей ML. В SML реализована ранняя версия языка модулей, являющаяся отдельным слоем языка: модули могут содержать объекты ядра языка, но не наоборот[12].

В отличие многих других языков семейства ML (OCaml, Haskell, F#, Felix, Opa, Nemerle и др.), SML весьма минималистичен: он не имеет изначально встроенных средств объектно-ориентированного программирования, средств конкурентности, ad hoc полиморфизма, динамической типизации, генераторов списков и многих других возможностей. Однако, SML отличается ортогональностью[13] (то есть реализует минимально необходимый, но полный набор максимально различных элементов), что позволяет сравнительно легко эмулировать прочие возможности, и необходимые для этого трюки широко освещены в литературе[14][15]>>>. Фактически, SML позволяет использовать сколь угодно высокоуровневую функциональность в качестве примитивной для реализации функциональности ещё более высокого уровня[16]. В частности, построены модели реализации классов типов и монад с использованием только стандартных конструкций SML, а также средств объектно-ориентированного программирования[14]. Более того, SML является одним из немногих языков, в котором непосредственно реализованы продолжения первого класса.

Возможности[править | править вики-текст]

Мощная выразительная система типов

Система типов Хиндли — Милнера (Х-М) является отличительной особенностью ML и его потомков. Она обеспечивает надёжность программ за счёт раннего выявления ошибок, высокий коэффициент повторного использования кода, высокий потенциал к оптимизации, сочетая эти качества с немногословностью и выразительностью на уровне динамически типизируемых языков. Наиболее характерными чертами, присущими Х-М, являются полиморфизм типов, а также алгебраические типы данных и сопоставление с образцом на них.

Реализация Х-М в SML имеет следующие особенности:

  • поддерживается полная абстракция и единообразие типов: любой конструктор типов применим к любому типу, и вводимые пользователем типы используются неотличимо от встроенных[17]
  • полиморфизм типов ограничен пренексным полиморфизмом, для чего в язык введено особое правило «value restriction» (ограничение на значения — то есть не все конструкции языка синтаксически считаются значениями)
  • отдельное место отводится типам, допускающим проверку на равенство (equality types)
  • выведение почти всех типов (за единичными исключениями)
  • Разнообразие встроенных разновидностей типов-произведений, используемых без необходимости предварительного объявления:
    • записи
    • кортежи (реализованные в действительности как записи с номерами в качестве имён полей)
    • массивы (служащие для обеспечения высокой эффективности — см. далее)
  • исключения имеют особую семантику: тип исключения является единственным в языке расширяемым типом (extensible type), то есть всякое определение exception X вводит в программу новую конструирующую функцию X для типа exn. Как следствие, определения исключений являются порождающими, то есть повторение идентичного определения exception Foo exception Foo вводит два разных конструктора, несовместимых друг с другом, и из-за совпадения имён второй заслоняет видимость первого. Это делает механизм динамической обработки исключений статически типобезопасным (но не гарантирует отсутствие необработанных исключений — соответствующие доработки системы типов были предложены много позже — см. полиморфизм управляющих конструкций).
Поддержка функционального программирования
Поддержка императивного программирования
Обеспечение высокой эффективности программ

Способы использования[править | править вики-текст]

В отличие от многих языков, SML предоставляет большое многообразие способов своего использования[20]:

При этом в определённых режимах возможны самые разные целевые платформы и стратегии компиляции:

  • в машинный код (на данный момент покрывается порядка десятка семейств архитектур; теоретически кроссплатформенность может быть существенно шире, чем у всех потомков Алгола и BCPL, за счёт более высокого уровня абстракции от машинного языка[21], и в каждом случае потенциально возможно создание эффективно оптимизирующего компилятора)
  • в общепринятые байт-коды (JVM, .Net)
  • в собственные байт-коды
  • в языки программирования общего назначения более низкого уровня (Си>>>, Ada>>>, Ассемблер — только пакетно или полнопрограммно)
  • в другие диалекты ML (см. Isabelle[en]>>> и преобразование программ[en])

Сами стратегии компиляции также существенно различаются:

  • преобразование замыканий[en], в стиле передачи продолжений, представление адресов функций глобальным вариантным типом.
  • сохранение явных потоков исходного кода, автоматическое распараллеливание, уплощение многопоточного исходного кода до линейного.
  • обёрнутое (boxed) или не-обёрнутое (unboxed) представление примитивных типов
  • динамическая или статическая сборка мусора (см. вывод регионов[en]), в одном потоке с приложением или в отдельном, полностью автоматическая или с возможностью явного контроля.

Язык[править | править вики-текст]

Базовая семантика[править | править вики-текст]

Выражения, блоки, функции[править | править вики-текст]

Объявления и присваивания[править | править вики-текст]

Примитивные типы[править | править вики-текст]

Составные и определяемые типы[править | править вики-текст]

Управляющие конструкции[править | править вики-текст]

Крупномасштабное программирование[править | править вики-текст]

Модульность[править | править вики-текст]

Система модулей SML является наиболее развитой системой типов в языках программирования[22]. Она повторяет семантику ядра ML (англ. Core ML), так что зависимости между крупными компонентами программ строятся подобно зависимостям мелкого уровня. Эта система модулей состоит из трёх видов модулей: структур (structure), сигнатур (signature) и функторов (functor). Структуры похожи на модули в большинстве языков программирования. Сигнатуры служат интерфесами структур, но не привязываются к жёстко к определённым структурам, а выстраивают отношения по схеме «многие-ко-многим», позволяя гибко управлять видимостью компонентов структур в зависимости от нужд контекста программы. Функторы представляют собой «функции над структурами», позволяя разрывать зависимости времени компиляции и описывать параметризованные модули (большинство языков не имеют ничего, сравнимого с ними[23]). Это даёт возможность типобезопасным образом описывать вычисления над компонентами программ, которые в других языках могут реализовываться только посредством метапрограммирования[24]. Обычно платой за это является некоторое снижение производительности программ, но методы полнопрограммной оптимизации успешно решают эту проблему.

Синтаксис и синтаксический сахар[править | править вики-текст]

Синтаксис языка очень краток, по количеству зарезервированных слов занимает промежуточную позицию между Haskell и Pascal[25].

SML имеет контекстно-свободную грамматику, хотя в ней отмечены некоторые неоднозначности. SML/NJ[en]>>> использует LALR(1), но в одном месте присутствует LALR(2).

Список ключевых слов языка (совпадающие с ними идентификаторы не допускаются)[26]:

abstype and andalso as case datatype do
else end eqtype exception fn fun functor
handle if in include infix infixr let local
nonfix of op open orelse raise rec
sharing sig signature struct structure
then type val where while with withtype

Допустимы также символьные идентификаторы — то есть имена типов, данных и функций могут состоять из следующих небуквенных символов:

! % & $ # + - * / : < = > ? @ \ ~ ' ^ |

Имена из этих символов могут быть любой длины[26]:

val ----> = 5
fun !!?©**??!! x = x - 1
infix 5 $^$^$^$ fun a $^$^$^$ b = a + b
val :-|==>-># = List.foldr

Разумеется, использование таких имён на практике не желательно, но если предыдущий автор поддерживаемого кода их интенсивно применял, то благодаря формальному определению, становится возможным (и SML сам позволяет довольно легко эту задачу решить) написание препроцессора для исправления мнемоники.

Исключаются лишь следующие цепочки символов:

:  |  =  =>  ->  #  :>

Причина этого ограничения заключена в их особой роли в синтаксисе языка:

:явное[en] аннотирование типа значения
| — разделение образцов
= — отделение тела функции от её заголовка
=> — отделение тела лямбда-функции от её заголовка
->конструктор функционального (стрелочного) типа
# — доступ к полю записи
:>сопоставление структуры с сигнатурой

В SML не предусматрено встроенного синтаксиса для массивов и векторов (константных массивов). Некоторые реализации в той или иной мере поддерживают синтаксис для массивов ([|1,2,3|]) и векторов (#[1,2,3]) в качестве расширения.

Операция присваивания записывается как в языках семейства Паскаль: x:=5

Экосистема языка[править | править вики-текст]

Стандартная библиотека[править | править вики-текст]

Стандартная библиотека SML носит название Базиса (англ. Basis). Она формировалась много лет, пройдя тщательное тестирование на реальных задачах на базе SML/NJ[en]>>>, её черновик был опубликован в 1996 году[27], и затем её спецификация была официально издана в 2004 году[28]. Уже до издания спецификации появились руководства по её использованию[29]. Базисная библиотека реализует лишь необходимый минимум модулей: тривиальные типы данных, арифметика над ними, ввод/вывод, платформенно-независимый интерфейс к операционной системе, и т. п., но не реализует более сложную функциональность (например, многопоточность). Многие компиляторы дополнительно представляют различные экспериментальные библиотеки.

Как и в большинстве языков, в Базисе SML действует ряд определённых архитектурных и синтаксических соглашений. Компиляторы могут использовать знания о Базисе для применения заранее оптимизированных алгоритмов и специализированных техник оптимизации: например, MLton>>> использует нативное представление типов Базиса (в точности соответствующее примитивным типам языка Си), а также простейших агрегатных типов, составленных из них.

Инструментарий разработки[править | править вики-текст]

К настоящему времени Standard ML полностью стал достоянием общественности: все реализации являются бесплатными и открытыми и распространяются под самыми лояльными лицензиями (BSD-style, MIT); тексты Определения языка (как в версии 1990 года, так и в ревизированной версии 1997 года) и спецификации Базиса также доступны бесплатно>>>. Значительная часть реализаций SML написана на самом SML; исключение составляют рантаймы некоторых компиляторов, написанные на Си и Ассемблере, а также система Poplog[en]>>>.

SML имеет большое число реализаций, достаточно строго соответствующих Определению. Однако, Определение предъявляет лишь минимальные требования к составу начального базиса, так что единственный обозримый результат корректной программы согласно Определению состоит в том, что программа завершается либо порождает исключение, и большинство реализаций совместимы на этом уровне[30]. Различия преимущественно заключаются в тонких деталях, таких как реализация FFI>>>. На практике, реальная программа должна отталкиваться от некоего базиса (минимального набора типов, средств ввода-вывода и т. д.).

Однако, даже в Базисе>>> заложены определённые потенциальные проблемы портируемости. Например[30], константа Int.maxInt содержит значение наибольшего возможного целого, упакованное в опциональный тип[en], и его необходимо извлекать либо сопоставлением с образцом, либо вызовом функции valOf. Для типов конечной размерности значение IntN.maxInt равно SOME(m), и использование обоих способов извлечения равнозначно. Но IntInf.maxInt равно NONE, так что прямое обращение к содержимому через valOf породит исключение Option. По умолчанию IntInf открыта в компиляторе Poly/ML>>>, так как он ориентирован на задачи числодробилки.

Диалекты, расширения[править | править вики-текст]

SML#[править | править вики-текст]

Язык SML# консервативно расширяет SML полиморфизмом записей в модели Атсуши Охори, который в SML# используется для бесшовного встраивания SQL в код на SML для интенсивного database-программирования. Одноимённый компилятор>>> порождает нативный код неплохого быстродействия. Разработан и развивается под руководством самого Охори.

Alice[править | править вики-текст]

Язык Alice ML консервативно расширяет SML примитивами для конкурентного программирования на основе экзотичной стратегии вычисления «вызов по преднамеченности (call by future)», решателем в ограничениях, а также всеми согласованными элементами проекта successor ML. В частности, Alice поддерживает модули первого класса в форме пакетов с динамической загрузкой и динамической типизацией, что позволяет реализовывать распределённые вычисления. Разработан и развивается Андреасом Россбергом.

Concurrent ML[править | править вики-текст]

Concurrent ML (CML) — библиотека, воплощающая встраиваемый язык, который расширяет SML конструкциями конкурентного программирования высшего порядка[en] на основе модели синхронной передачи первоклассных сообщений. Входит в стандартную поставку компиляторов SML/NJ[en]>>> и MLton. Ключевые идеи CML лежат в основе проекта Manticore>>> и включены в проект successor ML[9].

Manticore[править | править вики-текст]

Manticore реализует всестороннюю поддержку конкурентного и параллельного программирования, от логической декомпозиции системы на процессы до тонкого котроля за максимально эффективным использованием многоядерных систем. Manticore основан на подмножестве SML, исключая мутабельные массивы и ссылки, то есть является чистым языком, сохраняя строгий порядок вычисления. Механизмы явной конкурентности и грубого параллелизма (потоки) основаны на CML>>>, а механизмы тонкого параллелизма уровня данных (параллельные массивы) — аналогичны NESL[en]. Одноимённый компилятор>>> порождает нативный код.

Прочие[править | править вики-текст]

Утилиты[править | править вики-текст]

  • Compilation Manager (CM) и MLBasis System (MLB) — расширения компиляторов для лучшей поддержки модульности (контроля зависимостей). В принципе, для этой цели мог бы использоваться и традиционный для большинства языков make, но язык модулей SML значительно мощнее средств модульности других языков, а make его преимуществ не поддерживает, и не пригоден для работы в режиме REPL[57]. CM изначально реализован в SML/NJ[en]>>>, затем портирован на MLton>>>. Позже в составе MLton>>> была предложена система MLB и конвертор файлов формата .cm в формат .mlb.

Межъязыковое взаимодействие[править | править вики-текст]

  • FFI[en] (Foreign Function Interface — рус. интерфейс к чужеродным функциям) — межъязыковые привязки[en]. В разных компиляторах имеет разную реализацию, что тесно связано с представлением данных (прежде всего, обёрнутое или не обёрнутое). Некоторые (например, MLton) обеспечивают прямой вызов в обоих направлениях, вплоть до взаимной рекурсии[en].
  • NLFFI (No-Longer-Foreign Function Interface — рус. интерфейс к отныне-более-не-чужеродным функциям)[59] — библиотека, автоматически порождающая FFI[en]-определения, позволяя подключать заголовочные файлы Си *.h непосредственно в состав проекта на SML, снимая необходимость ручного описания интерфейса. Основана на CKit>>>. Поставляется с SML/NJ[en]>>> и MLton>>>.
  • CKit — фронт-энд языка Си, написанный на SML. Осуществляет трансляцию исходных кодов на Си (с учётом препроцессора) в AST, реализуемое посредством структур данных языка SML. Лежит в основе реализации NLFFI>>>.

Идеоматика, соглашения, типовые приёмы[править | править вики-текст]

К оформлению программ на SML не предъявляется никаких требований, поскольку грамматика языка полностью контекстно-свободна и не содержит явных неоднозначностей. Тем не менее, в ней отмечаются частные проблемы, например, при передаче оператора умножения op * закрывающую скобку необходимо отделять пробелом ((op * )), так как при сплошном написании многие реализации (не все) принимают пару символов *) за закрытие комментария в коде и выдают ошибку.

Однако, всё же существуют определённые рекомендации, нацеленные на улучшение читабельности, модульности и повторного использования кода, а также раннего обнаружения ошибок и повышения модифицируемости (но не для внесения информации о типах в идентификаторы, как это делается, например, в венгерской нотации)[60]. В частности, в SML рекомендуется правило именования идентификаторов уровня ядра языка, аналогичное тому, что требуется в Haskell: fooBar для значений, foo_bar для конструкторов типов, FooBar для конструирующих функций (некоторые компиляторы даже выдают предупреждение при его нарушении). Это связано с особенностью работы механизма сопоставления с образцом, который в общем случае не способен отличить ввод локальной переменной от использования нуль-арного конструктора типов, так что опечатки могут приводить к (сравнительно легко обнаружимым) ошибкам[61].

Наиболее непривычными и неожиданными могут быть:

  • предпочтение шага отступа в три символа (не в четыре)
  • частое применение апострофа в идентификаторах (аналогично принятому в математике): если на основе x требуется построить «новый x», то в большинстве языков пишут «x1», а в SML, как и в математике, зачастую «x'» («икс-штрих»).
  • синтаксис бинарных логических операций «И» и «ИЛИ»: andalso и orelse, соответственно.[62]
  • синтаксис инфиксных операций конкатенации строк и списков: ^ и @, соответственно (для векторов и массивов не предусмотрены).

Fold[править | править вики-текст]

Техника «Fold» позволяет ввести в SML ряд распространённых идиом, включая функции с переменным числом аргументов, именованные параметры функций, значения параметров по умолчанию, синтаксическую поддержку массивов в коде, функциональное обновление записей и косметическое изображение зависимой типизации для обеспечения типобезопасности функций вроде printf[15].


Примеры программ[править | править вики-текст]

Hello World![править | править вики-текст]

Простейшая программа на SML может быть записана в одну строку:

print "Hello World!\n"

Однако, учитывая ориентированность языка на крупномасштабное программирование[en], минимальной всё же следует считать её обёртку в язык модулей (некоторые компиляторы работают только с программами уровня модулей).

Выходной машинный код для минимальной программы также получается относительно крупным (в сравнении с реализаций Hello World на Си), поскольку даже самая маленькая программа на SML обязана включать в себя рантайм-систему языка, бо́льшую часть которой составляет сборщик мусора. Однако, не следует воспринимать размер исходного и машинного кодов на начальном этапе за тяжеловесность SML: их причиной является интенсивная ориентированность языка на разработку крупных и сложных систем. Дальнейшее наращивание программ происходит по существенно более пологой кривой, чем в большинстве других статически типизируемых языков, и оверхед становится едва заметным при разработке серьёзных программ[63].

Автоматическая вёрстка[править | править вики-текст]

fun firstLine s =
   let
      val (name, rest) =
      Substring.splitl (fn c => c <> #".") (Substring.full s)
   in
      "\n<P><EM>" ^ Substring.string name ^ "</EM>" ^ Substring.string rest
   end

fun htmlCvt fileName =
   let
       val is = TextIO.openIn fileName
       and os = TextIO.openOut (fileName ^ ".html")
       fun cvt _ NONE    = ()
         | cvt _ (SOME "\n")  = cvt true (TextIO.inputLine is)
         | cvt first (SOME s) =
                ( TextIO.output (os,
                                 if first then firstLine s
                                          else "<BR>" ^ s);
                  cvt false (TextIO.inputLine is)
                )
   in
      cvt true (SOME "\n"); TextIO.closeIn is; TextIO.closeOut os
   end

Этот код преобразует по простейшим правилам плоский текст в HTML, оформляя диалог по ролям[64].

Троичные деревья[править | править вики-текст]

Для задачи поиска строки в словаре троичные деревья[en] сочетают молниеносную скорость префиксных деревьев с экономичностью двоичных деревьев в отношении памяти.

type key = Key.ord_key
type item = Key.ord_key list
datatype set = LEAF | NODE of { key: key, lt: set, eq: set, gt: set }
val empty = LEAF
exception AlreadyPresent

fun member (_, LEAF) = false
  | member (h::t, NODE {key,lt,eq,gt}) =
      (case Key.compare (h, key) of
            EQUAL   => member(t, eq)
          | LESS    => member(h::t, lt)
          | GREATER => member(h::t, gt) )
  | member ([], NODE {key,lt,eq,gt}) =
      (case Key.compare (Key.sentinel, key) of
            EQUAL   => true
          | LESS    => member([], lt)
          | GREATER => member([], gt) )

fun insert(h::t, LEAF) = NODE { key=h, eq = insert(t, LEAF), lt=LEAF, gt=LEAF }
  | insert([], LEAF)   = NODE { key=Key.sentinel, eq=LEAF, lt=LEAF, gt=LEAF }
  | insert(h::t, NODE {key,lt,eq,gt}) =
      (case Key.compare (h, key) of
            EQUAL   => NODE {key=key, lt=lt, gt=gt, eq=insert(t, eq)}
          | LESS    => NODE {key=key, lt=insert(h::t, lt), gt=gt, eq=eq}
          | GREATER => NODE {key=key, lt=lt, gt=insert(h::t, gt), eq=eq} )
  | insert([], NODE {key,lt,eq,gt}) =
      (case Key.compare (Key.sentinel, key) of
            EQUAL   => raise AlreadyPresent
          | LESS    => NODE {key=key, lt=insert([], lt), gt=gt, eq=eq}
          | GREATER => NODE {key=key, lt=lt, gt=insert([], gt), eq=eq} )

fun add(l, n) = insert(l, n) handle AlreadyPresent => n

Этот код использует Базисную структуру Key, сопоставимую с сигнатурой ORD_KEY, а также глобальный тип order (над которым, в частности, определена функция Key.compare):

datatype order = LESS | EQUAL | GREATER

О языке[править | править вики-текст]

Быстродействие[править | править вики-текст]

Типичные преимущества функционального программирования (типобезопасность, автоматическое управление памятью, высокий уровень абстракции и др.) проявляются в обеспечении надёжности и вообще работоспособности программ, а в ответственных, особенно крупномасштабных[en] задачах быстродействие часто играет второстепенную роль. Упор на эти свойства исторически привёл к тому, что программистам на функциональных языках зачастую оказываются недоступны многие эффективные структуры данных (массивы, строки, битовые цепочки), поэтому функциональные программы обычно заметно менее эффективны, чем эквивалентные программы на Си.[65]

ML изначально предоставляет весмьа неплохие средства для тонкого контроля за быстродействием>>>, однако, исторически>>> реализации ML были крайне медлительными. Тем не менее, ещё в начале 1990-х Эндрю Аппель[en] прочил[66] языку SML скорость исполнения выше скорости языка Си, по крайней мере при интенсивной работе со сложноструктурированными данными (но SML не претендует на то, чтобы быть заменой Си в задачах системного программирования). За следующие несколько лет напряжённая работа над развитием компиляторов привела к тому, что скорость исполнения программ на SML повысилась в 20-40 раз[67].

В конце 1990-х Стивен Уикс задался целью добиться от программ на SML максимально возможной производительности и написал дефункторизатор для SML/NJ[en]>>>, сразу показавший прирост скорости ещё в 2-3 раза. Дальнейшая работа в этом направлении привела к созданию компилятора MLton>>>, который к середине нулевых годов XXI века показывал прирост скорости перед другими компиляторами в среднем на два порядка[45], конкурируя с Си (подробнее см. MLton).

Стратегия автоматического управление памятью на основе статического вывода регионов[en] позволяет устранять затраты на инициализацию и высвобождение памяти из исполнения программы (т.е. реализует сборку мусора на этапе компиляции). Компилятор ML Kit>>> использует эту стратегию, позволяя решать задачи реального времени, хотя он уступает MLton по возможностям оптимизации.

На основе фронт-енда SML/NJ был разработан компилятор в исходный код на Сиsml2c>>>. Он порождает код хорошего качества, но примечательно, что схема компиляции «сперва в Си, затем в машинный код» до двух раз снижает быстродействие по сравнению с прямой компиляцией SML в машинный код из-за семантических различий между SML и Си[50].

Некоторые компиляторы SML предоставляют возможность профилирования кода с целью определения функций, занимающих наибольшее процессорное время (причём результат всегда неожиданный)[65], после чего можно сосредоточиться на их оптимизации средствами SML, либо вынести их в код на Си через FFI>>>.

Обоснование семантики[править | править вики-текст]

Общие сведения[править | править вики-текст]

Теоретической основой языка является полиморфно типизированное лямбда-исчисление (Система F), ограниченное Let-полиморфизмом.

«Определение» (The Definition)[править | править вики-текст]

Официальным «стандартом» языка является изданное в виде книги «Определение» (англ. The Definition). Первоначальное Определение, «The Definition of Standard ML», было издано в 1990 году. Спустя год были изданы «Комментарии к Определению» («Commentary on Standard ML»), объясняющие применённые подходы и нотации. Вместе они составляют спецификацию языка, ныне известного как «SML'90». В течение следующих лет появился ряд критических замечаний и предложений по улучшению (одним из наиболее известных среди которых являются просвечивающие суммы Харпера — Лилибриджа), и в 1997 году многие из них были собраны в ревизированной версии Определения, «The Definition of Standard ML: Revised», определив версию языка «SML'97», сохраняющего обратную совместимость с прежним. Ревизированное Определение использует принципы, описанные в Комментариях 1991 года, так что намеревающимся досконально изучить Определение SML рекомендуется сперва изучать SML'90, и лишь затем SML'97[68].

Определение SML (The Definition) является примером структурной операционной семантики[en]; оно является не первым формальным определением языка, но первым, однозначно понятным разработчикам компиляторов[69]. Непротиворечивость Определения позволяет человеку без запуска конкретного компилятора проверить программу на корректность и вычислить её результат; но, с другой стороны, Определение требует высокой квалификации для понимания и не может служить учебником по языку[66]. Большинство реализаций достаточно строго соответствуют Определению, отклоняясь в технических особенностях — бинарных форматах, FFI>>> и др., так что несложные программы портируются без изменений.

Определение оперирует семантическими объектами, описывая их смысл (meaning). Во введении авторы делают акцент на том, что именно семантические объекты (к числу коих, в зависимости от конкретного языка, могут относиться такие понятия как пакет, модуль, структура, исключение, канал, тип, процедура, ссылка, соиспользование и пр.), а не синтаксис, определяют концептуальное представление о языке программирования, и именно на них должно строиться определение всякого языка[70].

Согласно Определению, SML разделяется на три языка, надстроенные один над другим: нижний слой, называемый «Ядром языка» (Core language), средний слой, называемый «Модулями»>>> (более известный как «Язык модулей ML») и небольшой верхний слой, называемый «Программами» (Programs), представляющий собой совокупность определений верхнего уровня (англ. top-level declarations).

Определение включает около 200 правил выведения (inferrence), записываемых в виде обыкновенной дроби, где в позиции числителя стоит формализованная фраза ML, а в позиции знаменателя — следствие, которое можно заключить, если фраза корректна.

Вычисление каждого определения по ходу программы меняет состояние глобального окружения (англ. top-level environment), называемого базисом. Стандартная библиотека в SML представляет собой «базис по умолчанию», доступный всякой программе от её начала, и потому называется просто Базисом. Само Определение содержит только начальный базис (initial basis), содержащий минимально необходимые определения; более обширный Базис был стандартизирован позже>>>.

Определение различает три основные фазы в языке[71][72]: разбор (parsing), выработка (elaboration) и вычисление (evaluation). Выработка относится к статической семантике; вычисление — к динамической. Но вычисление здесь не следует путать с исполнением (execution): SML является языком, основанным на выражениях (expression-based language), и получение результата от применения функции ко всем аргументам называется исполнением (execution), а «вычисление функции» означает построение определения её самой. Следует также обратить внимание, что поддержка каррирования в языке означает представление всех функций замыканиями, а это, в свою очередь, означает, что использовать термин «вызов функции» некорректно. Вместо вызова следует говорить о применении функции (function application) — функция просто не может быть вызвана, пока не получит все аргументы; частичное применение функции означает вычисление новой функции (нового замыкания). Для каждого из слоёв языка (ядро, модули, программы) отдельно описывается статическая и динамическая семантика, то есть этапы разбора, выработки и вычисления.

Конкретная реализация языка не обязана проводить все эти различия, они несут лишь формальный характер[72]. Выработка без вычисления фактически означает традиционное понятие о компиляции. Формально, исполнение программы представляет собой вычисление нового базиса как суммы начального базиса и определений программы.

Семантика Харпера — Стоуна[править | править вики-текст]

[13]

Критика и сравнение с альтернативами[править | править вики-текст]

Разработчики SML изначально установили самую высокую планку требований качества для языка, так что и порог критики располагается намного выше, чем у большинства промышленных языков. Упоминания о недостатках языка SML встречаются в официальной печати так же часто, как и языка C++, и много чаще большинства других языков, но причина вовсе не в негативном отношении к SML — напротив, всякая критика SML сопровождается очень тёплым отношением к нему. Даже педантичный разбор недостатков SML обычно сопровождается его описанием как «изумительного языка, единственного серьёзного из существующих»[73]. Иначе говоря, исследователи досконально копаются в недостатках, подразумевая, что даже с их учётом SML оказывается более предпочтителен для применения в гигантских наукоёмких проектах, чем многие более популярные языки, и желая довести SML до совершенства.

История, философия, терминология[править | править вики-текст]

Формальная семантика SML ориентирована на интерпретацию, однако большинство его реализаций является компиляторами (в том числе интерактивными компиляторами), некоторые из которых уверенно соперничают по эффективности с языком Си, так как язык хорошо поддаётся глобальному анализу. По той же причине SML может компилироваться в исходный код на других языках высокого или среднего уровня — например, существуют комплияторы из SML в Си и Ada.

В основе языка лежит Сильная статическая полиморфная типизация, которая не только обеспечивает верификацию программ на этапе компиляции, но и жёстко обособляет мутабельность, что само по себе повышает потенциал к оптимизации программ — в частности, упрощает реализацию механизма сборки мусора[86].

Первая версия ML была представлена миру в 1974 году в роли мета-языка для построения интерактивных доказательств в составе системы Edinburgh LCF (Logic for Computable Functions)[en]>>>[2]. Её реализовали Малькольм Ньюи, Локвуд Моррис и Робин Милнер на платформе DEC10. Первая реализация была крайне неэффективной, так как конструкции ML транслировались в Lisp, который затем интерпретировался[87]. Первое полное описание ML как компонента LCF издано в 1979 году[2].

Около 1980 года Лука Карделли[en] реализовал первый компилятор Vax ML, дополнив ML некоторыми своими идеями. Вскоре Карделли портировал Vax ML на Unix, используя Berkley Pascal. Среда выполнения была переписана на Си, но большая часть компилятора оставалась на Паскале. Работа Карделли вдохновила Милнера на создание SML как самостоятельного языка общего назначения, и они начали совместную работу в Эдинбурге, результатом чего стал компилятор Edinburgh ML>>>, выпущенный в 1984 году. В процессе этой работы Майк Гордон придумал ссылочные типы и предложил их Луи Дамасу, который позже защитил на них диссертацию[88]. Одновременно велось сотрудничество Кэмбриджа с INRIA. Жерар Хью из INRIA портировал ML на Maclisp под Multics. INRIA разработали собственный диалект ML, названный Caml, и в последствии развившийся в OCaml>>>. Лоуренс Полсон[en] оптимизировал Edinburgh ML>>>, так что код на ML стал работать в 4-5 раз быстрее. Вскоре после этого Дэвид Мэтьюз разработал язык Poly на основе ML. Дальнейшая работа в этом направлении привела к созданию среды Poly/ML>>>. В 1986 Дэвид МакКуин сформулировал язык модулей ML, и к работе подключился Эндрю Аппель[en]. Совместно они начали вести работу над компилятором SML/NJ[en]>>>, который служил одновременно исследовательской платформой для развития языка и первым промышленным оптимизирующим компилятором. Многие реализации языка были первоначально разработаны с использованием SML/NJ.

С опытом крупномасштабных разработок был обнаружен ряд недочётов в Определении языка от 1990 года. Часть недостатков была устранена в Ревизии Определения от 1997 года[3], но рамки ревизии исключают потерю обратной совместимости (коды адаптируются косметически, без необходимости переписывания с нуля). В 2004 году была опубликована спецификация на состав Базисной библиотеки (черновик спецификации датируется 1996 годом). Другие недостатки были устранены в других языках: ML породил целое семейство Х-М-типизированных языков. Эти языки завоевали популярность на задаче разработке языков и часто определяются как «DSL для денотационной семантики[en]»[89]. Исследователи, занимавшиеся развитием и использованием SML на протяжении почти трёх десятилетий, к концу XX века сформировали сообщество по созданию нового языка — successor ML (sML).

Фактически, SML не был первым в семействе после собственно LCF/ML — ему предшествовали такие языки как Cardelli ML и Hope[7]. Французы поддерживают собственный диалект — Caml/OCaml[10]. Тем не менее, говоря «ML», многие подразумевают «SML»[90], и даже пишут через дробь: «ML/SML»[91].

Изучение[править | править вики-текст]

Наиболее рекомендуемым[31][92][93][94][95][96] учебником по SML является книга Лоуренса Полсона[en] (автора системы HOL[en]) «ML for the Working Programmer»[90].

Для первоначального ознакомления с языком может быть полезен краткий (несколько десятков страниц) курс Роберта Харпера[en] «Introduction to Standard ML» (доступный в русском переводе[97]), который он использовал для преподавания языка и за следующие два десятилетия расширил до более крупного учебника[98].

Применение[править | править вики-текст]

SML, наряду с OCaml, служит первым языком преподавания обучения программированию во многих университетах мира. Среди аппликативных языков они имеют, вероятно, самый низкий собственный порог вхождения.

Значительная часть существующих кодов на SML представляет собой либо реализацию его же компиляторов, либо системы автоматического доказательства, наиболее известными из которых являются HOL[en] и Isabelle[en]>>>. Все они свободны и открыты.

Тем не менее, существуют и более «приземлённые», в том числе коммерческие продукты[99].

См. также[править | править вики-текст]

  • ML
  • successor ML — проект дальнейшего развития Standard ML
  • Близкородственные языки[91]:

Примечания[править | править вики-текст]

  1. SML'84, 1984.
  2. 1 2 3 SML'90, 1990.
  3. 1 2 SML'97, 1997.
  4. SML'90, 1990, E. Appendix: The Development of ML, с. 81-83.
  5. 1 2 Commentary on SML, 1991, с. V.
  6. 1 2 Pucella, "Notes on SML/NJ", 2001, с. 1.
  7. 1 2 3 4 MacQueen, "Reflections on SML", 1992.
  8. StandardML description in MLton compiler guide
  9. 1 2 ML2000 Preliminary Design, 1999.
  10. 1 2 Paulson, "ML for the Working Programmer", 1996, с. 12.
  11. Paulson, "ML for the Working Programmer", 1996, с. 2.
  12. Rossberg, "1ML", 2015.
  13. 1 2 Harper-Stone, 2000.
  14. 1 2 OOP in SML.
  15. 1 2 Fold.
  16. Paulson, "ML for the Working Programmer", 1996, 4.13 Tree-based data structures, с. 148-149.
  17. MacQueen, "Reflections on SML", 1992, с. 2.
  18. Commentary on SML, 1991, с. 15.
  19. Paulson, "ML for the Working Programmer", 1996, Imperative Programming in ML, с. 313.
  20. MacQueen, "Reflections on SML", 1992, с. 3.
  21. Paulson, "ML for the Working Programmer", 1996, с. 1.
  22. Cardelli - Typeful programming, 2.Typeful languages, с. 5.
  23. Paulson, "ML for the Working Programmer", 1996, 7.8 Testing the queue structures, с. 274.
  24. Appel, "A Critique of Standard ML", 1992, Lack of macros, с. 9.
  25. MacQueen, "Reflections on SML", 1992, с. 6.
  26. 1 2 Paulson, "ML for the Working Programmer", 1996, 2.3 Identifiers in Standard ML, с. 21.
  27. Paulson, "ML for the Working Programmer", 1996, с. 13.
  28. SML Basis, 2004.
  29. Pucella, "Notes on SML/NJ", 2001.
  30. 1 2 Standard ML Portability.
  31. 1 2 SML/NJ compiler
  32. Deviations of SML/NJ from The Definition of SML'97 (Revised)
  33. SML/NJ: Object Language Embedding with Quote/Antiquote
  34. Slind, "Language embedding in SML/NJ", 1991.
  35. MLton compiler
  36. Poly/ML compiler
  37. ML Kit compiler
  38. SML# compiler
  39. Manticore compiler
  40. CakeML compiler
  41. TILT compiler sources (Git)
  42. конференция sml-evolution: Rober Harper, 30.10.2006.
  43. Alice compiler
  44. Moscow ML compiler
  45. 1 2 MLton Performance, 2005.
  46. SML.NET compiler
  47. SMLtoJs compiler
  48. SMLtoJs online REPL
  49. sml2c compiler sources
  50. 1 2 Tarditi et al, "No Assembly Required", 1990.
  51. Tolmach, Oliva, "From ML to Ada", 1993.
  52. HaMLet interpreter
  53. MLWorks compiler sources (Git)
  54. Edinburgh ML compiler sources
  55. Taha et al, "Macros as Multi-Stage Computations", 2001.
  56. Mythryl project
  57. Pucella, "Notes on SML/NJ", 2001, Chapter 6. The Compilation Manager, с. 157.
  58. eXene — multi-threaded X Window System toolkit written in ConcurrentML
  59. Blume, "No-Longer-Foreign", 2001.
  60. MLton StyleGuide.
  61. Appel, "A Critique of Standard ML", 1992, Misspelled constructors, с. 12.
  62. Harper, "Intro to SML", 1986, с. 5.
  63. Shipman, "Unix Programming with SML", 2001, с. 31.
  64. Paulson, "ML for the Working Programmer", 1996, 8.9 Text processing examples, с. 348-350.
  65. 1 2 Paulson, "ML for the Working Programmer", 1996, 1.5 The efficiency of functional programming, с. 9.
  66. 1 2 3 Appel, "A Critique of Standard ML", 1992.
  67. Paulson, "ML for the Working Programmer", 1996, с. 108.
  68. about The Definition Of Standard ML in MLton guide
  69. Paulson, "ML for the Working Programmer", 1996, 1.9 ML and the working programmer, с. 16.
  70. SML'90, 1990, с. V.
  71. SML'90, 1990, с. 1.
  72. 1 2 Commentary on SML, 1991, с. 1-3.
  73. 1 2 Rossberg, "Defects in SML Revised", 2001.
  74. Kahrs, 1993.
  75. Kahrs, 1996.
  76. VandenBerghe, "Why ML/OCaml are good for writing compilers", 1998.
  77. Harper, "Programming in SML", 2005, 12.1.1 Primitive Exceptions, с. 104.
  78. Olsson, Rossberg, "SML vs. OCaml", 2009.
  79. 1 2 Shaw, "ML vs. Haskell".
  80. Dreyer, Harper, "Modular Type Classes", 2007.
  81. Yallop, White, "Lightweight higher-kinded polymorphism", 2014.
  82. Augustsson, "failed adventure in Haskell", 2008.
  83. Wehr, Chakravarty, "Modules vs. Type Classes", 2008.
  84. Paulson, "ML for the Working Programmer", 1996, Sequences, or infinite lists, с. 191-201.
  85. Rossberg, "1ML", 2015, с. 2.
  86. Appel, "A Critique of Standard ML", 1992, Efficiency, с. 7-8.
  87. Paulson, "ML for the Working Programmer", 1996, с. 11.
  88. MacQueen, "Cardelli and Early Evolution of ML", 2014, с. 4.
  89. Hudak - Modular Domain Specific Languages and Tools, 1998.
  90. 1 2 Paulson, "ML for the Working Programmer", 1996.
  91. 1 2 sml-family.org.
  92. Gilmore, "Programming in SML. Tutorial Introduction", 1997, с. 3.
  93. Shipman, "Unix Programming with SML", 2001, с. 455.
  94. MacQueen, "Reflections on SML", 1992, с. 1.
  95. Pucella, "Notes on SML/NJ", 2001, с. 42.
  96. SML Basis on Cambridge University Press — related books
  97. Harper, "Intro to SML", 1986.
  98. Harper, "Programming in SML", 2005.
  99. Пользователи Standard ML

Литература[править | править вики-текст]

Стандарты[править | править вики-текст]

Учебники, руководства, справочники, использование[править | править вики-текст]

  • Роберт Харпер[en]. Введение в Стандартный ML. — Carnegie Mellon University, 1986. — 97 с. — ISBN PA 15213-3891.
  • Konrad Slind. Object language embedding in Standard ML of New Jersey. — Proceedings of the 2nd ML workshop, Carnegie Mellon University., 1991.
  • Lawrence C. Paulson[en]. ML for the Working Programmer. — 2nd. — Cambridge, Great Britain: Cambridge University Press, 1996. — 492 с. — ISBN 0-521-57050-6 (твёрдый переплёт), 0-521-56543-X (мягкий переплёт).
  • Jeffrey Ullman. Elements of ML Programming. — Prentice-Hall, 1998. — ISBN 0-13-790387-1.
  • Anthony L. Shipman. Unix System Programming with Standard ML. — 2001.
  • Riccardo Pucella. Notes on Programming Standard ML of New Jersey. — Last revised January 10, 2001. — Cornell University, 2001.
  • Bernard Berthomieu. OO Programming Styles in ML. — LAAS Report #2000111, Centre National De La Recherche Scientifique Laboratoire d'Analyse et d'Architecture des Systèmes, 2000.
  • Riccardo R. Pucella. Reactive Programming in Standard ML ( (англ.)). — Bell Laboratories, Lucent Technologies, 2004.

История, анализ, критика[править | править вики-текст]

  • Milner, Morris, Newey. A Logic for Computable Functions with reflexive and polymorphic types // Arc-et-Senans. — Proc. Conference on Proving and Improving Programs, 1975.
  • Gordon, Milner, Morris, Newey, Wadsworth. A Metalanguage for Interactive Proof in LCF. — 1977.
  • David MacQueen. Structures and parameterisation in a typed functional language. — 1981.
  • Zhe Yang. Encoding Types in ML-like Languages. — New York University, (c) ACM, 1998.

Прочее[править | править вики-текст]

Ссылки[править | править вики-текст]