Nondeterministic call by need is neither lazy nor by name
William Clinger · 1982
This paper offers a definition of nondeterministic call by need and gives two alternative call by need power domain semantics for a language with McCarthy's ambiguous operator amb. amb is one of the earliest and most interesting nondeterministic programming language constructs [9]. The value of (amb E1 E2) is ambiguously the value of E1 or the value of E2, with one important qualification: if the value of E1 is undefined then the value of (amb E1 E2) is the value of E2, and vice versa. For example the parallel or of E1 and E2 can be written as(amb (if E1 true E2)(if E2 true E1)),showing the usefulness of amb even for writing deterministic expressions.