Alice ML (язык программирования)
Последнее изменение этой страницы: 02:48, 22 мая 2016.
Парадигма | функциональный |
---|---|
Спроектировано | Programming Systems Lab, Saarland University |
Первый появившийся | 2000 |
Печать дисциплины | сильная, статическая |
OS | crossplatform |
Портал: | alice |
Alice ML - язык программирования, разработанный в лаборатории Programming Systems Lab в Саарском университете. Это диалект языка Standard ML, дополненный ленивыми вычислениями, конкурентностью (многопоточностью и распределёнными вычислениями на основе вызова удалённых процедур) и программированием в ограничениях.
Содержание
Обзор
Alice ML отличается от Standard ML тем, что расширяет его возможности. Alice позволяет использовать параллельные вычисления в рамках кода SML за счёт использования "будущего" типа, представляющего значение, которое будет вычислено независимым потоком. Поток будет блокирован при попытки использования будущего значения до тех пор, пока значение не будет вычислено. Данный принцип, известный как "обещание", позволяет потоку предоставить будущее значение, которое будет вычислено в другом потоке. Переменные будущего типа используются для синхронизации потоков информации.
Так же Alice позволяет использовать стратегию ленивых вычислений, однако по умолчанию используется стратегия своевременных вычислений, а ленивость выражений необходимо указывать явно. Это отличается от Haskell, который применяет ленивые вычисления по умолчанию.
Реализация Alice Саарского университета использует виртуальную машину SEAM (Simple Extensible Abstract Mashine). Она является свободным программным обеспечением и использует компиляцию «на лету» как в байт-код, так и в родной код для архитектуры x86.
Возможность вызова удалённых процедур в Alice зависит от виртуальной машины, потому что она использует непосредственную пересылку исполняемого кода с одного компьютера на другой.
Синтаксис
Alice ML реализует возможности Standard ML. Программа написанная на Standard ML состоит из выражений,заменяющих утверждения и команд. Иногда выражения возвращают тривиальное значение и вычисляются только ради побочных эффектов.
Как и во всех функциональных языках, ключевым элементом является функция, используемая как абстракция. Например функция, вычисляющая факториал может быть задана так:
fun factorial n =
if n = 0 then 1 else n * factorial (n-1)
Компилятору нужно сделать вывод о типе функции int -> int без пользовательских аннотаций. Это означает, что он сделает вывод на основе того, что n используются только с целочисленными выражениями и все возвращаемые ей значения будут целочисленными.
Эта же функция может быть записана в клаузальной форме, что означает, что условное выражение if-then-else заменяется последовательностью шаблонов, разделённых '|' и определяющих, как вычислять факториал при различных значениях. Эти шаблоны будут последовательно сравниваться, пока не найдётся подходящий.
fun factorial 0 = 1
| factorial n = n * factorial (n - 1)
С использованием выражения выбор это можно записать так:
val rec factorial =
fn n => case n of 0 => 1
| n => n * factorial (n - 1)
А при помощи лямбда-функции так:
val rec factorial = fn 0 => 1 | n => n * factorial(n -1)
Ключевое слово val
осуществляет привязку идентификатора к значению, fn
предшествует анонимной функции, а case
предшествует последовательности шаблонов и соответствующих выражений.
Для повышения эффективности можно использовать хвостовую рекурсию, введя для этого локальную функцию.
fun factorial n = let
fun lp (0, acc) = acc
| lp (m, acc) = lp (m-1, m*acc)
in
lp (n, 1)
end
Синонимы типов данных
Синонимы типов данных определяются при помощи ключевого слова type. В приведённом примере используется синоним типа данных для точек плоскости и функции для вычисления расстояния между точками и для вычисления площади треугольника по формуле Герона.
type loc = real * real
fun dist ((x0, y0), (x1, y1)) = let
val dx = x1 - x0
val dy = y1 - y0
in
Math.sqrt (dx * dx + dy * dy)
end
fun heron (a, b, c) = let
val ab = dist (a, b)
val bc = dist (b, c)
val ac = dist (a, c)
val perim = ab + bc + ac
val s = perim / 2.0
in
Math.sqrt (s * (s - ab) * (s - bc) * (s - ac))
end
Составные типы данных и шаблоны
ML поддерживает составные типы данных. Любой тип данных в ML может быть представлен в виде не пересекающегося объединения кортежей.
Пример:
type loc = real * real
datatype shape
= Circle of loc * real (* center and radius *)
| Square of loc * real (* upper-left corner and side length; axis-aligned *)
| Triangle of loc * loc * loc (* corners *)
Замечание: для datatypes
, в отличии от type
может потребоваться задать конструктор.
Для шаблонов важен порядок задания, именно в этом порядке они будут проверяться.
fun area (Circle (_, r)) = 3.14 * r * r
| area (Square (_, s)) = s * s
| area (Triangle (a, b, c)) = heron (a, b, c)
В примере компоненты, которые не требуются для вычисления опущены при помощи _.
Клаузальной формой называется стиль функции, в которой шаблоны используются сразу после имени.
fun area shape =
case shape
of Circle (_, r) => 3.14 * r * r
| Square (_, s) => s * s
| Triangle (a, b, c) => heron (a, b, c)
Проверка шаблонов на исчерпанность позволяет проверить, что любой случай будет обработан. В приведённом примере шаблон не является исчерпывающим.
fun center (Circle (c, _)) = c
| center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)
Шаблон для Triangle не задан. Компилятор предупредит, что шаблон не исчерпывающий, а если во время выполнения в функцию будет передан Triangle то возникнет исключение Match.
В следующем примере шаблон исчерпывающий и не избыточный
fun hasCorners (Circle _) = false
| hasCorners _ = true
Если первый шаблон Circle не подойдёт, то известно, что параметр будет Square или Triangle.
В этом примере второй шаблон избыточен, ибо всё, что соответствует ему будет соответствовать первому.
fun f (Circle ((x, y), r)) = x+y
| f (Circle _) = 1.0
| f _ = 0.0
Объявление избыточных шаблонов тоже приведёт к предупреждению при компиляции.
Функции высших порядков
Функции могут принимать другие функции в качестве параметров:
fun applyToBoth f x y = (f x, f y)
Функции могут создавать другие функции и возвращать их:
fun constantFn k = let
fun const anything = k
in
const
end
(альтернативный вариант)
fun constantFn k = (fn anything => k)
Так же функции могут создавать новые функции из полученных:
fun compose (f, g) = let
fun h x = f (g x)
in
h
end
(альтернативный вариант)
fun compose (f, g) = (fn x => f (g x))
Функция List.map
из базовой библиотеки является самой используемой функцией высшего порядка.
fun map _ [] = []
| map f (x::xs) = f x :: map f xs
(Более эффективное использование map
должно использовать хвостовую рекурсию)
fun map f xs = let
fun m ([], acc) = List.rev acc
| m (x::xs, acc) = m (xs, f x :: acc)
in
m (xs, [])
end
Исключения
Для вызова исключения используется ключевое слово raise
. Обработка производится после ключевого слова 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
завершат выполнение. Это исключение позволяет перескочить через цепочку вызова функций и избежать лишних вычислений. Такая же оптимизация может быть достигнута при помощи хвостовой рекурсии.
Модульная система
Модульная система в ML довольно развита, что позволяет разработчику декомпозировать программы в иерархию организованных структур, состоящих из логически согласованных типов и значений. Помимо контроля за пространствами имён модули позволяют создавать слои абстракции.
Три основных компонента модульной системы: signature
, structure
и functor
.
structure
задаёт сам модуль, состоящий из набора типов, исключений, значений и других структур.
signature
является интерфейсом модуля. Она определяет имена и арности и типы компонентов и сигнатуры структур. Определения типов компонентов может экспортироваться. Компоненты, определение которых скрыто считаются абстрактными.
functor
функция, принимающая структуру или возвращающая структуру. Функторы используются для реализации составных типов данных и алгоритмов.
Пример: сигнатура очереди
signature QUEUE =
sig
type 'a queue
exception QueueError
val empty : 'a queue
val isEmpty : 'a queue -> bool
val singleton : 'a -> 'a queue
val insert : 'a * 'a queue -> 'a queue
val peek : 'a queue -> 'a
val remove : 'a queue -> 'a * 'a queue
end
Пример структуры, реализующей данную сигнатуру:
structure TwoListQueue :> QUEUE =
struct
type 'a queue = 'a list * 'a list
exception QueueError val empty = ([],[]) fun isEmpty ([],[]) = true
| isEmpty _ = false fun singleton a = ([], [a]) fun insert (a, ([], [])) = ([], [a])
| insert (a, (ins, outs)) = (a::ins, outs) fun peek (_,[]) = raise QueueError
| peek (ins, a::outs) = a fun remove (_,[]) = raise QueueError
| remove (ins, [a]) = (a, ([], rev ins))
| remove (ins, a::outs) = (a, (ins,outs)) end
Соответствие сигнатуре задаётся символом:>
. Тело структуры обеспечивает привязку компонентов к сигнатуре.
Для использования структуры используется точечная нотация. Очередь строк будет задаваться так:string TwoListQueue.queue
, пустая очередь так: TwoListQueue.empty
, а для удаления первого элемента в очереди q
нужно будет вызвать TwoListQueue.remove q
.
Расширение
Alice расширяет Standard ML несколькими примитивами для ленивых вычислений и распараллеливания.
Создание потока производится ключевым словом spawn
.
Обычный алгоритм для вычисления числа Фибоначчи:
fun fib 0 = 0
| fib 1 = 1
| fib n = fib(n-1) + fib(n-2);
Для больших значений n вычисления могут происходить долго, следующий код позволяет провести вычисления в отдельном потоке:
val x = spawn fib n;
Переменная x
теперь имеет будущий тип. Когда потребуется её значение поток будет блокирован, пока вычисления не завершатся. Распараллелить алгоритм можно следующим образом:
fun fib 0 = 0
| fib 1 = 1
| fib n = spawn fib(n-1) + fib(n-2);
Ленивые выражения имеют будущий ленивый тип. Когда их значение потребуется будет создан отдельный поток, а тип изменится на будущий.
fun lazy mapz f [] = nil
| mapz f (x::xs) = f x :: mapz f xs
(альтернативный вариант)
fun mapz f xs = lazy (case xs of
[] => nil
| x::xs => f x :: mapz f xs)
ISSN 2542-0356
Следуй за Полисом
Оставайся в курсе последних событий
Лицензия
Если не указано иное, содержание этой страницы доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» 4.0, а примеры кода – по лицензии Apache 2.0. Подробнее см. Условия использования.