6.4 Encapsulation And Computation Spaces

In traditional LP and CP, new bindings and constraints appear and take effect globally. Oz supports a much more general idea: encapsulation. In Oz, the constraint store is an explicit 1st-class object and is called a computation space [SSW94] [SS94] [Sch97b] [Sch00]. A computation space is a place where computations run and their constraints are accumulated. Every computation (also called a thread) is situated: it takes place (is encapsulated) in a specific computation space. You can have multiple computation spaces, each with different computations and different constraints.

Oz also supports an even more powerful idea: computation spaces can be nested. Since a computation space is a 1st class object in Oz, it is possible for a thread running in space S1 to create a new computation space S2. In this case, S2 is situated, and therefore nested, in S1. The semantics of nested computation spaces requires that if S2 is nested in S1, then all basic constraints of S1 are inherited, i.e. visible, in S2. However, whenever a thread running in S2 tells a basic constraint, this only takes effect in S2 but does not affect its parent S1.

Furthermore, it is possible to ask whether the space S2 is failed (i.e. an inconsistency was derived), or entailed (i.e. all its basic constraints are also present in S1). Thus, by creating a nested space S2 to run a constraint C, and then by asking whether S2 is entailed or disentailed, you can discover whether a non-basic constraint C is entailed or contradicted. For example, the condition statement below is implemented in terms of this facility:

cond C then {P} else {Q} end

A new space S2 is created to run C, and the statement simply asks whether S2 is entailed or disentailed. The statement blocks until there is sufficient information to answer the question. Nested computation spaces are used in a similar fashion to implement the disjunctive propagator.

The fact that computation spaces are 1st class values makes it possible to program search in Oz itself (see next section) and also to write tools, like the Explorer [Sch97a] [Sch99], that allow you to interactively explore the search tree and inspect the state of the constraints at any node in this tree.

Denys Duchier
Version 1.2.0 (20010221)