Lenient evaluation and parallelism

In a companion paper (Tremblay G. Lenient evaluation is neither strict nor lazy. Computer languages 2000;26:43-66.), we showed that non-strict functio nal languages were not necessarily lazy. More precisely, non-strict functio nal languages can be divided into lenient and lazy languages, both types al lowing program constructions not directly available in strict functional la nguages. In this paper, we present parallel models of three evaluation stra tegies (strict, lenient, and lazy), along with an examination of the impact of these evaluation strategies on the implicit parallelism that can be ext racted from programs. These formal semantics, expressed using a parallel no tation (pi -calculus), make it possible to show why lenient evaluation can be seen as more naturally parallel. (C) 2000 Elsevier Science Ltd. All righ ts reserved.