<< Prev | - Up - | Next >> |

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.

<< Prev | - Up - | Next >> |

Denys Duchier

Version 1.2.0 (20010221)