A SIMPLE FUNCTIONAL LANGUAGE

To make the new language Fun-MiniJava, we add function types to MiniJava:

ClassDecl → type id = TypeExp ;
 TypeExp → TypeExp -> TypeExp
 → ( TypeList ) -> TypeExp
 → ( TypeExp )
 → Type TypeList
 → TypeExp TypeRest*
 →
 TypeRest →, TypeExp

The type int->String is the type of functions that take a single integer argument and return a string result (assuming a class String is declared). The type (int,String)->int[] describes functions that take two arguments (one integer, one string) and return an array-of-integers result. Any variable can have a functional type; functions can be passed as arguments and returned as results. Thus, the type (int->int)->(int)->int is perfectly legal; the -> operator is right-associative, so this is the type of functions that take an int->int argument and return an int->int result. We also modify the format of a CALL expression, so that the function being called is an arbitrary expression, without the .methodname component, and so that a method itself can be the result of an expression:

Exp → Exp ( ExpList )
Exp → Exp . id

If v is an object of a class with a method int m(int[]), then the expression v.m evaluates to a function value of type (int[])->int. Evaluating v.m does not call the method. We permit variable declarations and function (method) declarations at the beginning of a compound statement (i.e., functions are nested). We remove the if statement and add an if expression: That is, (if (E) B else C) evaluates E, and then evaluates B if E is true, otherwise evaluates C. The value of the entire if expression is the value of B or C.

MethodDecl → public Type id ( FormalList ) Compound
 Compound → { VarDecl* MethodDecl* Statement* return Exp ;}
 Exp → Compound
 → if ( Exp ) Exp else Exp

Finally, we interpret the meaning of return differently: Instead of producing the result for an entire function body, it produces the result of its own compound statement. Thus, the expression {return 3;}+{return 4;} evaluates to 7. Program 15.1 illustrates the use of function types. The function add takes an integer argument n and returns a function h. Thus, addFive is a version of h whose n variable is 5, but addSeven is a function h(x) = 7 + x. The need for each different instance of h to "remember" the appropriate value for a nonlocal variable n motivates the implementation technique of closures, which is described later.

type intfun = int -> int;
class C {
 public intfun add(n: int) {
 public int h(int m) { return n+m;}
 return h;
 }
 public intfun twice(f: intfun) {
 public int g(int x) {return f(f(x));}
 return g;
 }
 public int test() {
 intfun addFive = add(5);
 intfun addSeven = add(7);
 int twenty = addFive(15);
 int twentyTwo = addSeven(15);
 intfun addTen = twice(addFive);
 int seventeen = twice(add(5))(7);
 intfun addTwentyFour = twice(twice(add(6)));
 return addTwentyFour(seventeen);
 }
}

The function twice takes an argument f that is a function from int to int, and the result of twice(f) is a function g that applies f twice. Thus, addTen is a function g(x) = addFive(addFive(x)). Each instance of g(x) needs to remember the right f value, just as each instance of h needs to remember n.

JaVa	Previous    Next