ML

ML

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

ML (Meta Language) — семейство строгих языков функционального программирования с развитой параметрически полиморфной системой типов и параметризуемыми модулями. Подобная система типов была раньше предложена Роджером Хиндли в 1969 году и сейчас часто называется системой Хиндли-Милнера. Языки данного семейства не являются чистыми функциональными языками, так как включают и императивные инструкции. ML преподаётся во многих западных университетах (в некоторых даже как первый язык программирования).

Предпосылки

В 1963 году Джон Алан Робинсон реализовал метод автоматического доказательства теорем, получивший название «принцип резолюции». Идея этого метода принадлежит Эрбрану, и предложена в 1930 году. Робинсон разработал эффективный с вычислительной точки зрения алгоритм унификации, являющийся основой метода. Так появился язык ML^{[уточнить]}, созданный для автоматического доказательства теорем, но, как оказалось, пригодный и в качестве языка программирования общего назначения.

Особенности

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

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

Примеры

Вычисление факториала на ML:

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

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

type key = Key.ord_key
type item = Key.ord_key list
datatype set = LEAF | NODE of { key: key, lt: set, eq: set, gt: set }
val empty = LEAF
exception AlreadyPresent

fun member (_, LEAF) = false
  | member (h::t, NODE {key,lt,eq,gt}) =
      (case Key.compare (h, key) of
            EQUAL   => member(t, eq)
          | LESS    => member(h::t, lt)
          | GREATER => member(h::t, gt) )
  | member ([], NODE {key,lt,eq,gt}) =
      (case Key.compare (Key.sentinel, key) of
            EQUAL   => true
          | LESS    => member([], lt)
          | GREATER => member([], gt) )

fun insert(h::t, LEAF) = NODE { key=h, eq = insert(t, LEAF), lt=LEAF, gt=LEAF }
  | insert([], LEAF)   = NODE { key=Key.sentinel, eq=LEAF, lt=LEAF, gt=LEAF }
  | insert(h::t, NODE {key,lt,eq,gt}) =
      (case Key.compare (h, key) of
            EQUAL   => NODE {key=key, lt=lt, gt=gt, eq=insert(t, eq)}
          | LESS    => NODE {key=key, lt=insert(h::t, lt), gt=gt, eq=eq}
          | GREATER => NODE {key=key, lt=lt, gt=insert(h::t, gt), eq=eq} )
  | insert([], NODE {key,lt,eq,gt}) =
      (case Key.compare (Key.sentinel, key) of
            EQUAL   => raise AlreadyPresent
          | LESS    => NODE {key=key, lt=insert([], lt), gt=gt, eq=eq}
          | GREATER => NODE {key=key, lt=lt, gt=insert([], gt), eq=eq} )

fun add(l, n) = insert(l, n) handle AlreadyPresent => n

Для задачи поиска строки в словаре, троичное дерево поиска сочетает молниеносную скорость префиксных деревьев с экономичностью двоичных в отношении памяти. Реализация на ML отличается компактностью и самодокументируемостью за счёт использования алгебраических типов, сопоставления с образцом, правила «последнее выражение в исполнимой цепочке является результатом всей функции» и возможности строить объекты агрегатных типов без предварительных объявлений. Также она отличается доказанной корректностью — в частности, исключением утечек памяти, характерных для Си / С++; или риска допущения ошибок в исходном коде, приводящих к зацикливанию программы с лавинообразным поглощением памяти, характерных для динамически типизируемых языков.

Система типов Хиндли — Милнера обеспечивает языкам высокий потенциал к оптимизации, так что снижение трудоёмкости и повышение стабильности программ является «бесплатным» (без потери эффективности), при условии наличия оптимизирующего компилятора (таких как OCaml или MLton).

См. также

• Язык модулей ML

Ссылки

• [progopedia.ru/language/ml Статья ML] в Прогопедии — энциклопедии языков программирования (рус.)
• [hyperpolyglot.org/ml ML Dialects and Haskell: SML, OCaml, F#, Haskell] — сравнение ряда языков семейства ML

Отрывок, характеризующий ML

– Да ведь, сказывали, Малые Мытищи мамоновские казаки зажгли.
– Они! Нет, это не Мытищи, это дале.
– Глянь ка, точно в Москве.
Двое из людей сошли с крыльца, зашли за карету и присели на подножку.
– Это левей! Как же, Мытищи вон где, а это вовсе в другой стороне.
Несколько людей присоединились к первым.
– Вишь, полыхает, – сказал один, – это, господа, в Москве пожар: либо в Сущевской, либо в Рогожской.
Никто не ответил на это замечание. И довольно долго все эти люди молча смотрели на далекое разгоравшееся пламя нового пожара.
Старик, графский камердинер (как его называли), Данило Терентьич подошел к толпе и крикнул Мишку.
– Ты чего не видал, шалава… Граф спросит, а никого нет; иди платье собери.
– Да я только за водой бежал, – сказал Мишка.
– А вы как думаете, Данило Терентьич, ведь это будто в Москве зарево? – сказал один из лакеев.
Данило Терентьич ничего не отвечал, и долго опять все молчали. Зарево расходилось и колыхалось дальше и дальше.
– Помилуй бог!.. ветер да сушь… – опять сказал голос.
– Глянь ко, как пошло. О господи! аж галки видно. Господи, помилуй нас грешных!
– Потушат небось.
– Кому тушить то? – послышался голос Данилы Терентьича, молчавшего до сих пор. Голос его был спокоен и медлителен. – Москва и есть, братцы, – сказал он, – она матушка белока… – Голос его оборвался, и он вдруг старчески всхлипнул. И как будто только этого ждали все, чтобы понять то значение, которое имело для них это видневшееся зарево. Послышались вздохи, слова молитвы и всхлипывание старого графского камердинера.


Камердинер, вернувшись, доложил графу, что горит Москва. Граф надел халат и вышел посмотреть. С ним вместе вышла и не раздевавшаяся еще Соня, и madame Schoss. Наташа и графиня одни оставались в комнате. (Пети не было больше с семейством; он пошел вперед с своим полком, шедшим к Троице.)
Графиня заплакала, услыхавши весть о пожаре Москвы. Наташа, бледная, с остановившимися глазами, сидевшая под образами на лавке (на том самом месте, на которое она села приехавши), не обратила никакого внимания на слова отца. Она прислушивалась к неумолкаемому стону адъютанта, слышному через три дома.
– Ах, какой ужас! – сказала, со двора возвративись, иззябшая и испуганная Соня. – Я думаю, вся Москва сгорит, ужасное зарево! Наташа, посмотри теперь, отсюда из окошка видно, – сказала она сестре, видимо, желая чем нибудь развлечь ее. Но Наташа посмотрела на нее, как бы не понимая того, что у ней спрашивали, и опять уставилась глазами в угол печи. Наташа находилась в этом состоянии столбняка с нынешнего утра, с того самого времени, как Соня, к удивлению и досаде графини, непонятно для чего, нашла нужным объявить Наташе о ране князя Андрея и о его присутствии с ними в поезде. Графиня рассердилась на Соню, как она редко сердилась. Соня плакала и просила прощенья и теперь, как бы стараясь загладить свою вину, не переставая ухаживала за сестрой.
– Посмотри, Наташа, как ужасно горит, – сказала Соня.
– Что горит? – спросила Наташа. – Ах, да, Москва.
И как бы для того, чтобы не обидеть Сони отказом и отделаться от нее, она подвинула голову к окну, поглядела так, что, очевидно, не могла ничего видеть, и опять села в свое прежнее положение.
– Да ты не видела?
– Нет, право, я видела, – умоляющим о спокойствии голосом сказала она.
И графине и Соне понятно было, что Москва, пожар Москвы, что бы то ни было, конечно, не могло иметь значения для Наташи.
Граф опять пошел за перегородку и лег. Графиня подошла к Наташе, дотронулась перевернутой рукой до ее головы, как это она делала, когда дочь ее бывала больна, потом дотронулась до ее лба губами, как бы для того, чтобы узнать, есть ли жар, и поцеловала ее.
– Ты озябла. Ты вся дрожишь. Ты бы ложилась, – сказала она.
– Ложиться? Да, хорошо, я лягу. Я сейчас лягу, – сказала Наташа.
С тех пор как Наташе в нынешнее утро сказали о том, что князь Андрей тяжело ранен и едет с ними, она только в первую минуту много спрашивала о том, куда? как? опасно ли он ранен? и можно ли ей видеть его? Но после того как ей сказали, что видеть его ей нельзя, что он ранен тяжело, но что жизнь его не в опасности, она, очевидно, не поверив тому, что ей говорили, но убедившись, что сколько бы она ни говорила, ей будут отвечать одно и то же, перестала спрашивать и говорить. Всю дорогу с большими глазами, которые так знала и которых выражения так боялась графиня, Наташа сидела неподвижно в углу кареты и так же сидела теперь на лавке, на которую села. Что то она задумывала, что то она решала или уже решила в своем уме теперь, – это знала графиня, но что это такое было, она не знала, и это то страшило и мучило ее.
– Наташа, разденься, голубушка, ложись на мою постель. (Только графине одной была постелена постель на кровати; m me Schoss и обе барышни должны были спать на полу на сене.)
– Нет, мама, я лягу тут, на полу, – сердито сказала Наташа, подошла к окну и отворила его. Стон адъютанта из открытого окна послышался явственнее. Она высунула голову в сырой воздух ночи, и графиня видела, как тонкие плечи ее тряслись от рыданий и бились о раму. Наташа знала, что стонал не князь Андрей. Она знала, что князь Андрей лежал в той же связи, где они были, в другой избе через сени; но этот страшный неумолкавший стон заставил зарыдать ее. Графиня переглянулась с Соней.