The Adl Language

Adl is a small strict functional language designed to support data parallelism. The purely functional nature of Adl ensures that BMF code produced from Adl source can be manipulated as a mathematical expression.

A small number of built-in higher-order combinators are provided. These include map, reduce, and scan and variants on these to cater for reductions and scans with no base value.

The scan operators have been provided as primitive, in spite of it being possible to define these in terms of list-homomorphisms. The reason for this decision is that a more efficient parallel implementation of scan exists than that furnished by the list homomorphism.

In addition to the list processing primitives Adl provides the two standard constructs of if and while. if caters for conditional evaluation of an expression. while is supplied as an iterator to be used in cases where computation is not bounded by the length of an input list.

The current version of Adl is non-recursive. The lack of recursion is convenient from the point of view of the language implementors since it allows all function calls to be in-lined and translated into composed sequences of functions in BMF. In the small number of Adl applications tested so far the lack of recursion has not caused us great difficulty, but further experiments on language expressiveness are underway.

Data Types

Adl contains three scalar data types: booleans, reals and integers. There are two type constructors: tuples and vectors. Tuples are used to group data of different types. Functions requiring more than one value will have their arguments grouped together in a single tuple. Thus all user-defined Adl functions are unary. This feature serves to simplify analysis later in the compilation process.

Vectors are groupings of elements of the same type; they are mapped by the compiler into BMF concatenate lists. In Adl there are only two means of creating vectors, the first is literal specification where the vector is written as constant e.g. [true,false,true,true]. The second is by the iota primitive which when given an integer argument n it creates the integer vector: [0,...,n-1]. This vector can be used to index another, or be directly transformed via the list-primitives. Two other vector operators are length, # and the infix operator for indexing, !. Vector indices always start at 0. Adl also possesses a number of primitives for arithmetic, type conversion, boolean logic and specific mathematical operations. All of these operate over the scalar data types.

An Example Adl program

Adl, through its map, reduce, and scan functions, is designed, primarily, for the efficient application of operations over its vector data type. This example takes two vectors as input and adds the first one to the reverse of the second one.
 add_rev(a:vof int,b:vof int) :=
     lb1 := #b-1;
     f x := a!x + b!(lb1-x);
     map (f,iota #a)

The main function must have the types of its input values declared. All other functions may, at the option of the programmer, have their types inferred by the compiler. If a function is used with more than one set of concrete types, separate instances of its definition are created by the type-checker. Access to elements of tuples is through pattern matching on the formal parameter of the function declaration.

In this program, access to elements of both lists is via vector indices drawn from the call iota #a. The elements of the second list are indexed in reverse-order. The result is a vector, the same length as a, containing the sums of the elements pointed to by the indices.

Return to Adl project page