Making choices lazily
John Hughes, Andrew Moran · 1995
We present a natural semantics that models the untyped, normal order -calculus plus McCarthy's amb in the context of call-by-need parameter passing. This results in a singular semantics for amb. Previous work on singular choice has concentrated on erratic choice, a less interesting nondeterministic choice operator, and only in relation to callby -value parameter passing, or call-by-name restricted to deterministic terms. The natural semantics contains rules for both convergent and divergent behaviour, allowing it to distinguish programs that dier only in their divergent behaviour. As a result, it is more discriminating than current domain-theoretic models. This, and the fact that it models singular amb, makes the natural semantics suitable for reasoning about lazy, functional languages containing McCarthy's amb. 1 Introduction The need for non-determinism in functional programming is apparent. There are parallel algorithms that are inherently non-deterministic, deterministic para...