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

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

Обзор [ править ]

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

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

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

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

Сегодня в семье ML есть несколько языков; три наиболее известных - это Standard ML (SML), OCaml и F # . Идеи ML повлияли на многие другие языки, такие как Haskell , Cyclone , Nemerle , [3] ATS и Elm . [4]

Примеры [ править ]

В следующих примерах используется синтаксис 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 от целого к целому (int -> int), то есть fac принимает целое число в качестве аргумента и возвращает целочисленный результат. Благодаря выводу типа аннотации типов могут быть опущены и будут получены компилятором. Переписанный без аннотаций типов, пример выглядит так:

весело  fac  0  =  1  |  fac  n  =  n  *  fac  ( n  -  1 )

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

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

забавный  факт  n  =  пусть  забавный  fac  0  =  1  |  fac  n  =  n  *  fac  ( n  -  1 )  in  if  ( n  <  0 ),  затем  вызвать  Fail  «отрицательный аргумент»  else  fac  n  end

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

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

забавный  факт  n  =  let  fun  fac  0  acc  =  acc  |  fac  n  acc  =  fac  ( n  -  1 )  ( n  *  acc )  in  if  ( n  <  0 )  затем  поднять  Fail  «отрицательный аргумент»  else  fac  n  1  end

Перевернуть список [ править ]

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

развлечение в  обратном направлении  []  =  []  |  reverse  ( x :: xs )  =  ( reverse  xs )  @  [ x ]

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

веселье  обратное  xs  =  пусть  веселье  rev  []  acc  =  acc  |  rev  ( hd :: tl )  acc  =  rev  tl  ( hd :: acc ) in  rev  xs  [] end

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

Модули [ править ]

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

подпись  ARITH  = sig  type  t ;  val  zero  :  t ; val  succ  :  t  ->  t  ;  val  sum  :  t  *  t  ->  t ; конец
структура  Rational  :  ARITH  = тип данных структуры  t = Rat of int * int ; val zero = Крыса ( 0 , 1 ); fun succ ( Rat ( a , b )) = Rat ( a + b , b ); забавная сумма ( Крыса ( a , b ), Крыса ( c , d )) =                         Крыса ( a * d +  c * b  ,  b * d )  :  t  ; конец

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

Стандартные библиотеки ML реализованы таким образом в виде модулей.

См. Также [ править ]

  • Стандартный ML и его реализации:
    • SML / NJ , реализация с расширениями для параллельного программирования, разработанная в Принстонском университете и Bell Laboratories.
    • Moscow ML , реализация, изначально основанная на Caml Light
    • Alice ML , расширение Standard ML с поддержкой параллельного программирования с использованием фьючерсов.
    • MLton , мощный оптимизирующий компилятор всей программы, строго соответствующий определению.
  • Зависимый ML , расширение ML с зависимой типизацией, которое привело к разработке:
    • АТС
  • Ленивый ML , экспериментальный диалект ML с ленивой оценки из начала 1980-х.
  • PAL (язык программирования) , образовательный язык, связанный с ML.
  • OCaml , "промышленная мощь" [5] диалекта ML, используемого для реализации средства доказательства теорем Coq.
  • F # , зрелый кроссплатформенный язык программирования с открытым исходным кодом, ориентированный на .NET.

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

  1. ^ Робин Милнер. Теория полиморфизма типов в программировании. Журнал компьютерных и системных наук, 17 (3): 348–375, 1978.
  2. ^ Гордон, Майкл JC (1996). «От LCF к HOL: краткая история» . Проверено 11 октября 2007 .
  3. ^ Язык программирования для «спецназа» разработчиков. , Российская сеть разработчиков программного обеспечения: команда проекта Nemerle , данные получены 24 января 2021 г.
  4. ^ Тейт, Брюс А .; Дауд, Фред; Дис, Ян; Моффитт, Джек (2014). «3. Вяз». Еще семь языков за семь недель (версия книги: P1.0, ноябрь 2014 г.). ООО "Прагматичные программисты". С. 97, 101. ISBN 978-1-941222-15-7. На странице 101 создатель Elm Эван Чаплики говорит: «Я склонен говорить, что« Elm - это язык семейства ML », чтобы понять общее наследие всех этих языков». [«эти языки» относятся к Haskell, OCaml, SML и F #.]
  5. ^ «OCaml - это промышленный язык программирования, поддерживающий функциональные, императивные и объектно-ориентированные стили» . Проверено 2 января, 2018.

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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