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.A FunJava program.
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.