Last modified: Feb 13, 2019

To avoid spam, all mail addresses on this page have the "@" replaced by "#".

- Introduction
- Data Fields
- Data Field Haskell - A Haskell Dialect with Data Fields
- A Compiler for Data Field Haskell
- Code Examples
- Links

Many computing applications require indexed data structures, such as arrays, nested sequences, hash tables, or distributed data parallel entities. Collection-oriented languages offer a convenient way to specify computations over such structures, through operations which act directly on the structures rather than on the individual elements. Data Field Haskell is an attempt to extend Haskell with flexible and generic features for collection-oriented programming.

Data Field Haskell provides an instance of *data fields*. Data
fields generalize arrays: they are pairs *(f,b)* where *f* is a
function and *b* is a "bound", an entity which can be interpreted as a
predicate (or set). The bound could be two tuples of numbers defining the
extents of an array: however, the data field model allows also bounds
defining other "shapes" (for instance nested, sparse, and even for
nonnumerical indices). The model is designed not to make any undue
assumptions on the bounds: rather, it postulates some properties which are
necessary to make common collection-oriented operations well-defined. Thus,
bounds and data fields can be seen as abstract data types.

A data field can be applied to an index and thus defines a partial function
from index domain to value domain. Partial function are conveniently defined
through lambda-syntax, and a similar syntax is defined for data fields: just
as `\x->t` defines a function (using Haskell syntax for
lambda-expressions), the expression `forall x->t` defines a data
field. Here, the bound is not given explicitly but is instead derived from
the bounds in data fields appearing in `t` according to a set of
rules. Bounds correspond to function domains: thus, these rules are designed
to compute bounds for `forall`-expressions corresponding to the
function domains for the corresponding lambda-expressions. For instance,
`forall x->((f,b1)!x + (g,b2)!x)` obtains the bound `b1 `meet`
b2` since (assuming "`+`" is strict in both arguments) `\x->(f
x + g x)` is defined on the intersection of the domains of `f`
and `g`. (Here, "`!`" denotes data field application, and
"`meet`" an abstract operation on bounds which corresponds to set
intersection.) A number of rules of this kind can be defined. They make the
`forall`-syntax convenient for expressing many collection-oriented
algorithms with a minimum of explicit handling of bounds.

Data field bounds can be overapproximations of the domain of the corresponding partial function. Semantically, a particular error value represents the result of calls falling out of bounds. This value can be stored within a data field, which then represents a partial function with a domain strictly smaller than the set defined by its bound. This makes it possible to, e.g., to use data fields to model SIMD-like data parallel entities, which often are regular arrays where certain elements can be "turned off".

There is a theory for data fields that includes a formal calculus for
"`forall`-abstraction". The homepage
of the *Data Field Haskell* project contains a number of papers on the
topic.

Data Field Haskell is a Haskell dialect where the arrays have been
replaced with an instance of data fields. This particular instance provides
dense, "traditional" array-like data fields, sparse data fields, infinite
data fields, and multidimensional data fields which can be sparse in some
dimension, dense in some, and infinite in others. The type of data field is
determined by the type of bound, which can be finite dense (pair of
indices), finite sparse (set of indices), general predicate, which is
infinite, and *products* which are multidimensional bounds formed from
simpler bounds. There are also the special bounds `empty` and
`universe` which represent the empty and universal set, respectively.

Data Field Haskell provides a number of operations on data fields and
bounds. There are functions to create data fields and extract their bounds,
and to apply data fields to indices. For finite data fields there are two
more kinds of operations: *data field evaluators*, which force an
evaluation to various degree of all elements in data fields, and a number of
*folds* over data fields. There are also a number of operations on
bounds: `join` and `meet`, which correspond to union and
intersection of sets, *explicit restriction* of a data field with a
bound, a test for *finiteness*, an *enumeration* of the set
defined by a finite bound, the *size*, and a test whether an index
belongs to the set defined by a bound or not. However, the intention is that
a programmer should not have to use these operations explicitly that
often. Data Field Haskell provides `forall`-abstraction which works
as sketched above, and the idea is that a programmer, by using this
mechanism, could avoid much explicit handling of bounds. The syntax of
`forall`-abstraction is precisely analogous with the one of
lambda-abstraction and the typing is similar. For a concise description of
the data field extensions in Data Field Haskell, see here. A more detailed description is found here.

There was an experimental compiler, now since long gone, that was based on nhc13 release 980327. We have, however, kept the online documentation.

- Jonas Holmerin's masters thesis, Implementing Data Field Haskell, describing Data Field Haskell, and the implementation of the compiler.
- Online documentation

There used to be a FTP directory with simple code examples. This directory is now defunct. We may try to reconstruct the code examples in the future.

nhc98, the current version of nhc from York.

Björn Lisper, bjorn.lisper#mdh.se