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