Стандартный ML

Стандартный ML

Парадигма	Мультипарадигмальность : функциональная , императивная , модульная.
Семья	МЛ
Впервые появился	1983 год ( 1983 )
Стабильная версия	Стандартный ML '97 / 1997 ( 1997 )
Дисциплина набора текста	Предполагаемый , статичный , сильный
Расширения имен файлов	.sml
Веб-сайт	смлсемья .github .что
Основные реализации
СМЛ/Нью-Джерси , MLton , Поли/ML
Диалекты
Алиса , Параллельное ML , Зависимое ML
Под влиянием
МЛ , Хоуп , Паскаль
Под влиянием
Elm , F# , F* , Haskell , OCaml , Python , Ржавчина , Скала

Standard ML ( SML ) — назначения с высокого уровня модульный , функциональный общего язык программирования во время компиляции проверкой типов и выводом типов . Он популярен при написании компиляторов , при исследовании языков программирования и при разработке средств доказательства теорем .

Стандартный ML — это современный диалект ML , языка, используемого в Логика для вычислимых функций проекте доказательства теорем « » (LCF). Среди широко используемых языков он отличается тем, что имеет формальную спецификацию , представленную в виде правил типизации и операционной семантики в «Определении стандартного машинного обучения» .

Язык

Стандартный ML — это функциональный язык программирования с некоторыми нечистыми функциями. Программы, написанные на стандартном ML, состоят из выражений, в отличие от операторов или команд, хотя некоторые выражения типа unit оцениваются только на предмет их побочных эффектов .

Функции

Как и во всех функциональных языках, ключевой особенностью Standard ML является функция , которая используется для абстракции. Факториал можно выразить следующим образом:

fun factorial n = 
    if n = 0 then 1 else n * factorial (n - 1)

Вывод типа

Компилятор SML должен определить статический тип. val factorial : int -> int без предоставленных пользователем аннотаций типов. Это должно сделать вывод n используется только с целочисленными выражениями и, следовательно, само должно быть целым числом, а все терминальные выражения являются целочисленными выражениями.

Декларативные определения

Та же самая функция может быть выражена с помощью определений клаузальных функций , где условие if - then - else заменяется шаблонами факториальной функции, вычисляемой для определенных значений:

fun factorial 0 = 1
  | factorial n = n * factorial (n - 1)

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

или итеративно:

fun factorial n = let val i = ref n and acc = ref 1 in
    while !i > 0 do (acc := !acc * !i; i := !i - 1); !acc
end

Лямбда-функции

или как лямбда-функция:

val rec factorial = fn 0 => 1 | n => n * factorial (n - 1)

Здесь ключевое слово val вводит привязку идентификатора к значению, fn вводит анонимную функцию и rec позволяет определению быть самореферентным.

Местные определения

Инкапсуляция сохраняющего инвариант жесткого цикла хвостовой рекурсии с одним или несколькими параметрами аккумулятора внутри безинвариантной внешней функции, как показано здесь, является распространенной идиомой в стандартном машинном обучении.

Используя локальную функцию, ее можно переписать в более эффективном стиле хвостовой рекурсии:

local
    fun loop (0, acc) = acc
      | loop (m, acc) = loop (m - 1, m * acc)
in
    fun factorial n = loop (n, 1)
end

Введите синонимы

Синоним типа определяется ключевым словом type. Вот синоним типа для точек на плоскости и функции, вычисляющие расстояния между двумя точками и площадь треугольника с заданными углами по формуле Герона . (Эти определения будут использоваться в последующих примерах).

type loc = real * real

fun square (x : real) = x * x

fun dist (x, y) (x', y') =
    Math.sqrt (square (x' - x) + square (y' - y))

fun heron (a, b, c) = let
    val x = dist a b
    val y = dist b c
    val z = dist a c
    val s = (x + y + z) / 2.0
    in
        Math.sqrt (s * (s - x) * (s - y) * (s - z))
    end

Алгебраические типы данных

Стандартный ML обеспечивает надежную поддержку алгебраических типов данных (ADT). Тип данных можно рассматривать как несвязное объединение кортежей (или «сумму произведений»). Их легко определить и легко использовать, в основном благодаря сопоставлению с образцом и проверке избыточности шаблонов в большинстве стандартных реализаций ML , а также проверке полноты шаблонов .

В объектно-ориентированных языках программирования несвязное объединение может быть выражено в виде иерархии классов . Однако, в отличие от иерархий классов , ADT закрыты . Таким образом, расширяемость АТД ортогональна расширяемости иерархий классов. Иерархии классов могут быть расширены новыми подклассами, реализующими тот же интерфейс, а функции АТД могут быть расширены для фиксированного набора конструкторов. См. проблему с выражением .

Тип данных определяется ключевым словом datatype, как в:

datatype shape
    = Circle   of loc * real      (* center and radius *)
    | Square   of loc * real      (* upper-left corner and side length; axis-aligned *)
    | Triangle of loc * loc * loc (* corners *)

Обратите внимание, что синоним типа не может быть рекурсивным; типы данных необходимы для определения рекурсивных конструкторов. (В данном примере это не обсуждается.)

Сопоставление с образцом

Шаблоны сопоставляются в том порядке, в котором они определены. Программисты на C могут использовать тегированные объединения , диспетчеризируя значения тегов, чтобы делать то, что ML делает с типами данных и сопоставлением с образцом. Тем не менее, хотя программа C, оснащенная соответствующими проверками, в некотором смысле будет такой же надежной, как и соответствующая программа ML, эти проверки обязательно будут динамическими; ML Статические проверки обеспечивают надежную гарантию корректности программы во время компиляции.

Аргументы функции можно определить как шаблоны следующим образом:

fun area (Circle (_, r)) = Math.pi * square r
  | area (Square (_, s)) = square s
  | area (Triangle p) = heron p (* see above *)

Так называемая «клаузальная форма» определения функции, в которой аргументы определяются как шаблоны, является просто синтаксическим сахаром для регистрового выражения:

fun area shape = case shape of
    Circle (_, r) => Math.pi * square r
  | Square (_, s) => square s
  | Triangle p => heron p

Проверка полноты

Проверка полноты шаблонов гарантирует, что каждому конструктору типа данных соответствует хотя бы один шаблон.

Следующий шаблон не является исчерпывающим:

fun center (Circle (c, _)) = c
  | center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)

Не существует шаблона для Triangle дело в center функция. Компилятор выдаст предупреждение о том, что выражение case не является исчерпывающим, и если Triangle передается этой функции во время выполнения, exception Match будет повышен.

Проверка избыточности

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

fun f (Circle ((x, y), r)) = x + y
  | f (Circle _) = 1.0
  | f _ = 0.0

Любое значение, соответствующее шаблону во втором предложении, будет также соответствовать шаблону в первом предложении, поэтому второе предложение недостижимо. Таким образом, это определение в целом демонстрирует избыточность и вызывает предупреждение во время компиляции.

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

val hasCorners = fn (Circle _) => false | _ => true

Если управление проходит первый шаблон ( Circle), мы знаем, что форма должна быть либо Square или Triangle. В любом из этих случаев мы знаем, что у фигуры есть углы, поэтому мы можем вернуться true не различая фактической формы.

Функции высшего порядка

Функции могут использовать функции в качестве аргументов:

fun map f (x, y) = (f x, f y)

Функции могут создавать функции как возвращаемые значения:

fun constant k = (fn _ => k)

Функции также могут как потреблять, так и создавать функции:

fun compose (f, g) = (fn x => f (g x))

Функция List.map из базовой библиотеки — одна из наиболее часто используемых функций высшего порядка в Standard ML:

fun map _ [] = []
  | map f (x :: xs) = f x :: map f xs

Более эффективная реализация с хвостовой рекурсией List.foldl:

fun map f = List.rev o List.foldl (fn (x, acc) => f x :: acc) []

Исключения

Исключения возникают с помощью ключевого слова raise и обрабатывается с помощью сопоставления с образцом handle построить. Система исключений может реализовать нелокальный выход ; этот метод оптимизации подходит для таких функций, как следующие.

local
    exception Zero;
    val p = fn (0, _) => raise Zero | (a, b) => a * b
in
    fun prod xs = List.foldl p 1 xs handle Zero => 0
end

Когда exception Zero поднимается, управление выходит из функции List.foldl вообще. Рассмотрим альтернативу: будет возвращено значение 0, оно будет умножено на следующее целое число в списке, будет возвращено полученное значение (неизбежно 0) и так далее. Вызов исключения позволяет элементу управления пропустить всю цепочку кадров и избежать связанных с ней вычислений. Обратите внимание на использование подчеркивания ( _) как шаблон подстановочного знака.

Ту же самую оптимизацию можно получить с помощью хвостового вызова .

local
    fun p a (0 :: _) = 0
      | p a (x :: xs) = p (a * x) xs
      | p a [] = a
in
    val prod = p 1
end

Модульная система

Расширенная система модулей Standard ML позволяет разлагать программы на иерархически организованные структуры логически связанных типов и определений значений. Модули обеспечивают не только управление пространством имен , но и абстракцию в том смысле, что они позволяют определять абстрактные типы данных . Систему модулей составляют три основные синтаксические конструкции: сигнатуры, структуры и функторы.

Подписи

Сигнатура — это интерфейс , который обычно рассматривается как тип структуры; он определяет имена всех сущностей, предоставляемых структурой, арность каждого компонента типа, тип каждого компонента значения и подпись каждой подструктуры. Определения компонентов типа не являются обязательными; Компоненты типа, определения которых скрыты, являются абстрактными типами .

Например, подпись для очереди может быть следующей:

signature QUEUE = sig
    type 'a queue
    exception QueueError;
    val empty     : 'a queue
    val isEmpty   : 'a queue -> bool
    val singleton : 'a -> 'a queue
    val fromList  : 'a list -> 'a queue
    val insert    : 'a * 'a queue -> 'a queue
    val peek      : 'a queue -> 'a
    val remove    : 'a queue -> 'a * 'a queue
end

Эта сигнатура описывает модуль, предоставляющий полиморфный тип. 'a queue, exception QueueErrorи значения, определяющие основные операции с очередями.

Структуры

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

Структуру очереди можно реализовать следующим образом:

structure TwoListQueue :> QUEUE = struct
    type 'a queue = 'a list * 'a list

    exception QueueError;

    val empty = ([], [])

    fun isEmpty ([], []) = true
      | isEmpty _ = false

    fun singleton a = ([], [a])

    fun fromList a = ([], a)

    fun insert (a, ([], [])) = singleton a
      | insert (a, (ins, outs)) = (a :: ins, outs)

    fun peek (_, []) = raise QueueError
      | peek (ins, outs) = List.hd outs

    fun remove (_, []) = raise QueueError
      | remove (ins, [a]) = (a, ([], List.rev ins))
      | remove (ins, a :: outs) = (a, (ins, outs))
end

Это определение заявляет, что structure TwoListQueue реализует signature QUEUE. Кроме того, непрозрачное приписывание , обозначаемое :> утверждает, что любые типы, которые не определены в сигнатуре (т.е. type 'a queue) должно быть абстрактным, то есть определение очереди как пары списков не видно за пределами модуля. Структура реализует все определения в сигнатуре.

Доступ к типам и значениям в структуре можно получить с помощью «точечной записи»:

val q : string TwoListQueue.queue = TwoListQueue.empty
val q' = TwoListQueue.insert (Real.toString Math.pi, q)

Функторы

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

Один популярный алгоритм для поиска деревьев в ширину используются очереди. Вот версия этого алгоритма, параметризованная в абстрактной структуре очереди:

(* after Okasaki, ICFP, 2000 *)
functor BFS (Q: QUEUE) = struct
  datatype 'a tree = E | T of 'a * 'a tree * 'a tree

  local
    fun bfsQ q = if Q.isEmpty q then [] else search (Q.remove q)
    and search (E, q) = bfsQ q
      | search (T (x, l, r), q) = x :: bfsQ (insert (insert q l) r)
    and insert q a = Q.insert (a, q)
  in
    fun bfs t = bfsQ (Q.singleton t)
  end
end

structure QueueBFS = BFS (TwoListQueue)

В пределах functor BFS, представление очереди не видно. Более конкретно, невозможно выбрать первый список в очереди из двух списков, если это действительно используемое представление. Этот механизм абстракции данных делает поиск в ширину действительно независимым от реализации очереди. В целом это желательно; в этом случае структура очереди может безопасно поддерживать любые логические инварианты, от которых зависит ее корректность, за пуленепробиваемой стеной абстракции.

Примеры кода

Фрагменты кода SML легче всего изучать, вводя их в интерактивный файл .

Привет, мир!

Далее следует «Привет, мир!» программа :

привет.sml
print "Hello, world!\n";
бить
$ mlton hello.sml $ ./hello Hello, world!

Алгоритмы

Сортировка вставкой

Сортировка вставкой для int list (по возрастанию) можно кратко выразить следующим образом:

fun insert (x, []) = [x] | insert (x, h :: t) = sort x (h, t)
and sort x (h, t) = if x < h then [x, h] @ t else h :: insert (x, t)
val insertionsort = List.foldl insert []

Сортировка слиянием

Основная статья: Сортировка слиянием

Здесь классический алгоритм сортировки слиянием реализован в трех функциях: разделение, слияние и сортировка слиянием. Также обратите внимание на отсутствие типов, за исключением синтаксиса op :: и [] которые обозначают списки. Этот код будет сортировать списки любого типа, если имеется последовательная функция упорядочивания. cmp определяется. Используя вывод типа Хиндли-Милнера , можно вывести типы всех переменных, даже таких сложных типов, как тип функции. cmp.

Расколоть

fun split реализуется с замыканием с отслеживанием состояния , которое чередуется между true и false, игнорируя ввод:

fun alternator {} = let val state = ref true
    in fn a => !state before state := not (!state) end

(* Split a list into near-halves which will either be the same length,
 * or the first will have one more element than the other.
 * Runs in O(n) time, where n = |xs|.
 *)
fun split xs = List.partition (alternator {}) xs

Объединить

Для повышения эффективности слияние использует локальный функциональный цикл. Внутренний loop определяется в терминах случаев: когда оба списка непусты ( x :: xs) и когда один список пуст ( []).

Эта функция объединяет два отсортированных списка в один. Обратите внимание, как аккумулятор acc строится задом наперед, а затем переворачивается перед возвратом. Это распространенный метод, поскольку 'a list представляется в виде связанного списка ; этот метод требует больше тактового времени, но асимптотика не хуже.

(* Merge two ordered lists using the order cmp.
 * Pre: each list must already be ordered per cmp.
 * Runs in O(n) time, where n = |xs| + |ys|.
 *)
fun merge cmp (xs, []) = xs
  | merge cmp (xs, y :: ys) = let
    fun loop (a, acc) (xs, []) = List.revAppend (a :: acc, xs)
      | loop (a, acc) (xs, y :: ys) =
        if cmp (a, y)
        then loop (y, a :: acc) (ys, xs)
        else loop (a, y :: acc) (xs, ys)
    in
        loop (y, []) (ys, xs)
    end

Сортировка слиянием

Основная функция:

fun ap f (x, y) = (f x, f y)

(* Sort a list in according to the given ordering operation cmp.
 * Runs in O(n log n) time, where n = |xs|.
 *)
fun mergesort cmp [] = []
  | mergesort cmp [x] = [x]
  | mergesort cmp xs = (merge cmp o ap (mergesort cmp) o split) xs

Быстрая сортировка

Основная статья: Быстрая сортировка

Быструю сортировку можно выразить следующим образом. fun part это замыкание , которое использует оператор заказа op <<.

infix <<

fun quicksort (op <<) = let
    fun part p = List.partition (fn x => x << p)
    fun sort [] = []
      | sort (p :: xs) = join p (part p xs)
    and join p (l, r) = sort l @ p :: sort r
    in
        sort
    end

Интерпретатор выражений

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

exception TyErr;

datatype ty = IntTy | BoolTy

fun unify (IntTy, IntTy) = IntTy
  | unify (BoolTy, BoolTy) = BoolTy
  | unify (_, _) = raise TyErr

datatype exp
    = True
    | False
    | Int of int
    | Not of exp
    | Add of exp * exp
    | If  of exp * exp * exp

fun infer True = BoolTy
  | infer False = BoolTy
  | infer (Int _) = IntTy
  | infer (Not e) = (assert e BoolTy; BoolTy)
  | infer (Add (a, b)) = (assert a IntTy; assert b IntTy; IntTy)
  | infer (If (e, t, f)) = (assert e BoolTy; unify (infer t, infer f))
and assert e t = unify (infer e, t)

fun eval True = True
  | eval False = False
  | eval (Int n) = Int n
  | eval (Not e) = if eval e = True then False else True
  | eval (Add (a, b)) = (case (eval a, eval b) of (Int x, Int y) => Int (x + y))
  | eval (If (e, t, f)) = eval (if eval e = True then t else f)

fun run e = (infer e; SOME (eval e)) handle TyErr => NONE

Пример использования правильно типизированных и неправильно типизированных выражений:

val SOME (Int 3) = run (Add (Int 1, Int 2)) (* well-typed *)
val NONE = run (If (Not (Int 1), True, False)) (* ill-typed *)

Целые числа произвольной точности

The IntInf Модуль обеспечивает целочисленную арифметику произвольной точности. Более того, целочисленные литералы могут использоваться как целые числа произвольной точности без необходимости каких-либо действий программиста.

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

факт.sml
fun fact n : IntInf.int = if n = 0 then 1 else n * fact (n - 1); fun printLine str = TextIO.output (TextIO.stdOut, str ^ "\n"); val () = printLine (IntInf.toString (fact 120));
бить
$ mlton fact.sml $ ./fact 6689502913449127057588118054090372586752746333138029810295671352301 6335572449629893668741652719849813081576378932140905525344085894081 21859898481114389650005964960521256960000000000000000000000000000

Частичное применение

Каррированные функции имеют множество применений, например, для устранения избыточного кода. Например, модулю могут потребоваться функции типа a -> b, но удобнее писать функции типа a * c -> b где существует фиксированная связь между объектами типа a и c. Функция типа c -> (a * c -> b) -> a -> b можно исключить эту общность. Это пример шаблона адаптера .

В этом примере fun d вычисляет числовую производную заданной функции f в точку x:

- fun d delta f x = (f (x + delta) - f (x - delta)) / (2.0 * delta)
val d = fn : real -> (real -> real) -> real -> real

Тип fun d указывает, что он отображает «плавающее число» на функцию типа (real -> real) -> real -> real. Это позволяет нам частично применять аргументы, известные как каррирование . В этом случае функция d можно специализировать, частично применив его с аргументом delta. Хороший выбор для delta при использовании этого алгоритма это кубический корень из машинного эпсилона .

- val d' = d 1E~8;
val d' = fn : (real -> real) -> real -> real

Выведенный тип указывает на то, что d' ожидает функцию типа real -> real в качестве первого аргумента. Мы можем вычислить приближение к производной $f(x)=x^{3}-x-1$ в $x=3$. Правильный ответ $f'(3)=27-1=26$.

- d' (fn x => x * x * x - x - 1.0) 3.0;
val it = 25.9999996644 : real

Библиотеки

Стандартный

Базовая библиотека был стандартизирован и поставляется с большинством реализаций. Он предоставляет модули для деревьев, массивов и других структур данных, а также интерфейсы ввода/вывода и системные интерфейсы.

Третья сторона

Для числовых вычислений существует модуль Matrix (но в настоящее время он не работает) https://www.cs.cmu.edu/afs/cs/project/pscico/pscico/src/matrix/README.html .

Что касается графики, cairo-sml — это интерфейс с открытым исходным кодом для графической библиотеки Cairo . Для машинного обучения существует библиотека графических моделей.

Реализации

Реализации Standard ML включают следующее:

Стандартный

• HaMLet : стандартный интерпретатор машинного обучения, призванный стать точной и доступной эталонной реализацией стандарта.
• MLton ( mlton.org ): компилятор , оптимизирующий всю программу , который строго соответствует определению и создает очень быстрый код по сравнению с другими реализациями ML, включая серверные части для LLVM и C.
• Московское машинное обучение : облегченная реализация, основанная на движке среды выполнения Caml Light, который реализует полный стандартный язык машинного обучения, включая модули и большую часть базовой библиотеки.
• Poly/ML : полная реализация Standard ML, которая создает быстрый код и поддерживает многоядерное оборудование (через потоки интерфейса переносимой операционной системы ( POSIX ); его система времени выполнения выполняет параллельную сборку мусора и совместное использование неизменяемых подструктур в режиме онлайн.
• Standard ML of New Jersey ( smlnj.org ): полный компилятор со связанными библиотеками, инструментами, интерактивной оболочкой и документацией с поддержкой Concurrent ML.
• SML.NET : стандартный компилятор ML для среды CLR с расширениями для связывания с другим .NET. кодом платформы
• ML Kit. Архивировано 7 января 2016 г. на Wayback Machine : реализация, очень близко основанная на определении, интегрирующая сборщик мусора (который можно отключить) и управление памятью на основе регионов с автоматическим выводом регионов с целью поддержки режима реального времени. приложения

Производная

• Алиса : интерпретатор Standard ML от Саарского университета с поддержкой параллельного программирования с использованием фьючерсов , ленивых вычислений , распределенных вычислений посредством удаленных вызовов процедур и программирования с ограничениями.
• SML# : расширение SML, обеспечивающее полиморфизм записей и совместимость с языком C. Это обычный собственный компилятор, и его название не является намеком на работу на платформе .NET.
• SOSML : реализация, написанная на TypeScript , поддерживающая большую часть языка SML и избранные части базовой библиотеки.

Исследовать

• CakeML — это REPL-версия ML с формально проверенной средой выполнения и переводом на ассемблер.
• Isabelle ( Isabelle/ML. Архивировано 30 августа 2020 г. на Wayback Machine ) интегрирует параллельный Poly/ML в интерактивное средство доказательства теорем со сложной интегрированной средой разработки (на основе jEdit ) для официального стандарта ML (SML'97), Isabelle/ML. диалект и язык доказательства. Начиная с Isabelle2016, для ML также доступен отладчик уровня исходного кода.
• Poplog реализует версию Standard ML вместе с Common Lisp и Prolog , что позволяет программировать на смешанных языках; все они реализованы в POP-11 , который компилируется постепенно .
• TILT — это полностью сертифицированный компилятор для Standard ML, который использует типизированные промежуточные языки для оптимизации кода и обеспечения корректности и может компилироваться в типизированный ассемблер .

Все эти реализации имеют открытый исходный код и доступны бесплатно. Большинство из них реализованы в Standard ML. Коммерческих реализаций больше нет; Harlequin , ныне несуществующая, когда-то выпустила коммерческую IDE и компилятор под названием MLWorks, которые перешли к Xanalys и позже были открыты с открытым исходным кодом после того, как 26 апреля 2013 года они были приобретены Ravenbrook Limited.

Крупные проекты с использованием SML

ИТ- университета Копенгагена Вся корпоративная архитектура реализована примерно в 100 000 строк SML, включая учет персонала, расчет заработной платы, администрирование курсов и обратную связь, управление студенческими проектами и веб-интерфейсы самообслуживания.

Помощники доказательства HOL4 , Isabelle , LEGO и Twelf написаны на стандартном ML. Он также используется авторами компиляторов и разработчиками интегральных схем, такими как ARM .

См. также

• Декларативное программирование

Внешние ссылки

О стандартном машинном обучении

• Пересмотренное определение
• Проект GitHub семейства Standard ML , заархивированный 20 февраля 2020 г. на Wayback Machine.
• Что такое СМЛ?
• Что такое SML '97?

О преемнике МЛ

• преемник ML (sML) : эволюция ML с использованием стандартного ML в качестве отправной точки.
• HaMLet на GitHub : эталонная реализация для преемника ML

Практичный

• Базовое вводное руководство
• Примеры в коде Rosetta

Академический

• Программирование в стандартном машинном обучении
• Программирование в Standard ML '97: онлайн-руководство