A Conflict Between Call-by-need Computation and Parallelism

J. Richard Kennaway

doi:10.1007/3-540-60381-6_15

A Conflict Between Call-by-need Computation and Parallelism

J. Richard Kennaway

School of Computing Sciences

Research output: Chapter in Book/Report/Conference proceeding › Chapter

14 Citations (Scopus)

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.

Original language	English
Title of host publication	Conditional and Typed Rewriting Systems
Editors	Nachum Dershowitz, Naomi Lindenstrauss
Publisher	Springer Berlin / Heidelberg
Pages	247-261
Number of pages	15
Volume	968
DOIs	https://doi.org/10.1007/3-540-60381-6_15
Publication status	Published - 1994
Event	Workshop on Conditional and Typed Rewriting Systems: 4th International Workshop - Jerusalem, Israel Duration: 13 Jul 1994 → 15 Jul 1994

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin / Heidelberg

Workshop

Workshop	Workshop on Conditional and Typed Rewriting Systems
Country/Territory	Israel
City	Jerusalem
Period	13/07/94 → 15/07/94

Access to Document

10.1007/3-540-60381-6_15

Cite this

@inbook{aaef562ad8fe4155825cc2a562296cf5,

title = "A Conflict Between Call-by-need Computation and Parallelism",

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.",

author = "Kennaway, \{J. Richard\}",

year = "1994",

doi = "10.1007/3-540-60381-6\_15",

language = "English",

volume = "968",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin / Heidelberg",

pages = "247--261",

editor = "Nachum Dershowitz and Naomi Lindenstrauss",

booktitle = "Conditional and Typed Rewriting Systems",

note = "Workshop on Conditional and Typed Rewriting Systems : 4th International Workshop ; Conference date: 13-07-1994 Through 15-07-1994",

}

Kennaway, JR 1994, A Conflict Between Call-by-need Computation and Parallelism. in N Dershowitz & N Lindenstrauss (eds), Conditional and Typed Rewriting Systems. vol. 968, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, pp. 247-261, Workshop on Conditional and Typed Rewriting Systems, Jerusalem, Israel, 13/07/94. https://doi.org/10.1007/3-540-60381-6_15

TY - CHAP

T1 - A Conflict Between Call-by-need Computation and Parallelism

AU - Kennaway, J. Richard

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-60381-6_15

DO - 10.1007/3-540-60381-6_15

M3 - Chapter

VL - 968

T3 - Lecture Notes in Computer Science

SP - 247

EP - 261

BT - Conditional and Typed Rewriting Systems

A2 - Dershowitz, Nachum

A2 - Lindenstrauss, Naomi

PB - Springer Berlin / Heidelberg

T2 - Workshop on Conditional and Typed Rewriting Systems

Y2 - 13 July 1994 through 15 July 1994

ER -