Oz Language
SDxWiki

OK, I've become obsessed with the need to understand this language. Here's what I think I've understood so far.

The language encourages the use of threads. The thread system of the Mozart implementation claims to be phenomenally efficient and fast compared to traditional languages. Threads are preemptive and use round-robin scheduling, with three priority levels that control the CPU slice sizes.

Synchronization between threads is trivially easy because of the way that data is shared. Understanding this takes a little explaining.

Variables (any identifier starting with a capital letter) can be declared. These are not variables like we're used to, though; they're much more like variables in a mathematical notation.

If you just declare a variable, it starts out "free" (no value or type defined). You can also equate a variable to another variable, or to an expression involving variables. If you set a variable to a specific value, or to an expression that can be resolved to a specific value, then the variable is "determined" and has a specific type. (Oz variables are implicitly but strongly typed.) (There are other states a variable can be in, but these two will do for now.)

Variables exist in a "computation space" -- a global space shared by all threads, and local spaces nested inside that and inside each other. (Think "scope".)

Here I declare three variables in global space:

declare X Y=2 Z=X

X is free. Y is determined, value 2, type integer. Z is also free (because X is), but it now refers to the same "box" as X. This means that if X becomes determined, so does Z.

Now, here's the first wierd thing: A statement that refers to a free variable waits until that variable is determined. This is pretty wild. It means that if I create a thread that needs the value of X or Y, it will suspend until some other thread determines one of them. (Remember that the other will become determined at the same time.) Example:

local
  W   % Declares a new, free variable in a new local space.
in
  thread          % Start a new thread
    W = X+Y       % This suspends until X is determined
    {Browse W}    % This is a call to the browser to show the variable W.
  end
  {Browse W}      % This executes right away, and shows W as free in the browser.
end

Interesting to note here that the thread can see the local space containing W (Oz is generally lexically scoped), but nobody else can.

If you run this code in the Oz emulator system (which runs under Emacs, sorry), the second "Browse" call above will cause an Oz browser window to open up, and display "_" to indicate that W is free.

Now if we execute ...

Z=3

... in the main thread, the "_" in the browser changes to "5", and an additional line with the value "5" will pop up in the browser application because the first "Browse" call is reached in the thread that was suspended.

Pretty wierd, eh? So you can spin off lots of threads to do things, and they just kind of sit around waiting for the data they need to show up.

Here's the next really wierd thing. Remember when I said that these variables aren't like the variables we're used to? Well get this: Once a variable is determined, you can't change it anymore. Like mathematical variables: They either have a value, or are related to other variables by equations. If you know the values of all those other variables then you know X's value. Otherwise, it's a free variable. Once a variable's value in a space is determined, it doesn't change. The information in a space can increase monotonically, but what's already there can't change.

There a few other doo-dads in the core language that allow you to do more traditional "stateful" programming when that's appropriate, and extensions built on top of the core language that allow you to implement classes and objects. So it's really a multi-paradigm language, but the core of the language is very small and unusual.

Other interesting points:

[Mozart] is a development system built on Oz. (8/16/01: The site seems to be down a lot today. The site is in Germany, and it's August, so most of Europe is on vacation; maybe that explains it. Here's [another site], in the U.S., that has the documentation set.)

The site has a lot of documentation. The tutorials are good; the references are pretty bad. The basic language references describe the lexical syntax in excruciating and confusing detail, but are completely lacking semantic descriptions.

Learning Mozart-Oz

Using Oz for Cognitive Modelling

Funge's approach to cognitive modelling is very attractive, because it holds out the possibility of getting complex emergent behavior from (relatively) small sets of domain knowledge, encoded using (relatively) easy-to-write high-level definitions.

In turn, Oz's finite domain constraint solving tools seem well-suited to Funge's approach to cognitive modelling. Many of the concepts that Funge offers as possible tools can be expressed fairly directly in Oz.

Basic algorithm for solving finite domain constraint problems

The highest-level tools are oriented towards finding all, first, or best solutions to a problem. (In our case, the "solution" is a set of actions to be taken.) But there's enough flexibility in the tools to adapt them.

The basic algorithm behind constraint solving is:

  1. State all the constraints that relate the problem variables to one another.
  2. Figure out as much as you can about the possible values of the problem variable based on the constraints. This usually means that you're narrowing the domain of each variable. This is called constraint propagation.
  3. If all variables' domain have been narrowed down to a singular value, then you've found a solution to the problem.
  4. If a constraint fails, i.e. it is found to be contradictory with the domains of the problem variables, then you've failed to find a solution.
  5. If propagation neither fails nor succeeds, then you use some strategy to try out additional constraints on the variables. Usually, you just vary the domain of a single variable in various ways. For example, if you know that Y's domain is from 1 to 5 (denoted 1#5 in Oz), try setting Y to 1, then try setting Y to the domain 2#5. Repeat the propagation step each time.

The distribution algorithm is critical to performance and often has to be tailored to the problem at hand. In the example above, it might have been better to try Y domains 3, 1#2, and 4#5. The order in which you try things can matter critically. Oz provides various standard distribution strategies, but it's pretty easy to write your own.

The algorithm is of course recursive. In each step of your distribution , you create an alternative "computation space" containing your alternative trial constraint(s). You then performa a propagation step in that space. This may cause the space to fail (i.e. a constraint failed), or it may find a specific solution. If neither of these happens, then that space will in turn distribute, until you get to a computation space that either fails or succeeds. You remember a success, forget a failure, discard the computation space, and back up to a previous one to try the other alternatives provided by the distribution strategy. (This describes an exhaustive search. You might have other criteria for halting. If you're just looking for a single, first solution, you can stop on the first success.)

Some details about how Oz implements this

Oz makes it very easy to define constraints. Every constraint you "post" to the computation space causes the creation of a "constraint propagator" that runs in a separate thread, examining the state of the variables that is references in the computation space. If it can add information to the space, by narrowing the range of some of its variables, then it does so. If all of its variables are fully determined, it just goes away. If it finds that the states of its variables are inconsistent with the constraint that it's imposing then it signals failure, which causes the entire computation space to fail. If none of these is the case, then it goes to sleep until the domain of one of its variables changes, after which it repeats this activity. Lots of different constraint types are pre-defined, and there's a C/C++ interface that allows you to write your own propagators.

When all propagators have either gone to sleep or gone away, we say that the computation space is "stable" (no propagator threads are changing the computation space). Distribution is usually only done when this state is achieved!

Basic Terminology

As with any new area of knowledge, I find it helpful to spend some time nailing down new terminology. Like most computer scientists, the Mozart people can be loose with their terms, although many of the main authors are steeped in German academia and thus a bit more rigorous than most. Following are some definitions that I've found useful, but keep in mind that the literature won't always precisely follow these definitions at all times.

Feel free to edit and rearrange these definitions for clarity; I'll check them for accuracy if you do.

;store:Also computation store (see constraint programming section). Can be thought of as a single conjunctive expression of the form E1 and E2 and E3... where each subexpression En says something about a variable, for instance, X=2, Y=5, or Z=r(a:1 b:2) (where the thing shown here after the assignment operator is an Oz record). Executing statements adds new terms to this conjunction; a contradictory term (e.g. Y=X+1 when the store contains X=2 and Y=3) causes failure of the thread.

;variable: Hard to define, because the term is used a bit inconsistently. More formally, logic variable, to distinguish from the notion of variable that we're used to in imperative languages. Best thought of as lexically scoped name that refers to a "box" or node in the store. You can declare a logic variable without assigning a value to the node. The code fragment local X in local Y in X=Y end end declares two variables X and Y in nested scopes, makes them equivalent (i.e. the names refer to the same box), but doesn't actually define them. Variables can be free (as in the example), determined (it's value is known), future (meaning that it's read-only), or kinded (a state that only comes into play in constraint programming).

;thread:Just what it is for us imperative programmers. Oz encourages the use of threads; they're easy to create. They're also easy to synchronize, because the store's information grows monotonically; you can always read information from the store and be guaranteed that it won't change on you. Threads block when they need information from the store that isn't available. For instance, an equality test if (X==Y) then <do something> end will block if either X or Y is not determined in the store. As soon as they are both determined, the thread will continue. Note though that if we have stated X=Z, then the expression X==Z will not block, even if X and Z are not determined! We may not know what they eventually will be, but we know that they refer to the same node and thus are equivalent.

;cell:Although basic Oz is a declarative logic programming language and not stateful in the way that more mainstream languages are, it nonetheless provides a stateful variable primitive that can be used to do more traditional programming. This is called a cell', and it acts just like a traditional variable. A cell can be bound to a node in the store; which'' node it's bound to can be changed over time. The basic syntax for accessing cells is based on procedure calls, so they're not as convenient as logic variables. (Appropriate given the language design.) However, additional programming paradigms are built on top of the cell, including object-oriented programming, making Oz a truly multi-paradigm language like C++. For common idioms, such OO, additional syntax is layered onto the base language for convenience.

Constraint Programming Terminology

This is an important subdomain of Oz programming, which has its own additional terminology. I really created this section to force myself to unravel space states.

;computation store: This is a refinement of the term store used in the base language. The store is considered to consist of a constraint store, a procedure store, and a cell store.

;constraint: A constraint is a statement of a relation between variables. You tell constraints to a constraint store. Expressing these relations is easy; X <: Y indicates that whatever X and Y are determined to be, Y must be greater than X. When you tell a constraint, one or more propagators are created.

;constraint store: The part of a computation store that defines variables and their relationships. In contrast to the base language's notion of determined and free variables in the store, constraint programming extends the constraint store so that it can remember domains of undetermined variables. A variable that is neither free nor determined is said to be constrained or kinded.

;procedure store: The part of a computation store that contains procedure definitions. Logic variables defined in the constraint store can refer to procedures (which is normal way of defining a named procedure), although it's also possible to use procedures that have never been bound to a logic variable.

;cell store: The part of a computation store that contains cells, i.e. stateful objects.

;propagator:Also constraint propagator. A propagator is an "computational agent" which attempts to add information to the store by reasoning about a constraint, for example X <: Y. A propagator exists as long as it might be able to add information to the store. It goes away when its constraint fails (for instance, Y is determined to be 1 and X is 2) or when they determine that they can't add any more information, for instance when Y is determined to be in the range 5 to 10, and X is determined to be in the range 1 to 4. In this example, neither X nor Y is actually determined, but their domains have been resolved to the point where the constraint X <: Y is entailed, and thus couldn't possibly add any more knowledge to the store. Often, a propagator can't add any more information to the store right now, but might be able to given additional information. For instance, if X's domain is 1 to 5 and Y's is 2 to 10, then X <:Y can't add any information, but if either domain is narrowed further (by some other propagator, for instance), the X<:Y can kick in again. In this case the propagator continues to exist, suspended, waiting around for more data. A propagator is stable if it is either failed or suspended.

;space: Also computation space. A space is essentially a computation store and any threads attached to it. A thread can only be attached to a single space. Spaces are treated as first-class things in Oz. You can clone a space, which effectively copies everything but the threads, and then perform speculative computations in it. This is the basis for Oz's constraint-solving capabilities. For instance, you might clone a store and try adding new constraints to it, to see what happens. Spaces can be in a variety of different states. The next section describes space states in detail.

Computation Space States

The base documentation for Oz's spaces is, speaking kindly, sparse. The real details on this topic can only be found in Chapter 10 of Christian Schulte's doctoral thesis, "Programming Constraint Services". The mathematical notation there makes for some slow slogging, too. The basic ideas of stability and failure can be understood intuitively up to a point, but the subtle details are harder to get. A couple of definitions are needed in order to understand the space state descriptions:

;subordinate space: A space S2 is subordinated to S1 if S1 and S2 are the same space, or if S2 is an descendant of S1.

;superordinate space: A space S1 is superdinated to S2 if S2 is a descendant of, but not identical to, S1.

Following is a summary of the states from Christian's paper. The state model is hierarchical.

;merged: A space that has been merged is marked as such. You can't do much with a space after it's been merged. Merging copies information (variable states, constraints, procedure definitions) into a target space, giving the target space access to the speculative computations that were done in the merged space.

;runnable: A space is runnable if the set of subordinated spaces contains a runnable (i.e. not blocked) thread.

;blocked: A space which is not merged or runnable is blocked.

;;stable: A space S is stable if it is blocked and remains blocked regardless of changes to information in the set of superordinated spaces.

;;;failed: A space is failed if any thread failed. When a failure is detected (usually due to a constraint conflict, or a programming error), then all threads are killed and the space is marked failed.

;;;distributable: A space is distributable if it contains a distributor, i.e. a thread that is waiting to distribute on a choice.

;;;succeeded: A space is succeeded if it is stable but neither failed nor distributable.

;;;;stuck: A space is stuck if it is succeeded and contains a thread. Note that if a propagator becomes suspended because it might be able to add additional information to the store in the future, then there is a thread associated with propagator execution, and the space will be succeeded but stuck.

;;;;entailed: A space is entailed if it is succeeded and contains no threads. This implies that any propagators have become fully entailed and gone away, because they determined that they would be unable to add any new information to the store regardless of future changes. It does not imply that all variables are fully determined, though!

;;suspended: A space is suspended if it is blocked but not stable. If, for instance, a thread in S is waiting on a variable that is declared but not determined in the parent space of S, then S would be suspended, and not stable, because a change to the variable in the parent space would cause the space to be runnable. Another example if that variable were told a value in S. Because of space encapsulation, the value of the variable in S would not affect the parent space; however, if the value were subsequently determined to a different value in the parent space, the conflict in S would case S to become failed. This state usually occurs due to a programming error. As a general rule, spaces should probably not refer to undetermined variables of parent spaces. Understanding this part gave me headaches.