A Conflict Between Call-by-need Computation and Parallelism

Kennaway, J. Richard (1994) A Conflict Between Call-by-need Computation and Parallelism. In: Conditional and Typed Rewriting Systems. Lecture Notes in Computer Science, 968 . Springer Berlin / Heidelberg, ISR, pp. 247-261.

Full text not available from this repository. (Request a copy)

Abstract

In functional language implementation, there is a folklore belief that there is a conflict between implementing call-by-need semantics and parallel evaluation. In this note we illustrate this by proving that reduction algorithms of a certain general and commonly used form which give call-by-need semantics offer very little parallelism. The analysis of lazy pattern-matching which leads to the above result also suggests an efficient sequential algorithm for the evaluation of a class functional programs satisfying certain constraints, an algorithm which respects the mathematical semantics of the program considered as a term rewrite system.

Item Type:	Book Section
Faculty \ School:	Faculty of Science > School of Computing Sciences
Depositing User:	EPrints Services
Date Deposited:	01 Oct 2010 13:42
Last Modified:	24 Oct 2022 00:03
URI:	https://ueaeprints.uea.ac.uk/id/eprint/3916
DOI:	10.1007/3-540-60381-6_15

Actions (login required)

View Item