ML (язык программирования)

Чтобы узнать о других значениях, см. ML .

МЛ

Парадигма	Мультипарадигмальность : функциональная , общая , императивная.
Разработано	Робин Милнер и другие сотрудники Эдинбургского университета
Впервые появился	1973 год ( 1973 )
Дисциплина набора текста	Предполагаемый , статичный , сильный
Диалекты
OCaml , стандартное машинное обучение , F#
Под влиянием
ИСВИМ
Под влиянием
Clojure , Coq , Cyclone , C++ , Elm , F# , F* , Haskell , Idris , Kotlin , Miranda , Nemerle , OCaml , Opa , Erlang , Rust , Scala , Standard ML

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

Обзор

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

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

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

Машинное обучение было разработано Робином Милнером и другими в начале 1970-х годов в Эдинбургском университете . и его синтаксис вдохновлен ISWIM . Исторически ML был задуман для разработки тактики доказательства в средстве доказательства теорем LCF (чей язык, plambda , комбинация исчисления предикатов первого порядка и просто типизированного полиморфного лямбда-исчисления , имел ML в качестве метаязыка).

Сегодня в семействе ML есть несколько языков; тремя наиболее известными являются Standard ML (SML), OCaml и F# . Идеи машинного обучения повлияли на многие другие языки, такие как Haskell , Cyclone , Nemerle , АТС и Вяз .

Примеры

В следующих примерах используется синтаксис Standard ML. Другие диалекты машинного обучения, такие как OCaml и F#, незначительно отличаются.

Факториал

Факториальная функция , выраженная как чистый ML:

fun fac (0 : int) : int = 1
  | fac (n : int) : int = n * fac (n - 1)

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

Часть показанного определения является необязательной и описывает типы этой функции. Обозначение E:t можно прочитать как выражение E имеет тип t . Например, аргументу n присвоен тип целое число (int), а fac (n : int), результат применения fac к целому числу n, также имеет тип целое число. Функция fac в целом имеет тип функции от целого числа до целого (int -> int), то есть fac принимает целое число в качестве аргумента и возвращает целочисленный результат. Благодаря выводу типов аннотации типов могут быть опущены и будут получены компилятором. Переписанный без аннотаций типов, пример выглядит так:

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

Функция также использует сопоставление с образцом — важную часть программирования машинного обучения. Обратите внимание, что параметры функции не обязательно заключаются в круглые скобки, а разделяются пробелами. Если аргумент функции равен 0 (ноль), она вернет целое число 1 (единица). Во всех остальных случаях пробуется вторая линия. Это рекурсия , которая выполняет функцию снова, пока не будет достигнут базовый случай.

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

fun fact n = let
  fun fac 0 = 1
    | fac n = n * fac (n - 1)
  in
    if (n < 0) then raise Domain else fac n
  end

Проблемный случай (когда n отрицательно) демонстрирует использование системы исключений ML.

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

fun fact n = let
  fun fac 0 acc = acc
    | fac n acc = fac (n - 1) (n * acc)
  in
    if (n < 0) then raise Domain else fac n 1
  end

Список обратный

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

fun reverse [] = []
  | reverse (x :: xs) = (reverse xs) @ [x]

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

fun 'a reverse xs : 'a list = List.foldl (op ::) [] xs

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

Модули

Модули — это система машинного обучения для структурирования больших проектов и библиотек. Модуль состоит из файла подписи и одного или нескольких файлов структуры. Файл подписи определяет API реализуемый интерфейса Java (например, файл заголовка C или файл ). Структура реализует подпись (например, исходный файл C или файл класса Java). Например, следующее определяет арифметическую сигнатуру и ее реализацию с использованием чисел Rational:

signature ARITH =
sig
        type t
        val zero : t
        val succ : t -> t
        val sum : t * t -> t
end

structure Rational : ARITH =
struct
        datatype t = Rat of int * int
        val zero = Rat (0, 1)
        fun succ (Rat (a, b)) = Rat (a + b, b)
        fun sum (Rat (a, b), Rat (c, d)) = Rat (a * d + c * b , b * d)
end

Они импортируются в интерпретатор командой «use». Взаимодействие с реализацией разрешено только через функции подписи, например, невозможно создать объект данных «Крыса» напрямую с помощью этого кода. Блок «структура» скрывает все детали реализации снаружи.

Таким образом, стандартные библиотеки ML реализуются как модули.

См. также

• Стандартное машинное обучение и стандартное машинное обучение § Реализации
• Зависимый ML : зависимо типизированное расширение ML.
  • ATS : дальнейшее развитие зависимого ОД
• Lazy ML : экспериментальный диалект ML с ленивой оценкой начала 1980-х годов.
• PAL (язык программирования) : образовательный язык, связанный с ML.
• OCaml : диалект машинного обучения, используемый для реализации Coq и различного программного обеспечения.
• F # : кроссплатформенный функциональный язык с открытым исходным кодом для .NET. платформы

Дальнейшее чтение

• Определение стандартного ОД , Робин Милнер, Мэдс Тофте , Роберт Харпер , MIT Press, 1990; (в исправленное издание добавлен автор Дэвид МакКуин), MIT Press 1997, ISBN   0-262-63181-4 Определение стандартного ОД (пересмотренное) .
• Комментарий к стандартному ОД , Робин Милнер , Мэдс Тофте , MIT Press 1997, ISBN   0-262-63137-7 .
• ML для работающего программиста , Лоуренс Полсон , издательство Кембриджского университета, 1991, 1996, ISBN   0-521-57050-6 .
• Харпер, Роберт (2011). Программирование в Standard ML (PDF) . Университет Карнеги-Меллон.
• Элементы программирования машинного обучения , Джеффри Д. Уллман , Прентис-Холл, 1994, 1998, ISBN   0-13-790387-1 .

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

• Стандартный ML Нью-Джерси, еще одна популярная реализация.
• F #, реализация машинного обучения с использованием платформы Microsoft .NET. Архивировано 18 февраля 2010 г. на Wayback Machine.
• MLton, компилятор Standard ML, оптимизирующий всю программу.
• CakeML, версия ML с циклом чтения-оценки-печати с формально проверенной средой выполнения и переводом на ассемблер.