ML ( Meta Language ) — это универсальный функциональный язык программирования высокого уровня . Он известен использованием полиморфной системы типов Хиндли–Милнера , которая автоматически назначает типы данных большинству выражений, не требуя явных аннотаций типов ( вывод типов ), и обеспечивает безопасность типов; существует формальное доказательство того, что хорошо типизированная программа ML не вызывает ошибок типов во время выполнения. [1] ML обеспечивает сопоставление с образцом для аргументов функций, сборку мусора , императивное программирование , вызов по значению и каррирование . Будучи универсальным языком программирования , ML широко используется в исследованиях языков программирования и является одним из немногих языков, которые полностью определены и проверены с использованием формальной семантики . Его типы и сопоставление с образцом делают его хорошо подходящим и широко используемым для работы с другими формальными языками, такими как написание компиляторов , автоматическое доказательство теорем и формальная верификация .
Возможности ML включают стратегию оценки вызова по значению , функции первого класса , автоматическое управление памятью посредством сборки мусора, параметрический полиморфизм , статическую типизацию , вывод типа , алгебраические типы данных , сопоставление с образцом и обработку исключений . ML использует статические правила области действия. [2]
ML можно назвать нечистым функциональным языком, потому что, хотя он поощряет функциональное программирование, он допускает побочные эффекты [3] (как языки типа Lisp , но в отличие от чисто функционального языка типа Haskell ). Как и большинство языков программирования, ML использует активное вычисление , что означает, что все подвыражения всегда вычисляются, хотя ленивое вычисление может быть достигнуто с помощью замыканий . Таким образом, бесконечные потоки могут быть созданы и использованы как в Haskell, но их выражение является косвенным.
Сильные стороны машинного обучения в основном применяются в разработке и обработке языков (компиляторы, анализаторы, программы доказательства теорем), но это язык общего назначения, который также используется в биоинформатике и финансовых системах.
ML был разработан Робином Милнером и другими в начале 1970-х годов в Эдинбургском университете [4] , и его синтаксис вдохновлен ISWIM . Исторически ML был задуман для разработки тактик доказательства в LCF-доказательстве теорем (язык которого, pplambda , комбинация исчисления предикатов первого порядка и просто-типизированного полиморфного лямбда-исчисления , имел ML в качестве своего метаязыка).
Сегодня в семействе ML есть несколько языков; три наиболее известных — Standard ML (SML), OCaml и F# . Идеи ML оказали влияние на множество других языков, таких как Haskell , Cyclone , Nemerle , [5] ATS и Elm . [6]
В следующих примерах используется синтаксис Standard ML. Другие диалекты ML, такие как OCaml и F#, немного отличаются.
Факториальная функция , выраженная в виде чистого ML:
весело fac ( 0 : int ) : int = 1 | fac ( n : int ) : int = n * fac ( n - 1 )Это описывает факториал как рекурсивную функцию с одним конечным базовым случаем. Это похоже на описания факториалов в учебниках по математике. Большая часть кода ML похожа на математику по удобству и синтаксису.
Часть показанного определения является необязательной и описывает типы этой функции. Обозначение E : t можно прочитать как выражение E имеет тип t . Например, аргументу n назначается тип integer (int), а fac (n : int), результат применения fac к целому числу n, также имеет тип integer. Функция fac в целом тогда имеет тип function from integer to integer (int -> int), то есть fac принимает целое число в качестве аргумента и возвращает целочисленный результат. Благодаря выводу типов аннотации типов могут быть опущены и будут выведены компилятором. Переписанный без аннотаций типов пример выглядит так:
весело , факт 0 = 1 | факт n = n * факт ( n - 1 )Функция также полагается на сопоставление с образцом, важную часть программирования ML. Обратите внимание, что параметры функции не обязательно заключаются в скобки, а разделяются пробелами. Когда аргумент функции равен 0 (нулю), она вернет целое число 1 (один). Во всех остальных случаях пробуется вторая строка. Это рекурсия , и она снова выполняет функцию, пока не будет достигнут базовый случай.
Эта реализация факториальной функции не гарантирует завершения, поскольку отрицательный аргумент вызывает бесконечную нисходящую цепочку рекурсивных вызовов. Более надежная реализация будет проверять неотрицательный аргумент перед рекурсией, как показано ниже:
забавный факт n = пусть забавный факт 0 = 1 | факт n = n * факт ( n - 1 ) в если ( n < 0 ) тогда поднять Домен иначе факт n конецПроблемный случай (когда n отрицательно) демонстрирует использование системы исключений ML.
Функцию можно улучшить еще больше, записав ее внутренний цикл как вызов хвоста , так что стек вызовов не должен расти пропорционально количеству вызовов функций. Это достигается путем добавления дополнительного параметра accumulator к внутренней функции. Наконец, мы приходим к
забавный факт n = пусть забавный факт 0 акк = акк | факт n акк = факт ( n - 1 ) ( n * акк ) в если ( n < 0 ) тогда поднять Домен иначе факт n 1 конецСледующая функция переворачивает элементы в списке. Точнее, она возвращает новый список, элементы которого расположены в обратном порядке по сравнению с заданным списком.
весело реверс [] = [] | реверс ( x :: xs ) = ( реверс xs ) @ [ x ]Эта реализация реверса, хотя и правильная и понятная, неэффективна, требуя квадратичного времени для выполнения. Функцию можно переписать для выполнения за линейное время :
fun 'a reverse xs : 'a list = List . foldl ( op :: ) [] xsЭта функция является примером параметрического полиморфизма. То есть она может потреблять списки, элементы которых имеют любой тип, и возвращать списки того же типа.
Модули — это система ML для структурирования больших проектов и библиотек. Модуль состоит из файла сигнатуры и одного или нескольких файлов структуры. Файл сигнатуры определяет API , который должен быть реализован (например, файл заголовка C или файл интерфейса Java ). Структура реализует сигнатуру (например, исходный файл C или файл класса Java). Например, следующее определяет арифметическую сигнатуру и ее реализацию с использованием рациональных чисел:
сигнатура ARITH = тип sig t значение ноль : t значение succ : t -> t значение сумма : t * t -> t конец структура 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'. Взаимодействие с реализацией разрешено только через функции подписи, например, невозможно создать объект данных 'Rat' напрямую через этот код. Блок 'structure' скрывает все детали реализации снаружи.
Стандартные библиотеки ML реализованы в виде модулей именно таким образом.
На странице 101 создатель Elm Эван Чаплицки говорит: «Я склонен говорить, что «Elm — это язык семейства ML», чтобы указать на общее наследие всех этих языков». [«эти языки» относятся к Haskell, OCaml, SML и F#.]