Courses/CS 460/Fall 2005/What programmers should know about Oz
From CSWiki
There are two features of Oz that may make it difficult for programmers who are used to traditional programming languages to get used to Oz: logic variables and Oz's presumptively communitarian run-time environment.
Contents |
[edit] Logic variables
The variables in Oz are what are known as logic variables. Logic variables are unlike variables in traditional programming languages in two important ways.
- Logic variables may have only one value. Once a value is assigned to a logic variable, it retains that value forever. Logic variables are more like mathematical variables than like variables in programming language. Because of their assign-once nature, logic variables may be set equal to each other even before they have a value—just as mathematical variables may be declared equal to each other (or declared to be in some other relationship to each other) even when their values are unknown. Logic variables are common in logic programming languages. The original logic programming language was Prolog, in which logic variables were introduced.
- Logic variables support an operation known as unification, a generalized form of pattern matching, in which structures may be matched and their internal substructures set equal to each other.
[edit] The presumptively communitarian Oz run-time environment
Most distinctive about Oz, and the feature which is most likely to confuse programmers who are familiar with programming in a traditional run-time environment, is Oz's presumptively communitarian run-time framework.
Every Oz program is a thread that is assumed to be running within a community of other threads. Although Oz threads are similar to threads in other multi-threaded shared-memory environments, Oz differs from most other languages in that its semantics presume that there will be multiple threads operating—even if a particular program has created only one thread. That is, there are a great many elements of the Oz language that simply won't work unless they are run in the company of other threads.
In particular, it is part of the semantics of Oz that under a great many circumstances a thread will suspend and wait for information from another thread—whether or not there are any other threads in existence. It is the fact that this presumption is built into the Oz language that distinguishes Oz from other programming languages.
Here is a simple example.
declare X
{Browse a}
{Browse X}
{Browse b}
{Browse X+1}
{Browse c}
If one runs the preceding program, the output will be:
a X (or _ depending on something that I don't understand) b
At that point the program will suspend. It is unable to continue because X has no value—and since X has no value, X+1 cannot be computed.
It is built into Oz that this is not an error condition. In other programming languages, the run-time system would either use a default value for X, or it would raise an exception. Oz does neither. Instead it suspends—and it does so silently. The beginning Oz programmer will have no idea why the program stopped.
The reason is that the Oz language is based on the presumption that if one reaches a point in a thread at which the thread cannot continue because a variable does not (yet) have a value, the thread should simply suspend and wait until some other thread comes to its rescue—even if there are no other threads. The decision to suspend (silently) when the value of an uninstantiated variable is needed is simply built into the language.
If one then enters and runs the line
X = 5
the original thread will resume and produce the expected output.
6 c
Note that every time one runs a piece of a program from the Emacs buffer, it runs in a new thread. All threads share a common global memory space.
What is unusual about Oz, and what differentiates it from other languages, is the extent to which this principle of suspend-and-wait is built into the language.
For example, if one had replaced the line
{Browse X+1}
with the line
{Browse X == 9}
the program would still have suspended: one cannot evaluate X == 9 because X has no value. If one then again enters and runs
X = 5
the original thread will resume and produce the expected output.
false c
[edit] Data flow variables
Although suspending a thread until a variable becomes instantiated can be useful—any variable can function as a virtual port on which a thread can wait until a message arrives—it is also a potential trap for Oz programmers. One must be constantly aware of the possibility that one's code will encounter a situation in which it will suspend.
In Oz, such behavior is associated with what are known as data flow variables. Every Oz variable is not only a logic variable, it is also a data flow variable. When a thread arrives at a point at which a variable must be instantiated for the program to continue, the program will suspend and wait for instantiation.
As indicated, this can be very useful for writing distributed processing systems. But it can also lead to bugs that are difficult to find. If through a coding mistake, a variable is not instantiated when the programmer expects it to be instantiated, the program will silently suspend and wait for instantiation to occur.
Consider the following code for an interesting example of using data flow variables.
declare A B
proc {WaitFor X} if X == 0 then skip end end
proc {PredSucc ?X ?Y}
if {IsDet X} then X+1 = Y
elseif {IsDet Y} then X = Y-1
else Ready in
thread {WaitFor X} Ready = ready end
thread {WaitFor Y} Ready = ready end
{WaitFor Ready}
{PredSucc X Y}
end
end
{PredSucc A B}
{Browse A#B}
The proc PredSucc takes two arguments. If either is instantiated (or both are) it succeeds if either
- X = Y-1 or
- it can make X = Y-1 (or, equivalently, X+1 = Y).
As written, the code will wait since neither A nor B is instantiated. If one then writes
A = 4
one will then get 4#5 as output.
An interesting alternative is to define
declare A B
proc {PredSucc X Y}
thread X+1 = Y end
thread X = Y-1 end
end
{PredSucc A B}
{Browse A#B}
When this code is run, the output will be A#B, i.e., PredSucc will not suspend since the suspensions occur in the threads within PredSucc. But neither A nor B will be instantiated.
If one then runs
A = 3
{Browse A#B}
one will get 3#4 as output. But if instead one runs
A#B = 3#6
one will get two exceptions since both suspended threads will find that the variables that they are attempting to unify are incompatible: 3 \= 5 and 4 \= 6.
Presumably, there is no guarantee which unification will fail. A#B = 3#6 may not be guaranteed to execute atomically. But even if it doesn't, it will fail when it resumes if either of the threads within PredSucc succeeds when one of A or B is instantiated.
Note: It's not clear to me in what ways this embedded thread disjunction is similar to Oz's or construct. They don't seem to be exactly the same. But I don't understand or.
It might be useful to see to what extent this technique could be used to implement constraint propagators at the Oz level instead of having to write C++ code.
To accomplish that it would be useful for code to be able to refer to the computational space within which it is executing.
It would also be interesting for choice simply to spawn multiple threads in cloned computational spaces. They could all run in parallel, and some other program could then reap the results. Since the Oz language is so fundamentally predicated on the notion of a community of threads, defining choice to be a generator of threads (in cloned rather than shared spaces) seems compatible with its basic philosophy.
Defining choice as spawing multiple threads in disjoint spaces and or as spawing multiple threads in a shared space might be a nice way to formulate the difference between search and constrain.
[edit] Suspension situations to watch for
Perhaps more confusing for traditional programmers, Oz control constructs also suspend.
- If the preceding Boolean comparison operation were the conditional part of an if statement, the if statement will suspend until X gets a value.
- Similarly, the Oz case statement suspends if the pattern to be matched is insufficiently instantiated given the patterns against which it is compared.
- The Oz choice statement suspends no matter what. Threads with a choice statement are meaningless unless they are run in an environment in which other threads are there to poke them when they suspend.
- Oz defines a full-evaluation logical or, which differs from the short-circuit orelse. {Or A B} evaluates both A and B even if A returns true.
declare X
{Browse {Or true X == 0}}
suspends, whereas
declare X
{Browse true orelse X == 0}
prints true.
- There are other more obscure situations in which Oz threads suspend. For example, a thread executing within what Oz calls a computational space suspends if it attempts to unify an instantiated variable (or simply a value) with an uninstantiated variable outside that space.
I am not aware of a comprehensive list of situations in which Oz threads suspend. Such a list would be useful to Oz programmers.
Oz's run-time environment could make things more transparent for developers if it offered an Emacs buffer that showed all the threads in existence and where they are suspended. Perhaps a future Mozart release will offer such a feature.
Until then, Oz programmers must keep in mind that there is a very wide (and not very well documented) range of circumstances under which Oz threads suspend—and they do so silently—because that's how the language is defined.
[edit] Thread bombs
This code illustrates how Oz suspends and the effect of suspensions on computations within a SearchAll.
local
% Simply fails.
proc {V1} fail end
% Simply succeeds.
proc {V2} skip end
% Blocks on X == Y.
proc {V3}
X Y in
X == Y = false
end
% The same as V3. Blocks on X == Y.
% Never gets to setting X and Y to different values.
proc {V4}
X Y in
X == Y = false
X = x
Y = y
end
% Simply succeeds because X and Y have
% different values when X == Y is tested.
proc {V5}
X Y in
X = x
Y = y
X == Y = false
end
% Fails because X == Y is encapsulated in a thread.
% Even though X == Y suspends in that thread, the
% main V6 computation continues and sets X and Y
% to the same value. At that point the test
% X == Y executes. It returns true, which fails
% to unify with false. That causes the entire
% v6 computation to fail.
proc {V6}
X Y in
thread X == Y = false end
X = z
Y = z
end
% Succeeds because X == Y is encapsulated in a thread.
% Even though X == Y suspends in that thread,
% the main V7 thread continues and sets X and Y
% to different values. At that point the test
% X == Y executes. It returns false, which
% unifies with false. The entire v7
% computation succeeds.
proc {V7}
X Y in
thread X == Y = false end
X = x
Y = y
end
% Splits into 7 distinct computations.
% For each one that succeeds, returns
% an identifier for that computation.
fun {TestThreadBomb}
choice
{V1}
v1
[]
{V2}
v2
[]
{V3}
v3
[]
{V4}
v4
[]
{V5}
v5
[]
{V6}
v6
[]
{V7}
v7
end
end
in
{Browse {SearchAll TestThreadBomb}}
end
When the preceding code is run, the output is
[v2 _ _ v5 v7]
This means that
- V1 failed and resulted in no result for SearchAll's list.
- V2 succeeded.
- V3 and V4 blocked. SearchAll returned _ for these paths. I have not seen any documentation to the effect that SearchAll produces _ for blocked paths. But apparently, that's what happens.
- V5 succeeded.
- V6 failed and resulted in no result for the SearchAll list.
- V7 succeeded.
This section is entitled Thread Bombs because it illustrates a way to encapsulate a constraint that will terminate a computation path if the constraint fails. Think of it as something like an Improvised Explosive Device (IED).
- It is triggered when the condition it specifies becomes testable.
- It goes off and destroys the computation within which it was planted when the condition it is testing is not satisfied.
In this example, we planted two thread bombs: v6 and v7. In the v6 case, the condition was not met, and the computation was terminated. In the v7 case, the condition was met, and the computation was allowed to proceed to completion.
[edit] Using the thread bomb
Here's a simple example that uses thread bombs to generate all permutations of [a b c].
The proc AllDistinct generates thread bombs that ensure that no two elements in the list provided to it have the same value.
The key is in the Permute function.
- First it generates Permutation, a list of variables, which is as long as the input list. That list will be returned as a result.
- Second it generates thread bombs that prevent two elements of the Permutation list from having the same value.
- Then it ensures that every element of the Permutation list has some value from the input list. In doing this it generates multiple computations depending on how values from the input list are selected for values in the output list.
Permute needn't test the elements that it puts into the output list to ensure that they are a permutation of the input list. The thread bombs prevent any non-permutation from surviving.
local
% Generate thread bombs that ensure that each element in Xs
% is different from its successors in Xs.
proc {AllDistinct Xs}
case Xs of X|Xr then
for Y in Xr do
thread X==Y = false end
end
{AllDistinct Xr}
else skip end
end
% Is X in the list of Xs
proc {IsIn ?X Xs}
Head Tail in
Xs = Head | Tail
choice X = Head [] {IsIn X Tail} end
end
% Return all permutations of List.
fun {Permute L}
Permutation = {MakeList {Length L}}
in
{AllDistinct Permutation}
{ForAll Permutation proc {$ Elt} {IsIn Elt L} end}
Permutation
end
in
{Browse {SearchAll fun {$} {Permute [a b c]} end}}
end
