The authors examine how nondeterminism interacts with the various ways by which parameters can be passed to procedures. For example, the binding of a nondeterministic variable to a particular value can be forced at the time of a procedure call, so the variable has a fixed value within the procedure, or it can be left unresolved, so that different uses of the parameter can yield different results. The authors’ basic approach is to use sets to indicate the possible result values of a variable or operation and then map those values to single elements of the sets when the nondeterminism is removed. An algebraic semantics and a language for expressing it are defined, and soundness and completeness concerns are addressed.

People who are interested in the semantics of nondeterminism and have strong algebraic backgrounds are the intended audience. The paper is unlikely to be of much interest to language designers, because of the complexity of the algebras involved. Such people will probably want to avoid nondeterminism altogether, or, when this is not possible, bite the bullet and introduce explicit operations to associate nondeterministic references with their times of resolution. (This situation might arise when dealing with event streams routed over communication links among concurrent objects.) While the paper is useful from a mathematical point of view, it is not of general interest.