Download 1 Introduction

what is going on. However, what happens when two unbound variables are equated
X = Y, or when two large data structures are equated? Here is a short explanation.
We may think of the store as a dynamically expanding array of cells, each cell is
labeled by a variable. When a variable X is introduced a cell is created in the store,
labeled by X, and its value is unknown. At this point, the cell does not possess any
value; it is empty as a container that might be lled later.
A variable with an empty cell is a free variable. The cell as a container is exible
enough to contain any arbitrary Oz value. The operation W = tree(1:I 2:Y
3:LT 4:LR) stores the record structure in the cell associated with W. Notice that
we are just getting a graph structure where arcs emanating from the W-labeled cell
are pointing to the cells of I Y LT, and LR respectively. Each arc in turn is labeled
by the corresponding feature of the record. Given two variable X and Y, X = Y will
try to merge their respective cells. Now we are in a position to give a reasonable
account for the merge operation of X = Y, known as the incremental tell operation.
X and Y are labels of the same cell: the operation is completed.
X (Y) is free: merge X (Y) to the cell of Y (X), and discard the original cell of X
(Y); we have a situation where a cell is labeled by a set of variables.
X and Y are labels of dierent cells containing the records Rx and Ry respectively:
{ Rx, and Ry have dierent labels, arities, or both: the operation is completed, and an exception is raised.
{ Otherwise arguments of Rx and Ry with the same feature are pair-wise
merged in arbitrary order 4 .
Here are some examples of successful equality operations:
local X Y Z in
f(1:X 2:b) = f(a Y)
f(Z a) = Z
{Browse [X Y Z]}
end
will show [a b R14=f(R14 a)] in the browser. R14=f(R14 a) is the external
representation of a cyclic graph.
The following example shows, what happens when variables with incompatible
values are equated.
declare X Y Z
X = f(c a)
Y = f(Z b)
X = Y
The incremental tell of X = Y will assign Z the value c, but will also raise an exception
that is caught by the system, when it tries to equate a and b.
In general the two graphs to merge could have cycles, however any correct implementation
of the merge operation will consider cell pairs for which an attempt to merge has been made as
successfully merged.
4
8