# Alice ML (programming language)

Paradigm functional Programming Systems Lab, Saarland University 2000 strong, static, inferred crossplatform alice

Alice ML is a programming language designed by the Programming Systems Lab at Saarland University, Saarbrücken, Germany. Alice ML is a dialect of Standard ML, augmented with support for lazy evaluation, concurrency and constraint programming.

## Overview

Alice provides concurrency features as part of the base language through the use of a “future” type that represents a value being provided by an independent thread of execution. A thread that uses a future value will block on an attempt to access the value until the thread performing it has completed the computation. A related concept is also provided known as a "promise", allowing a thread to provide a future value that it will compute to another thread. Future and promise typed variables are used to implement data-flow synchronization.

Alice also provides facilities to allow programmers to use a lazy evaluation strategy in their programs versus the traditional eager evaluation strategy that Standard ML takes. But unlike the Haskell, which adopts the lazy model by default, Alice adopts an eager evaluation model by default, requiring the programmer to explicitly state that a computation is to be evaluated lazily/

The Alice implementation from Saarland University uses the SEAM (Simple Extensible Abstract Machine) virtual machine. Alice is features just-in-time compilation to bytecode as well as native code for the x86 architecture. It is free software.

## Language

Alice ML implements Standard ML features. Programs written in Standard ML consist of expressions to be evaluated, as opposed to statements or commands, although some expressions return a trivial "unit" value and are only evaluated for their side-effects.

Like all functional programming languages, a key feature of Alice ML is the function, which is used for abstraction. For instance, the factorial function can be expressed as:

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


A compiler is required to infer the static type int -> int of this function without user-supplied type annotations. I.e., it has to deduce that n is only used with integer expressions, and must therefore itself be an integer, and that all value-producing expressions within the function return integers.

The same function can be expressed with clausal function definitions where the if-then-else conditional is replaced by a sequence of templates of the factorial function evaluated for specific values, separated by '|', which are tried one by one in the order written until a match is found:

 fun factorial 0 = 1
| factorial n = n * factorial (n - 1)


This can be rewritten using a case statement like this:

 val rec factorial =
fn n => case n of 0 => 1
| n => n * factorial (n - 1)


or as a lambda function:

 val rec factorial = fn 0 => 1 | n => n * factorial(n -1)


Here, the keyword val introduces a binding of an identifier to a value, fn introduces the definition of an anonymous function, and case introduces a sequence of patterns and corresponding expressions.

Using a local function, this function can be rewritten in a more efficient tail recursive style.

 fun factorial n = let
fun lp (0, acc) = acc
| lp (m, acc) = lp (m-1, m*acc)
in
lp (n, 1)
end


(The value of a let-expression is that of the expression between in and end.) The encapsulation of an invariant-preserving tail-recursive tight loop with one or more accumulator parameters inside an invariant-free outer function.

### Type synonyms

A type synonym is defined with the type keyword. Here is a type synonym for points in the plane, and functions computing the distances between two points, and the area of a triangle with the given corners as per Heron's formula.

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


### Algebraic datatypes and pattern matching

ML provides strong support for algebraic datatypes. An ML datatype can be thought of as a disjoint union of tuples.

A datatype is defined with the datatype keyword, as in


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 *)


Note: datatypes, not type synonyms, are necessary to define recursive constructors. (This is not at issue in the present example.)

Order matters in pattern matching; patterns that are textually first are tried first. Pattern matching can be syntactically embedded in function definitions as follows:


fun area (Circle (_, r)) = 3.14 * r * r
| area (Square (_, s)) = s * s
| area (Triangle (a, b, c)) = heron (a, b, c)


Note that subcomponents whose values are not needed in a particular computation are ellided with underscores, or so-called wildcard patterns.

The so-called "clausal form" style function definition, where patterns appear immediately after the function name, is merely syntactic sugar for

fun area shape =
case shape
of Circle (_, r) => 3.14 * r * r
| Square (_, s) => s * s
| Triangle (a, b, c) => heron (a, b, c)


Pattern exhaustiveness checking will make sure each case of the datatype has been accounted for, and will produce a warning if not. The following pattern is inexhaustive:


fun center (Circle (c, _)) = c
| center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)


There is no pattern for the Triangle case in the center function. The compiler will issue a warning that the pattern is inexhaustive, and if, at runtime, a Triangle is passed to this function, the exception Match will be raised.

The set of clauses in the following function definition is exhaustive and not redundant:


fun hasCorners (Circle _) = false
| hasCorners _ = true


If control gets past the first pattern (the Circle), we know the value must be either a Square or a Triangle. In either of those cases, we know the shape has corners, so we can return true without discriminating which case we are in.

The pattern in second clause the following (meaningless) function is redundant:

 fun f (Circle ((x, y), r)) = x+y
| f (Circle _) = 1.0
| f _ = 0.0


Any value that matches the pattern in the second clause will also match the pattern in the first clause, so the second clause is unreachable. Therefore, this definition as a whole exhibits redundancy, and causes a compile-time warning.

### Higher-order functions

Functions can consume functions as arguments:


fun applyToBoth f x y = (f x, f y)


Functions can produce functions as return values:


fun constantFn k = let
fun const anything = k
in
const
end


(alternatively)


fun constantFn k = (fn anything => k)


Functions can also both consume and produce functions:

 fun compose (f, g) = let
fun h x = f (g x)
in
h
end


(alternatively)


fun compose (f, g) = (fn x => f (g x))


The function List.map from the basis library is one of the most commonly used higher-order functions in Standard ML:


fun map _ [] = []
| map f (x::xs) = f x  :: map f xs


(A more efficient implementation of map would define a tail-recursive inner loop as follows:)


fun map f xs = let
fun m ([], acc) = List.rev acc
| m (x::xs, acc) = m (xs, f x  :: acc)
in
m (xs, [])
end


### Exceptions

Exceptions are raised with the raise keyword, and handled with pattern matching handle constructs.


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


The exception system can be exploited to implement non-local exit, an optimization technique suitable for functions like the following.

 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


When the exception Zero is raised in the 0 case, control leaves the function p altogether. Consider the alternative: the value 0 would be returned to the most recent awaiting frame, it would be multiplied by the local value of h, the resulting value (inevitably 0) would be returned in turn to the next awaiting frame, and so on. The raising of the exception allows control to leapfrog directly over the entire chain of frames and avoid the associated computation. It has to be noted that the same optimization could have been obtained by using a tail recursion for this example.

### Module system

ML has an advanced module system, allowing programs to be decomposed into hierarchically organized structures of logically related type and value declarations. ML modules provide not only namespace control but also abstraction, in the sense that they allow programmers to define abstract data types.

Three main syntactic constructs comprise the ML module system: signatures, structures and functors. A structure is a module; it consists of a collection of types, exceptions, values and structures (called substructures) packaged together into a logical unit. A signature is an interface, usually thought of as a type for a structure: it specifies the names of all the entities provided by the structure as well as the arities of type components, the types of value components, and signatures for substructures. The definitions of type components may or may not be exported; type components whose definitions are hidden are abstract types. Finally, a functor is a function from structures to structures; that is, a functor accepts one or more arguments, which are usually structures of a given signature, and produces a structure as its result. Functors are used to implement generic data structures and algorithms.

For example, the signature for a queue data structure might be:


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


This signature describes a module that provides a parameterized type queue of queues, an exception called QueueError, and six values (five of which are functions) providing the basic operations on queues. One can now implement the queue data structure by writing a structure with this signature:


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


This definition declares that TwoListQueue is an implementation of the QUEUE signature. Furthermore, the opaque ascription (denoted by :>) states that any type components whose definitions are not provided in the signature (i.e., queue) should be treated as abstract, meaning that the definition of a queue as a pair of lists is not visible outside the module. The body of the structure provides bindings for all of the components listed in the signature.

To use a structure, one can access its type and value members using "dot notation". For instance, a queue of strings would have type string TwoListQueue.queue, the empty queue is TwoListQueue.empty, and to remove the first element from a queue called q one would write TwoListQueue.remove q.

## Extentions

Alice extends Standard ML with several primitives for lazy evaluation and concurrency. For example, threads may be created using the spawn keyword. Consider the naive algorithm for computing the Fibonacci numbers:

 fun fib 0 = 0
| fib 1 = 1
| fib n = fib(n-1) + fib(n-2);


For large values of n, fib n will take a long time to compute. This computation can be performed in a separate thread by

 val x = spawn fib n;


The variable x is now bound to a so-called "future". When an operation requires the actual value of x, it blocks until the thread is done with the computation. To exploit parallelism one could even define fib as follows:

 fun fib 0 = 0
| fib 1 = 1
| fib n = spawn fib(n-1) + fib(n-2);


A lazy expression immediately evaluates to a lazy future of the result of exp. As soon as a thread requests the future, the computation is initiated in a new thread. The lazy future is replaced by a concurrent future and evaluation proceeds similar to spawn.

fun lazy mapz f   []    = nil
| mapz f (x::xs) = f x :: mapz f xs


(alternatively)

fun mapz f xs = lazy (case xs of
[]   => nil
| x::xs => f x :: mapz f xs)