Technical reports

Implementing aggregates in parallel functional languages

T.J.W. Clarke

August 1989, 13 pages

DOI: 10.48456/tr-176

Abstract

Many constructions which are difficult to write efficiently in pure functional languages have as underlying semantics an aggregate. An aggregate is a collection of individual elements whose order does not matter, it can thus be constructed functionally using a commutative associative combining operator. Equivalent and more efficient implementations for aggregates exist which are operational. A new construction, the A-thread, an aggregate specified operationally which introduces provably local data indeterminacy, is defined. Operational specification of an aggregate, in which each element is specified by a separate function call, does not necessarily destroy referential transparency in a functional language. Aggregates defined using joins on partial orders allow early termination if an operational implementation is used: Arvind’s ‘I-structures’ and Burton’s ‘improving values’ are examples of this.

Full text

PDF (1.0 MB)

BibTeX record

@TechReport{UCAM-CL-TR-176,
  author =	 {Clarke, T.J.W.},
  title = 	 {{Implementing aggregates in parallel functional languages}},
  year = 	 1989,
  month = 	 aug,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-176.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-176},
  number = 	 {UCAM-CL-TR-176}
}