Lambda the Ultimate

Generalized Committed Choice by Joxan Jaffar

As this paper reminded me, software transactional memory (STM) also belongs to this company of constructs.

Oz has a whole family of delaying constructs. Most of the constructs in other logic languages can be mapped to Oz in a straightforward way. Here is a brief summary of the family of constructs that 'choose' between alternatives:

• case: wait until a value matches a pattern (deterministic)
• or: logical disjunction without backtracking, waits until all guards fail except one (deterministic)
• cond: nondeterministic choice among guarded clauses (like committed-choice languages), waits until at least one guard succeeds and then commits to a successful guard (a.k.a. 'don't care' nondeterminism)
• choice: creates a choice point that allows trying all clauses, should not be confused with or or cond (a.k.a. 'don't know' nondeterminism)

(There are two others, dis which gives Andorra-style choice, and condis which does constructive disjunction, but they are deprecated.) This family can be combined with another family, the primitive dataflow operations 'Wait' and 'WaitNeeded', to get more flexible control:

• {Wait X}: wait until argument X is bound
• {WaitNeeded X}: wait until another thread 'needs X', i.e., does an explicit or implicit '{Wait X}' (this is the basis for lazy execution)

For more information, there are several sources: this message and its thread, chapter 12 of the Oz tutorial, and of course, CTM (especially chapters 9 and 12). You can also read Christian Schulte's dissertation to learn all about how these constructs are implemented (using computation spaces). For example, the or, cond, and choice constructs implement deep guards, in which arbitrary computations are allowed inside guards. Computation spaces give a clear and simple way to implement deep guards.