Lenient evaluation and parallelism

In a companion paper, we showed that non-strict functional languages were not necessarily lazy. More precisely, non-strict functional languages can be divided into lenient and lazy languages, both types allowing program constructions not directly available in strict functional languages.

In this paper, we present a formal parallel model of three evaluation strategies (strict, lenient, and lazy), along with an examination of the impact of these evaluation strategies on the implicit parallelism that can be extracted from programs. This formal semantics, expressed using a parallel notation (pi-calculus), makes it possible to show why lenient evaluation can be seen as more naturally parallel.