Procedural parameter

Some programming languages that have this feature may allow or require a complete type declaration for each procedural parameter f, including the number and type of its arguments, and the type of its result, if any. For example, in the C programming language the example above could be written as

int P(int (*f)(int a, int b)) {
    return f(6,3) * f(2,1);
}

In principle, the actual function actf that is passed as argument when P is called must be type-compatible with the declared type of the procedure parameter f. This usually means that actf and f must return the same type of result, must have the same number of arguments, and corresponding arguments must have the same type. The names of the arguments need not be the same, however, as shown by the plus and quot examples above. However, some programming languages may be more restrictive or more liberal in this regard.

In languages that allow procedural parameters, the scoping rules are usually defined in such a way that procedural parameters are executed in their native scope. More precisely, suppose that the function actf is passed as argument to P, as its procedural parameter f; and f is then called from inside the body of P. While actf is being executed, it sees the environment of its definition.

The implementation of these scoping rules is not trivial. By the time that actf is finally executed, the activation records where its environment variables live may be arbitrarily deep in the stack. This is the so-called downwards funarg problem.

For instance, we can sort an array z of 20 floating-point numbers, z[1] through z[20] in increasing order by calling isort (1, 20,zprec,zswap), where the functions zprec and zswap are defined as

procedure zprec(r, s):
    return (z[r] < z[s]);

procedure zswap(r, s):
    float t;
    t ← z[r];
    z[r] ← z[s];
    z[s] ← t

For another example, let M be a matrix of integers with 10 rows and 20 columns, with indices starting at 1. The following code will rearrange the elements in each row so that all the even values come before all odd values:

integer i
procedure eoprec(r, s):
    return (M[i, r] mod 2) < (M[i, s] mod 2);

procedure eoswap(r, s):
    integer t;
    t ← M[i,r];
    M[i,r] ← M[i,s];
    M[i,s] ← t;

for i from 1 to 10 do
    isort(1, 20, eoprec, eoswap);

Note that the effects of eoprec and eoswap depend on the row number i, but the isort procedure does not need to know that.

The following example uses isort to define a procedure vecsort that takes an integer n and an integer vector v with elements v[0] through v[n−1] and sorts them in either increasing or decreasing order, depending on whether a third parameter incr is true or false, respectively:

procedure vecsort(n, v, incr):

    procedure vprec(r, s):
        if incr then
            return v[r] < v[s];
        else
            return v[r] > v[s];

    procedure vswap(r, s):
        integer t;
        t ← v[r];
        v[r] ← v[s];
        v[s] ← t

    isort(0, n−1, vprec, vswap);

Note the use of nested function definitions to get a function vprec whose effect depends on the parameter incr passed to vecsort. In languages that do not allow nested function definitions, like standard C, obtaining this effect would require rather complicated and/or thread-unsafe code.

To illustrate the use of the generic merge procedure, here is the code for merging two simple linked lists, starting with nodes at addresses R, S. Here we assume that each record x contains an integer field x.INFO and an address field x.NEXT that points to the next node; where the info fields are in increasing order in each list. The input lists are dismantled by the merge, and their nodes are used to build the output list.

procedure listmerge(R, S):

    procedure prec(r, s):
        return r.INFO < s.INFO

    procedure next(x):
        return x.NEXT

    procedure append(x, fin)
        if fin ≠ Λ then fin.NEXT ← x
        x.NEXT ← Λ
        return x
     
    return merge(R, S, prec, next, append, next, append)

The following code illustrates the independence of the generic merge procedure from the actual representation of the sequences. It merges the elements of two ordinary arrays U[0] through U[m−1] and V[0] through V[n−1] of floating-point numbers, in decreasing order. The input arrays are not modified, and the merged sequence of values is stored into a third vector W[0] through W[m+n−1]. As in the C programming language, we assume that the expression "&V" yields the address of variable V, "*p" yields the variable whose address is the value of p, and that "&(X[i])" is equivalent to "&(X[0]) + i" for any array X and any integer i.

procedure arraymerge(U, m, V, n, W):

    procedure prec(r, s):
        return (*r) > (*s)

    procedure nextU(x):
        if x = &(U[m−1]) then return Λ else return x + 1

    procedure nextV(x):
        if x = &(V[n−1]) then return Λ else return x + 1

    procedure append(x, fin)
        if fin = Λ then fin ← &(W[0])
        (*fin) ← (*x)
        return fin + 1
        
    if m = 0 then U ← Λ
    if n = 0 then V ← Λ
    return merge(U, V, prec, nextU, append, nextV, append)

The following procedure computes the approximate integral ${\displaystyle \textstyle \int _{a}^{b}}$ f (x) dx of a given real-valued function f over a given interval [a,b] of the real line. The numerical method used is the trapezium rule with a given number n of steps; the real numbers are approximated by floating-point numbers.

procedure Intg(f, a, b, n):
    float t, x, s; integer i
    if b = a then return 0
    x ← a; s ← f(a) / 2;
    for i from 1 to n−1 do
        t ← i/(n+1); x ← (1−t) * a + t * b;
        s ← s + f(x)
    s ← f(b) / 2
    return (b − a) * s / n

Consider now the problem of integrating a given function g, with two arguments, over a disk D with given center (xc,yc) and given radius R. This problem can be reduced to two nested single-variable integrals by the change of variables

${\displaystyle \int \!\int _{D}g(x,y)\,\mathrm {d} x\,\mathrm {d} y=\int _{0}^{R}z\left(\int _{0}^{2\pi }g({\mathit {xc}}+z\cos t,{\mathit {yc}}+z\sin t)\,\mathrm {d} t\right)\,\mathrm {d} z}$

The following code implements the right-hand-side formula:

procedure DiskIntg(g, xc, yc, R, n)

    procedure gring(z):

        procedure gpolar(t):
            float x, y
            x ← xc + z * cos(t)
            y ← yc + z * sin(t)
            return g(x, y)

        integer m ← round(n*z/R)
        return z * Intg(gpolar, 0, 2*π, m)

    return Intg(gring, 0, R, n)

This code uses the integration procedure Intg in two levels. The outer level (last line) uses Intg to compute the integral of gring(z) for z varying from 0 to R. The inner level (next-to-last line) defines gring(z) as being the line integral of g(x,y) over the circle with center (xc,yc) and radius z.