Information Technology Reference
In-Depth Information
{
In
three types of parameter mechanisms are allowed: call by value,
call by variable and
call by mixed form
. The rst two are those of Pascal
and Modula-2; the third one is an amalgamation of the rst two (see [2]).
Parameters passed by mixed form can be used both for testing and for com-
puting.
Alma-0
Let us summarize these features of
Alma-0
by clarifying which of them are
based on rst-order logic.
In the logical reading of the programming language constructs the program
composition
S; T
is viewed as the conjunction
S
T
. A dual of \;", the
EITHER
S ORELSE T END
statement, corresponds then to the disjunction
S
^
T
.
Further, the
FOR i:= s TO t DO S END
statement is viewed as the bounded
universal quantication,
_
[
s
::
t
]
S
, and its dual, the
SOME i:= s TO t DO S
END
statement is viewed as the bounded existential quantication,
8
i
2
[
s
::
t
]
S
.
In turn, the
FORALL S DO T END
statement can be viewed as the restricted
quantication
9
i
2
8
x
(
S
!
T
), where
x
are all the variables of
S
.
Because the boolean expressions are identied with the statements, we can
apply the negation connective,
NOT
, to the statements. Finally, the equality can
be interpreted both as a test and as an one-time assignment, depending on
whether the variable in question is initialized or not.
3 Programming in
Alma-0
To illustrate the above features of
Alma-0
and the resulting programming style
we now consider two examples.
3.1
The Frequency Assignment Problem
The rst problem we discuss is a combinatorial problem from telecommunication.
Problem 1. Frequency Assignment
([7]). Given is a set of
n
cells
,
C
:=
fc
1
;
c
2
;:::;c
n
g
and a set of
m
frequencies (or channels)
F
:=
ff
1
;f
2
;:::;f
m
g
.An
assignment
is a function which associates with each cell
c
i
a frequency
x
i
2
F
. The problem consists in nding an assignment that satises the following
constraints.
Separations:
Given
h
and
k
we call the value
d
(
f
h
;f
k
)=
jh−kj
the
dis-
tance
between two channels
f
k
. (The assumption is that consecutive
frequencies lie one unit apart.) Given is an
f
h
and
n n
non-negative integer sym-
metric matrix
s
ij
represents
the minimum distance between the frequencies assigned to the cells
S
, called a
separation matrix
, such that each
c
i
and
c
j
. That is, for all
i 2
[1
::n
]and
j2
[1
::n
] it holds that
d
(
x
i
;x
j
)
s
ij
.
Illegal channels:
Given is an
nm
boolean matrix
F
such that if
F
ij
=
true
,
then the frequency
f
j
cannot be assigned to the cell
i
, i.e.,
x
i
=
f
j
.
Search WWH ::
Custom Search