Nested Procedure Values

Concept

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.

Example

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.

Publications

[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.


Christian Heinlein, 22.09.09