You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.

The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.

For the reports in this repository we specifically note that

  • the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at
  • the use of articles under ACM copyright is governed by the ACM copyright policy (available at
  • technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
  • in other cases, please contact the copyright owner for detailed information

By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.

If you are in doubt, feel free to contact

The Data Field Model



Björn Lisper, Per Hammarlund


An earlier version of this report exists as report TRITA-IT 99:02, Dept of Teleinformatics, KTH.

Research group:

Publication Type:

Report - MRTC




Indexed data structures are prevalent in many programming applications. Collection-oriented languages provide means to operate directly on these structures, rather than having to loop or recurse through them. This style of programming will often yield clear and succinct programs. However, these programming languages will often provide only a limited choice of indexed data types and primitives, and the exact semantics of these primitives will sometimes vary with the data type and language.In this paper we develop a unifying semantical model for indexed data structures. The purpose is to support the construction of abstract data types and language features for such structures from first principles, such that they are largely generic over many kinds of data structures. The use of these abstract data types can make programs and their semantics less dependent of the actual data structure. This makes programs more portable across different architectures and facilitates the early design phase. The model is a generalisation of arrays, which we call data fields: these are functions with explicit information about their domains. This information can be conventional array bounds but it could also define other shapes, for instance sparse.Data fields can be interpreted as partial functions, and we define a metalanguage for partial functions. In this language we define abstract versions of collection-oriented operations, and we show a number of identities for them. This theory is used to guide the design of data fields and their operations so they correspond closely to the more abstract notion of partial functions. We define phi-abstraction, a lambda-like syntax for defining data fields in a shape-independent manner, and prove a theorem which relates phi-abstraction and lambda-abstraction semantically. We also define a small data field language whose semantics is given by formal data fields, and give examples of data field programming for parallel algorithms with arrays and sparse structures, database quering and computing, and specification of symbolic drawings.


author = {Bj{\"o}rn Lisper and Per Hammarlund},
title = {The Data Field Model},
note = {An earlier version of this report exists as report TRITA-IT 99:02, Dept of Teleinformatics, KTH. },
number = {ISSN 1404-3041 ISRN MDH-MRTC-42/2001-1-SE},
month = {June},
year = {2001},
url = {}