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 http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
- the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
- 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 webmaster@ide.mdh.se
The Data Field Model
Note:
An earlier version of this report exists as report
TRITA-IT 99:02, Dept of Teleinformatics, KTH.
Publication Type:
Report - MRTC
ISRN:
MDH-MRTC-42/2001-1-SE
Abstract
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.
Bibtex
@techreport{Lisper267,
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 = {http://www.es.mdu.se/publications/267-}
}
