Alice ML (язык программирования)

Alice ML

Парадигма	функциональный
Спроектировано	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)

Ссылки

• Оффицальный сайт
• Публикации, связанные с языком Alice