HIGHER-ORDER FUNCTIONS

But in languages supporting both nested functions and function-valued variables, it may be necessary to keep local variables after a function has returned! Consider Program 6.1: This is legal in ML, but of course in C one cannot really nest the function g inside the function f.An example of higher-order functions.

fun f(x) =
 let fun g(y) = x+y
 in g
 end val h = f(3)
val j = f(4)
val z = h(5)
val w = j(7)

 int (*)() f(int x) {
  int g(int y) {return x+y;}
  return g;
 }
 int (*h)() = f(3);
 int (*j)() = f(4);
 int z = h(5);
 int w = j(7);

When f(3) is executed, a new local variable x is created for the activation of function f. Then g is returned as the result of f(x); but g has not yet been called, so y is not yet created. At this point f has returned, but it is too early to destroy x, because when h(5) is eventually executed it will need the value x = 3. Meanwhile, f(4) is entered, creating a different instance of x, and it returns a different instance of g in which x = 4. It is the combination of nested functions (where inner functions may use variables defined in the outer functions) and functions returned as results (or stored into variables) that causes local variables to need lifetimes longer than their enclosing function invocations. Pascal has nested functions, but it does not have functions as returnable values. C has functions as returnable values, but not nested functions. So these languages can use stacks to hold local variables. ML, Scheme, and several other languages have both nested functions and functions as returnable values (this combination is called higher-order functions). So they cannot use stacks to hold all local variables. This complicates the implementation of ML and Scheme - but the added expressive power of higher-order functions justifies the extra implementation effort.

For the remainder of this chapter we will consider languages with stackable local variables and postpone discussion of higher-order functions to . Notice that while Java allows nesting of functions (via inner classes), MiniJava does not.