Alice (programming language)
Encyclopedia
Alice ML is a functional programming language designed by the Programming Systems Lab at Saarland University
. It is a dialect of Standard ML
, augmented with support for lazy evaluation
, concurrency
(multithreading
and distributed computing
via remote procedure call
s) and constraint programming
.
in a number of ways that distinguish it from its predecessor. 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. The Haskell
language is a functional language that also provides lazy evaluation. Alice adopts an eager evaluation model by default, requiring the programmer to explicitly state that a computation is to be evaluated lazily. This differs from Haskell, which adopts the lazy model by default.
The Alice implementation from Saarland University uses the SEAM (Simple Extensible Abstract Machine) virtual machine
. It is free software
, and features just-in-time compilation
to bytecode
as well as native code for the x86 architecture
.
Early versions of Alice ran on the Mozart/Oz
VM, allowing interfacing between Alice and Oz code.
Alice's remote procedure calling depends on the virtual machine, because it may actually send code to be computed from one computer to another.
. 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
val x = spawn fib n;
The variable
". When an operation requires the actual value of
fun fib 0 = 0
| fib 1 = 1
| fib n = spawn fib(n-1) + fib(n-2);
Saarland University
Saarland University is a university located in Saarbrücken, the capital of the German state of Saarland, and Homburg. It was founded in 1948 in Homburg in co-operation with France and is organized in 8 faculties that cover all major fields of science...
. It is a dialect of Standard ML
Standard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
, augmented with support for lazy evaluation
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
, concurrency
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
(multithreading
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
and distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
via remote procedure call
Remote procedure call
In computer science, a remote procedure call is an inter-process communication that allows a computer program to cause a subroutine or procedure to execute in another address space without the programmer explicitly coding the details for this remote interaction...
s) and constraint programming
Constraint programming
Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties...
.
Overview
Alice extends Standard MLStandard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
in a number of ways that distinguish it from its predecessor. Alice provides concurrency features as part of the base language through the use of a “future”
Future (programming)
In computer science, future, promise, and delay refer to constructs used for synchronization in some concurrent programming languages. They describe an object that acts as a proxy for a result that is initially not known, usually because the computation of its value has not yet completed.The term...
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
Future (programming)
In computer science, future, promise, and delay refer to constructs used for synchronization in some concurrent programming languages. They describe an object that acts as a proxy for a result that is initially not known, usually because the computation of its value has not yet completed.The term...
", 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
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
strategy in their programs versus the traditional eager evaluation
Eager evaluation
In computer programming, eager evaluation or greedy evaluation is the evaluation strategy in most traditional programming languages. In eager evaluation an expression is evaluated as soon as it gets bound to a variable. The term is typically used to contrast lazy evaluation, where expressions are...
strategy that Standard ML takes. The Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
language is a functional language that also provides lazy evaluation. Alice adopts an eager evaluation model by default, requiring the programmer to explicitly state that a computation is to be evaluated lazily. This differs from Haskell, which adopts the lazy model by default.
The Alice implementation from Saarland University uses the SEAM (Simple Extensible Abstract Machine) virtual machine
Virtual machine
A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...
. It is free software
Free software
Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
, and features just-in-time compilation
Just-in-time compilation
In computing, just-in-time compilation , also known as dynamic translation, is a method to improve the runtime performance of computer programs. Historically, computer programs had two modes of runtime operation, either interpreted or static compilation...
to bytecode
Bytecode
Bytecode, also known as p-code , is a term which has been used to denote various forms of instruction sets designed for efficient execution by a software interpreter as well as being suitable for further compilation into machine code...
as well as native code for the x86 architecture
X86 architecture
The term x86 refers to a family of instruction set architectures based on the Intel 8086 CPU. The 8086 was launched in 1978 as a fully 16-bit extension of Intel's 8-bit based 8080 microprocessor and also introduced segmentation to overcome the 16-bit addressing barrier of such designs...
.
Early versions of Alice ran on the Mozart/Oz
Mozart Programming System
The Mozart Programming System is a multiplatform implementation of the Oz programming language developed by an international group, the Mozart Consortium, which originally consisted of Saarland University, the Swedish Institute of Computer Science, and the Université catholique de Louvain.Mozart...
VM, allowing interfacing between Alice and Oz code.
Alice's remote procedure calling depends on the virtual machine, because it may actually send code to be computed from one computer to another.
Example
Alice extends Standard ML with several primitives for lazy evaluation and concurrency. For example, threads may be created using the spawn keywordKeyword (computer programming)
In computer programming, a keyword is a word or identifier that has a particular meaning to the programming language. The meaning of keywords — and, indeed, the meaning of the notion of keyword — differs widely from language to language....
. 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 byval x = spawn fib n;
The variable
x is now bound to a so-called "futureFuture (programming)
In computer science, future, promise, and delay refer to constructs used for synchronization in some concurrent programming languages. They describe an object that acts as a proxy for a result that is initially not known, usually because the computation of its value has not yet completed.The term...
". 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);