A Conflict Between Call-by-need Computation and Parallelism

Research output: Chapter in Book/Report/Conference proceedingChapter

13 Citations (Scopus)


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 languageEnglish
Title of host publicationConditional and Typed Rewriting Systems
EditorsNachum Dershowitz, Naomi Lindenstrauss
PublisherSpringer Berlin / Heidelberg
Number of pages15
Publication statusPublished - 1994
EventWorkshop on Conditional and Typed Rewriting Systems: 4th International Workshop - Jerusalem, Israel
Duration: 13 Jul 199415 Jul 1994

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg


WorkshopWorkshop on Conditional and Typed Rewriting Systems

Cite this