Writing simple JVM compiler using Parser Combinator

-- to come

Hacking closure in Java 7.0 (4): Exception Transparency

I spent some times yesterday and today to play around with the closure prototype right from the source. First, I reinstalled the binary jdk 7 to the build 103 one and then get the langtools project from mercury. Finally, I built the project and got my javac that can compile closure. 

The exception transparency is an interesting concept explained by Brian Goetz in http://blogs.sun.com/briangoetz/entry/exception_transparency_in_java. The idea is actually not specifically related to closure, but the need to have it becomes clear with inclusion of closure in Java.

As clear from previous posts (e.g. https://sites.google.com/site/anrizal05/home/java/007---hacking-closure-in-jdk-7-0), the use of SAM is a key in closure. The challenge is, of course, to have an interface that promotes reusability and of course simplity of use. One of the problem in designing such interface is the type of exception to be thrown.  

For example, if we want to define an interface Block with run method that throws BlockExecutionException like the following:

public interface Block<T> {

  public void run(T) throws BlockExecutionException;

}

That looks fine. Now imagine if we want to have an implementation of Block that throws SubBlockExecution1Exception and SubBlockExecution2Exception (both extends BlockExecutionException) like this:

public class BlockImpl<Integer> implements Block{

public void run(Integer) throws SubBlockExecution1Exception , SubBlockExecution2Exception {

              ...

             }

}

And imagine that the code works directly with BlockImpl like this:

BlockImpl blockImpl = new BlockImpl();

blockImpl.run();

We need to catch SubBlockExecution1Exception and SubBlockExecution2Exception thrown by BlockImpl.run, which may be great, since both are more specific exceptions than BlockExecutionException. 

If we work with Block:

Block<Integer>  blockImpl = new BlockImpl();

blockImpl.run();

We're still able to catch SubBlockExecution1Exception and SubBlockExecution2Exception thrown by Block.run, but compiler still requires us to catch BlockExecutionException. 

Block<Integer> block = new BlockImpl();

try {

   block.run();

} 

catch (SubBlockExecution1Exception e) {

   handleSubBlockExecution1Exception(e);

}

catch (SubBlockExecution2Exception e) {

   handleSubBlockExecution2Exception(e);

}

catch (BlockExecutionException e) {

//  still needed.

}

If we go further to apply such problematic in closure, this becomes clearer. Imagine if we call the method foreach like the following:

foreach( myList,  #() { method1(); method2(); } )

With the definition of foreach as follow:

void foreach( List<Integer> list, Block<T> block) {

    for (i : list) {

        block.run();

    }

}

And method1 and method2 as follow:

void method1() throws SubBlockExecution1Exception;

void method2() throws SubBlockExecution2Exception;

Because of the definition of Block<T>, we cannot catch only SubBlockExecution1Exception and SubBlockExecution2Exception, but instead we need also to catch BlockExecutionException. This is not great since this will encourage application to directly catch BlockExecutionException instead of handling the more specific exception. In closure, it is even worse since we need to catch  exception specified in the SAM, while we don't even see the SAM code.

So, what the proposal is about ?

The proposal is about the possibility to generify exception like follow:

interface Block<T throws E> {

   void run(T item) throws E;

}

or 

interface Block<T throws E extends BlockExecutionException> {

   void run(T item) throws E;

}

Basically, exception transparency allows us to specify throws in  variable type. Then, we can have the following code:

private void execute(String x) throws SubBlockExecutionException {

    System.out.println("Execute" + x);

    ...

}

and we add foreach to ListUtil class as follow:

    public static <T,E extends BlockExecutionException>

            void foreach(List<T> list, Block<T, E> block) throws E{

        for (T item : list) {

            block.run(item);

        }

    }

We're ready then to write the code that shows the use of exception transparency:

             List<String> myList = Arrays.<String>asList("A", "B", "K");

        try {

          ListUtil.foreach(

            myList,

            Block<String, SubBlockExecutionException> #(x) {execute(x)});

        }

        catch (SubBlockExecutionException e) {

            e.printStackTrace();

        }

We don't need to catch BlockExecutionException because we know that execute method throws SubBlockException instead. Hence the transparency.

It is pretty cool, except the need to explicitly specify the target type. I asked this to lambda-dev mailing list and the response is that the type inference would only be done on the enviroment of the execution of closure not the content of the closure itself. So, the type inference does not check that the closure actually invokes execute( ) that throws SubBlockExecutionException. One solution would be to infer using the content of the closure or to live with that solution, which means that the exception is not really transparent :-)

But...., somehow, the following code works (that is, the type of lambda parameter is provided). According to Maurizio Cimadamore this is due to circular inference. Hmm... I hope to be informed more on what circular inference is.

        List<String> myList = Arrays.<String>asList("A", "B", "K");

        try {

          ListUtil.foreach(

            myList,

            #(String x) {execute(x)});

        }

        catch (SubBlockExecutionException e) {

            e.printStackTrace();

        }

Hacking closure in Java 7.0 (3): Target Type Selection

I spent some times yesterday and today to play around with the closure prototype right from the source. First, I reinstalled the binary jdk 7 to the build 103 one and then get the langtools project from mercury. Finally, I built the project and got my javac that can compile closure. 

We have seen in previous posts (008 - Hacking closure in Java 7.0 (2): Capturing local variable and instance and 007 - Hacking closure in Java 7.0 (1): SAM Conversion ) that closure can be used to convert SAM. From the context of the code, the compiler infers which class it should create from the lambda. Now, this is OK when there is one interface that matches the lambda. For example, the method apply of ListUtil accepts two null-ary interfaces, Constant and Tester that have the following codes:

public interface Constant<T> {

    T get();

}

public interface Tester<T> {

   T test();

}

class ListUtil {

   ...

   static void apply(Constant<T> c)  { ... }

   static void apply(Tester<T> t) { ...}

}

The call ListUtil.apply( #() { 5 }) is ambigous, because it matches two apply methods above. To disambiguate the call, an explicit target type needs to be selected. This can be done as follow:

ListUtil.apply(Constant<Integer> #() { 5 }) 

which explicitly tells the complier to use the apply(Constant<T> ) version of the overloaded method.

But...

I would have prefered not to overload, it's better to have method with different name than overload it.

Hacking closure in Java 7.0 (2): Capturing local variable and instance

I spent some times yesterday and today to play around with the closure prototype right from the source. First, I reinstalled the binary jdk 7 to the build 103 one and then get the langtools project from mercury. Finally, I built the project and got my javac that can compile closure. 

We have seen in 007 - Hacking closure in Java 7.0 (1): SAM Conversion how a closure can be written. Now, let's see more in detail some interesting properties owned by a closure.

Let's start with an example of a class FareList below that has a list of fares as follow:

public class FareList {

    private List<Double> listOfFares = new LinkedList<>();

    public FareList() {

    }

    public FareList(List<Double> fares) {

        listOfFares.addAll(fares);

    }

    public List<Double> getFares() {

        return listOfFares;

    }

...

}

Now, imagine that we have a discount( ) method that returns a new instance of FareList given a discount rate with the following signature:

    public FareList discount(double discountRate);

Just reminder, map is a ListUtil method that is introduced in 007 - Hacking closure in Java 7.0 (1): SAM Conversion and  has the following signature      

     

    public static <T> List<T> map(List<T> list, UnaryFunction<T> fn) 

If the method is implemented without closure, we will have an implementation like this:

    

    public FareList discount(final double discountRate) {

        FareList result = new FareList();

        ListUtil.map(listOfFares, new UnaryFunction<Double>() {

            public Double apply(Double x) {

                return (1 - discountRate) * x;

            }

        });

        return result;

    }

Note how final is needed by the anonymous inner class UnaryFunction. The final qualifier is needed for the apply method to access a local variable in the same block as the creation of the UnaryFunction.

It turns out, fortunately, that we don't have the same limitation in closure. Local variable can be accessed inside the closure without being qualified by final qualifier. This is the code of discount method implemented using closure:

public FareList discount(double discountRate) {

    FareList result = new FareList();

    result.listOfFares =

       ListUtil.map(listOfFares, #(x) {(1 - discountRate) * x} );

    return result;

}

(Note that I don't use the type in the definition of closure, that is instead of #(Double x) {(1 - discountRate) * x} , I use 

#(x) {(1 - discountRate) * x}, that is, I omit the type of the parameter. Indeed, it is possible to omit the type for parameter of closure (lambda) and let the compiler infers the type).

I have shown above that closure can use the value from its environment, in this case from the local variable. Closure may also access the instance variable (property) of the class. 

The example below shows an example where discount method accesses maxDiscountRate that makes sure that the discountRate passed as parameter to be less than maxDiscountRate property of FareList class. 

public FareList discount(double discountRate) {

    FareList result = new FareList();

    result.listOfFares =

       ListUtil.map(listOfFares, 
          #(x) {(1 - (Math.min(discountRate, maxDiscountRate)) * x} );

    return result;

}

What about that ? Quite nice, isn't it?

Hacking closure in Java 7.0 (1): SAM Conversion

I used a lot of functor library from Apache couple years ago and found it very handy to write with minimal boiler-plate code. At that time, I wondered, whether closure (or functor at that time) would be included in the language itself. Now, it is indeed to be included in Java 7.0 however unclear it is. In OpenJDK, through Lambda project, there would very likely be -- but again, still unclear -- a closure support in Java 7. Indeed, in lambda-dev mailing list, a lot of things seem to be more or less finalized, and we may really hope to have closure in Java 7.0 in September.

I spent some times yesterday and today to play around with the closure prototype right from the source. First, I reinstalled the binary jdk 7 to the build 103 one and then get the langtools project from mercury. Finally, I built the project and got my javac that can compile closure. 

The first use of closure is to simplify the implementation of Simple Abstract Method (SAM). So, what is SAM ? It is a method of interface that contains only one method, like run method of Runnable, call method of Callable, compare method of Comparator, and so on.

For example, we can use sort that accepts Comparator as follow:

       List<String> myList = new LinkedList<>();

   myList.addAll(Arrays.<String>asList(
       "AAA", "BB", "CCCC", "D", "FDFFFF"));   

     Collections.sort(

       myList,

       new Comparator<String> () {

         public int compare(String o1, String o2) {

           return o1.length() - o2.length();

         }

      });

(Note also how I use the diamond <> for myList creation, which is also introduced in Java 7).

This is not cool  because the need to write the inner class Comparator makes the code unreadable. And guess what, some companies even don't allow writing those kinds of inner class. Good news is, using closure, we can write an implementation of SAM shorter. Here is the code:

        List<String> myList = new LinkedList<>();

     myList.addAll(Arrays.<String>asList("AAA", "BB", "CCCC", "D", "FDFFFF"));   

     Collections.sort(myList, 

                      #(String x, String y) { x.length() - y.length() });

Much better, isn't it ? We can also write the comparator as follow:

         Comparator<String> lengthComparator = 
      #(String x, String y) { x.length() - y.length() }

Or runnable as follow:

     Runnable r = #() { method1(); method2();};

Now, let's put into practice.

Let's imagine we need to write a sum, multiplication, max, or min of a list. Without closure we'll have to have four different implementations of for loop for each:

public class ListIntUtil {

    public static Integer sum(List<Integer> list) {

        Integer result  = 0;

        for (Integer el : list) {

            result += el;

        }

        return result;

    }

    public static Integer multiply(List<Integer> list) {

        Integer result  = 1;

        for (Integer el : list) {

            result *= el;

        }

        return result;

    }

}

With closure, we can define a method that accepts the initial value and the function in addition to the list itself. So, we want to call like

foldLeft(myList, 0, #(Integer x, Integer y) { x + y })

for sum and 

foldLeft(myList, 1, #(Integer x, Integer y) { x * y })

for multiplication.

The definition of foldLeft is the following:

public static Integer foldLeft(Integer initial, List<Integer> integerList, BinaryFunction fn) {

     Integer result = initial;

     for (Integer in  : integerList) {

        result = f.apply(result, in);

     }

     return result;

}

with BinaryFunction is a SAM defined as follow:

public interface BinaryFunction {

   Integer apply(Integer x, Integer y);

}

Again, there's no need to implement BinaryFunction, it's enough to to write #(Integer x, Integer y) { x + y }. 

Indeed, we can assign the closure directly to BinaryFunction :

BinaryFunction fn = #(Integer x, Integer y) { x + y }.

With foldLeft above, we can easily apply max and min of a list 

Integer maxNumber = foldLeft(myList, Integer.MIN_VALUE, #(Integer x, Integer y) { Math.max(x,y) })

Integer minNumber = foldLeft(myList, Integer.MAX_VALUE, #(Integer x, Integer y) { Math.min(x,y) })

Let's try with something else, let's say a method that maps a list of integer to another list of integer that contains the double of the value of each element of the first list. That is, if we have (1, 3, 3, 4), the function returns (2, 6, 6, 8).

First, we need a SAM definition (note that, we usually don't need to do this, some existing libraries already exist, but here I just want to show that it really works with any interface).

public interface UnaryFunction {

  Integer apply(Integer x);

}

Then, the implementation of double is as follow:

    List<Integer> twice = map(intList, #(Integer x) { x * 2 }); // (2, 6, 6, 8)

That can be modified easily when multiplication by three is expected instead:   

    List<Integer> thrice  = map(intList, #(Integer x) { x * 3 }); // (3, 9, 9, 12)

Finally, the implementation of map is as follow:

public static List<Integer> map(List<Integer> list, UnaryFunction fn) {

       List<Integer> result = new LinkedList<>();

       for (Integer el : list) {

           result.add(fn.apply(el));

       }

       return result;

}

All right. Let's refactor a little bit more. Now, we have seen that BinaryFunction and UnaryFunction that works with Integer type.  Of course, we can use generic to make them more reusable. So, here is the generified version of the two interfaces:

public interface UnaryFunction<T> {

  T apply(T x);

}

public interface BinaryFunction<T> {

  T apply(T x, T y);

}

The adapted version of foldLeft and map is as follow:

public static <T> T foldLeft(T initial, List<T> integerList, BinaryFunction<T> fn) {

     T result = initial;

     for (Integer in  : integerList) {

        result = f.apply(result, in);

     }

     return result;

}

public static <T> List<T> map(List<T> list, UnaryFunction<T> fn) {

     List<T> result = new LinkedList<>();

     for (T el : list) {

        result.add(fn.apply(el));

     }

     return result;

}

With that we can now sum a list of double by using this code:

   foldLeft(0.0d, doubleList, #(Double x, Double y) {x + y})

Or why not 

   foldLeft("", stringList, #(String x, String y) {x + y})

and map:

    map(doubleList, #(Double x) { x * 2 });

The last syntax of closure (version posted by Maurizio Cimadamore on August 4) also allows to use sequence of statement, typically for SAM that does not have a return value. For example:

      foreachRun(myInt, #{method1(); method2();});

With foreachRun is defined as follow: 

void foreachRun(List<Integer> list, Runnable sequence) {

    for (Integer el : list> {

         sequence.run();

    }

}