ML (Meta Language)

ML

Парадигма	мультипарадигменный: функциональный, императивный, модульный
Спроектировано	Робин Милнер и др. - Эдинбургский университет
Первый   появившийся	1973
Печать дисциплины	сильная, статическая, выводная
Диалект
Standard ML, Caml Light, OCaml, F#, LazyML, OcaMl
Под влиянием
ISWIM
Влияние
Miranda, Haskell, Cyclone, Nemerle, C++

Функциональный язык программирования ML был разработан Робином Мионером (Награда Тьюринга, 1991 г.). Это был первый язык, в котором вместе с типобезопасным механизмом обработки исключений была применена подстановка типов.

Введение

Основной задачей языка ML было предоставление возможности разрабатывать методы доказательства в LCF Theorem Prover (Логика для Вычислимых Функционалов), Его язык, pplambda, является комбинацией предикатов первого порядка и ляибда-вычислений простых типов. ML являлся метаязыком для этого языка.

ML предоставляет следующие свойства:

• Автоматическое вычисление типов: программисту не нужно писать типы явно, компилятор вычислит их сам
• Декларативный синтаксис с использованием технологии Pattern Matching
• Шаблонные типы (имеют некоторое сходство с шаблонами в C++)
• Параметрические модули (функторы): модули программы могут принимать другие модули в качестве аргумента.

В отличие от Haskell (Lisp и Scheme) , ML является строгим языком. Аргументы функции должны всегда быть вычислены до вычисления тела этой функции.

Диалекты в ML

В широком использовании можно встретить три диалекта:

• O'Caml
• Standard ML
• F#

Идеи языка ML легли в основу таких языков программирования, как Haskell, Cyclone, Nemerle, ATS, и Elm.

Standard ML

Определение

Язык программирования Standard ML, также известный как SML, имеет в своей основе определенные фундаментальные идеи информатики. Именно поэтому считается, что он выражает их наиболее явно, делая доступным любому программисту без применения специфических конструкций языка, которые не относятся к алгоритмической теории. Так, например, Деревья и другие рекурсивные типы данных могут быть объявлены и использованы без применения указателей (в отличие, например, от C/C++)

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

Полиморфизм типов (Milner, 1978) позволяет определять функции, не используя явного указания типа: тип возвращаемого значения (или аргументов) будет зависеть от контекста вызова этой функции. Одна и та же функция может быть использована для того, чтобы развернуть список целых чисел и список строк, например.

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

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

Применение Standard ML

Обучение

Standard ML применяется для обучения бакалавров и магистров Информатики в таких крупных университетах, как: University of Edinburgh, University of Cambridge, Carnegie Mellon University, University of Princeton, University of Copenhagen и пр.

Исследования

Standard ML используется как инструмент в исследовании доказательства теорем, технологии компиляторов и программного анализа. Например, HOL Theorem Prover (Логика Высших Порядков), разработанный в Cambridge University, написан на Standard ML.

Другие способы применения

Было подсчитано, что в University of Copenhagen в реальных проектах используется около 100 000 строк кода, написанного для веб-приложений для студентов и персонала. В числе этих приложений, например, система кадров универститета, электронный кабинет студента, приложение для администрирования проектных разработок студентов.

Технология компиляции

Несколько десятков лет исследований и разработок потребовались для получения устойчивой технологии компиляции для Standard ML. В итоге, сейчас мы имеем широкий набор компиляторов для выбора. Среди них такие, как Standard ML of New Jersey, Moscow ML, MLWorks, SML.NET, SML Server, Ml Kit и многие другие.

Типы

Проверка типов

В компиляторе для Standard ML содержится компонент для проверки типов, который проверяет, возможно ли для данной программы такое применение правил преобразования типов, которое приведет к успешной компиляции. Для приведения типов компонент использует правила унификации типов, и работает по алгоритму, разработанному Милнером в 1982 г.

Как и во многих других языках, в ML доступны базовые типы. В данном случае это int, real, string, boolean. Из них можно строить более сложные конструкции – кортежи (tuples), списки (lists), функции и структуры (records). Кроме того, программист также может задать и свой базовый тип. Посмотрим примеры создания структур данных из базовых типов на примере кортежей.

(2,"Andrew")    : int * string
(true,3.5,"x")  : bool * real * string
((4,2),(7,3))   : (int * int) * (int * int)

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

[1,2,3]                : int list
["Andrew","Ben"]       : string list
[(2,3),(2,2),(9,1)]    : (int * int) list
[[],[1],[1,2]]         : int list list

Необходимо помнить об этом различии: в языке ML конструкции (1, 2) и (1, 2, 3) являются кортежами разных типов, в то время, как [1, 2] и [1, 2, 3] – одинакового типа. В ML стоит быть осторожным и помнить о том, каких типов конструкции используются в программе. Тем не менее, на этапе изучения языка скорее всего большинство ошибок будут выявляться простой проверкой типов, которую совершает ML при преобразовании.

Технология Pattern Matching

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

- val (d,e) = (2,"two");
val d = 2 : int
val e = "two" : string
- val [one,two,three] = [1,2,3];
std_in:0.0-0.0 Warning: binding not exhaustive
                one :: two :: three :: nil = ...
val one = 1 : int
val two = 2 : int
val three = 3 : int

Списки

Список – это крайне важная и необходимая структура данных. Списки в ML построены точно так же, как подобные в языке C или Pascal. Но для программирования они содержат существенное упрощение – нет больше необходимости задумываться об указателях, из которых список сформирован. Существует два типа конструкторов списка: конструктор пусого списка и cons-оператор ::. Пустой конструктор создает список, который не содержит ни одного элемента. Оператор cons принимает новый элемент списка слева от оператора и сам список справа, возвращая список с длиной на 1 больше изначального. Примеры:

nil                     []
1::nil                  [1]
2::(1::nil)             [2,1]
3::(2::(1::nil))        [3,2,1]

Кроме того, оператор cons является ассоциативным справа. Это значит, что нам не нужно ставить скобки. Можно просто написать 3::2::1::nil и получить список [3, 2, 1]. Стоит заметить, оператор используется строго между новым элементом списка слева и списком справа. Т.е. можно сказать, что оператор :: соединяет одиночный элемент с головой списка. Другой оператор, @, используется для конкатенации двух списков вместе. Частой ошибкой является путаница между одиночным элементом и списком с одним элеменом. Так, например, для получения списка, начинающегося с 4 и до 7, можно сделать так: 4::[5, 6, 7] или [4]@[5, 6. 7], но никак не наоборот.

::      : 'a * 'a list -> 'a list
nil     : 'a list

Для того, чтобы получить тот же список с 4 в конце мы также не можем сделать так: [5, 6, 7] :: 4, т.к. с левой стороны оператора cons всегда стоит одиночный элемент. Получается, можно сделать только вот так: [5, 6, 7]@[4].

Использование Pattern Matching и рекурсии

Введение

Для определения функции, которая работает со списком, используются два подхода

fun	lfun nil	= ...
|	lfun(h::t)	= ... lfun t ...;

Однако это не работает во всех случаях. Рассмотрим функцию last, которая возвращает последний элемент списка.

last [4,2,5,1] = 1
last ["sydney","beijeng","manchester"] = "manchester"

Оба паттерна не подходят под описание стандартной функции. Допустим, функция last получает на вход пустой список. Что такое последний элемент пустого списка? Этот вопрос порождает друглй: “А что вообще такое последний элемент пустого списка?”. Вместо того, чтобы возвратить список нулевой длины, что было бы неправильно, сделаем так, что минимальная длина списка = 1, Значит функция last может возвращать в таком случае только undefined, а конструкторы для списка написать начиная с 1 элемента. Это и есть применение паттерна [h], который матчится с любым списком, содержащим хотя бы 1 элемент.

fun	last [h] 	= h
|	last(h::t)	= last t;

Данная конструкция наглядно показывает два важных нововведения ML:

Неполная левая сторона

Если определить в Standard ML вышеуказанную функцию, получим следующие предупреждения: std_in:217.1-218.23 Warning: match non exhaustive

	h :: nil => ...
	h :: t => ...

Тем не менее, функция будет работать, а ML только лишь предупреждает нас о том, что эта функция не определена для всех значений: а именно не определена для значения nil. Выражение last nil все равно будет скомпилировано как верное (потому что следует правилам приведения типов), но у нас нет для него определения.

Пересекающаяся левая сторона

Так как паттерн [h] полностью удовлетворяет паттерн h:nil, мы можем дописать определение функции:

fun	last(h::nil) = h
|	last(h::t)   = last t;

Рассматривая паттерны в левой стороне выражений, заметим, что существует некоторое перекрытие между ними. Такое выражение, как 5:nil подойдет обоим паттернам: первому (связывая 5 с h) и второму (связывая 5 и h, nil и t). Очевидно, нам нужно первое связывание и, к счастью, ML так и поступит, т.к. важен порядок определения операторов. Это свойство встречается не первый раз в статье, почти все предыдущие примеры также имели перекрывающуюся левую часть.

Анонимные функции

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

fn <parameters> => <expression>

Например:

- fn x => 2*x;
> it = fn : int -> int
- it 14;
> 28 : int

Это может быть крайне полезно при определении функций высшего порядка (функций от функций), например с функцией map:

map (fn x=> 2*x) [2,3,4];

Исключения

Исключение можно бросить, использовав ключевое слово raise, а поймать используя конструкции pattern-matching с ключевым словом handle.

exception Undefined
  fun max [x] = x
    | max (x::xs) = let val m = max xs in if x > m then x else m end
    | max [] = raise Undefined
  fun main xs = let
     val msg = (Int.toString (max xs)) handle Undefined => "empty list...there is no max!"
    in
      print (msg ^ "\n")
    end

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

exception Zero
  fun listProd ns = let
     fun p [] = 1
      | p (0::_) = raise Zero
      | p (h::t) = h * p t
    in
      (p ns) handle Zero => 0
    end

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

Кодогенерация

Стандартный процесс компиляции в Standard ML – это генерация кода, который, будучи запущенным, возвращает результат, описанный последовательностью операций языка. Некоторые компиляторы генерируют байт-код, некоторые – нативный код. Большинство компиляторов выполняют тщательный анализ программы и трансформируют ее в целях увеличения производительности. В результате, получившийся оптимизированный код может соревноваться с тем, что у нас могло бы получиться, используй мы язык С. Все компиляторы Standard ML могут собирать программы в stand-alone пакеты. Такую программу можно запустить самостоятельно из командной строки или используя для этого веб-сервис.

Управление памятью во время работы программ

Все реализации Standard ML предлагают автоматическую очистку памяти. Причем SML New Jersey и Moscow ML используют для этого сборщик мусора, построенный на поколениях объектов. А, например, SML Server использует для этой цели статический анализ, который называется подстановкой регионов. (Tofte, Taplin, 1994), который предсказывает выделение памяти во время компиляции программы и вручную вставляет в генерируемую программу методы безопасной очистки этой памяти.

Раздельная компиляция, библиотеки, утилиты и инструменты

Для обеспечения работы с большими программами все компиляторы позволяют раздельно компилировать файлы исходного кода. Базовая библиотека Standard ML состоит из исчерпывающей коллекции модулей Standard ML. Они предоставляют программисту использование эффективной реализации стандартных структур данных и алгоритмов. Кроме того, в базовой библиотеке есть модули, отвечающие за особые опции ввода-вывода, за доступ к функциям операционной системы для того чтобы можно было программировать на системном уровне, используя Standard ML. Инструменты также включают в себя лексические анализаторы и парсеры.

История Standard ML

“ML” означает MetaLanguage – метаязык ML, предшественник Standard ML, разработанный Милнером и его коллегами из университета Эдинбурга в 1970-х как часть программы по доказательству теорем LCF. Влияние также оказали прикладные языки программирования, используемые для разработки искусственного интеллекта: Lisp, ISWIM, HOPE. В 1980-е и первую половину 90-х ML был интернациональным двигателем иссоелования в области языков программирования. Расширяя идеи языков HOPE и CLEAR, был предложен стандарт Standard ML как система модулей в 1984 году. Затем появились продвинутые компиляторы (1991), стандартная библиотека (2004), теория относительно преобразования типов (1994), формальное определение языка (1997). Дополнительная информация о становлении языка может быть найдена в стандарте языка от его создателя (Milner, 1997).

Примеры кода

Hello world

Код

 print "Hello world!\n";

Компиляция

$ mlton hello.sml

Результат

$ ./hello
  Hello world!

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

Вот так можно легко определить сортировку вставками в ML

 fun ins (n, []) = [n]
    | ins (n, ns as h::t) = if (n<h) then n::ns else h::(ins (n, t))
  val insertionSort = List.foldr ins []

Можно применить принцип полиморфизма и абстрагироваться от оператора упорядочивания <<

 fun ins' << (num, nums) = let
     fun i (n, []) = [n]
      | i (n, ns as h::t) = if <<(n,h) then n::ns else h::i(n,t)
    in
      i (num, nums)
    end
   fun insertionSort' << = List.foldr (ins' <<) []

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

Быстрая сортировка реализуется вот так. Применен шаблонный оператор <<

  fun quicksort << xs = let
     fun qs [] = []
       | qs [x] = [x]
      | qs (p::xs) = let
          val (less, more) = List.partition (fn x => << (x, p)) xs
          in
            qs less @ p :: qs more
          end
     in
       qs xs
     end

Узнать больше

• Standard ML language
• Functional Programming Languages