Efficient Lazy Data-Structures on a Dataflow Machine

Abstract

Eager interpreters are able to exploit vast parallelism, yet lazy interpreters have more desirable termination properties. We propose lazy data-structures, an extension to the dataflow language Id, to support a combination of eager and lazy evaluation. We describe the semantics of lazy data-structures, as well as efficient implementation on the Tagged-Token Dataflow Architecture and the Monsoon Explicit Token Store Machine. We develop support for lazy data-structures in the language, the compiler, the run-time system, the interpreter, and the proposed hardware; and demonstrate the effectiveness of the construct as well as the limitations. Keywords: Dataflow, Evaluation order, Functional languages, Lazy evaluation, Parallel data-structures, Computer languages, Computer programming, Data processing.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1989
Accession Number
ADA209117

Entities

People

  • Steven K. Heller

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Biomedical
  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Alkanes
  • Computer Architecture
  • Computer Languages
  • Computer Programming
  • Computer Science
  • Computers
  • Computing System Architectures
  • Construction
  • Information Processing
  • Law
  • Military Research
  • Parallel Computing
  • Parallel Processing
  • Programming Languages
  • Simulations
  • Standards

Fields of Study

  • Computer science
  • Engineering

Readers

  • Parallel and Distributed Computing.