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 |