Information Technology Reference
In-Depth Information
5 Constraints and Procedures
So far we explained how the program interacts with the store in absence of
procedures. In
one level (i.e., not nested) procedures are allowed. In
presence of procedures we need to explain a number of issues.
First, to keep matters simple, we disallow local unknowns. This means that
the constrained types can be only introduced at the outer level. However, un-
knowns can be used within the procedure bodies provided the restrictions intro-
duced in Denition 2 are respected.
Next, we need to explain how unknowns can be passed as parameters. Formal
parameters of constrained types are considered as unknowns. This means that in
the procedure body such formal parameters can occur only within the constraints
or within the right hand side of an assignment.
We discuss rst call by variable. An unknown (or a compound variable con-
taining an unknown) passed as an actual variable parameter is handled in the
same way as the customary variables, by means of the usual reference mecha-
nism.
For example consider the following problem.
Alma-0
Problem 4. Given is an array which assigns to each pixel on an M N board a
colour. A region is a maximal set of adjacent pixels that have the same colour.
Determine the number of regions.
To solve it we represent each pixel as a record, one eld of which holds the
colour of the pixel and the other is an unknown integer. Then we assign to
each pixel a number in such a way that pixels in the same region get the same
number. These assignments are performed by means of constraint solving. For
instance, in the case of Figure 1 the constraint solving takes care that the value
1 is assigned to all but two pixels once it is assigned to the leftmost uppermost
pixel.
Fig. 1. Constraint Solving and Pixels
To achieve this eect in the program below we assume that the constraint
solving process is able to reduce the domain of y to
f a g
given the constraint
x=y and the fact that the domain of x equals
. The program uses both
constraints and an assignment. In addition, the program uses the built-in KNOWN
that, when used on unknowns, checks whether the domain of the argument is a
singleton.
f a g
 
Search WWH ::




Custom Search