Alice ML (programming language)
This page was last modified on 21 May 2016, at 23:48.
|Designed by||Programming Systems Lab, Saarland University|
|Typing discipline||strong, static, inferred|
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.
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.
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.
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.
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
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
fun compose (f, g) = (fn x => f (g x))
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 are raised with the
raise keyword, and handled with pattern matching
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.
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
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
fib n will take a long time to compute. This computation can be performed in a separate thread by
val x = spawn fib n;
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
fun mapz f xs = lazy (case xs of  => nil | x::xs => f x :: mapz f xs)