Due on Thursday, May 7th

Programming with Explicit Polymorphism

This past week, we've studied the incorporation of higher-order functions, explicit static typing, and parametric polymorphism in a programming language. This offers a powerful combination of static safety guarantees and reusability, but the requirement of explicit type annotations imposes a significant notational burden. If you've used Java's generics mechanism in any significant way, you've surely encountered this fact already.

In this assignment, you'll explore this idea in the setting of the Java 8 generics mechanism and the support for first class functions. Although it was always possible to simulate first class functions using anonymous inner classes, Java 8 provides direct support for functional programming through the java.util.function.* package and the new lambda construct for anonymous functions.

Here, we'll consider one of the more straightforward interfaces, java.util.function.Function, which represents functions of one argument. For types α and β, you can declare a variable of type Function<α>. You can construct a value of this type through the old, anonymous inner class form

Function<α> f = new Function<α>() {
                    public β apply(α x) { return E; }
                  };

Or else directly, using the lambda form

Function<α> f = x -> E;

Here is an example, using the higher order function compose to define an odd function in terms of even and add1:

import java.util.function.*;

public class testCompose {
    public static void main(String[] args) {
        
        // val add1 x = x + 1 
        Function<Integer,Integer> add1 = x -> x + 1;
        
        // val odd x = x mod 2 = 0 
        Function<Integer,Boolean> even = x -> (x%2 == 0);
        
        // val odd = compose even add1 
        Function<Integer,Boolean> odd = 
            UsefulFunctions.<Integer,Boolean,Integer>compose(even).apply(add1);
        
        System.out.println("odd 6;\nval it = " + odd.apply(6) + " : bool");
        System.out.println("even 6;\nval it = " + even.apply(6) + " : bool");        
    }
}

/*
  fun compose f g = fn x => f (g x);
 */

class UsefulFunctions {
    public static <A,B,C> Function<Function<C,A>, 
                                   Function<C,B>> compose(Function<A,B> f) {
        return  (g -> (x -> f.apply(g.apply(x))));        
    }
}

Notice the way that type variables are declared in the signature of compose ("<A,B,C>"). This corresponds to the type-lambda construct in the τμScheme of our text. It allows the declaration of a polymorphic type for compose, corresponding to the type of the ML version:

  > val ('a, 'b, 'c) compose = fn : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b 

In fact, you can see the very same "type lambda" in the type inferred by the Moscow ML compiler.

Similarly, polymorphic types are instantiated throughout the code, in the type declarations of even, odd, and add1, and in the call

       UsefulFunctions.<Integer,Boolean,Integer>compose(even)

which is used to define odd (this corresponds to the @ operator in τμScheme).

Your Job

Here is an SML program that computes prime numbers, using an algorithm known as the Sieve of Eratosthenes. It uses an infinite Sequence data structure, which makes available only the initial element (the rest of the sequence is accessed by calling the generator function g, which returns the next element and another generator function for the rest of the sequence).

datatype infiniteSequence = Seq of int * (unit -> infiniteSequence) ;

fun filterSeq pred (Seq(i,g)) = 
    if (pred i) then Seq(i, (fn () => filterSeq pred (g())))
    else filterSeq pred (g())
;

fun take k (Seq(i,g)) =
    if k=0 then [] else i :: (take (k-1) (g()));

fun makeNats i = Seq (i, fn () => makeNats (i+1)) ;
val nats = makeNats 2;
fun notMultiple i = (fn j => (j mod i) <> 0) ;

fun makePrimes (Seq(i,g)) = 
        Seq (i, fn () => 
                 (makePrimes 
                    (filterSeq (notMultiple i) (g())))) ;

val primes = makePrimes nats ;

(* You can test the program by typing: 
take 10 primes
*)

Rewrite the program in Java with the following constraint: Maintain the structure of the SML program as much as possible. In particular, define functions filterSeq, take, makeNats, notMultiple, and makePrimes, which correspond to those in the ML version. Match the types of your Java classes to those of the corresponding SML functions. You will need to pay careful attention to the scope of type variables (generics) and to their correct instantiations.

To help you get started, here's the beginning of my solution. In addition to Function, it uses a Supplier, also from the Java 8 functional programming package.

import java.util.LinkedList;
import java.util.function.Function;
        // A function of one argument, which returns a value.  The lambda
        // syntactic sugar is "x -> E", where x is of the same declared type 
        // as the Function's domain and E the type of the function's range.  E
        // is the expression returned by the Function's apply() method
import java.util.function.Supplier;  
        // A function of no arguments, which returns a value:  the lambda 
        // syntactic sugar is () -> E, where E is the expression returned by the
        // Supplier's get() method
       
public class EritosthenesSieve {

    public static class Seq<A> {
        public final A i;
        public final Supplier<Seq<A>> g;
        
        public Seq(A i, Supplier<Seq<A>> generator) {
            this.i = i;  this.g = generator;
        }
    }
    
    public static void main(String[] args) {

        Seq nats = makeNats(2);
        Seq primes = makePrimes(nats);
        
        LinkedList primeList;
        
        if (args.length == 0)
            primeList = EritosthenesSieve.take(10).apply(primes);
        else {
            int len = Integer.parseInt(args[0]);
            primeList = EritosthenesSieve.take(len).apply(primes);
        }
        
        for(Integer p: primeList)
            System.out.print("" + p + " ");
        
        System.out.println();
    }
    
    public static Function filterSeq(Function pred) {
        return ((Seq s) -> 
                (pred.apply(s.i)? 
                     new Seq(s.i, () -> (filterSeq(pred).apply(s.g.get())) ):
                     filterSeq(pred).apply(s.g.get())
                ));
    }

You will need to correctly instantiate the generic types in the definition of filterSeq() and in the calls throughout the body of main(). You'll also need to write the definitions of the other functions.


Note for pre-Java 8 versions

The java.util.function package and the special lambda forms were introduced in version 8 of the language. The code above and the "compose" example will not compile under earlier versions of the language. If you haven't already upgraded your version of Java to version 8, this is a good time to do so.

However, the problem can be solved using earlier versions, though it is more inconvenient. To do so, define interfaces comparable to Function and Supplier:

interface Fun<A,B> {
    B apply (A x);
}

interface Sup<B> {
    B get();
}

You can use these to do express everything in the ML code, but you have to use the old anonymous inner class form, and you have to declare most of the parameters as final (a requirement for access within anonymous inner classes). For example, compose<() would be written as

public static <A,B,C> Fun<Fun<C,A>, Fun<C,B>> compose(final Fun<A,B> f) {
        return new Fun<Fun<C,A>, Fun<C,B>>(){
            public Fun<C,B> apply(final Fun<C,A> g) {
                return new Fun<C,B>() {
                    public B apply(C x) {
                        return f.apply(g.apply(x));
                    } // g.apply()
                } ;  // "closure"                
            } // f.apply()
        }  ; // "closure"        
    } //compose.apply()    }

while FilterSeq() (except for the correct declaration and instantiation of type variables) is

public static Fun filterSeq(final Fun pred) {
    return new Fun() {
        public Seq apply(final Seq s) {
            return (pred.apply(s.i)?
                        new Seq(s.i,
                                   new Sup(){
                                     public Seq get() {
                                       return  filterSeq(pred).apply(s.g.get());
                                     }
                                   }
                                  ):
                        filterSeq(pred).apply(s.g.get())
                        );
        };
    };
}

Note for the curious

Much of what I've done in this problem can be achieved using other classes from the java.util.function package. In particular, there is extensive support for streams, including a more robust version of the filterSeq function. The new static method references feature is often useful, as well. I've avoided these here in order to simplify the problem a bit and give a more straightforward correspondence to the ML code.

Also, the use of recursion in these functions imposes a fundamental limit on the size of the stream, since the runtime system enforces a limit on the size of the call stack. With a compiler that offers good tail call optimization, you can generate shockingly large results (using the SML/NJ interpreter, the call "take 50000 primes" completes in about 40 seconds on my MacBook pro; Moscow ML won't fare nearly as well). In Java, which does not support tail call optimization, you'll get a StackOverflowError on only moderately large arguments (anywhere from 500 - 5000).

John H. E. Lasseter