Bits of Learning

Learning sometimes happens in big jumps, but mostly in little tiny steps. I share my baby steps of learning here, mostly on topics around programming, programming languages, software engineering, and computing in general. But occasionally, even on other disciplines of engineering or even science. I mostly learn through examples and doing. And this place is a logbook of my experiences in learning something. You may find several things interesting here: little cute snippets of (hopefully useful) code, a bit of backing theory, and a lot of gyan on how learning can be so much fun.

Monday, July 23, 2018

Simulating Higher Order Functions using Strategy Design Pattern

We wish to implement a function that takes an integer array as an input and returns an integer array of the same length but each of its elements double the corresponding element in the input array. One possibly reasonable implementation is shown below.


public class Hof {

    public static void main(String[] args) {
        int[] a = { 1, 2, 3};
        printArray(doubleArray(a));
    }

    private static int dbl(int n) {
        return n * 2;
    }

    private static int print(int n) {
        System.out.print(n + " ");
        return 0;
    }

    private static int[] doubleArray(int[] array) {
        int[] ans = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            ans[i] = dbl(array[i]);
        }
        return ans;
    }

    private static int[] printArray(int[] array)  {
        int[] ans = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            ans[i] = print(array[i]);
        }
        return ans;
    }
}


On running this program, we get the following output:


2 4 6


Now, we additionally wish to implement a function that squares an integer array, we may have to insert the pieces below.


public class Hof {

    public static void main(String[] args) {
        int[] a = { 1, 2, 3};
        printArray(doubleArray(a));
    }

    private static int dbl(int n) {
        return n * 2;
    }

    private static int print(int n) {
        System.out.print(n + " ");
        return 0;
    }

    private static int[] doubleArray(int[] array) {
        int[] ans = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            ans[i] = dbl(array[i]);
        }
        return ans;
    }

    private static int[] printArray(int[] array)  {
        int[] ans = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            ans[i] = print(array[i]);
        }
        return ans;
    }
}



2 4 6
1 4 9 


However, Java does badly when it comes to economy of expression.
Let's just look at how the same code would look in another programming language, Python, shown below.

print map(lambda x: 2 * x, [1, 2, 3])
print map(lambda x: x * x, [1, 2, 3])

On running this program, we get the following output:



[2, 4, 6]
[1, 4, 9]



One of the reasons for this enormous of economy of syntax is a higher order function called map. A higher order function is a function that takes other functions as inputs (and possibly computes functions as output). map is one such function that takes a function, say \lstinline$f$, and a list, say l, and returns a list each of whose elements is f applied to the corresponding element in l. HOFs are a common feature of functional programming. In fact, what inheritance and polymorphism is to object-oriented programming, HOFs are the same to functional programming: the main abstraction mechanism for code reuse and modularisation.

Unfortunately, Java (until Java 8) doesn't have higher order functions. But the case for higher order functions is strong enough that we wish to implement something similar in Java. How do we do it?

With our knowledge of object-oriented programming, we can come out with a fairly close approximation to the idea of higher order functions. The central idea is: in OOP, we can't pass functions to functions, but we can pass objects which have functions in them. Thus, all we need to do is pack the function that we want to pass to a HOF in a class, and pass an object of that class to the HOF.
The solution for the problem is presented below.


public class Hof {
  public static void main(String[] a) {
    int[] ar = {1, 2, 3};

    int[] newarray = Hof.map(new Dbl(), ar);
    for(int n : newarray) {
      System.out.println(n);
    }
 
    newarray = Hof.map(new Dbl(), ar);
    for(int n : newarray) {
      System.out.println(n);
    }
  }

  public static int [] map(Function f, int [] a) {
    int[] newarray = new int[a.length];
    for(int i = 0; i &lt; a.length; i++) {
      newarray[i] = f.execute(a[i]);
    }
    return newarray;
  }
}

interface Function {
  int execute(int n);
}

class Dbl implements Function {
  public int execute(int n) {
    return 2 * n;
  }
}

class Sqr implements Function {
  public int execute(int n) {
    return n * n;
  }
}

which gives us the following output:


2
4
6
1
4
9

Just in case it's not clear already, let me help you walk through the code.

  1. The first thing to notice is the interface Function. It has a method declaration execute that takes an integer and returns an integer. This represents the function that would be passed to the higher order function map and would be applied to each element of the integer array.
  2. The next thing to observe is the map method which takes two parameters: the first is f, an instance of Function; and the other is the array of ints a. It returns the resultant array after applying f on each element of a as shown.
  3. Finally, an instance of Dbl and Sqr are passed in turn to Hof.map in the \lstinline@main@ method to be applied to array.

This application is to demonstrate how object-oriented principles can be used to create highly reusable code. The map method here is a boiler-plate code that can be used wherever there's a need to apply a function on all elements of an integer array to create a new one. What that function to applied should be is a parameter to the method, and hence is flexible.

Anonymous Classes

The next question we ask is: In Java, is there something equivalent to lambda expressions as seen in Python. Lambda expressions are like anonymous functions which are typically created for a one time use as a parameter to a higher order function. This avoids creation of extra named functions and saves the namespace (variable environment) from unnecessary clutter. Here, the classes Dbl and Sqr are similar classes: to be instantiated once to be passed to Hof.map, and then to be forgotten. Why do we need to create a named class which will ever be implemented only once? Like anonymous functions (lambda) in Python, do we have something like anonymous classes? Indeed, yes!

We replace the earlier Hof.main method with the lines shown below.

  public static void main(String[] a) {

    int[] ar = {1, 2, 3};

    Function triple = new Function() {
        public int execute(int n) {
          return 3 * n;
        }
      };

    newarray = Hof.map(triple, ar);
    for(int n : newarray) {
      System.out.println(n);
    }
  }

Here's the output:

3
6
9

Here, we used the map method to triple the array. The Function interface is implemented through an anonymous class (a class with no name) set to Function triple. All we need to do to make it a concrete class is to provide its own implementation of the execute method. We do so. And it just works smoothly. No need to create another class named Triple or something. No too many unused class names. No namespace clutter!

No comments: