IMMUTABLE VARIABLES

The FunJava language has higher-order functions with nested scope, but it is still not really possible to use equational reasoning about FunJava programs. That is, f(3) may return a different value each time. To remedy this situation, we prohibit side effects of functions: When a function is called, it must return a result without changing the "world" in any observable way. Thus, we make a new pure functional programming language PureFunJava, in which the following are prohibited:

To distinguish clearly between initializing instance variables (which is permitted) and updating instance variables (which is not), we require that every class have a constructor in a special, stereotypical form that initializes all the instance variables: 

 ClassDecl →  id { VarDecl* MethodDecl* Constructor }
Constructor → public id ( FormalList ){ Init*}
 Init → this . id = id

This seems rather Draconian: How is the program to get any work done? To program without assignments, in a functional style, you produce new values instead of updating old ones. For example, shows the implementation of binary search trees in imperative and functional styles. As explained in (page 108), the imperative program updates a tree node, but the functional program returns a new tree much like the old one, though the path from the root to a "new" leaf has been copied. If we let t1 be the tree in on page 108, we can sayBinary search trees implemented in two ways. 

class tree {
 String key; int binding; tree left; tree right;
 public tree(String key, int binding, tree left, tree right) {
 this.key=key; this.binding=binding;
 this.left=left; this.right=right;
 }
 public int look(String k) {
 int c = key.compareTo(k);
 if (c < 0) return left.look(k);
 else if (c > 0) return right.look(k);
 else return binding;
 }
 public void enter(String k, int b) {
 int c = key.compareTo(k);
 if (c < 0)
 if (left==null)
 left = new tree(k,b,null,null);
 else left.enter(k,b);
 else if (c > 0)
 if (right==null)
 right = new tree(k,b,null,null);
 else right.enter(k,b);
 else binding=b;
 }
}
 (a) Imperative, object-oriented Java
 // Alternative implementation of enter
 public tree enter(String k, int b) {
 int c = key.compareTo(k);
 if (c < 0)
 if (left==null)
 return new tree(k,b,null,null);
 else return left.enter(k,b);
 else if (c > 0)
 if (right==null)
 return new tree(k,b,null,null);
 else return right.enter(k,b);
 else return new tree(k,b,left,right);
 }
 (b) Functional, object-oriented Java

int t2 = t1.enter("mouse",4);

and now t1 and t2 are both available for the program to use. On the other hand, if the program returns t2 as the result of a function and discards t1, then the root node of t1 will be reclaimed by the garbage collector (the other nodes of t1 will not be reclaimed, because they are still in use by tree t2). Similar techniques can allow functional programs to express the same wide variety of algorithms that imperative programs can, and often more clearly, expressively, and concisely.

CONTINUATION-BASED I/O

Producing new data structures instead of updating old ones makes it possible to obey the "no assignments" rules, but how is the program to do input/output? The technique of continuation-based I/O expresses input/output in a functional framework. As shown in , the predefined types and functions in PureFunJava rely on the notion of an answer: This is the "result" returned by the entire program.Built-in types and functions for PureFunJava. 

type answer // a special, built-in type
type intConsumer = int -> answer type cont = () -> answer class ContIO {
 public answer readByte (intConsumer c);
 public answer putByte (int i, cont c);
 public answer exit();
}

MiniJava doesn't have an input function, but if it did, the type would be straightforward: something like int readByte(). To express this without side effects, PureFunJava's readByte takes an argument that is a int-Consumer and passes the newly read integer to that consumer. Whatever answer the consumer produces will also be the answer of the readByte. Similarly, putByte takes a character to print as well as a continuation (cont); putByte outputs a character and then calls the cont to produce an answer.

The point of these arrangements is to allow input/output while preserving equational reasoning. Interestingly, input/output is now "visible" to the typechecker: Any function which does I/O will have answer in its result type.

LANGUAGE CHANGES

The following modifications of FunJava make the new language PureFunJava:

shows a complete PureFunJava program that loops, reading integers and printing the factorial of each integer, until an integer larger than 12 is input.PureFunJava program to read i, print i!. 

class Factorial {
 boolean isDigit (int c) {
 return c >= 48 && c <= 48+9; // 48 == (int)'0'
 }
 public answer getInt(intConsumer done) {
 public answer nextDigit(int accum) {
 public answer eatChar(int dig) {
 return if (isDigit(dig))
 nextDigit(accum*10+dig-48)
 else done(accum);
 }
 return ContIO.readByte(eatChar);
 }
 return nextDigit(0);
 }
 answer putInt(int i, cont c) {
 return if (i==0)
 c()
 else {
 int rest = i/10;
 int dig = i - rest * 10;
 public answer doDigit() { return ContIO.putByte(dig,c); }
 return putInt(rest, doDigit);
 };
 }
 int factorial (int i) {
 return if (i==0) 1 else i * factorial(i-1);
 }
 answer loop (int i) {
 return if (i > 12) ContIO.exit()
 else {
 public answer next() { return getInt(loop); }
 return putInt(factorial(i), next);
 };
 }
 public static answer main (String [] argv) {
 return getInt(loop);
 }
}

OPTIMIZATION OF PURE FUNCTIONAL LANGUAGES

Because we have only deleted features from FunJava, and not added any new ones (except changing some predefined types), our FunJava compiler can compile PureFunJava right away. And, in general, functional-language compilers can make use of the same kinds of optimizations as imperative- language compilers: inline expansion, instruction selection, loop-invariant analysis, graph-coloring register allocation, copy propagation, and so on. Calculating the control-flow graph can be a bit more complicated, however, because much of the control flow is expressed through function calls, and some of these calls may to be function variables instead of statically defined functions. A PureFunJava compiler can also make several kinds of optimizations that a FunJava compiler cannot, because it can take advantage of equational reasoning. Consider this program fragment, which builds a record r and then later fetches fields from it: 

class recrd {int a; int b;
 public recrd(int a, int b) {this.a=a; this.b=b;}
}
int a1 = 5;
int b1 = 7;
recrd r = new recrd(a1,b1);
int x = f(r);
int y = r.a + r.b;

In a pure functional language, the compiler knows that when the computation of y refers to r.a and r.b, it is going to get the values a1 and b1. In an imperative (or impure functional) language, the computation f(r) might assign new values to the fields of r, but not in PureFunJava. Thus, within the scope of r every occurrence of r.a can be replaced with a1, and similarly b1 can be substituted for r.b. Also, since no other part of the program can assign any new value to a1, it will contain the same value (5) for all time. Thus, 5 can be substituted for a1 everywhere, and 7 for b1. Thus, we end up with int y = 5+7, which can be turned into int y = 12; thus, 12 can be substituted for y throughout its scope. The same kind of substitution works for imperative languages too; it's just that a compiler for an imperative language is often not sure whether a field or variable is updated between the point of definition and the point of use. Thus, it must conservatively approximate - assuming that the variable may have been modified - and thus, in most cases, the substitution cannot be performed. See also alias analysis ().

The ML language has pure functional records, which cannot be updated and on which this substitution transformation is always valid, and also has updatable reference cells, which can be assigned to and which behave like records in a conventional imperative language.