Русская Википедия:Standard ML

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Язык программирования Standard ML (SML) — компилируемый язык программирования общего назначения Шаблон:Iw, основанный на системе типов Хиндли — Милнера.

Является «в основном функциональным» языкомШаблон:SfnШаблон:Sfn, то есть поддерживает большинство технических свойств функциональных языков, но также предоставляет развитые возможности императивного программирования при необходимости. Сочетает устойчивость программ, гибкость на уровне динамически типизируемых языков и быстродействиеШаблон:Переход на уровне языка Си; обеспечивает превосходную поддержку как быстрого прототипирования, так и модульности и Шаблон:IwШаблон:Sfn[1].

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

Общие сведения

Язык изначально ориентирован на Шаблон:Iw программных систем: он предоставляет эффективные средства абстракции и модульности, обеспечивая высокий коэффициент повторного использования кода, и это делает его подходящим также для быстрого прототипирования программ, в том числе и Шаблон:Iw. Например, в процессе разработки (тогда ещё экспериментального) компилятора Шаблон:IwШаблон:Переход (60 тысяч строк на SML), порой приходилось вносить радикальные изменения в реализации ключевых структур данных, влияющих на десятки модулей — и новая версия компилятора была готова в течение дня.Шаблон:Sfn (см. также ICFP Programming Contest за 2008, 2009.) При этом, в отличие многих других языков, подходящих для быстрого прототипирования, SML может очень эффективно компилироватьсяШаблон:Переход.

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

Отличительные особенности

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

SML является в основном функциональным (Шаблон:Lang-en2 или Шаблон:Lang-en2) языкомШаблон:SfnШаблон:Sfn, то есть поддерживает большинство технических свойств функциональных языков, но также предоставляет возможности императивного программирования. Его чаще называют «Шаблон:Iw», чтобы подчеркнуть поддержку первоклассных функций и при этом отличить его от ссылочно-прозрачных языков.

SML реализует выдающиеся средства поддержки Шаблон:Iw за счёт наиболее мощной и выразительной системы модулей среди известных (язык модулей ML). В SML реализована ранняя версия языка модулей, являющаяся отдельным слоем языка: модули могут содержать объекты ядра языка, но не наоборотШаблон:Sfn.

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

Возможности

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

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

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

  • поддерживается полная абстракция и единообразие типов: любой конструктор типов применим к любому типу, и вводимые пользователем типы используются неотличимо от встроенныхШаблон:Sfn
  • полиморфизм типов ограничен пренексным полиморфизмом и имеет дополнительные ограниченияШаблон:Переход
  • отдельное место отводится [[переменная типа#Специальные переменные типа|типам, допускающим проверку на равенство (Шаблон:Lang-en2)]]
  • выведение почти всех типов (за единичными исключениями)
  • Разнообразие встроенных разновидностей типов-произведений, используемых без необходимости предварительного объявления:
    • записи
    • кортежи (реализованные в действительности как записи с номерами в качестве имён полей)
    • массивы (служащие для обеспечения высокой эффективности — см. далее)
  • исключения имеют особую семантику: тип исключения является единственным в языке расширяемым типом (Шаблон:Lang-en2), то есть всякое определение exception X вводит в программу новую конструирующую функцию X для типа exn. Как следствие, определения исключений являются порождающими, то есть повторение идентичного определения exception Foo exception Foo вводит два разных конструктора, несовместимых друг с другом, и из-за совпадения имён второй заслоняет видимость первого. Это делает механизм динамической обработки исключений статически типобезопасным (но не гарантирует отсутствие необработанных исключений — соответствующие доработки системы типов были предложены много позже — см. полиморфизм управляющих конструкций).
Поддержка функционального программирования
Поддержка императивного программирования
Обеспечение высокой эффективности программ

Способы использования

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

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

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

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

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

Язык

Базовая семантика

Шаблон:Заготовка раздела

Объявления, выражения, блоки, функции

Примитивные типы

Составные и определяемые типы

Мутабельные значения

Ограничение на значения

Ограничение на значения (Шаблон:Lang-en)

Управляющие конструкции

Крупномасштабное программирование

Модульность

Шаблон:Main

Система модулей SML является наиболее развитой системой модулей в языках программирования. Она повторяет семантику ядра ML (Шаблон:Lang-en), так что зависимости между крупными компонентами программ строятся подобно зависимостям мелкого уровня. Эта система модулей состоит из трёх видов модулей:

  • структур (structure)
  • сигнатур (signature)
  • функторов (functor)

Структуры похожи на модули в большинстве языков программирования. Сигнатуры служат интерфейсами структур, но не привязываются жёстко к определённым структурам, а выстраивают отношения по схеме «многие-ко-многим», позволяя гибко управлять видимостью компонентов структур в зависимости от нужд контекста программы.

Функторы представляют собой «функции над структурами», позволяя разрывать зависимости времени компиляции и описывать параметризованные модули. Они дают возможность типобезопасным образом описывать вычисления над компонентами программ, которые в других языках могут реализовываться только посредством метапрограммированияШаблон:Sfn — как шаблоны C++, только без боли и страданийШаблон:Sfn, или макроязык Лиспа, только со статическим контролем безопасности порождаемого кодаШаблон:Sfn. Большинство языков вовсе не имеют ничего, сравнимого с функторамиШаблон:Sfn.

Принципиальным отличием языка модулей ML является то, что результат функтора может включать не только значения, но и типы, причём они могут зависеть от типов, входящих в состав параметра функтора. Этим модули ML оказываются наиболее близки в своей выразительности к системам с зависимыми типами, но, в отличие от последних, модули ML могут быть редуцированы в плоскую Шаблон:Iw (см. Язык модулей ML#F-преобразование Россберга — Руссо — Дрейера).

Синтаксис и синтаксический сахар

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

SML имеет контекстно-свободную грамматику, хотя в ней отмечены некоторые неоднозначности. Шаблон:IwШаблон:Переход использует LALR(1), но в одном месте присутствует LALR(2).

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

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

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

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

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

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

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

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

:  |  =  =>  ->  #  :>

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

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

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

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

Экосистема языка

Стандартная библиотека

Стандартная библиотека SML носит название Базиса (Шаблон:Lang-en). Она формировалась много лет, пройдя тщательное тестирование на реальных задачах на базе Шаблон:IwШаблон:Переход, её черновик был опубликован в 1996 годуШаблон:Sfn, и затем её спецификация была официально издана в 2004 годуШаблон:Sfn. В этот период уже появлялись руководства по её использованиюШаблон:Sfn. Базисная библиотека реализует лишь необходимый минимум модулей: тривиальные типы данных, арифметика над ними, ввод-вывод, платформенно-независимый интерфейс к операционной системе, и т. п., но не реализует более сложную функциональность (например, многопоточность). Многие компиляторы дополнительно представляют различные экспериментальные библиотеки.

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

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

Конверторы и сканеры

Стандартная схема преобразования в строковый тип и обратно инкапсулирована в структуру StringCvt: 

structure StringCvt :
   sig
      datatype radix = BIN | OCT | DEC | HEX

      datatype realfmt
            = SCI of int option
            | FIX of int option
            | GEN of int option
            | EXACT

      type ('a, 'b) reader = 'b -> ('a * 'b) option

      val padLeft : char -> int -> string -> string
      val padRight : char -> int -> string -> string
      val splitl : (char -> bool) -> (char, 'a) reader -> 'a -> (string * 'a)
      val takel : (char -> bool) -> (char, 'a) reader -> 'a -> string
      val dropl : (char -> bool) -> (char, 'a) reader -> 'a -> 'a
      val skipWS : (char, 'a) reader -> 'a -> 'a

      type cs
      val scanString : ((char, cs) reader -> ('a, cs) reader) -> string -> 'a option
   end

Схема преобразования не ограничивается перечислением обоснований систем счисления, как в Си (BIN, OCT, DEC, HEX). Она распространяется на Шаблон:Iw, позволяя описывать операции чтения значений конкретных типов из абстрактных потоков и записи в них, и затем преобразовывать простые операции в более сложные посредством комбинаторов. В роли потоков могут выступать как стандартные потоки ввод-вывода, так и просто агрегатные типы, такие как списки или строки.Шаблон:Sfn

Ключевым ингредиентом этой схемы являются ридеры, то есть значения типа ('a,'b) reader. Интуитивно, ридер — это функция, которая принимает на вход поток типа 'b и предпринимает попытку считать из него значение типа 'a, возвращая либо считанное значение и «остаток» потока, либо NONE в случае неудачи. Важной разновидностью ридеров являются сканеры, или сканирующие функции. Для данного типа T сканирующая функция имеет тип 

(char,'b) reader -> (T,'b) reader

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

signature INTEGER = sig
   eqtype int
   ...
   val scan : StringCvt.radix -> (char, 'a) StringCvt.reader -> 'a -> (int * 'a) option
end

Числа считываются атомарным образом, но ридеры могут считывать из потоков и цепочки поэлементно, например, посимвольно строку из строки: 

fun stringGetc (s) =
   let
      val ss = Substring.full (s)
   in
      case Substring.getc (ss)
        of NONE => NONE
         | SOME (c,ss') => SOME (c,Substring.string (ss'))
   end;

stringGetc ("hello");
(* val it = SOME (#"h","ello") : (char * string) option *)

stringGetc ( #2(valOf it) );
(* val it = SOME (#"e","llo") : (char * string) option *)

stringGetc ( #2(valOf it) );
(* val it = SOME (#"l","lo") : (char * string) option *)

stringGetc ( #2(valOf it) );
(* val it = SOME (#"l","o") : (char * string) option *)

stringGetc ( #2(valOf it) );
(* val it = SOME (#"o","") : (char * string) option *)

stringGetc ( #2(valOf it) );
(* val it = NONE : (char * string) option *)

Сканеры позволяют создавать ридеры из имеющихся ридеров, например: 

val stringGetInt = Int.scan StringCvt.DEC stringGetc

Структура StringCvt предоставляет также ряд вспомогательных функций. Например, splitl, takel и dropl комбинируют символьные ридеры с символьными предикатами, позволяя фильтровать потоки.

Следует отметить, что не символьные ридеры являются особым случаем ридеров вообще, а наоборотШаблон:Sfn. Причина этого в том, что извлечение подпоследовательности из последовательности представляет собой обобщение извлечения подстроки из строки.

Портирование

Большинство реализаций языка достаточно строго соответствуют ОпределениюШаблон:Переход. Различия заключаются в технических деталях, таких как бинарный формат раздельно компилируемых модулей, реализация FFIШаблон:Переход и др. На практике, реальная программа должна отталкиваться от некоего базиса (минимального набора типов, средств ввода-вывода и т. д.). Однако, Определение предъявляет лишь минимальные требования к составу начального базиса, так что единственный обозримый результат корректной программы согласно Определению состоит в том, что программа завершается либо порождает исключение, и большинство реализаций совместимы на этом уровнеШаблон:Sfn.

Однако, даже в стандартном БазисеШаблон:Переход заложены определённые потенциальные проблемы портируемости. НапримерШаблон:Sfn, константа Int.maxInt содержит значение наибольшего возможного целого, упакованное в Шаблон:Iw, и его необходимо извлекать либо сопоставлением с образцом, либо вызовом функции valOf. Для типов конечной размерности значение IntN.maxInt равно SOME(m), и использование обоих способов извлечения равнозначно. Но IntInf.maxInt равно NONE, так что прямое обращение к содержимому через valOf породит исключение Option. По умолчанию IntInf открыта, например, в компиляторе Шаблон:NowrapШаблон:Переход.

С определёнными усилиями возможна разработка программ, свободно портируемых между всеми актуальными реализациями языка. Примером такой программы является HaMLetШаблон:Переход.

Инструментарий разработки

К настоящему времени Standard ML полностью стал достоянием общественности: все реализации являются бесплатными и открытыми и распространяются под самыми лояльными лицензиями (BSD-style, MIT); тексты Определения языкаШаблон:Переход (как в версии 1990 года, так и в ревизированной версии 1997 года) и спецификации БазисаШаблон:Переход также доступны бесплатноШаблон:Переход.

SML имеет большое число реализаций. Значительная их часть написана на самом SML; исключение составляют рантаймы некоторых компиляторов, написанные на Си и Ассемблере, а также система Шаблон:IwШаблон:Переход. Шаблон:Hider Шаблон:Hider Шаблон:Hider Шаблон:Hider Шаблон:Hider

Диалекты, расширения

SML#

SML#[2] консервативно расширяет SML полиморфизмом записей в модели Ацуси Охори, который в SML# используется для бесшовного встраивания SQL в код на SML для интенсивного database-программирования. Шаблон:Details Символ решётки (#) в названии языка символизирует селектор (операцию выбора поля из записи). Одноимённый компиляторШаблон:Переход претендует на хорошее быстродействие. Разработан и развивается в институте Тохоку (Япония) под руководством самого Охори.

Alice

Шаблон:Main

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

Concurrent ML

Шаблон:Main

Concurrent ML (CML) — библиотека, воплощающая встраиваемый язык, который расширяет SML конструкциями конкурентного программирования Шаблон:Iw на основе модели синхронной передачи первоклассных сообщений. Входит в стандартную поставку компиляторов Шаблон:IwШаблон:Переход и MLton. Ключевые идеи CML лежат в основе проекта ManticoreШаблон:Переход и включены в проект successor MLШаблон:Sfn.

Manticore

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

Шаблон:Details

MLPolyR

MLPolyR — игрушечный язык, основанный на простейшем подмножестве SML и дополняющий его несколькими уровнями типобезопасности. Целью проекта является глубокое исследование полиморфизма записей для нужд проекта successor ML. Инновационная система типов MLPolyR решает Шаблон:Iw и гарантирует отсутствие необработанных исключений в программах. Шаблон:Details Разработан под руководством Матиаса Блюма (автора NLFFIШаблон:Переход) в Шаблон:Iw, США.

Mythryl

Mythryl[4] — синтаксический вариант SML, нацеленный на повышение скорости разработки под POSIX. Новый синтаксис во многом заимствован из Си; терминология также пересмотрена под более традиционную (например, функторы переименованы в дженерики). При этом авторы подчёркивают, что не намерены создать «очередную свалку языковых возможностей», а придерживаются минималистичной природы SML и опираются на его ОпределениеШаблон:Переход. Реализация является форком Шаблон:IwШаблон:Переход.

Прочие

Утилиты

  • Compilation Manager (CM) и MLBasis System (MLB) — расширения компиляторов для лучшей поддержки модульности (контроля зависимостей). В принципе, для этой цели мог бы использоваться и традиционный для большинства языков make, но язык модулей SML значительно мощнее средств модульности других языков, а make его преимуществ не поддерживает, и не пригоден для работы в режиме REPLШаблон:Sfn. CM изначально реализован в Шаблон:Iw, затем портирован на MLton. Позже в составе MLton была предложена система MLB и конвертор файлов формата .cm в формат .mlb. Поддержка MLB была добавлена в ML Kit.
  • eXene[5] — библиотека графического интерфейса пользователя под X Window System. Реализует реактивную модель взаимодействия на основе CMLШаблон:Переход. Поставляется с Шаблон:Iw.
  • MLLex, MLYacc, MLAntlr, MLLPT — генераторы лексеров и парсеров (см. Lex и Yacc).

Межъязыковое взаимодействие

  • Интерфейс внешних функций. В разных компиляторах имеет разную реализацию, что тесно связано с представлением данных (прежде всего, обёрнутое или необёрнутое, теговое или бестеговое). В SML/NJ FFI основан на динамической кодогенерации, и если функция принимает на вход данные общим объёмом n байт и возвращает m байт, то её вызов имеет сложность n+mШаблон:Sfn. Некоторые компиляторы (MLtonШаблон:Переход, SML#Шаблон:Переход) используют необёрнутое и бестеговое представление данных и обеспечивают прямые обращения к функциям и данным Си. В последнем случае вынесение медлительных функций в код на Си может существенно повышать общее быстродействие программыШаблон:Sfn.
  • NLFFI (No-Longer-Foreign Function Interface — Шаблон:Lang-ru)Шаблон:Sfn — альтернативный, более высокоуровневый интерфейс внешних функций. NLFFI автоматически порождает связующий код, позволяя подключать *.h-файлы (заголовочные файлы Си) непосредственно в состав проекта на SML (CMШаблон:Переход или MLBШаблон:Переход), что снимает необходимость ручного кодирования определений FFIШаблон:Переход. Конструктивно идея NLFFI состоит в моделировании системы типов Си посредством типов ML; реализация основана CKitШаблон:Переход. Поставляется с Шаблон:Iw и MLton.
  • CKit — фронт-энд языка Си, написанный на SML. Осуществляет трансляцию исходных кодов на Си (с учётом препроцессора) в AST, реализуемое посредством структур данных языка SML. Лежит в основе реализации NLFFIШаблон:Переход.

Идеоматика, соглашения

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

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

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

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

Процедуры

Для процедур принята та же идиома, что и в Си: процедуры представляются функциями, возвращающими значение Шаблон:Iw: 

fun p s = print s
(* val p = fn : sting -> unit *)

Последовательные вычисления

Шаблон:Заготовка раздела 

let D in E end

fun foo ... =
   let
      val _ = ...
   in
      ...
   end

Приёмы

Эта-расширение

Эта-расширение (Шаблон:Lang-en) выражения e есть выражение fn z => e z, то есть обёртка исходного выражения в лямбда-функцию, где z не встречается в e. Разумеется, это имеет смысл лишь в случае, если e имеет стрелочный тип, то есть является функцией. Эта-расширение принуждает задержку вычисления e до применения функции и повторное его вычисление при каждом применении. Этот приём применяется в SML для преодоления ограничений выразительности, связанных с семантикой ограничения на значенияШаблон:Переход. Термин «эта-расширение» заимствован из эта-преобразования в лямбда исчислении, означающего, напротив, редукцию выражения fn z => e z до e в случае, если z не встречается в e (эта-сжатие).[7]Шаблон:Sfn

Значения, индексированные типами

Значения, индексированные типами (Шаблон:Lang-en) — это техника, позволяющая ввести в SML поддержку ad-hoc-полиморфизма (которая в нём изначально отсутствует)[8]. Существует целый ряд её вариантов, в том числе нацеленные на поддержку полноценного объектно-ориентированного программированияШаблон:Sfn.

Fold

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

Примеры программ

Hello World!

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

print "Hello World!\n"

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

Автоматическая вёрстка

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, оформляя диалог по ролямШаблон:Sfn. Шаблон:Hider

Троичные деревья

Для задачи поиска строки в словаре Шаблон:Iw сочетают молниеносную скорость префиксных деревьев с экономичностью двоичных деревьев в отношении памяти. 

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

О языке

Быстродействие

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

ML изначально предоставляет весьма неплохие средства для тонкого контроля за быстродействиемШаблон:Переход, однако, историческиШаблон:Переход реализации ML были крайне медлительными. Тем не менее, ещё в начале 1990-х Шаблон:Iw прочилШаблон:Sfn языку SML скорость исполнения выше скорости языка Си, по крайней мере при интенсивной работе со сложноструктурированными данными (но SML не претендует на то, чтобы быть заменой Си в задачах системного программирования). За следующие несколько лет напряжённая работа над развитием компиляторов привела к тому, что скорость исполнения программ на SML повысилась в 20-40 разШаблон:Sfn.

В конце 1990-х Стивен Уикс задался целью добиться от программ на SML максимально возможной производительности и написал дефункторизатор для Шаблон:IwШаблон:Переход, сразу показавший прирост скорости ещё в 2-3 раза. Дальнейшая работа в этом направлении привела к созданию компилятора MLtonШаблон:Переход, который к середине нулевых годов XXI века показывал прирост скорости перед другими компиляторами в среднем на два порядкаШаблон:Sfn, конкурируя с Си (подробнее см. MLton).

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

На основе фронт-енда Шаблон:Iw был разработан компилятор в исходный код на Си — sml2cШаблон:Переход. Он порождает код хорошего качества, но примечательно, что схема компиляции «сначала в Си, затем в машинный код» до двух раз снижает быстродействие по сравнению с прямой компиляцией SML в машинный код из-за семантических различий между SML и СиШаблон:Sfn.

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

Обоснование семантики

Общие сведения

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

«Определение» (The Definition)

Официальным «стандартом» языка является изданное в виде книги «Определение» (Шаблон:Lang-en). Определение сформулировано в строгих математических понятиях и имеет доказанную надёжность. Непротиворечивость Определения позволяет человеку без запуска конкретного компилятора проверить программу на корректность и вычислить её результат; но, с другой стороны, Определение требует высокой квалификации для понимания и не может служить учебником по языкуШаблон:Sfn.

Доказуемость надёжности не далась сама по себе — Определение было неоднократно пересмотрено прежде, чем увидело свет. Многие языки опираются на общие теории, но при разработке они почти никогда не проверяются на безопасность совместного использования конкретных языковых элементов, являющихся частными приложениями этих теорий, что неизбежно приводит к несовместимости между реализациями языка. Эти проблемы либо игнорируются, либо начинают преподноситься как естественное явление (Шаблон:Lang-en), но в действительности их причиной является то, что язык не был подвергнут математическому анализуШаблон:Sfn. Шаблон:HiderШаблон:Hider

Семантика Харпера — Стоуна

Семантика Харпера — Стоуна (сокращённо «семантика Х-С», Шаблон:Lang-en) представляет собой интерпретацию SML в типизированной системе (Шаблон:Lang-en2). Семантика SML по Х-С определяется через выработкуШаблон:Переход внешнего языка SML во внутренний язык, представляющий собой явно типизированное лямбда-исчисление, и, таким образом, служит теоретико-типовым обоснованием языка. Эта интерпретация может рассматриваться как альтернатива ОпределениюШаблон:Переход, формализующая «статические семантические объекты» через выражения типизированного лямбда-исчисления; а также как декларативное описание правил выработки для компиляторов, управляемых типами (Шаблон:Lang-en), таких как TILT или SML/NJШаблон:Переход. Фактически, фронт-енд компилятора TILT воплощает эту семантику, хотя он был разработан на несколько лет раньше.Шаблон:SfnШаблон:SfnШаблон:Sfn

Внутренний язык основан на языке XML Харпера — Митчела, но имеет более обширный набор примитивов и более выразительную систему модулей, основанную на просвечивающих суммах Харпера — Лилибриджа. Этот язык пригоден для выработки многих других языков, семантика которых основана на лямбда-исчислении, таких как Haskell и Scheme.

Применение этого подхода заложено в проект successor ML. При этом, изменения в языке, не влияющие на внутренний язык, рассматриваются как кратковременная перспектива (Шаблон:Lang-en), а требующие его изменения — как долговременная перспектива (Шаблон:Lang-en).

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

Шаблон:Заготовка раздела

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

Шаблон:Hider Шаблон:Hider Шаблон:Hider Шаблон:Hider

История, философия, терминология

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

В основе языка лежит сильная статическая полиморфная типизация, которая не только обеспечивает верификацию программ на этапе компиляции, но и жёстко обособляет мутабельность, что само по себе повышает потенциал к автоматической оптимизации программ — в частности, упрощает реализацию сборщика мусораШаблон:Sfn.

Первая версия ML была представлена миру в 1974 году в роли мета-языка для построения интерактивных доказательств в составе системы Шаблон:IwШаблон:ПереходШаблон:Sfn. Её реализовали Малькольм Ньюи, Локвуд Моррис и Робин Милнер на платформе DEC10. Первая реализация была крайне неэффективной, так как конструкции ML транслировались в Lisp, который затем интерпретировалсяШаблон:Sfn. Первое полное описание ML как компонента LCF издано в 1979 годуШаблон:Sfn.

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

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

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

Изучение

Наиболее рекомендуемым[10]Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn[11] учебником по SML является книга Шаблон:Iw (автора системы Шаблон:Iw) «ML for the Working Programmer»Шаблон:Sfn.

Для первоначального ознакомления с языком может быть полезен краткий (несколько десятков страниц) курс Шаблон:Iw «Introduction to Standard ML» (доступный в русском переводеШаблон:Sfn), который он использовал для преподавания языка и за следующие два десятилетия расширил до более крупного учебникаШаблон:Sfn.

Учебным руководством по использованию стандартной библиотеки языка, предполагающим его базовое знание, служит книга Рикардо ПуцеллыШаблон:Sfn.

В числе других учебников можно назвать книги ГилмораШаблон:Sfn, УльманаШаблон:Sfn, ШипманаШаблон:Sfn, онлайн-книгу КаммингаШаблон:Sfn.

Среди руководств по профессиональному использованию языка можно выделить книгу Шаблон:Iw (ведущего разработчика Шаблон:Iw) «Modern compiler implementation in ML»Шаблон:Sfn (у этой книги есть две сестры-близняшки: «Modern compiler implementation in Java» и «Modern compiler implementation in C», эквивалентные по структуре, но использующие другие языки для воплощения излагаемых методов). Имеется также масса статей, издаваемых в таких журналах, как JFP, «ML workshop» и др.Шаблон:SfnШаблон:Sfn

Применение

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

Значительная часть существующих кодов на SML представляет собой либо реализацию его же компиляторов, либо системы автоматического доказательства, такие как Шаблон:Iw, Шаблон:Iw и Isabelle (система автоматического доказательства теорем). Все они свободны и открыты.

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

Примечания

Шаблон:Примечания

Литература

Стандарты

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

История, анализ, критика

Прочее

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ Ошибка цитирования Неверный тег <ref>; для сносок автоссылка1 не указан текст
  4. ↑ Шаблон:Cite web
  5. ↑ Шаблон:Cite web
  6. ↑ Шаблон:Cite web
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Cite web
  9. ↑ Шаблон:Cite web
  10. ↑ Шаблон:Cite web
  11. ↑ Шаблон:Cite web
  12. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Standard_ML&oldid=8815138