Nested procedures,
i. e., procedures declared local to another procedure,
are a useful concept for structuring and decomposing large procedures
into smaller and more comprehensible units in a natural way,
without needing to introduce artificial global procedures
to achieve that aim.
Furthermore,
the fact that nested procedures can directly access
the local variables and parameters of their enclosing procedures
helps to keep their parameter lists short,
without needing to introduce artificial global variables
for that purpose.
Procedure types,
i. e., types possessing procedures as values,
are another useful concept for program development
that allows algorithms (e. g., for sorting)
to be decoupled from their basic operations (e. g., comparing objects)
and by that means increasing their generality and applicability.
The combination of nested procedures and procedure types,
i. e., the possibility of using not only global,
but also nested procedures
as actual parameters of other procedures,
would be an even more useful and powerful concept,
as the example below will demonstrate.
Unfortunately, however,
languages such as Modula—2 and Oberon(—2)
do not allow this combination,
i. e., they require procedure values (i. e., values of procedure types)
to be global procedures
in order to avoid the danger of so-called dangling procedure values.
(Other languages,
such as C and C++,
do not allow nested procedures at all.)
However, by introducing alternative language rules as well as a small language extension, it is possible to allow nested procedures to be safely used as values of procedure types and especially to pass them as parameters to other procedures. The basic idea of these rules is that procedure values must not be assigned to “more global” variables, unless it is explicitly guaranteed that the actual value's lifetime is greater than or equal to the variable's lifetime.
Even though this concept has been developed in the context of Oberon(—2), it is easily portable to other languages, e. g., C and C++, if they were extended by the concept of nested procedures.
The following module BinTree
defines and exports data structures
for representing binary trees of integer values
as well as a general procedure Trav to traverse such a tree t
and invoke a callback procedure cb for every node's value.
Furthermore,
a specialized procedure Sum is provided
that computes the sum of all values contained in a tree t
by passing a nested procedure Add as a callback procedure to Trav.
MODULE BinTree;
TYPE
Tree* = POINTER TO Node;
Node = RECORD
val: INTEGER;
left, right: Tree;
END;
CallbackProc = PROCEDURE (x: INTEGER);
PROCEDURE Trav* (t: Tree; cb: CallbackProc);
BEGIN
IF t # NIL THEN
Trav(t.left, cb);
cb(t.val);
Trav(t.right, cb);
END
END Trav;
PROCEDURE Sum* (t: Tree) : INTEGER;
VAR sum: INTEGER;
PROCEDURE Add (x: INTEGER);
BEGIN sum := sum + x
END Add;
BEGIN
sum := 0;
Trav(t, Add);
RETURN sum;
END Sum;
END BinTree.
[1] C. Heinlein:
"Safely Extending Procedure Types to Allow Nested Procedures as Values."
In: L. Böszörményi, P. Schojer (eds.): Modular Programming Languages (Joint Modular Languages Conference, JMLC 2003; Klagenfurt, Austria, August 2003; Proceedings). Lecture Notes in Computer Science 2789, © Springer-Verlag, Berlin, 2003, 144–149.
Describes the alternative language rules
and the language extension mentioned above
for Oberon—2.
[2] C. Heinlein: Safely Extending Procedure Types to Allow Nested Procedures as Values (Corrected Version). Nr. 2003-07, Ulmer Informatik-Berichte, Fakultät für Informatik, Universität Ulm, September 2003.
(PostScript, PDF)
A corrected and extended version of the previous paper.